7.2 Analyses asymptotiques
329
Proposition 7.42 (Hauteur asymptotique dans le modèle de Bernoulli
pour une source sans mémoire binaire non biaisée) La valeur moyenne
de la hauteur E n [h] d’un trie construit sur n mots produits par une source
sans mémoire binaire non biaisée vérifie quand n → +∞,
E n [h] = 2 log 2 n + Q(2 log 2 n) −
γ
log 2
− 1
+ o(1),
où Q(u) est une fonction périodique d’amplitude « très petite ».
De plus, la distribution asymptotique de la hauteur est de type double
exponentielle en k,
lim
n→∞
sup
k≥0
Pn(h ≤ k) − exp
−n
2 2
−k−1
= 0.
(7.40)
Remarque 7.43 L’expression (7.40) ci-dessus permet de mettre en évidence
que les probabilités q n,k = P n (h ≤ k) pour k autour de 2 log 2 n sont
« asymptotiquement périodiques ». D’après [79, Th. 1], pour n, k → +∞,
q n,k = P n (h ≤ k) = exp
−2
u(n) 2
−δ−1
1 + O
(log n) 2
n
,
(7.41)
où δ = k −
2 log 2 n
et u(n) =
2 log 2 n
est la partie fractionnaire de
2 log 2 n. Cette expression est valide lorsque k est assez proche de 2 log 2 n au
sens où δ > − log 2 log n. De plus, le O(·) est uniforme en k et n. Notons que
pour n = n
√
2,
u(n
) = u(n), 2 log 2 n
= =2 log 2 n + 1,
de sorte que les quantités q n ,k+1 et q n,k sont équivalentes (du moins pour k
dans une fenêtre autour de 2 log 2 n).
Remarque 7.44 Ces résultats s’étendent au cas des tries paginés avec exactement les mêmes techniques (voir Flajolet et al. [79, 96], ainsi que les
exercices 7.10 et 7.11).