4.6 Pour aller plus loin
67
correspond exactement au processus des restaurants chinois du chapitre 14,
et la loi uniforme sur S n coïncide avec la loi d’Ewens de paramètre θ = 1.
Pour tout n 1 fixé, la marche aléatoire sur S n dont les pas sont i.i.d. de
loi uniforme sur l’ensemble des transpositions, étudiée par Persi Diaconis et
Mehrdad Shahshahani [DS81], converge vers la loi uniforme sur S n de manière
abrupte après environ n log(n) étapes, comme pour celle du mélange de cartes
du chapitre 2. Si σ ∈ S n et τ = (i, j) est une transposition, alors la décomposition en cycles de στ s’obtient à partir de celle de σ en fusionnant les cycles
de σ contenant i et j s’ils sont différents, ou bien en fissionnant le cycle de σ
contenant i et j dans le cas contraire. La chaîne de Diaconis et Shahshahani,
traduite sur Π n en considérant la partition des supports des cycles, est une
chaîne de fragmentation-coalescence. Il est possible de concevoir son noyau
de transition de la manière suivante : sachant que la chaîne est en P ∈ Π n ,
on tire au hasard uniformément et avec remise i et j dans {1, . . . , n}, puis
on fusionne les blocs de P contenant i et j s’ils sont différents, ou bien on
fissionne uniformément le bloc de P contenant i et j dans le cas contraire.
Cette chaîne sur Π n est considérée dans un article de Persi Diaconis, Eddy
Mayer-Wolf, Ofer Zeitouni, et Martin Zerner [DMWZZ04]. Plus généralement,
au-delà des transpositions aléatoires, Nathanaël Berestycki, Oded Schramm,
et Ofer Zeitouni ont établi dans [BSZ11] que pour tout n k 2, la marche
aléatoire sur S n dont les pas sont des k-cycles i.i.d. uniformes converge vers
la loi uniforme sur S n après environ (1/k)n log(n) étapes.
L’algorithme de Aart Stam de simulation de la loi uniforme sur les partitions se trouve dans [Sta83] et dans le livre de Knuth [Knu05, Volume 4A].
On prendra garde à ne pas confondre les partitions d’un ensemble fini avec la
notion de partition d’entier, qui est reliée aux diagrammes de Alfred Young
ou de Norman Ferrers. Le théorème de Paul Erdős et Tibor Gallai figure dans
[EG60], et a été redémontré par plusieurs auteurs, dont Claude Berge [Ber76].
Une preuve courte et constructive se trouve par exemple dans un article de
Amitabha Tripathi, Sushmita Venugopalan, et Douglas West [TVW10]. L’algorithme des configurations remonte à Béla Bollobás [Bol80], et a été raffiné
et étendu notamment par Brendan McKay et Nicholas Wormald [MW90]. Il
est abordé dans les cours de Charles Bordenave [Bor14a] et de Remco van der
Hofstad [vdH14]. À ce sujet, soit M n le multigraphe aléatoire du modèle des
configurations de sommets {1, . . . , n} pour la suite de degrés d n,1 , . . . , d n,n , et
p n,k = (1/n)
n
i=1 1 {dn,i=k} la proportion de sommets de degré k, et supposons qu’il existe une loi (p k ) k1 telle que lim n→∞ p n,k = p k , et telle que les
deux premiers moments convergent :
μ = lim
n→∞
1
n
n
i=1
d n,i = lim
n→∞
∞
k=1
k
n
n
i=1
1 {dn,i=k}
= lim
n→∞
∞
k=1
kp n,k =
∞
k=1
kp k < ∞
et
67
correspond exactement au processus des restaurants chinois du chapitre 14,
et la loi uniforme sur S n coïncide avec la loi d’Ewens de paramètre θ = 1.
Pour tout n 1 fixé, la marche aléatoire sur S n dont les pas sont i.i.d. de
loi uniforme sur l’ensemble des transpositions, étudiée par Persi Diaconis et
Mehrdad Shahshahani [DS81], converge vers la loi uniforme sur S n de manière
abrupte après environ n log(n) étapes, comme pour celle du mélange de cartes
du chapitre 2. Si σ ∈ S n et τ = (i, j) est une transposition, alors la décomposition en cycles de στ s’obtient à partir de celle de σ en fusionnant les cycles
de σ contenant i et j s’ils sont différents, ou bien en fissionnant le cycle de σ
contenant i et j dans le cas contraire. La chaîne de Diaconis et Shahshahani,
traduite sur Π n en considérant la partition des supports des cycles, est une
chaîne de fragmentation-coalescence. Il est possible de concevoir son noyau
de transition de la manière suivante : sachant que la chaîne est en P ∈ Π n ,
on tire au hasard uniformément et avec remise i et j dans {1, . . . , n}, puis
on fusionne les blocs de P contenant i et j s’ils sont différents, ou bien on
fissionne uniformément le bloc de P contenant i et j dans le cas contraire.
Cette chaîne sur Π n est considérée dans un article de Persi Diaconis, Eddy
Mayer-Wolf, Ofer Zeitouni, et Martin Zerner [DMWZZ04]. Plus généralement,
au-delà des transpositions aléatoires, Nathanaël Berestycki, Oded Schramm,
et Ofer Zeitouni ont établi dans [BSZ11] que pour tout n k 2, la marche
aléatoire sur S n dont les pas sont des k-cycles i.i.d. uniformes converge vers
la loi uniforme sur S n après environ (1/k)n log(n) étapes.
L’algorithme de Aart Stam de simulation de la loi uniforme sur les partitions se trouve dans [Sta83] et dans le livre de Knuth [Knu05, Volume 4A].
On prendra garde à ne pas confondre les partitions d’un ensemble fini avec la
notion de partition d’entier, qui est reliée aux diagrammes de Alfred Young
ou de Norman Ferrers. Le théorème de Paul Erdős et Tibor Gallai figure dans
[EG60], et a été redémontré par plusieurs auteurs, dont Claude Berge [Ber76].
Une preuve courte et constructive se trouve par exemple dans un article de
Amitabha Tripathi, Sushmita Venugopalan, et Douglas West [TVW10]. L’algorithme des configurations remonte à Béla Bollobás [Bol80], et a été raffiné
et étendu notamment par Brendan McKay et Nicholas Wormald [MW90]. Il
est abordé dans les cours de Charles Bordenave [Bor14a] et de Remco van der
Hofstad [vdH14]. À ce sujet, soit M n le multigraphe aléatoire du modèle des
configurations de sommets {1, . . . , n} pour la suite de degrés d n,1 , . . . , d n,n , et
p n,k = (1/n)
n
i=1 1 {dn,i=k} la proportion de sommets de degré k, et supposons qu’il existe une loi (p k ) k1 telle que lim n→∞ p n,k = p k , et telle que les
deux premiers moments convergent :
μ = lim
n→∞
1
n
n
i=1
d n,i = lim
n→∞
∞
k=1
k
n
n
i=1
1 {dn,i=k}
= lim
n→∞
∞
k=1
kp n,k =
∞
k=1
kp k < ∞
et