382
9 Urnes de Pólya et applications
(du moins dès que |Y 0 | + λ n’est pas un entier négatif), il apparaît que le
comportement asymptotique de EY n sera donné par la ou les valeurs propres de
R de plus grande partie réelle.
Lemme 9.5 La valeur propre de R de plus grande partie réelle est λ 1 = 1 et toutes
les autres valeurs propres sont telles que (λ) < 1.
Preuve Comme la somme des coefficients d’une ligne de R est égale à 1, cela
entraîne que v 1 := t (1, 1, . . . , 1) est vecteur propre à droite de R pour la valeur
propre 1.
Plaçons-nous dans un premier temps dans l’ensemble M des matrices à k lignes
et k colonnes (rappelons que k est le nombre de couleurs), à coefficients positifs
ou nuls et dont la somme des lignes est égale à 1. Cet ensemble est stable par la
multiplication des matrices et il est compact (pour la topologie des normes). Par
conséquent, pour tout entier n, la matrice R n est encore dans ce compact donc la
suite de matrices (R n ) est bornée. Donc pour toute valeur propre λ de R, la suite
(λ n ) est bornée. Cela implique que |λ| ≤ 1, que toutes les valeurs propres sont dans
le disque de rayon 1 et que 1 est la seule valeur propre de partie réelle égale à 1, les
autres étant de partie réelle strictement inférieure à 1.
Si les coefficients de la matrice de remplacement ne sont pas tous positifs, nous
nous y ramenons en choisissant un réel a > 0 tel que
R+aI
1+a ∈ M (car seuls les
termes diagonaux peuvent être négatifs).
Supposons que 1 soit valeur propre simple. Alors, ce lemme et les formules (9.7)
et (9.8) entraînent EY n ∼
n
|Y 0 | Y 0 π 1 . Choisissons v 1 = t (1, . . . , 1) comme vecteur
propre à droite pour la valeur propre (simple) λ 1 = 1, et prenons u 1 comme vecteur
propre à gauche tel que u 1 v 1 = 1, de sorte que π 1 = v 1 u 1 . Alors Y 0 π 1 = Y 0 v 1 u 1 =
|Y 0 |u 1 et donc EY n ∼ nu 1 . D’où le théorème suivant, qui est valide même si R n’est
pas diagonalisable :
Théorème 9.6 Soit une urne de Pólya à k couleurs, de balance 1, de composition
initiale Y 0 . Supposons que 1 soit valeur propre simple, posons v 1 = t (1, . . . , 1) et
appelons u 1 le vecteur propre à gauche pour la valeur propre 1, tel que u 1 v 1 = 1.
Alors, quand n tend vers +∞,
EY n
n
−→ u 1 .
En fait il y a mieux que cette convergence en moyenne, il y a convergence presque
sûre du vecteur
Y n
n , mais c’est un peu plus long à obtenir. De plus, nous voudrions
préciser le développement asymptotique de Y n : est-ce que (Y n −nu 1 ) divisé par une
puissance de n a une limite ? C’est l’objet du théorème 9.8 dont la démonstration
repose sur une approche algébrique exposée dans la section qui suit.
9 Urnes de Pólya et applications
(du moins dès que |Y 0 | + λ n’est pas un entier négatif), il apparaît que le
comportement asymptotique de EY n sera donné par la ou les valeurs propres de
R de plus grande partie réelle.
Lemme 9.5 La valeur propre de R de plus grande partie réelle est λ 1 = 1 et toutes
les autres valeurs propres sont telles que (λ) < 1.
Preuve Comme la somme des coefficients d’une ligne de R est égale à 1, cela
entraîne que v 1 := t (1, 1, . . . , 1) est vecteur propre à droite de R pour la valeur
propre 1.
Plaçons-nous dans un premier temps dans l’ensemble M des matrices à k lignes
et k colonnes (rappelons que k est le nombre de couleurs), à coefficients positifs
ou nuls et dont la somme des lignes est égale à 1. Cet ensemble est stable par la
multiplication des matrices et il est compact (pour la topologie des normes). Par
conséquent, pour tout entier n, la matrice R n est encore dans ce compact donc la
suite de matrices (R n ) est bornée. Donc pour toute valeur propre λ de R, la suite
(λ n ) est bornée. Cela implique que |λ| ≤ 1, que toutes les valeurs propres sont dans
le disque de rayon 1 et que 1 est la seule valeur propre de partie réelle égale à 1, les
autres étant de partie réelle strictement inférieure à 1.
Si les coefficients de la matrice de remplacement ne sont pas tous positifs, nous
nous y ramenons en choisissant un réel a > 0 tel que
R+aI
1+a ∈ M (car seuls les
termes diagonaux peuvent être négatifs).
Supposons que 1 soit valeur propre simple. Alors, ce lemme et les formules (9.7)
et (9.8) entraînent EY n ∼
n
|Y 0 | Y 0 π 1 . Choisissons v 1 = t (1, . . . , 1) comme vecteur
propre à droite pour la valeur propre (simple) λ 1 = 1, et prenons u 1 comme vecteur
propre à gauche tel que u 1 v 1 = 1, de sorte que π 1 = v 1 u 1 . Alors Y 0 π 1 = Y 0 v 1 u 1 =
|Y 0 |u 1 et donc EY n ∼ nu 1 . D’où le théorème suivant, qui est valide même si R n’est
pas diagonalisable :
Théorème 9.6 Soit une urne de Pólya à k couleurs, de balance 1, de composition
initiale Y 0 . Supposons que 1 soit valeur propre simple, posons v 1 = t (1, . . . , 1) et
appelons u 1 le vecteur propre à gauche pour la valeur propre 1, tel que u 1 v 1 = 1.
Alors, quand n tend vers +∞,
EY n
n
−→ u 1 .
En fait il y a mieux que cette convergence en moyenne, il y a convergence presque
sûre du vecteur
Y n
n , mais c’est un peu plus long à obtenir. De plus, nous voudrions
préciser le développement asymptotique de Y n : est-ce que (Y n −nu 1 ) divisé par une
puissance de n a une limite ? C’est l’objet du théorème 9.8 dont la démonstration
repose sur une approche algébrique exposée dans la section qui suit.