9.5 Applications algorithmiques
389
où u 1 , C et S sont des vecteurs réels qui se calculent explicitement, ρ = |W 2 | et
φ = Arg(W 2 ) ∈ [−π, π[ sont des variables aléatoires ; les premiers moments de
W 2 et |W 2 | sont calculés dans Pouyanne [213].
Calcul de u 1 : rappelons que v 1 = t (1, . . . , 1) est vecteur propre à droite pour
la valeur propre 1 et que u 1 est vecteur propre à gauche pour la valeur propre 1,
caractérisé par u 1 R = u 1 et u 1 v 1 = 1. Le calcul fournit
u 1 =
1
H m (1)
1
2
,
1
3
, . . . ,
1
m
,
avec la notation H m (z) =
1≤k≤m−1
1
z+k , de sorte que la proposition suivante
permet de prouver la première partie du théorème 8.10 annoncé au chapitre 8.
Proposition 9.11 Soit X n le vecteur d’occupation des feuilles d’un arbre m-aire
de recherche. Son comportement asymptotique au premier ordre est donné par la
convergence presque sûre
X n
n
p.s.
−→
n→∞
u 1 :=
1
H m (1)
1
k(k + 1)
1≤k≤m−1
,
avec la notation H m (z) =
1≤k≤m−1
1
z+k . Via la relation (9.11), cette convergence
équivaut à la suivante :
Y n
n
p.s.
−→
n→∞
1
H m (1)
1
2
,
1
3
, . . . ,
1
m
,
où Y n est le vecteur composition de l’urne correspondante.
La seconde partie du théorème 8.10 annoncé au chapitre 8 est elle aussi la
traduction via la relation (9.11) du comportement asymptotique de Y n , explicité plus
haut dans le développement (9.13) pour m ≥ 27. Ce qui donne
Théorème 9.12 Soit X n le vecteur occupation des feuilles d’un arbre m-aire de
recherche.
(i) si m ≤ 26 alors σ ≤
1
2 et le comportement asymptotique de X n est donné par
la convergence en loi
X n − nu 1
√
n
D
−→
n→∞
N(0, ,
2 ),
où N(0, , 2 ) désigne un vecteur gaussien centré.
(ii) si m ≥ 27, alors σ >
1
2 et le comportement asymptotique de X n est donné par
X n = nu 1 + +(n
λ 2 W u 2 ) + o(n
σ ),
(9.14)