190
14 Restaurants chinois
Fig. 14.2. Histogramme d’un échantillon de taille 5000 de la loi d’Ewens de taille
n = 1000 et de paramètre θ = 1.
Démonstration. La suite markovienne (π n ) n1 a la même loi que la suite
récurrente aléatoire définie par π 1 = {{1}} puis pour tout n 1 par
π n+1 = f n (π n , ε n+1 )
où (ε n ) n1 sont des variables aléatoires i.i.d. de loi uniforme sur [0, 1], et où
f n (π, ε) est l’élément de Π n+1 obtenu à partir de π ∈ Π n soit en ajoutant n+1
au bloc b k de π si ε ∈ [(|b 1 | + · · · + |b k−1 |)/(θ + n), (|b 1 | + · · · + |b k |)/(θ + n)]
avec 1 k |π|, où b 1 , . . . , b |π| sont les blocs de π, soit en ajoutant le bloc
{n + 1} à la partition π si ε ∈ [n/(θ + n), (θ + n)/(θ + n)]. On rappelle que
n = |b 1 | + · · · + |b |π| |. On a alors |π n | = ξ 1 + · · · + ξ n pour tout k 1, où
ξ k := 1 {εk∈[
k−1
θ+k−1 ,
θ+k−1
θ+k−1 ]} .
La suite (ξ k ) k1 est constituée de variables aléatoires indépendantes de lois
de Bernoulli, et pour tout k 1
P(ξ k = 1) = 1 − P(ξ k = 0) =
θ
θ + k − 1
.
L’événement {ξ n = 1} signifie que le client n décide de créer sa propre table,
tandis que l’événement {ξ n = 0} signifie qu’il décide de rejoindre une table