7.1 Analyses exactes
307
Nous utilisons le principe de dépoissonisation algébrique de la proposition 7.24 pour
obtenir dans le modèle usuel de Bernoulli
E n [S] = n![Z
N
]e
Z
w∈A
∗
1 − e
−Zp w (1 + Zp w )
=
w∈A
∗
1 − (1 − p w )
n
− np w (1 − p w )
n−1
.
Notons que le cas classique du trie binaire vu précédemment est retrouvé en
considérant p w = 1/2 |w| .
Longueur de cheminement externe d’un trie Pour la longueur de cheminement
externe, le péage est γ (ω) = |ω| si |ω| est supérieur ou égal à 2, et 0 sinon.
L’espérance de γ (N), où N est une variable aléatoire de Poisson (pour la taille
de ω) de paramètre Z, est
γ (Z) = e
−Z
k≥2
k
Z k
k!
= Z
1 − e
−Z
.
Ainsi la valeur moyenne de la longueur de cheminement externe dans le modèle
de Poisson est donnée par
E Z [] =
w∈A
∗
Zp w
1 − e
−Zpw
.
À nouveau, l’application du principe de la dépoissonisation algébrique mène, après
quelques calculs, à l’expression de l’espérance dans le modèle de Bernoulli
E n [] =
w∈A
∗
p w
1 − (1 − np w )
n−1
.
Hauteur d’un trie Soit P Z (h ≤ k) la probabilité qu’un trie aléatoire soit de
hauteur au plus k dans le modèle (P Z , S). Cette probabilité se calcule en considérant
la situation où tous les intervalles fondamentaux de profondeur k contiennent au
plus une clé. Comme la probabilité qu’un intervalle de longueur λ contienne au plus
un point est e −Zλ (1 + Zλ) dans le modèle de Poisson de paramètre Z, et que les
intervalles fondamentaux distincts de même profondeur sont d’intérieurs disjoints,
nous avons
P Z (h ≤ k) =
w∈A
k
e
−Zp w (1 + Zp w ) .