66
4 Permutations, partitions, et graphes
P(s 2n−k+1 = s 2n−k − 1 | s 0 , . . . , s 2n−k ) =
N (r − 1, k − 1)
N (r, k)
où r = s 2n−k .
Le nombre N (r, k) est également le nombre de chemins de la marche reliant
(0, r) et (k, 0) en restant positifs ou nuls. On a forcément k r. Chaque
chemin de ce type comporte t r incréments −1 et k − t = t − r incréments
+1, d’où 2t = k + r, ce qui fait que k + r est pair. En utilisant les notations
et résultats de la preuve du théorème du scrutin 2.6, il vient
N (r, k) = P
+
k+1,r+1 =
r + 1
k + 1
k + 1
t + 1
=
r + 1
t + 1
k
t
.
Il en découle que
P(s 2n−k+1 = s 2n−k − 1 | s 0 , . . . , s 2n−k ) =
r(k + r + 2)
2k(r + 1)
où r = s 2n−k .
Enfin le changement de variable 2n−k → k fournit le résultat annoncé. Notons
que si r = k alors P(s 2n−k+1 = s 2n−k − 1 | s 0 , . . . , s 2n−k ) = 1.
D’après le théorème 2.5, le cardinal de P n et de T n est le nombre de Catalan
C n−1 . Les ensembles T n et P n sont également en bijection avec l’ensemble des
parenthésages constitués de n paires de parenthèses. Il suffit en effet de recoder
la suite des incréments du chemin de la marche aléatoire par des parenthèses.
Ainsi par exemple la suite d’incréments +1, +1, −1, −1 correspondant à la
trajectoire (s i ) 0i4 de la figure 4.2 se traduit par le parenthésage (()). Cette
interprétation apparaît dans la preuve du théorème de Wigner 21.9.
4.6 Pour aller plus loin
Il arrive que la structure de l’ensemble d’intérêt ne fournisse pas d’algorithme séduisant de simulation de la loi uniforme, et que la méthode du
rejet à partir d’un ensemble plus gros ne soit pas praticable. Dans ce cas,
il est souvent possible d’utiliser des algorithmes markoviens comme celui de
Metropolis-Hasting ou de Propp-Wilson, abordés dans le chapitre 5.
Une analyse probabiliste de la complexité de l’algorithme de tri rapide
randomisé se trouve par exemple dans le livre de Rajeev Motwani et Prabhakar
Raghavan [MR95]. Le livre monumental de Donald Knuth [Knu05] constitue
une référence incontournable pour l’analyse des algorithmes et la simulation
de la loi uniforme sur les ensembles classiques comme les permutations ou
les partitions. C’est dans la première édition de ce livre datant des années
1960 que Knuth a popularisé l’algorithme de simulation de la loi uniforme
sur les permutations, reprenant un article antérieur de Richard Durstenfeld
[Dur64]. L’algorithme remonte en fait à Ronald Fisher et Frank Yates [FY48].
Il est implémenté en standard dans les logiciels de calcul. Cet algorithme
4 Permutations, partitions, et graphes
P(s 2n−k+1 = s 2n−k − 1 | s 0 , . . . , s 2n−k ) =
N (r − 1, k − 1)
N (r, k)
où r = s 2n−k .
Le nombre N (r, k) est également le nombre de chemins de la marche reliant
(0, r) et (k, 0) en restant positifs ou nuls. On a forcément k r. Chaque
chemin de ce type comporte t r incréments −1 et k − t = t − r incréments
+1, d’où 2t = k + r, ce qui fait que k + r est pair. En utilisant les notations
et résultats de la preuve du théorème du scrutin 2.6, il vient
N (r, k) = P
+
k+1,r+1 =
r + 1
k + 1
k + 1
t + 1
=
r + 1
t + 1
k
t
.
Il en découle que
P(s 2n−k+1 = s 2n−k − 1 | s 0 , . . . , s 2n−k ) =
r(k + r + 2)
2k(r + 1)
où r = s 2n−k .
Enfin le changement de variable 2n−k → k fournit le résultat annoncé. Notons
que si r = k alors P(s 2n−k+1 = s 2n−k − 1 | s 0 , . . . , s 2n−k ) = 1.
D’après le théorème 2.5, le cardinal de P n et de T n est le nombre de Catalan
C n−1 . Les ensembles T n et P n sont également en bijection avec l’ensemble des
parenthésages constitués de n paires de parenthèses. Il suffit en effet de recoder
la suite des incréments du chemin de la marche aléatoire par des parenthèses.
Ainsi par exemple la suite d’incréments +1, +1, −1, −1 correspondant à la
trajectoire (s i ) 0i4 de la figure 4.2 se traduit par le parenthésage (()). Cette
interprétation apparaît dans la preuve du théorème de Wigner 21.9.
4.6 Pour aller plus loin
Il arrive que la structure de l’ensemble d’intérêt ne fournisse pas d’algorithme séduisant de simulation de la loi uniforme, et que la méthode du
rejet à partir d’un ensemble plus gros ne soit pas praticable. Dans ce cas,
il est souvent possible d’utiliser des algorithmes markoviens comme celui de
Metropolis-Hasting ou de Propp-Wilson, abordés dans le chapitre 5.
Une analyse probabiliste de la complexité de l’algorithme de tri rapide
randomisé se trouve par exemple dans le livre de Rajeev Motwani et Prabhakar
Raghavan [MR95]. Le livre monumental de Donald Knuth [Knu05] constitue
une référence incontournable pour l’analyse des algorithmes et la simulation
de la loi uniforme sur les ensembles classiques comme les permutations ou
les partitions. C’est dans la première édition de ce livre datant des années
1960 que Knuth a popularisé l’algorithme de simulation de la loi uniforme
sur les permutations, reprenant un article antérieur de Richard Durstenfeld
[Dur64]. L’algorithme remonte en fait à Ronald Fisher et Frank Yates [FY48].
Il est implémenté en standard dans les logiciels de calcul. Cet algorithme