396
9 Urnes de Pólya et applications
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 m = u 1 et u 1 v 1 = 1. Nous trouvons
u 1 =
1
H m+1 (m)
1
m + 1
,
1
m + 2
, . . . ,
1
2m
,
avec la notation H m (z) =
1≤k≤m−1
1
z + k
, et la proposition suivante est ainsi
obtenue :
Proposition 9.14 La composition asymptotique d’un arbre-B de paramètre m est
donnée au premier ordre par la convergence presque sûre du vecteur composition
des gaps Y n :
Y n
n
−→
n→∞
1
H m+1 (m)
1
m + 1
,
1
m + 2
, . . . ,
1
2m
,
avec la notation H m+1 (m) =
1
m + 1
+ · · · +
1
2m
.
Ce résultat permet en corollaire, par combinaisons linéaires, d’avoir le comportement asymptotique du nombre de feuilles, ou bien le taux de remplissage des
feuilles. Voir l’exercice 9.5.
Pour un grand arbre-B, de paramètre m ≥ 60, la méthode algébrique permet
de décliner le théorème 9.8 et le plongement en temps continu permet de décliner
le théorème 9.10. Dans ces théorèmes apparaît une variable aléatoire limite W
qui rend compte des fluctuations de Y n autour de son premier terme asymptotique
d’ordre n et cette variable aléatoire W n’est pas gaussienne. Les propriétés de W ne
sont pas encore bien connues (voir les exercices 9.7 et 9.8). Elles ressemblent aux
propriétés de son analogue pour les arbres m-aires de recherche (notée aussi W en
section 9.5.1).
9.6 Exercices
9.1. Lorsque R =
0 3
2 1
, coder et compter toutes les histoires de longueur 2 qui mènent de
2
0
à
4
4
.
Indication : dessiner l’arbre des possibles.
9.2. (c’est l’urne de l’article originel de Pólya en 1931) Lorsque R = SI 2 , calculer tous les
nombres H n , n ≥ 0.
Indication : faire le dessin d’un chemin dans N 2 et compter les histoires qui suivent chacun des
chemins.
9 Urnes de Pólya et applications
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 m = u 1 et u 1 v 1 = 1. Nous trouvons
u 1 =
1
H m+1 (m)
1
m + 1
,
1
m + 2
, . . . ,
1
2m
,
avec la notation H m (z) =
1≤k≤m−1
1
z + k
, et la proposition suivante est ainsi
obtenue :
Proposition 9.14 La composition asymptotique d’un arbre-B de paramètre m est
donnée au premier ordre par la convergence presque sûre du vecteur composition
des gaps Y n :
Y n
n
−→
n→∞
1
H m+1 (m)
1
m + 1
,
1
m + 2
, . . . ,
1
2m
,
avec la notation H m+1 (m) =
1
m + 1
+ · · · +
1
2m
.
Ce résultat permet en corollaire, par combinaisons linéaires, d’avoir le comportement asymptotique du nombre de feuilles, ou bien le taux de remplissage des
feuilles. Voir l’exercice 9.5.
Pour un grand arbre-B, de paramètre m ≥ 60, la méthode algébrique permet
de décliner le théorème 9.8 et le plongement en temps continu permet de décliner
le théorème 9.10. Dans ces théorèmes apparaît une variable aléatoire limite W
qui rend compte des fluctuations de Y n autour de son premier terme asymptotique
d’ordre n et cette variable aléatoire W n’est pas gaussienne. Les propriétés de W ne
sont pas encore bien connues (voir les exercices 9.7 et 9.8). Elles ressemblent aux
propriétés de son analogue pour les arbres m-aires de recherche (notée aussi W en
section 9.5.1).
9.6 Exercices
9.1. Lorsque R =
0 3
2 1
, coder et compter toutes les histoires de longueur 2 qui mènent de
2
0
à
4
4
.
Indication : dessiner l’arbre des possibles.
9.2. (c’est l’urne de l’article originel de Pólya en 1931) Lorsque R = SI 2 , calculer tous les
nombres H n , n ≥ 0.
Indication : faire le dessin d’un chemin dans N 2 et compter les histoires qui suivent chacun des
chemins.