9.2 Etude combinatoire analytique
375
fixe S de boules. 2 Ce nombre S est appelé par anglicisme la balance de l’urne.
Autrement dit, nous supposons qu’il existe un entier S tel que pour tout i = 1, . . . , k
S =
k
j =1
r ij .
Par conséquent, si |Y 0 | est le nombre de boules initialement dans l’urne :
|Y 0 | :=
k
i=1
Y
(i)
0 ,
alors le nombre total de boules dans l’urne à l’instant n est déterministe, égal à
|Y n | = |Y 0 | + nS. Bien sûr, la composition de l’urne est aléatoire. L’évolution de
l’urne est décrite par les probabilités de transition : pour tout i = 1, . . . , k,
P(Y n+1 = Y n + i |Y n ) =
Y
(i)
n
|Y 0 | + nS
,
où les vecteurs i , i = 1, . . . , k sont les vecteurs lignes de la matrice R. Ce
qui est remarquable, dû à l’hypothèse d’équilibre, est que ces transitions (bien
que non homogènes) sont linéaires en Y n . C’est pour cette raison que l’approche
algébrique (au sens algèbre linéaire) dans la section 9.3.2 sera efficace. Lorsque que
l’hypothèse d’équilibre n’est pas vérifiée, d’autres méthodes peuvent être utilisées,
comme la combinatoire analytique (dans Morcrette [188] et en section 9.2) ou le
plongement en temps continu (dans Kotz, Mahmoud et Robert [161], Janson [147]
et en section 9.4).
9.2 Etude combinatoire analytique
L’approche combinatoire analytique des urnes de Pólya est due à Flajolet et ses
co-auteurs Dumas, Gabarró, Pekari et Puyhaubert au milieu des années 2000. Les
deux articles fondateurs sont [102] et [103]. La présentation qui suit est reprise de
Pouyanne [215], dans un cours de master donné en Tunisie en 2012.
9.2.1 Les histoires
Nous supposons dans cette section que l’urne est à deux couleurs, sa matrice de
remplacement est
a b
c d
et la composition initiale de l’urne est (α, β). La première
2 La notation S vient de l’article originel en allemand d’Eggenberger et Pólya [210] pour Summe
qui veut dire somme.
375
fixe S de boules. 2 Ce nombre S est appelé par anglicisme la balance de l’urne.
Autrement dit, nous supposons qu’il existe un entier S tel que pour tout i = 1, . . . , k
S =
k
j =1
r ij .
Par conséquent, si |Y 0 | est le nombre de boules initialement dans l’urne :
|Y 0 | :=
k
i=1
Y
(i)
0 ,
alors le nombre total de boules dans l’urne à l’instant n est déterministe, égal à
|Y n | = |Y 0 | + nS. Bien sûr, la composition de l’urne est aléatoire. L’évolution de
l’urne est décrite par les probabilités de transition : pour tout i = 1, . . . , k,
P(Y n+1 = Y n + i |Y n ) =
Y
(i)
n
|Y 0 | + nS
,
où les vecteurs i , i = 1, . . . , k sont les vecteurs lignes de la matrice R. Ce
qui est remarquable, dû à l’hypothèse d’équilibre, est que ces transitions (bien
que non homogènes) sont linéaires en Y n . C’est pour cette raison que l’approche
algébrique (au sens algèbre linéaire) dans la section 9.3.2 sera efficace. Lorsque que
l’hypothèse d’équilibre n’est pas vérifiée, d’autres méthodes peuvent être utilisées,
comme la combinatoire analytique (dans Morcrette [188] et en section 9.2) ou le
plongement en temps continu (dans Kotz, Mahmoud et Robert [161], Janson [147]
et en section 9.4).
9.2 Etude combinatoire analytique
L’approche combinatoire analytique des urnes de Pólya est due à Flajolet et ses
co-auteurs Dumas, Gabarró, Pekari et Puyhaubert au milieu des années 2000. Les
deux articles fondateurs sont [102] et [103]. La présentation qui suit est reprise de
Pouyanne [215], dans un cours de master donné en Tunisie en 2012.
9.2.1 Les histoires
Nous supposons dans cette section que l’urne est à deux couleurs, sa matrice de
remplacement est
a b
c d
et la composition initiale de l’urne est (α, β). La première
2 La notation S vient de l’article originel en allemand d’Eggenberger et Pólya [210] pour Summe
qui veut dire somme.