384
9 Urnes de Pólya et applications
(iii) les moments joints des W i sont donnés en fonction de polynômes à k variables
Q α qui se calculent récursivement :
∀α := (α 2 , . . . , α r ) avec α 2 , . . . , α r entiers positifs,
E
r
i=2
W
α i
i
=
1
+
r
i=2 α i λ i )
Q α (Y 0 ).
Remarque 9.9 Il est intéressant de noter que les variables aléatoires limite W i d’une
grande urne dépendent de la composition initiale de l’urne, alors que la limite u 1
(valable pour les petites et grandes urnes) n’en dépend pas et la limite gaussienne
des petites urnes n’en dépend pas non plus (voir le théorème 9.10).
9.4 Passage du modèle combinatoire discret au modèle
continu
Le processus d’urne de Pólya (Y n ) auquel nous nous sommes intéressés jusqu’à
maintenant est un processus à temps discret. Nous allons « poissoniser » le temps en
introduisant un processus à temps continu (Y CT (t)) t ≥0 qui a la même dynamique.
Cette méthode appelée plongement en temps continu est classique en probabilités
(voir par exemple Bertoin [22] section 1.1) et elle est développée pour les urnes de
Pólya dans l’important travail de Janson [147]. Nous en donnons ici le principe et
les résultats essentiels. Cette méthode fournit les meilleurs résultats à ce jour pour
les grandes urnes à deux couleurs (dans [40]).
Le principe a déjà été utilisé de façon analogue dans la section 6.2.3 pour plonger
les arbres binaires de recherche en temps continu.
9.4.1 Principe du plongement en temps continu
Imaginons que chaque boule présente dans l’urne soit munie d’une horloge colorée
comme la boule, de loi exponentielle de paramètre 1 (les histoires d’horloges exponentielles sont racontées en annexe C.3.2). Toutes les horloges sont indépendantes
entre elles. Lorsqu’une horloge de couleur i sonne, la boule porteuse (de couleur i)
disparaît et donne naissance à (r ij + δ ij ) boules 6 de couleur j , munies d’horloges
colorées, indépendantes et de loi exponentielle de paramètre 1.
Pour t = 0, prenons la même composition initiale que l’urne qu’en temps discret.
Pour tout t ≥ 0, appelons Y CT (t) le vecteur de R k dont la j -ième coordonnée est
le nombre de boules de couleur j dans l’urne à l’instant t. Il s’agit d’un processus de
6 δ ij désigne le symbole de Kronecker : δ ij = 0 si i = j et δ ii = 1.
9 Urnes de Pólya et applications
(iii) les moments joints des W i sont donnés en fonction de polynômes à k variables
Q α qui se calculent récursivement :
∀α := (α 2 , . . . , α r ) avec α 2 , . . . , α r entiers positifs,
E
r
i=2
W
α i
i
=
1
+
r
i=2 α i λ i )
Q α (Y 0 ).
Remarque 9.9 Il est intéressant de noter que les variables aléatoires limite W i d’une
grande urne dépendent de la composition initiale de l’urne, alors que la limite u 1
(valable pour les petites et grandes urnes) n’en dépend pas et la limite gaussienne
des petites urnes n’en dépend pas non plus (voir le théorème 9.10).
9.4 Passage du modèle combinatoire discret au modèle
continu
Le processus d’urne de Pólya (Y n ) auquel nous nous sommes intéressés jusqu’à
maintenant est un processus à temps discret. Nous allons « poissoniser » le temps en
introduisant un processus à temps continu (Y CT (t)) t ≥0 qui a la même dynamique.
Cette méthode appelée plongement en temps continu est classique en probabilités
(voir par exemple Bertoin [22] section 1.1) et elle est développée pour les urnes de
Pólya dans l’important travail de Janson [147]. Nous en donnons ici le principe et
les résultats essentiels. Cette méthode fournit les meilleurs résultats à ce jour pour
les grandes urnes à deux couleurs (dans [40]).
Le principe a déjà été utilisé de façon analogue dans la section 6.2.3 pour plonger
les arbres binaires de recherche en temps continu.
9.4.1 Principe du plongement en temps continu
Imaginons que chaque boule présente dans l’urne soit munie d’une horloge colorée
comme la boule, de loi exponentielle de paramètre 1 (les histoires d’horloges exponentielles sont racontées en annexe C.3.2). Toutes les horloges sont indépendantes
entre elles. Lorsqu’une horloge de couleur i sonne, la boule porteuse (de couleur i)
disparaît et donne naissance à (r ij + δ ij ) boules 6 de couleur j , munies d’horloges
colorées, indépendantes et de loi exponentielle de paramètre 1.
Pour t = 0, prenons la même composition initiale que l’urne qu’en temps discret.
Pour tout t ≥ 0, appelons Y CT (t) le vecteur de R k dont la j -ième coordonnée est
le nombre de boules de couleur j dans l’urne à l’instant t. Il s’agit d’un processus de
6 δ ij désigne le symbole de Kronecker : δ ij = 0 si i = j et δ ii = 1.