386
9 Urnes de Pólya et applications
(i) Si σ <
1
2 (cas d’une petite urne), alors
Y n − nu 1
√
n
D
−→
n→∞
N(0, ,
2 )
où u 1 est un vecteur propre de R pour la valeur propre 1 et où 2 a une forme
close, fonction de R.
(ii) Si σ =
1
2 (cas d’une petite urne), alors
Y n − nu 1
√
n log n
D
−→
n→∞
N(0, ,
2 )
où u 1 est un vecteur propre de R pour la valeur propre 1 et où 2 a une forme
close, fonction de R.
(iii) Si σ >
1
2 (cas d’une grande urne), alors si λ 2 , . . . , λ r sont les valeurs propres
de partie réelle σ et u 2 , . . . , u r sont des vecteurs propres associés, il existe des
variables aléatoires W 2 , . . . , W r telles que
Y n = nu 1 +
r
i=2
n
λ i W i u i + o(n
σ ),
où o(.) signifie une convergence presque sûre et dans tous les L p , p ≥ 1.
A vrai dire, les résultat (i) et (ii) sont encore vrais lorsque la matrice R n’est pas
diagonalisable. Les résultats de (iii) sont encore vrais pour R non irréductible.
Pour (iii), l’hypothèse R diagonalisable est suffisante ; si elle n’est pas satisfaite,
le comportement asymptotique de Y n est connu, mais plus compliqué. Remarquons
enfin que nous retrouvons dans le cas (iii) des grandes urnes ce qui a déjà été vu
dans le Théorème 9.8 de la Section 9.3.2 par une approche algébrique et en restant
en temps discret.
9.5 Applications algorithmiques
Toutes les situations dans lesquelles un choix uniforme est opéré parmi des
objets de types différents sont naturellement modélisées par une urne de Pólya.
C’est pourquoi de très nombreux modèles d’urnes de Pólya apparaissent dans les
questions combinatoires liées ou non à l’algorithmique. Un exemple algorithmique
est le décompte des feuilles et des nœuds internes dans les arbres récursifs, qui, avec
plusieurs exemples de ce genre, sont considérés dans le livre de Mahmoud [173].
Nous avons choisi d’insister dans cette partie sur l’étude de deux familles
d’arbres de recherche qui font apparaître une urne de Pólya : les arbres m-aires
de recherche en section 9.5.1 et les arbres-B en section 9.5.3 avec en particulier les
9 Urnes de Pólya et applications
(i) Si σ <
1
2 (cas d’une petite urne), alors
Y n − nu 1
√
n
D
−→
n→∞
N(0, ,
2 )
où u 1 est un vecteur propre de R pour la valeur propre 1 et où 2 a une forme
close, fonction de R.
(ii) Si σ =
1
2 (cas d’une petite urne), alors
Y n − nu 1
√
n log n
D
−→
n→∞
N(0, ,
2 )
où u 1 est un vecteur propre de R pour la valeur propre 1 et où 2 a une forme
close, fonction de R.
(iii) Si σ >
1
2 (cas d’une grande urne), alors si λ 2 , . . . , λ r sont les valeurs propres
de partie réelle σ et u 2 , . . . , u r sont des vecteurs propres associés, il existe des
variables aléatoires W 2 , . . . , W r telles que
Y n = nu 1 +
r
i=2
n
λ i W i u i + o(n
σ ),
où o(.) signifie une convergence presque sûre et dans tous les L p , p ≥ 1.
A vrai dire, les résultat (i) et (ii) sont encore vrais lorsque la matrice R n’est pas
diagonalisable. Les résultats de (iii) sont encore vrais pour R non irréductible.
Pour (iii), l’hypothèse R diagonalisable est suffisante ; si elle n’est pas satisfaite,
le comportement asymptotique de Y n est connu, mais plus compliqué. Remarquons
enfin que nous retrouvons dans le cas (iii) des grandes urnes ce qui a déjà été vu
dans le Théorème 9.8 de la Section 9.3.2 par une approche algébrique et en restant
en temps discret.
9.5 Applications algorithmiques
Toutes les situations dans lesquelles un choix uniforme est opéré parmi des
objets de types différents sont naturellement modélisées par une urne de Pólya.
C’est pourquoi de très nombreux modèles d’urnes de Pólya apparaissent dans les
questions combinatoires liées ou non à l’algorithmique. Un exemple algorithmique
est le décompte des feuilles et des nœuds internes dans les arbres récursifs, qui, avec
plusieurs exemples de ce genre, sont considérés dans le livre de Mahmoud [173].
Nous avons choisi d’insister dans cette partie sur l’étude de deux familles
d’arbres de recherche qui font apparaître une urne de Pólya : les arbres m-aires
de recherche en section 9.5.1 et les arbres-B en section 9.5.3 avec en particulier les