194
14 Restaurants chinois
Notons que pour θ = 1, la permutation aléatoire σ n suit la loi uniforme
sur S n , et possède |σ n | = |π n | ∼ log(n) cycles, et en moyenne E(A n,1 ) = 1
point fixe pour tout n 1.
Démonstration. Il s’agit de décrire la loi de la première composante A n,1
d’un vecteur aléatoire A n de N
n qui suit la loi d’Ewens. Il est cependant plus
commode de voir A n,1 comme le nombre de blocs de taille 1 dans π n . On
a A 1,1 = 1 et 0 A n,1 n pour tout n ∈ N
∗ . De plus, pour tous entiers
1 a 1 , . . . , a n n et 0 a n+1 n + 1 on a
P(A n+1,1 = a n+1 | A 1,1 = a 1 , . . . , A n,1 = a n ) = P(A n+1,1 = a n+1 | A n,1 = a n )
qui vaut
⎧
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩
θ
θ + n
si a n+1 = a n + 1 (s’attabler seul à une table vide) ;
a n
θ + n
si a n+1 = a n − 1 (rejoindre la table d’un solitaire) ;
n − a n
θ + n
si a n+1 = a n (rejoindre une table comptant 2 clients ou +) ;
0
sinon.
En particulier, (A n,1 ) n1 est une chaîne de Markov inhomogène d’espace
d’états N. On obtient la remarquable formule affine
3
E(A n+1,1 | A n,1 = a) =
a(θ + n − 1) + θ
θ + n
.
Cela donne (n + θ)m n+1 = (θ + n − 1)m n + θ où m n := E(A n,1 ). La formule
annoncée pour m n s’en déduit. Pour la variance, les calculs sont semblables
mais plus lourds, et utilisent la formule
Var(X) = E(Var(X | Y )) + Var(E(X | Y ))
où Var(X | Y ) := E(X
2
| Y ) − E(X | Y )
2 est la variance conditionnelle.
L’entier A n,n représente le nombre de tables comportant n clients, autrement dit le nombre de blocs de taille n dans π n . Lorsqu’une telle table existe,
elle regroupe tous les clients, et on dit donc qu’il s’agit d’une table unique.
On a A n,n = 1 si et seulement si |π n | = 1. Le théorème suivant précise les
choses, et montre en particulier qu’asymptotiquement, le modèle des restaurants chinois ne fait pas apparaître de table unique.
3. Une martingale se cache dans la chaîne de Markov !