376
9 Urnes de Pólya et applications
idée consiste à coder la composition de l’urne par une suite de mots finis dont les
lettres sont prises dans l’alphabet {r, n} (r pour rouge, n pour noire). La composition
initiale de l’urne est codée par le mot
W 0 = rr . . . rnn . . . n = r
α n
β .
La tirage dans l’urne revient à choisir uniformément une lettre du mot. Si la lettre
choisie est un r, nous la remplaçons dans le mot par r a+1 n b ; si la lettre choisie est
un n, nous la remplaçons par r c n d+1 . La succession des tirages donne ainsi lieu à
une suite de mots (aléatoires)
W 0 , W 1 , W 2 . . .
A l’instant n, nous retrouvons bien sûr le vecteur composition Y n en comptant le
nombre de lettres r et n dans le mot W n . Dans toute cette section d’étude par
combinatoire analytique, notons que les vecteurs composition Y n sont des vecteurs
colonne.
Définition 9.1 (Histoires du processus) Si n est un entier naturel, si
u 0
v 0
et
u
v
sont deux vecteurs non nuls 3 à coefficients entiers naturels, une histoire de longueur
n menant de
u 0
v 0
à
u
v
est une suite de mots W 0 = r u 0 n v 0 , W 1 , W 2 , . . . , W n
produits de la manière ci-dessus, pour lesquels W n contient exactement u lettres r
et v lettres n.
Naturellement, avec ces notations, à cause de l’hypothèse de balance, quelle que
soit son histoire, le mot W n a toujours (u 0 + v 0 + nS) lettres. L’objet combinatoire
central de cette méthode est le nombre de ces histoires : notons
H n
u 0 u
v 0 v
le nombre d’histoires de longueur n menant de
u 0
v 0
à
u
v
. Voir les exercices 9.1
et 9.2 pour se familiariser avec cette notion d’histoires.
Comme presque toujours en combinatoire analytique, nous travaillons sur des
séries génératrices. Ici, c’est de la série trivariée des histoires qu’il s’agit : la
variable x compte le nombre de boules rouges, la variable y compte le nombre de
boules noires et la variable z compte la longueur (le temps). La série génératrice est
exponentielle en z. Ainsi, une matrice de remplacement étant donnée, nous noterons
H
x, y, z
u 0
v 0
=
u,v,n∈N
H n
u 0 u
v 0 v
x
u y
v z n
n!
.
3 Nous considérons seulement des urnes viables et donc
u
v
=
0
0
ne se produit jamais.
9 Urnes de Pólya et applications
idée consiste à coder la composition de l’urne par une suite de mots finis dont les
lettres sont prises dans l’alphabet {r, n} (r pour rouge, n pour noire). La composition
initiale de l’urne est codée par le mot
W 0 = rr . . . rnn . . . n = r
α n
β .
La tirage dans l’urne revient à choisir uniformément une lettre du mot. Si la lettre
choisie est un r, nous la remplaçons dans le mot par r a+1 n b ; si la lettre choisie est
un n, nous la remplaçons par r c n d+1 . La succession des tirages donne ainsi lieu à
une suite de mots (aléatoires)
W 0 , W 1 , W 2 . . .
A l’instant n, nous retrouvons bien sûr le vecteur composition Y n en comptant le
nombre de lettres r et n dans le mot W n . Dans toute cette section d’étude par
combinatoire analytique, notons que les vecteurs composition Y n sont des vecteurs
colonne.
Définition 9.1 (Histoires du processus) Si n est un entier naturel, si
u 0
v 0
et
u
v
sont deux vecteurs non nuls 3 à coefficients entiers naturels, une histoire de longueur
n menant de
u 0
v 0
à
u
v
est une suite de mots W 0 = r u 0 n v 0 , W 1 , W 2 , . . . , W n
produits de la manière ci-dessus, pour lesquels W n contient exactement u lettres r
et v lettres n.
Naturellement, avec ces notations, à cause de l’hypothèse de balance, quelle que
soit son histoire, le mot W n a toujours (u 0 + v 0 + nS) lettres. L’objet combinatoire
central de cette méthode est le nombre de ces histoires : notons
H n
u 0 u
v 0 v
le nombre d’histoires de longueur n menant de
u 0
v 0
à
u
v
. Voir les exercices 9.1
et 9.2 pour se familiariser avec cette notion d’histoires.
Comme presque toujours en combinatoire analytique, nous travaillons sur des
séries génératrices. Ici, c’est de la série trivariée des histoires qu’il s’agit : la
variable x compte le nombre de boules rouges, la variable y compte le nombre de
boules noires et la variable z compte la longueur (le temps). La série génératrice est
exponentielle en z. Ainsi, une matrice de remplacement étant donnée, nous noterons
H
x, y, z
u 0
v 0
=
u,v,n∈N
H n
u 0 u
v 0 v
x
u y
v z n
n!
.
3 Nous considérons seulement des urnes viables et donc
u
v
=
0
0
ne se produit jamais.