250
6 Arbres binaires de recherche
Fig. 6.9 Une représentation d’un arbre de Yule. Les longueurs des branches horizontales n’ont
pas de signification
Appelons N(t) l’ensemble des individus en vie à l’instant t et N t le cardinal de
cet ensemble (c’est une variable aléatoire), qui est le nombre d’individus en vie à
l’instant t. Appelons T 0 = 0 < T 1 < T 2 < . . . , les variables aléatoires qui sont les
instants successifs de saut :
T n := inf{t, N t = n + 1},
et de façon duale :
N t = 1 + sup{n ∈ N, T n ≤ t}.
En considérant le processus de Yule pris aux instants T n , nous pouvons reconnaître
le processus de forme d’abr, c’est-à-dire le processus d’arbres bourgeonnants : la
loi exponentielle nous assure en effet que l’horloge qui sonne en premier parmi n
horloges est choisie uniformément parmi ces n horloges. Autrement dit, pour passer
de τ
Yule
T n
, qui possède n + 1 feuilles, à τ
Yule
T n+1
, nous avons choisi une feuille au hasard
et l’avons transformée en un nœud interne et deux feuilles. Nous reconnaissons là
le processus des arbres bourgeonnants. La connexion s’écrit ainsi :
τ
Yule
T n
, n ≥ 0
L
= (τ n , n ≥ 0).
De façon duale, l’égalité des deux événements suivants, pour tout n ∈ N, pour tout
t ∈ R ≥0 :
{N t = n + 1} = {T n ≤ t < T n+1 },