58
4 Permutations, partitions, et graphes
E(N ) =
a∈E
ϕ(a)μ(a),
qui peut très bien être infini si μ◦ϕ
−1 n’a pas d’espérance (ne peut se produire
que si E est infini) ! Si la numérotation ϕ minimise le coût moyen E(N ) alors
μ(a 1 ) μ(a 2 ) · · · .
Pour la loi géométrique (de moyenne quelconque) et pour la loi de Poisson
(de moyenne 1), la numérotation naturelle est à poids décroissants. D’autre
part, si card(E) est petit, alors on peut déterminer l’ordre à poids décroissants
en utilisant un algorithme de tri (qui a un coût).
Les lois discrètes usuelles (binomiale, géométrique, Poisson, etc.) sont simulables par divers algorithmes dédiés tirant partie de leurs propriétés spéciales. À ce sujet, signalons qu’il est possible de simuler la loi de Poisson
de moyenne quelconque λ à partir d’un générateur de la loi de Poisson de
moyenne 1. Il suffit en effet d’utiliser un amincissement
1 . Plus précisément,
on simule λ variables aléatoires X 1 , . . . , X λ i.i.d. de loi Poi(1), puis, conditionnellement à leur somme S = X 1 + · · · + X λ , on simule S variables
aléatoires i.i.d. de loi de Bernoulli de moyenne λ/λ, et on tire parti du fait
que B 1 + · · · + B S ∼ Poi(λ) (mélange poissonnien de binomiales
2 ).
Simuler la loi uniforme sur un ensemble E fini peut être très simple :
ϕ
−1 (card(E)U ) suit cette loi ! Cependant, cet algorithme basique est impraticable lorsque E est difficile à énumérer et donc ϕ est difficile d’accès, ou
lorsque card(E) est très grand. Nous étudions par la suite des exemples de ce
type faits de permutations, de partitions, et de graphes, pour lesquels nous
présentons des algorithmes spécifiques efficaces et exacts.
4.2 Permutations aléatoires
Certaines situations nécessitent de permuter aléatoirement une liste finie
d’objets : construction de plans d’expérience dans les sciences expérimentales, anonymisation, etc. Cela conduit au problème de la simulation de la
loi uniforme
σ∈Sn card(S n )
−1 δ σ sur l’ensemble fini S n des permutations
de {1, . . . , n} (groupe symétrique). Or card(S n ) = n! ∼
√
2πn(n/e)
n est un
nombre à environ n log(n) chiffres, et cette réalité combinatoire disqualifie
très vite l’algorithme basique de simulation des lois discrètes. Il est possible
de simuler la loi uniforme sur S n en réordonnant un désordre symétrique : si
U 1 , . . . , U n sont des variables aléatoires i.i.d. de loi uniforme sur [0, 1] et si σ
est une permutation aléatoire telle que U σ(1) · · · U σ(n) , alors σ suit la loi
uniforme sur S n . La complexité est celle de l’algorithme de tri utilisé
3 .
1. «Thinning» en anglais.
2. Si X ∼ Poi(λ) et Loi(Y |X = n) = Bin(n, p) pour tout n alors Y ∼ Poi(pλ).
3. De l’ordre de n log(n) avec grande probabilité et n
2 au pire pour l’algorithme
de tri rapide («quick sort» en anglais).
4 Permutations, partitions, et graphes
E(N ) =
a∈E
ϕ(a)μ(a),
qui peut très bien être infini si μ◦ϕ
−1 n’a pas d’espérance (ne peut se produire
que si E est infini) ! Si la numérotation ϕ minimise le coût moyen E(N ) alors
μ(a 1 ) μ(a 2 ) · · · .
Pour la loi géométrique (de moyenne quelconque) et pour la loi de Poisson
(de moyenne 1), la numérotation naturelle est à poids décroissants. D’autre
part, si card(E) est petit, alors on peut déterminer l’ordre à poids décroissants
en utilisant un algorithme de tri (qui a un coût).
Les lois discrètes usuelles (binomiale, géométrique, Poisson, etc.) sont simulables par divers algorithmes dédiés tirant partie de leurs propriétés spéciales. À ce sujet, signalons qu’il est possible de simuler la loi de Poisson
de moyenne quelconque λ à partir d’un générateur de la loi de Poisson de
moyenne 1. Il suffit en effet d’utiliser un amincissement
1 . Plus précisément,
on simule λ variables aléatoires X 1 , . . . , X λ i.i.d. de loi Poi(1), puis, conditionnellement à leur somme S = X 1 + · · · + X λ , on simule S variables
aléatoires i.i.d. de loi de Bernoulli de moyenne λ/λ, et on tire parti du fait
que B 1 + · · · + B S ∼ Poi(λ) (mélange poissonnien de binomiales
2 ).
Simuler la loi uniforme sur un ensemble E fini peut être très simple :
ϕ
−1 (card(E)U ) suit cette loi ! Cependant, cet algorithme basique est impraticable lorsque E est difficile à énumérer et donc ϕ est difficile d’accès, ou
lorsque card(E) est très grand. Nous étudions par la suite des exemples de ce
type faits de permutations, de partitions, et de graphes, pour lesquels nous
présentons des algorithmes spécifiques efficaces et exacts.
4.2 Permutations aléatoires
Certaines situations nécessitent de permuter aléatoirement une liste finie
d’objets : construction de plans d’expérience dans les sciences expérimentales, anonymisation, etc. Cela conduit au problème de la simulation de la
loi uniforme
σ∈Sn card(S n )
−1 δ σ sur l’ensemble fini S n des permutations
de {1, . . . , n} (groupe symétrique). Or card(S n ) = n! ∼
√
2πn(n/e)
n est un
nombre à environ n log(n) chiffres, et cette réalité combinatoire disqualifie
très vite l’algorithme basique de simulation des lois discrètes. Il est possible
de simuler la loi uniforme sur S n en réordonnant un désordre symétrique : si
U 1 , . . . , U n sont des variables aléatoires i.i.d. de loi uniforme sur [0, 1] et si σ
est une permutation aléatoire telle que U σ(1) · · · U σ(n) , alors σ suit la loi
uniforme sur S n . La complexité est celle de l’algorithme de tri utilisé
3 .
1. «Thinning» en anglais.
2. Si X ∼ Poi(λ) et Loi(Y |X = n) = Bin(n, p) pour tout n alors Y ∼ Poi(pλ).
3. De l’ordre de n log(n) avec grande probabilité et n
2 au pire pour l’algorithme
de tri rapide («quick sort» en anglais).