278
6 Arbres binaires de recherche
uniformes et pour n ≤ 4, calculer la distribution de probabilité sur l’ensemble des arbres binaires
de taille n. Est-elle uniforme ? Calculer la profondeur moyenne d’insertion d’une nouvelle clé.
6.2. Pour n donné, calculer la probabilité qu’un arbre binaire de recherche obtenu par insertion
de n clés sous le modèle des permutations uniformes soit de hauteur maximale.
6.3. Section 6.1.2 : Déduire de la fonction génératrice de la profondeur d’insertion que
E(D n+1 ) = 2(H n+1 − 1)
et calculer Var (D n+1 ).
6.4. Convergence dans L 2 de la martingale de l’abr
Avec les notations de la section 6.1.2, soit D n+1 la profondeur d’insertion d’une nouvelle clé
dans l’abr τ n , soit W τn le polynôme de niveau et soit M n (z) :=
Wτ n (z)
E(Wτ n (z)) =
Wτ n (z)
γn(2z−1) la martingale
associée.
a) Montrer que
W τ n+1 (z) = W τn (z) + (2z − 1)z
D n+1 .
b) Pour z 1 , z 2 ∈ C, posons F n (z 1 , z 2 ) = E
W τn (z 1 )W τn (z 2 )
. Montrer que
F n+1 (z 1 , z 2 ) = α n (z 1 , z 2 )F n (z 1 , z 2 ) + β n (z 1 , z 2 ),
où α n (z 1 , z 2 ) = 1 +
2(z 1 +z 2 −1)
n+1
et β n (z 1 , z 2 ) = (2z 1 − 1)(2z 2 − 1)
E(Wτ n (z 1 z 2 ))
n+1
.
c) En déduire une expression de F n (z 1 , z 2 ) en fonction de n.
d) Utiliser le comportement asymptotique du polynôme γ n (2z − 1) rappelé dans l’annexe B.5.1
pour majorer et minorer E (M n (z 1 )M n (z 2 )) et en déduire que (M n (z)) n est bornée dans L 2 si
et seulement si 4(z) − 2|z| 2 > 1, autrement dit si et seulement si z ∈ D(1,
1
√
2
).
6.5. Martingale et analogue du théorème 6.11 pour la longueur de cheminement interne
Soit lci(τ n ) la longueur de cheminement interne d’un abr de taille n. Rappeler la relation entre
longueurs de cheminement interne et externe. En déduire des résultats de convergence p.s. pour
lci(τ n ) lorsque n → +∞.
6.6. TLC et grandes déviations pour s n
Soit z un réel strictement positif. Soit s n une marche aléatoire dont les pas sont des variables
aléatoires indépendantes ε k , k ≥ 1, chacune de loi de Bernoulli de paramètre
2z
k+2z . De plus, s 0 = 0
et s 1 = 1. Autrement dit, pour n ≥ 1,
s n = 1 +
n−1
k=1
ε k .
a) Montrer que presque sûrement, quand n tend vers +∞,
s n
log n
→ 2z.
b) Montrer que
s n − 2z log n
√
2z log n
converge en loi vers une loi normale centrée réduite N(0, 1).
6 Arbres binaires de recherche
uniformes et pour n ≤ 4, calculer la distribution de probabilité sur l’ensemble des arbres binaires
de taille n. Est-elle uniforme ? Calculer la profondeur moyenne d’insertion d’une nouvelle clé.
6.2. Pour n donné, calculer la probabilité qu’un arbre binaire de recherche obtenu par insertion
de n clés sous le modèle des permutations uniformes soit de hauteur maximale.
6.3. Section 6.1.2 : Déduire de la fonction génératrice de la profondeur d’insertion que
E(D n+1 ) = 2(H n+1 − 1)
et calculer Var (D n+1 ).
6.4. Convergence dans L 2 de la martingale de l’abr
Avec les notations de la section 6.1.2, soit D n+1 la profondeur d’insertion d’une nouvelle clé
dans l’abr τ n , soit W τn le polynôme de niveau et soit M n (z) :=
Wτ n (z)
E(Wτ n (z)) =
Wτ n (z)
γn(2z−1) la martingale
associée.
a) Montrer que
W τ n+1 (z) = W τn (z) + (2z − 1)z
D n+1 .
b) Pour z 1 , z 2 ∈ C, posons F n (z 1 , z 2 ) = E
W τn (z 1 )W τn (z 2 )
. Montrer que
F n+1 (z 1 , z 2 ) = α n (z 1 , z 2 )F n (z 1 , z 2 ) + β n (z 1 , z 2 ),
où α n (z 1 , z 2 ) = 1 +
2(z 1 +z 2 −1)
n+1
et β n (z 1 , z 2 ) = (2z 1 − 1)(2z 2 − 1)
E(Wτ n (z 1 z 2 ))
n+1
.
c) En déduire une expression de F n (z 1 , z 2 ) en fonction de n.
d) Utiliser le comportement asymptotique du polynôme γ n (2z − 1) rappelé dans l’annexe B.5.1
pour majorer et minorer E (M n (z 1 )M n (z 2 )) et en déduire que (M n (z)) n est bornée dans L 2 si
et seulement si 4(z) − 2|z| 2 > 1, autrement dit si et seulement si z ∈ D(1,
1
√
2
).
6.5. Martingale et analogue du théorème 6.11 pour la longueur de cheminement interne
Soit lci(τ n ) la longueur de cheminement interne d’un abr de taille n. Rappeler la relation entre
longueurs de cheminement interne et externe. En déduire des résultats de convergence p.s. pour
lci(τ n ) lorsque n → +∞.
6.6. TLC et grandes déviations pour s n
Soit z un réel strictement positif. Soit s n une marche aléatoire dont les pas sont des variables
aléatoires indépendantes ε k , k ≥ 1, chacune de loi de Bernoulli de paramètre
2z
k+2z . De plus, s 0 = 0
et s 1 = 1. Autrement dit, pour n ≥ 1,
s n = 1 +
n−1
k=1
ε k .
a) Montrer que presque sûrement, quand n tend vers +∞,
s n
log n
→ 2z.
b) Montrer que
s n − 2z log n
√
2z log n
converge en loi vers une loi normale centrée réduite N(0, 1).