46
2 Aléa sur les arbres
n-ième génération sont indépendants et de même loi que l’arbre τ . Autrement dit,
nous avons
E
⎛
⎝
u, |u|=n
f u (τ
u )
Fn
⎞
⎠ =
u, |u|=n
E(f u ),
(2.4)
où les f u , u ∈ U sont des fonctions mesurables positives et où F n est la tribu du
passé avant n, c’est-à-dire que F n est engendrée par les M u pour tous les u tels que
|u| ≤ n − 1 (voir l’annexe C).
Une étude plus détaillée des processus de Galton-Watson est faite dans la
section 5.1.
2.2 Aléa sur les arbres marqués
Dans cette section, les clés stockées dans l’arbre sont aléatoires, et l’arbre le devient
aussi. Deux classes d’arbres marqués aléatoires sont présentées, tout d’abord les tas
en section 2.2.2, puis les arbres binaires de recherche en section 2.2.3. Auparavant,
dans la section 2.2.1, nous précisons le modèle probabiliste utilisé.
2.2.1 Le modèle des permutations uniformes
Partant de « vraies » données x 1 , x 2 , . . . , x n , . . . appartenant à un ensemble
totalement ordonné, le modèle dit « des permutations uniformes » permet de
disposer d’un modèle probabiliste universel, à savoir la loi uniforme sur l’ensemble
S n des permutations de {1, . . . , n}, à l’issue d’une étape de modélisation.
Proposition-Définition 2.4 Soient x 1 , x 2 , . . . , x n , . . . une suite de variables aléatoires indépendantes et de même loi continue, à valeurs dans un ensemble totalement ordonné. Pour tout n ≥ 1, soit σ n ∈ S n le réordonnement de x 1 , . . . , x n , défini
en (1.5) par
x σ n (1) < x σ n (2) < · · · < x σ n (n) .
Alors σ n suit la loi uniforme sur S n .
Nous parlons de modèle des permutations uniformes lorsqu’un arbre τ est
marqué par des clés i.i.d. (indépendantes et identiquement distribuées) de même
loi continue. Sous ce modèle, les paramètres étudiés ont même loi pour τ et pour
l’arbre des rangs C(τ ) obtenu par marquage canonique (cf. la définition 1.16).
Preuve L’hypothèse de loi continue assure que les données sont presque sûrement
distinctes. L’hypothèse i.i.d. assure que les variables aléatoires sont échangeables, ce
2 Aléa sur les arbres
n-ième génération sont indépendants et de même loi que l’arbre τ . Autrement dit,
nous avons
E
⎛
⎝
u, |u|=n
f u (τ
u )
Fn
⎞
⎠ =
u, |u|=n
E(f u ),
(2.4)
où les f u , u ∈ U sont des fonctions mesurables positives et où F n est la tribu du
passé avant n, c’est-à-dire que F n est engendrée par les M u pour tous les u tels que
|u| ≤ n − 1 (voir l’annexe C).
Une étude plus détaillée des processus de Galton-Watson est faite dans la
section 5.1.
2.2 Aléa sur les arbres marqués
Dans cette section, les clés stockées dans l’arbre sont aléatoires, et l’arbre le devient
aussi. Deux classes d’arbres marqués aléatoires sont présentées, tout d’abord les tas
en section 2.2.2, puis les arbres binaires de recherche en section 2.2.3. Auparavant,
dans la section 2.2.1, nous précisons le modèle probabiliste utilisé.
2.2.1 Le modèle des permutations uniformes
Partant de « vraies » données x 1 , x 2 , . . . , x n , . . . appartenant à un ensemble
totalement ordonné, le modèle dit « des permutations uniformes » permet de
disposer d’un modèle probabiliste universel, à savoir la loi uniforme sur l’ensemble
S n des permutations de {1, . . . , n}, à l’issue d’une étape de modélisation.
Proposition-Définition 2.4 Soient x 1 , x 2 , . . . , x n , . . . une suite de variables aléatoires indépendantes et de même loi continue, à valeurs dans un ensemble totalement ordonné. Pour tout n ≥ 1, soit σ n ∈ S n le réordonnement de x 1 , . . . , x n , défini
en (1.5) par
x σ n (1) < x σ n (2) < · · · < x σ n (n) .
Alors σ n suit la loi uniforme sur S n .
Nous parlons de modèle des permutations uniformes lorsqu’un arbre τ est
marqué par des clés i.i.d. (indépendantes et identiquement distribuées) de même
loi continue. Sous ce modèle, les paramètres étudiés ont même loi pour τ et pour
l’arbre des rangs C(τ ) obtenu par marquage canonique (cf. la définition 1.16).
Preuve L’hypothèse de loi continue assure que les données sont presque sûrement
distinctes. L’hypothèse i.i.d. assure que les variables aléatoires sont échangeables, ce