14.2 Nombre de tables
189
Pour tout temps n 1 et tout 1 k n, soit A n,k le nombre de tables de
taille k au temps n, c’est-à-dire le nombre de blocs de taille k dans la partition
aléatoire π n . On a
n = A n,1 + 2A n,2 + · · · + nA n,n et |π n | = A n,1 + · · · + A n,n .
Théorème 14.7 (Loi d’Ewens sur les blocs). Pour tout n ∈ N
∗ et tout
(a 1 , . . . , a n ) ∈ N vérifiant a 1 + 2a 2 + · · · + na n = n, on a
P(A n,1 = a 1 , . . . , A n,n = a n ) =
n!
θ(θ + 1) · · · (θ + n − 1)
n
j=1
1
a j !
θ
j
aj
.
Démonstration. Le théorème 14.5 donne
P(A n,1 = a 1 , . . . , A n,n = a n ) =
θ
a1+···+an
θ(θ + 1) · · · (θ + n − 1)
n
j=1
((j − 1)!)
aj
|Π n (a)|
où Π n (a) désigne l’ensemble des π ∈ Π n comportant a k blocs de taille k pour
tout 1 k n. Or l’ensemble Π n (a) a pour cardinal
n!
n
j=1 (j!) aj a j !
,
d’où la formule.
Remarque 14.8 (Apparition et maintient de petites tables). Le processus
des restaurants chinois permet l’apparition de petites tables et le maintien de
leur présence au fil du temps car elles sont choisies au prorata de leur taille !
14.2 Nombre de tables
Au temps n 1, la salle du restaurant se compose de |π n | tables occupées.
Théorème 14.9 (Nombre de tables). Pour tout n 1, on a
E(|π n |) =
n−1
k=0
θ
θ + k
= θ log(n) + O n→∞ (1) ∼
n→∞
θ log(n),
et
Var(|π n |) =
n−1
k=1
θk
(θ + k) 2 = θ log(n) + O n→∞ (1) ∼
n→∞
θ log(n).