188
14 Restaurants chinois
Démonstration. La formule est vraie pour n = 1. Procédons par récurrence
sur n et supposons-la vraie pour n 1. Soit σ
∈ S n+1 . On observe tout
d’abord qu’il existe un unique σ ∈ S n tel que P(σ n+1 = σ
| σ n = σ) > 0. Si
|σ
| = |σ| + 1 alors P(σ n+1 = σ
| σ n = σ) = θ/(θ + n) et si |σ
| = |σ| alors
P(σ n+1 = σ
| σ n = σ) = 1/(θ + n). Dans les deux cas, on a bien
P(σ n+1 = σ
) = P(σ n = σ) P(σ n+1 = σ
| σ n = σ) =
θ
|σ
|
θ(θ + 1) · · · (θ + n)
.
Remarque 14.4 (Marche aléatoire, transpositions, et loi uniforme sur S n ).
Conditionnellement à {σ n = σ}, on peut construire σ n+1 à partir de σ en
choisissant d’abord un élément aléatoire K de {1, . . . , n + 1} valant n + 1 avec
probabilité θ/(θ + n) et 1, . . . , n avec probabilité 1/(θ + n), puis en ajoutant
n + 1 au cycle de σ contenant K si K n ou en créant un nouveau cycle
(n + 1) si K = n + 1. Ceci revient à fabriquer à partir de σ un élément σ
de S n+1 en ajoutant à σ le cycle (n + 1), puis à calculer le produit σ
τ dans
S n+1 où τ est la transposition aléatoire (n + 1, K). Ainsi
(σ n ) n1
loi
= ((1, K 1 ) · · · (n, K n )) n1
où (K n ) n1 est une suite de variables aléatoires indépendantes avec K 1 = 1
et pour tout n 1, K n+1 de loi
1
θ+n δ 1 + · · · +
1
θ+n δ n +
θ
θ+n δ n+1 , et (σ n ) n0
est une marche aléatoire sur S n , non homogène en temps, sur le graphe de
Cayley de S n engendré par les transpositions. Si θ = 1 alors pour tout n 1,
K n suit la loi uniforme sur {1, . . . , n}, tandis que σ n suit la loi uniforme sur
S n , et on retrouve l’algorithme de Fisher-Yates-Knuth du théorème 4.1.
Théorème 14.5 (Loi d’Ewens sur Π n ). Pour tout π ∈ Π n , on a
P(π n = π) =
θ
|π|
θ(θ + 1) · · · (θ + n − 1)
b∈π
(|b| − 1)!.
Démonstration. Le théorème 14.3 donne
P(π n = π) =
σ∈Eπ
P(σ n = σ) =
θ
|π|
θ(θ + 1) · · · (θ + n − 1)
|E π |
où E π est l’ensemble des σ ∈ S n dont la partition de la décomposition en
cycles est π. Il y a (k − 1)! cycles de longueur k d’un ensemble à k éléments
donc le cardinal de E π est donné par
b∈π (|b| − 1)!.
Remarque 14.6 (Loi d’Ewens et loi uniforme sur Π n ). Pour n 3, quel que
soit θ, la loi d’Ewens sur Π n n’est jamais la loi uniforme étudiée dans le chapitre 4. En effet, notons π = {{1}, {2}, . . . , {n}}, π
= {{1, 2}, {3}, . . . , {n}},
π
= {{1, 2, . . . , n}}. Alors P(π n = π) = P(π n = π
) uniquement pour θ = 1
et dans ce cas P(π n = π) = P(π n = π
).
14 Restaurants chinois
Démonstration. La formule est vraie pour n = 1. Procédons par récurrence
sur n et supposons-la vraie pour n 1. Soit σ
∈ S n+1 . On observe tout
d’abord qu’il existe un unique σ ∈ S n tel que P(σ n+1 = σ
| σ n = σ) > 0. Si
|σ
| = |σ| + 1 alors P(σ n+1 = σ
| σ n = σ) = θ/(θ + n) et si |σ
| = |σ| alors
P(σ n+1 = σ
| σ n = σ) = 1/(θ + n). Dans les deux cas, on a bien
P(σ n+1 = σ
) = P(σ n = σ) P(σ n+1 = σ
| σ n = σ) =
θ
|σ
|
θ(θ + 1) · · · (θ + n)
.
Remarque 14.4 (Marche aléatoire, transpositions, et loi uniforme sur S n ).
Conditionnellement à {σ n = σ}, on peut construire σ n+1 à partir de σ en
choisissant d’abord un élément aléatoire K de {1, . . . , n + 1} valant n + 1 avec
probabilité θ/(θ + n) et 1, . . . , n avec probabilité 1/(θ + n), puis en ajoutant
n + 1 au cycle de σ contenant K si K n ou en créant un nouveau cycle
(n + 1) si K = n + 1. Ceci revient à fabriquer à partir de σ un élément σ
de S n+1 en ajoutant à σ le cycle (n + 1), puis à calculer le produit σ
τ dans
S n+1 où τ est la transposition aléatoire (n + 1, K). Ainsi
(σ n ) n1
loi
= ((1, K 1 ) · · · (n, K n )) n1
où (K n ) n1 est une suite de variables aléatoires indépendantes avec K 1 = 1
et pour tout n 1, K n+1 de loi
1
θ+n δ 1 + · · · +
1
θ+n δ n +
θ
θ+n δ n+1 , et (σ n ) n0
est une marche aléatoire sur S n , non homogène en temps, sur le graphe de
Cayley de S n engendré par les transpositions. Si θ = 1 alors pour tout n 1,
K n suit la loi uniforme sur {1, . . . , n}, tandis que σ n suit la loi uniforme sur
S n , et on retrouve l’algorithme de Fisher-Yates-Knuth du théorème 4.1.
Théorème 14.5 (Loi d’Ewens sur Π n ). Pour tout π ∈ Π n , on a
P(π n = π) =
θ
|π|
θ(θ + 1) · · · (θ + n − 1)
b∈π
(|b| − 1)!.
Démonstration. Le théorème 14.3 donne
P(π n = π) =
σ∈Eπ
P(σ n = σ) =
θ
|π|
θ(θ + 1) · · · (θ + n − 1)
|E π |
où E π est l’ensemble des σ ∈ S n dont la partition de la décomposition en
cycles est π. Il y a (k − 1)! cycles de longueur k d’un ensemble à k éléments
donc le cardinal de E π est donné par
b∈π (|b| − 1)!.
Remarque 14.6 (Loi d’Ewens et loi uniforme sur Π n ). Pour n 3, quel que
soit θ, la loi d’Ewens sur Π n n’est jamais la loi uniforme étudiée dans le chapitre 4. En effet, notons π = {{1}, {2}, . . . , {n}}, π
= {{1, 2}, {3}, . . . , {n}},
π
= {{1, 2, . . . , n}}. Alors P(π n = π) = P(π n = π
) uniquement pour θ = 1
et dans ce cas P(π n = π) = P(π n = π
).