Chapitre 9
Urnes de Pólya et applications
Nous présentons ici le modèle des urnes de Pólya et les analyses qui s’ensuivent.
Les motivations algorithmiques viennent de l’utilisation de ce modèle pour l’étude
des arbres m-aires de recherche, annoncée en section 8.1.3, ainsi que pour l’étude
des arbres-B de recherche définis en section 3.2.2 (b) et dont les formes d’arbre ont
été dénombrés en section 4.4.
Dans ce chapitre, les urnes de Pólya sont définies en section 9.1, puis étudiées
de plusieurs façons complémentaires : par combinatoire analytique en section 9.2
sont obtenues une description fine de la composition de l’urne à temps fini et
des convergences en loi. Ces dernières peuvent aussi être vues par des approches
probabilistes et nous verrons en section 9.3 comment tirer parti de la dynamique
du processus d’évolution de l’urne et obtenir dans certains cas des convergences
presque sûres. Le plongement en temps continu qui sera précisé en section 9.4
permettra de faire le lien avec des processus de branchement. Une approche
algébrique, au sens de l’algèbre linéaire, permettra d’obtenir le comportement
asymptotique de l’urne, en restant en temps discret. Enfin, trois applications aux
arbres liés à l’algorithmique sont détaillées en section 9.5.
9.1 Définition
Considérons une seule urne qui contient des boules de différentes couleurs. À
chaque instant (le temps est discret), nous procédons au tirage « au hasard » d’une
boule dans l’urne, ce qui signifie que le tirage est uniforme parmi les boules de
l’urne. Nous regardons la couleur de la boule tirée et nous la remettons dans l’urne.
Nous ajoutons alors r ij boules de couleur j quand nous avons tiré une boule de
couleur i. Appelons (Y n ) n≥0 la suite des vecteurs composition de l’urne, c’est-àdire que Y n est le vecteur dont les coordonnées sont le nombre de boules de chaque
couleur à l’instant n. La suite (Y n ) n≥0 (qui est une chaîne de Markov non homogène
© Springer Nature Switzerland AG 2018
B. Chauvin et al., Arbres pour l’Algorithmique, Mathématiques et Applications 83,
https://doi.org/10.1007/978-3-319-93725-0_9
373
Urnes de Pólya et applications
Nous présentons ici le modèle des urnes de Pólya et les analyses qui s’ensuivent.
Les motivations algorithmiques viennent de l’utilisation de ce modèle pour l’étude
des arbres m-aires de recherche, annoncée en section 8.1.3, ainsi que pour l’étude
des arbres-B de recherche définis en section 3.2.2 (b) et dont les formes d’arbre ont
été dénombrés en section 4.4.
Dans ce chapitre, les urnes de Pólya sont définies en section 9.1, puis étudiées
de plusieurs façons complémentaires : par combinatoire analytique en section 9.2
sont obtenues une description fine de la composition de l’urne à temps fini et
des convergences en loi. Ces dernières peuvent aussi être vues par des approches
probabilistes et nous verrons en section 9.3 comment tirer parti de la dynamique
du processus d’évolution de l’urne et obtenir dans certains cas des convergences
presque sûres. Le plongement en temps continu qui sera précisé en section 9.4
permettra de faire le lien avec des processus de branchement. Une approche
algébrique, au sens de l’algèbre linéaire, permettra d’obtenir le comportement
asymptotique de l’urne, en restant en temps discret. Enfin, trois applications aux
arbres liés à l’algorithmique sont détaillées en section 9.5.
9.1 Définition
Considérons une seule urne qui contient des boules de différentes couleurs. À
chaque instant (le temps est discret), nous procédons au tirage « au hasard » d’une
boule dans l’urne, ce qui signifie que le tirage est uniforme parmi les boules de
l’urne. Nous regardons la couleur de la boule tirée et nous la remettons dans l’urne.
Nous ajoutons alors r ij boules de couleur j quand nous avons tiré une boule de
couleur i. Appelons (Y n ) n≥0 la suite des vecteurs composition de l’urne, c’est-àdire que Y n est le vecteur dont les coordonnées sont le nombre de boules de chaque
couleur à l’instant n. La suite (Y n ) n≥0 (qui est une chaîne de Markov non homogène
© Springer Nature Switzerland AG 2018
B. Chauvin et al., Arbres pour l’Algorithmique, Mathématiques et Applications 83,
https://doi.org/10.1007/978-3-319-93725-0_9
373