14
Restaurants chinois
Mots-clés. Partition aléatoire ; permutation aléatoire ; loi d’Ewens ; algorithme de Fisher-Yates-Knuth ; nombres de Bell ; nombres de Stirling.
Outils. Combinatoire ; groupe symétrique ; chaîne de Markov ; martingale ; inégalité de Markov ; loi de Poisson.
Difficulté. **
Ce chapitre est consacré à l’étude de propriétés remarquables de la loi
d’Ewens, apparue dans le chapitre 13 comme la loi de la partition d’une population en fonction des allèles d’un même gène dans un modèle à nombre
d’allèles infini. Les propriétés sont présentées sous la forme ludique du processus dit des restaurants chinois mais ce sont bien les interactions avec la
biologie évoquées ci-dessus qui en sont la réelle motivation d’origine.
Pour tout entier n 1, on note S n l’ensemble des permutations de
{1, . . . , n} (groupe symétrique). Le processus des restaurants chinois est une
chaîne de Markov inhomogène (σ n ) n1 , d’espace d’états ∪ n1 S n , où σ n est à
valeurs dans S n pour tout n 1, de valeur initiale σ 1 = (1), et de noyau de
transition donné pour tous (σ, σ
) ∈ S n × S n+1 par
P(σ n+1 = σ
| σ n = σ) =
⎧
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩
1
θ + n
si σ
s’obtient en insérant n + 1
dans l’un des cycles de σ ;
θ
θ + n
si σ
s’obtient en ajoutant
le cycle (n + 1) à σ ;
0
sinon ;
185
© Springer-Verlag Berlin Heidelberg 2016
D. Chafaï and F. Malrieu, Recueil de Modèles Aléatoires,
Mathématiques et Applications 78, DOI 10.1007/978-3-662-49768-5_14