182
13 Généalogies et coalescence
P(C
inc
k−1 = β | C
inc
k = α) =
1
(
k
2 )
si α ∼ β et |α| = k,
0
sinon.
Le processus C évolue donc selon une suite
Δ = C
inc
n ∼ C
inc
n−1 ∼ · · · ∼ C
inc
1 = Θ,
où Θ est la partition triviale et passe en la partition C
inc
k un temps exponentiel
de paramètre
k
2
. Les taux de transition ne dépendent de la partition qu’au
travers de son cardinal et
|C(t)| = A n (t),
puisque les classes de C(t) sont en bijection avec les ancêtres au temps t. Ainsi,
les processus (A n (t)) t0 et (C
inc
k ) k sont indépendants et pour tout t 0,
C(t) = C
inc
An(t) .
Plus précisément, on a
P(C(t) = α) = P(A n (t) = |α|)P(C
inc
|α| = α).
Théorème 13.6 (Loi du coalescent de Kingman). Soit 1 j n et α
une partition de [n] dont les classes d’équivalence admettent les cardinaux
λ 1 , . . . , λ j . Alors,
P(C
inc
j
= α) =
(n − j)!j!(j − 1)!
n!(n − 1)!
λ 1 ! · · · λ j !.
Démonstration. On procède par récurrence descendante. Le résultat est clair
pour j = n (si α n’est pas la partition Δ, sa probabilité d’apparition est nulle,
et Δ est la seule partition à n classes, toutes singleton). Supposons que le
résultat soit vrai pour j 2. Alors
p j−1 (β) := P(C
inc
j−1 = β)
=
α∈En
p j (α)P(C
inc
j−1 = β | C
inc
j
= α)
=
α∼β
p j (α)
2
j(j − 1)
.
Notons λ 1 , . . . , λ j−1 les tailles des classes d’équivalence de β. Celles de α sont
λ 1 , . . . , λ l−1 , m, λ l − m, λ l+1 , . . . , λ j−1
pour un certain 1 l j − 1 et 1 m λ l − 1. Posons
π l,m := λ 1 ! · · · λ l−1 !m!(λ l − m)!λ l+1 ! · · · λ j−1 !.