308
7 Arbres digitaux
Le principe de dépoissonisation algébrique de la proposition 7.24 donne dans le
modèle de Bernoulli (B n , S)
P n (h ≤ k) = n![Z
n
]e
Z
w∈A
k
e
−Zp w (1 + Zp w )
= n![Z
n
]
w∈A
k
(1 + Zp w )
= n!
E∈SET n (A
k )
w∈E
p w .
Dans la dernière égalité, SET n (A
k ) désigne l’ensemble des sous-ensembles de
cardinal n de mots de tailles k. Cette formule ne permet pas d’obtenir une expression
simple dans le modèle de Bernoulli (à nombre de clés fixé). Nous pouvons résumer
les résultats ci-dessus.
Proposition 7.27 (Tries – mots produits par une source – expressions exactes)
Les valeurs moyennes de la taille S et de la longueur de cheminement externe d’un
trie dans le modèle (B n , S) (contenant n mots, avec alphabet A et des probabilités
de préfixes {p w } w∈A
∗ ) satisfont
E n [S] =
w∈A
∗
1 − (1 − p w )
n
− np w (1 − p w )
n−1
E n [] =
w∈A
∗
p w
1 − (1 − np w )
n−1
.
La probabilité qu’un trie dans ce même modèle contenant n mots soit de hauteur
inférieure ou égale à k est
P n (h ≤ k) = n![Z
n
]
w∈A
k
(1 + Zp w ).
Il faut user de méthodes plus sophistiquées pour dépoissoniser en même temps
qu’on procède à l’étude asymptotique (voir [46]). Nous donnerons cependant à la
section suivante l’idée qui permet d’utiliser cette expression pour obtenir une valeur
asymptotique.
7.2 Analyses asymptotiques
L’analyse est assez différente selon que nous considérons des paramètres additifs
ou non additifs (la hauteur dans ce chapitre). Cette section commence donc
par s’intéresser aux paramètres additifs en donnant plusieurs approches et dans
différents modèles.