8.1 Arbres m-aires de recherche
347
Plus généralement, la n-ième clé est insérée dans un nœud de type i (i =
1, . . . , m − 1) avec probabilité iX
(i)
n /n et dans ce cas, le nœud se transforme en un
nœud de type i + 1 pour i = 1, 2, . . . , m − 2 et en m nœuds de type 1 si i = m − 1.
Autrement dit, pour tout i = 1, . . . , m − 1, avec probabilité iX
(i)
n /n,
X n+1 = X n + i ,
où
⎧
⎪ ⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎪ ⎩
1 = (−1, 1, 0, 0, . . . )
2 = (0, −1, 1, 0, . . . )
. . .
m−2 = (0, . . . , 0, −1, 1)
m−1 = (m, 0, . . . , 0, −1).
.
En comptant le nombre d’intervalles vacants dans T n−1 nous obtenons une seconde
relation entre les X
(i)
n , qui exprime aussi que la somme des probabilités de transition
vaut 1 :
n =
m−1
i=1
iX
(i)
n .
(8.7)
La suite (X n ) n≥1 apparaît comme une chaîne de Markov à temps discret, plus
précisément une marche aléatoire, non homogène dans le temps, dont les incréments
sont les i et dont les probabilités de transition sont linéaires en X n . C’est pour cette
raison qu’un peu d’algèbre linéaire va conduire à l’asymptotique de X n en écrivant
sa décomposition spectrale. C’est la démarche adoptée dans [36], qui conduit à la
partie (ii) pour m ≥ 27 du théorème 8.10 ci-dessous. La partie (i) pour m ≤ 26 se
trouve dans Mahmoud [172] ou Janson [147].
La preuve du théorème 8.10 fait l’objet de la section 9.5.1 du chapitre consacré
aux urnes de Pólya. Nous verrons dans cette section pourquoi la dynamique de
l’arbre m-aire de recherche est celle d’une urne de Pólya.
Théorème 8.10 Soit X n le vecteur 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
.
347
Plus généralement, la n-ième clé est insérée dans un nœud de type i (i =
1, . . . , m − 1) avec probabilité iX
(i)
n /n et dans ce cas, le nœud se transforme en un
nœud de type i + 1 pour i = 1, 2, . . . , m − 2 et en m nœuds de type 1 si i = m − 1.
Autrement dit, pour tout i = 1, . . . , m − 1, avec probabilité iX
(i)
n /n,
X n+1 = X n + i ,
où
⎧
⎪ ⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎪ ⎩
1 = (−1, 1, 0, 0, . . . )
2 = (0, −1, 1, 0, . . . )
. . .
m−2 = (0, . . . , 0, −1, 1)
m−1 = (m, 0, . . . , 0, −1).
.
En comptant le nombre d’intervalles vacants dans T n−1 nous obtenons une seconde
relation entre les X
(i)
n , qui exprime aussi que la somme des probabilités de transition
vaut 1 :
n =
m−1
i=1
iX
(i)
n .
(8.7)
La suite (X n ) n≥1 apparaît comme une chaîne de Markov à temps discret, plus
précisément une marche aléatoire, non homogène dans le temps, dont les incréments
sont les i et dont les probabilités de transition sont linéaires en X n . C’est pour cette
raison qu’un peu d’algèbre linéaire va conduire à l’asymptotique de X n en écrivant
sa décomposition spectrale. C’est la démarche adoptée dans [36], qui conduit à la
partie (ii) pour m ≥ 27 du théorème 8.10 ci-dessous. La partie (i) pour m ≤ 26 se
trouve dans Mahmoud [172] ou Janson [147].
La preuve du théorème 8.10 fait l’objet de la section 9.5.1 du chapitre consacré
aux urnes de Pólya. Nous verrons dans cette section pourquoi la dynamique de
l’arbre m-aire de recherche est celle d’une urne de Pólya.
Théorème 8.10 Soit X n le vecteur 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
.