2 4
CHAPITRE 6. PROCESSUS D’ÉVOLUTION GÉNÉTIQUE
Preuve. La preuve consiste en une induction descendante sur . Quand = k, la seule
partition π possible est la partition composée des blocs singletons, et la probabilité de
réalisation de π est 1, ce qui est également donné par le membre de droite de (6.4.25)
pour = k.
Supposons que (6.4.25) soit vraie pour toute partition de taille et considérons une
partition η de taille − 1. Nous notons ξ < η si Card(ξ) = Card(η) + 1 et si la partition
η est obtenue après regroupement de deux blocs de ξ. Dans ce cas, il y a exactement un
événement de coalescence qui fait passer de ξ à η. On a alors
P(Π T k−+1 = η|Π T k− = ξ) =
2
(−1)
si ξ < η
0
sinon.
(6.4.28)
Nous avons donc
P(Π T k−+1 = η) =
2
( − 1)
ξ<η
P(Π T k− = ξ).
(6.4.29)
Etant donnée une partition ξ de {1, · · · , k} en blocs, nous ordonnons ses blocs en ξ 1 , ξ 2 ,
..., ξ , où ξ 1 est le bloc contenant 1, ξ 2 celui contenant le plus petit nombre qui n’est pas
dans ξ 1 ,...
Si les entiers λ 1 , . . . , λ −1 sont les tailles des blocs de la partition η, alors pour pour j
tel que 1 ≤ j ≤ − 1, et m tel que 1 ≤ m < λ j , nous associons une partition ξ < η,
où les blocs de ξ ont les tailles λ 1 , . . . , λ j−1 , m, λ j − m, λ j+1 , . . . , λ −1 . Remarquons qu’il
y a
1
2
λj
m
choix d’une telle partition ξ < η, où le j-ième bloc a été coupé en λ j − m et m
individus.
Utilisant l’hypothèse de récurrence, nous obtenons alors que
P(Π T k−+1 = η) =
2
( − 1)
−1
j=1
λj −1
m=1
1
2
λ j
m
c k,, λ 1 ! . . . λ j−1 ! m! (λ j − m)! λ j+1 ! . . . λ !
= w(η)
c k,,
( − 1)
−1
j=1
λj −1
m=1
1.
(6.4.30)
La double somme vaut
−1
j=1
(λ j − 1) = k − ( − 1).
Nous vérifions alors facilement que
c k,,
( − 1)
(k − + 1) = c k,,−1 .
Le résultat est donc prouvé par induction.
2