374
9 Urnes de Pólya et applications
à valeurs dans N k avec k un entier fixé égal au nombre de couleurs), est entièrement
décrite par la composition initiale de l’urne et par la matrice dite de remplacement
R = (r ij ) à k lignes et k colonnes et à coefficients entiers relatifs. L’objectif
de ce chapitre est d’étudier le comportement asymptotique de Y n , c’est-à-dire la
composition asymptotique de l’urne.
Comme nous autorisons des coefficients négatifs de la matrice de remplacement,
ce qui signifie des suppressions de boules, la question se pose de la viabilité 1
(en anglais « tenability ») de l’urne. Dans le modèle étudié ici, nous supposerons
que seuls les coefficients diagonaux de R peuvent être négatifs. Une condition
nécessaire et suffisante pour assurer dans ce cas la viabilité de l’urne est la condition
arithmétique suivante qui contraint les coefficients de R et les valeurs Y
(j )
0 (où Y
(j )
0
est la j -ième coordonnée du vecteur Y 0 ) de l’état initial :
Une urne est viable si et seulement si pour tout j ∈ {1, 2, . . . , k} tel que
r jj ≤ −1, alors
r jj divise Y
(j )
0 et ∀i = j, r jj divise r ij .
(9.1)
La vérification se fait par récurrence sur n. Le cas de coefficients diagonaux négatifs
apparaîtra dans les exemples des arbres-B et des arbres m-aires de recherche. L’urne
−2 3
4 −3
associée aux arbres 2–3, dans la section 9.5.2 en est un cas particulier.
Le modèle historique a été introduit par Eggenberger et Pólya [210] en 1923 :
l’urne contient des boules de deux couleurs, disons rouges et noires. Tirons au
hasard une boule dans l’urne ; si une boule rouge (respectivement noire) a été tirée,
remettons-la dans l’urne puis ajoutons S boules rouges (respectivement S boules
noires) dans l’urne avec S ≥ 1. La matrice de remplacement est R =
S 0
0 S
.
Ce cas et sa généralisation à plus de deux couleurs ne sont pas détaillés ici ; après
renormalisation, le vecteur composition de l’urne suit alors asymptotiquement une
loi de Dirichlet sur le simplexe de R k . Chaque coordonnée (le nombre de boules
rouges par exemple) suit asymptotiquement une loi Beta. Ces résultats remontent
apparemment à Athreya [11], sont mentionnés par Blackwell et Kendall [29], et
évoqués dans le livre de Johnson et Kotz [151]. Pour un résumé par la méthode des
moments, voir l’appendice de [42] et l’annexe C.9.
Dans ce chapitre, nous considérons uniquement le cas dit des urnes équilibrées
(en anglais « balanced ») dans lesquelles nous ajoutons à chaque instant un nombre
1 Nous dirons qu’une urne est viable lorsqu’à tout instant n ≥ 0, toute opération de suppression de
boules induite par la matrice de remplacement est possible.
9 Urnes de Pólya et applications
à valeurs dans N k avec k un entier fixé égal au nombre de couleurs), est entièrement
décrite par la composition initiale de l’urne et par la matrice dite de remplacement
R = (r ij ) à k lignes et k colonnes et à coefficients entiers relatifs. L’objectif
de ce chapitre est d’étudier le comportement asymptotique de Y n , c’est-à-dire la
composition asymptotique de l’urne.
Comme nous autorisons des coefficients négatifs de la matrice de remplacement,
ce qui signifie des suppressions de boules, la question se pose de la viabilité 1
(en anglais « tenability ») de l’urne. Dans le modèle étudié ici, nous supposerons
que seuls les coefficients diagonaux de R peuvent être négatifs. Une condition
nécessaire et suffisante pour assurer dans ce cas la viabilité de l’urne est la condition
arithmétique suivante qui contraint les coefficients de R et les valeurs Y
(j )
0 (où Y
(j )
0
est la j -ième coordonnée du vecteur Y 0 ) de l’état initial :
Une urne est viable si et seulement si pour tout j ∈ {1, 2, . . . , k} tel que
r jj ≤ −1, alors
r jj divise Y
(j )
0 et ∀i = j, r jj divise r ij .
(9.1)
La vérification se fait par récurrence sur n. Le cas de coefficients diagonaux négatifs
apparaîtra dans les exemples des arbres-B et des arbres m-aires de recherche. L’urne
−2 3
4 −3
associée aux arbres 2–3, dans la section 9.5.2 en est un cas particulier.
Le modèle historique a été introduit par Eggenberger et Pólya [210] en 1923 :
l’urne contient des boules de deux couleurs, disons rouges et noires. Tirons au
hasard une boule dans l’urne ; si une boule rouge (respectivement noire) a été tirée,
remettons-la dans l’urne puis ajoutons S boules rouges (respectivement S boules
noires) dans l’urne avec S ≥ 1. La matrice de remplacement est R =
S 0
0 S
.
Ce cas et sa généralisation à plus de deux couleurs ne sont pas détaillés ici ; après
renormalisation, le vecteur composition de l’urne suit alors asymptotiquement une
loi de Dirichlet sur le simplexe de R k . Chaque coordonnée (le nombre de boules
rouges par exemple) suit asymptotiquement une loi Beta. Ces résultats remontent
apparemment à Athreya [11], sont mentionnés par Blackwell et Kendall [29], et
évoqués dans le livre de Johnson et Kotz [151]. Pour un résumé par la méthode des
moments, voir l’appendice de [42] et l’annexe C.9.
Dans ce chapitre, nous considérons uniquement le cas dit des urnes équilibrées
(en anglais « balanced ») dans lesquelles nous ajoutons à chaque instant un nombre
1 Nous dirons qu’une urne est viable lorsqu’à tout instant n ≥ 0, toute opération de suppression de
boules induite par la matrice de remplacement est possible.