4
Permutations, partitions, et graphes
Mots-clés. Loi uniforme ; simulation ; permutation ; partition ; graphe ;
arbre ; nombres de Catalan ; nombres de Bell.
Outils. Groupe symétrique ; marche aléatoire ; loi discrète.
Difficulté. *
Ce chapitre présente des algorithmes de simulation de loi uniforme sur
quelques ensembles remarquables de permutations, partitions, et graphes. La
portée des concepts et techniques abordés dépasse le cadre considéré, qui a le
mérite d’être élémentaire.
4.1 Algorithme basique pour les lois discrètes
Considérons le problème de la simulation d’une réalisation d’une loi discrète μ =
a∈E μ(a)δ a où E est fini ou dénombrable. Nous pouvons numéroter les éléments de E avec une bijection ϕ : E → {1, 2, . . .}. Soit a k := ϕ
−1 (k).
Si on partitionne l’intervalle réel [0, 1] en blocs de mesures de Lebesgue respectives μ(a 1 ), μ(a 2 ), etc, par exemple en utilisant les intervalles
I 1 = [0, μ(a 1 )[ , I 2 = [μ(a 1 ), μ(a 1 ) + μ(a 2 )[ , . . . ,
et si U est une variable aléatoire de loi uniforme sur l’intervalle [0, 1], alors
P(U ∈ I ϕ(a) ) = μ(a) pour tout a ∈ E. L’algorithme basique de simulation de
μ est alors le suivant : on génère une réalisation u de U , ensuite si u μ(a 1 )
alors on décide a 1 ; sinon, si u μ(a 1 ) + μ(a 2 ), alors on décide a 2 , etc. Si F
est la fonction de répartition de la loi μ ◦ ϕ
−1 sur {1, 2, . . .} ⊂ R, d’inverse
généralisé F
−1 , alors (ϕ
−1
◦ F
−1 )(U ) ∼ μ. Il s’agit d’un cas spécial de la
méthode de simulation par inversion. Le coût de cet algorithme est le nombre
N de tests utilisés. Ce nombre est aléatoire, de loi μ ◦ ϕ
−1 . En particulier,
P(N < ∞) = 1, et le coût moyen est
57
© Springer-Verlag Berlin Heidelberg 2016
D. Chafaï and F. Malrieu, Recueil de Modèles Aléatoires,
Mathématiques et Applications 78, DOI 10.1007/978-3-662-49768-5_4
Permutations, partitions, et graphes
Mots-clés. Loi uniforme ; simulation ; permutation ; partition ; graphe ;
arbre ; nombres de Catalan ; nombres de Bell.
Outils. Groupe symétrique ; marche aléatoire ; loi discrète.
Difficulté. *
Ce chapitre présente des algorithmes de simulation de loi uniforme sur
quelques ensembles remarquables de permutations, partitions, et graphes. La
portée des concepts et techniques abordés dépasse le cadre considéré, qui a le
mérite d’être élémentaire.
4.1 Algorithme basique pour les lois discrètes
Considérons le problème de la simulation d’une réalisation d’une loi discrète μ =
a∈E μ(a)δ a où E est fini ou dénombrable. Nous pouvons numéroter les éléments de E avec une bijection ϕ : E → {1, 2, . . .}. Soit a k := ϕ
−1 (k).
Si on partitionne l’intervalle réel [0, 1] en blocs de mesures de Lebesgue respectives μ(a 1 ), μ(a 2 ), etc, par exemple en utilisant les intervalles
I 1 = [0, μ(a 1 )[ , I 2 = [μ(a 1 ), μ(a 1 ) + μ(a 2 )[ , . . . ,
et si U est une variable aléatoire de loi uniforme sur l’intervalle [0, 1], alors
P(U ∈ I ϕ(a) ) = μ(a) pour tout a ∈ E. L’algorithme basique de simulation de
μ est alors le suivant : on génère une réalisation u de U , ensuite si u μ(a 1 )
alors on décide a 1 ; sinon, si u μ(a 1 ) + μ(a 2 ), alors on décide a 2 , etc. Si F
est la fonction de répartition de la loi μ ◦ ϕ
−1 sur {1, 2, . . .} ⊂ R, d’inverse
généralisé F
−1 , alors (ϕ
−1
◦ F
−1 )(U ) ∼ μ. Il s’agit d’un cas spécial de la
méthode de simulation par inversion. Le coût de cet algorithme est le nombre
N de tests utilisés. Ce nombre est aléatoire, de loi μ ◦ ϕ
−1 . En particulier,
P(N < ∞) = 1, et le coût moyen est
57
© Springer-Verlag Berlin Heidelberg 2016
D. Chafaï and F. Malrieu, Recueil de Modèles Aléatoires,
Mathématiques et Applications 78, DOI 10.1007/978-3-662-49768-5_4