7.2 Analyses asymptotiques
313
7.2.2 Paramètres additifs : transformée de Mellin
Les définitions et propriétés de la transformée de Mellin sont rassemblées dans
l’annexe B.4.
Pour l’étude des tries, nous utilisons deux propriétés importantes :
– la formule de la transformée de Mellin pour une somme harmonique ;
– le comportement asymptotique obtenu grâce à la transformée de Mellin inverse.
Comme exemple d’application de la transformée de Mellin, examinons
l’expression obtenue pour l’espérance de la longueur de cheminement L n d’un
trie binaire dans le modèle infini i.i.d binaire :
L n = n
k≥0
1 −
1 −
1
2 k
n−1
.
(7.27)
Afin de ne pas alourdir inutilement cette présentation, nous nous ramenons,
comme dans la section précédente avec l’équation (7.24), à étudier
L n = n
k≥0
1 − e
−n/2 k
,
car L n = L n + o(n). L’argument repose de la même façon sur la comparaison entre
(1 − a) n et e −an .
La somme harmonique (voir l’annexe B.4.4) correspondant à
L n est
F (x) =
k≥0
2
k x
2 k (1 − e
x/2 k
),
(7.28)
de fonction de base f (x) = x(1 − e −x ), de fréquences {μ k = 2 −k } k≥0 et
d’amplitudes {λ k = 2 k } k≥0 . La transformée de Mellin de f , sur la bande s ∈
−2, −1, est
f
(s) = −(s + 1).
La série de Dirichlet associée à F (x) est
(s) =
k≥0
2
k 2
ks
=
∞
k=0
(2
s+1 )
k
=
1
1 − 2 s+1 .
La série de Dirichlet (s) a un demi-plan de convergence simple (s) < −1. Les
pôles de sont situés sur une droite verticale (s) = −1 aux points
χ k = −1 +
2ikπ
log 2
,