52
2 Aléa sur les arbres
Remarque 2.11 La forme de l’abr construit avec des marques i.i.d., sous la loi Ord,
est exactement l’arbre bourgeonnant.
Description en termes de processus d’arbres
La description précédente à n fixé permet de considérer maintenant la suite d’arbres
(τ n ) n≥1 , c’est-à-dire un processus d’arbres.
À chaque suite i.i.d. (x n ) n≥1 de loi uniforme sur [0, 1] correspond une suite
croissante d’arbres (τ n ) n≥1 , croissante au sens où pour tout n ≥ 1, τ n est contenu
dans τ n+1 . De plus, la suite des réordonnements (σ n ) n≥1 est compatible, ce qui
signifie que pour tout n ≥ 1, la permutation σ n+1 (représentée canoniquement par
un (n + 1)-uplet) privée de l’entier n + 1 est égale à σ n . Dans l’exemple de la
figure 2.6, pour n = 7, nous avons σ n+1 = (6, 2, 4, 7, 1, 3, 8, 5) qui est compatible
avec σ n = (6, 2, 4, 7, 1, 3, 5).
Soit P n la loi induite sur les arbres binaires complets de taille n par x 1 , . . . , x n
i.i.d. de loi uniforme sur [0, 1]. Alors
• la suite (τ n ) n≥1 est une suite croissante d’arbres binaires complets où pour chaque
n, τ n est de loi P n ;
• la suite des réordonnements (σ n ) n≥1 est compatible, et pour chaque n, σ n est de
loi uniforme sur S n ; par conséquent la suite des (σ −1
n ) n≥1 est aussi telle que
pour chaque n, σ −1
n est de loi uniforme sur S n .
Ainsi, les P n pour n ≥ 1 sont compatibles 3 et le théorème de Kolmogorov
s’applique (voir Billingsley [28]), de sorte que les P n pour n ≥ 1 permettent de
définir une probabilité P sur l’ensemble B des arbres binaires complets en disant que
P restreinte aux arbres binaires complets de taille n est égale à P n . Nous travaillons
désormais sous P.
Remarque 2.12 Dans ce modèle des permutations uniformes, l’uniformité est sur
S n , le groupe des permutations, et non sur l’ensemble des arbres ; ce qui signifie que
les abr de taille n ne sont pas équiprobables. A l’inverse, dans le modèle uniforme
appelé aussi modèle de Catalan ou modèle combinatoire, les arbres binaires de
taille n sont équiprobables. Voir la figure 2.7.
Principe « diviser pour régner »
La proposition suivante est une instance du principe « diviser pour régner » dans le
cas particulier des abr.
3 ce qui signifie que P n+1 restreinte aux arbres binaires de taille n est égale à P n .
2 Aléa sur les arbres
Remarque 2.11 La forme de l’abr construit avec des marques i.i.d., sous la loi Ord,
est exactement l’arbre bourgeonnant.
Description en termes de processus d’arbres
La description précédente à n fixé permet de considérer maintenant la suite d’arbres
(τ n ) n≥1 , c’est-à-dire un processus d’arbres.
À chaque suite i.i.d. (x n ) n≥1 de loi uniforme sur [0, 1] correspond une suite
croissante d’arbres (τ n ) n≥1 , croissante au sens où pour tout n ≥ 1, τ n est contenu
dans τ n+1 . De plus, la suite des réordonnements (σ n ) n≥1 est compatible, ce qui
signifie que pour tout n ≥ 1, la permutation σ n+1 (représentée canoniquement par
un (n + 1)-uplet) privée de l’entier n + 1 est égale à σ n . Dans l’exemple de la
figure 2.6, pour n = 7, nous avons σ n+1 = (6, 2, 4, 7, 1, 3, 8, 5) qui est compatible
avec σ n = (6, 2, 4, 7, 1, 3, 5).
Soit P n la loi induite sur les arbres binaires complets de taille n par x 1 , . . . , x n
i.i.d. de loi uniforme sur [0, 1]. Alors
• la suite (τ n ) n≥1 est une suite croissante d’arbres binaires complets où pour chaque
n, τ n est de loi P n ;
• la suite des réordonnements (σ n ) n≥1 est compatible, et pour chaque n, σ n est de
loi uniforme sur S n ; par conséquent la suite des (σ −1
n ) n≥1 est aussi telle que
pour chaque n, σ −1
n est de loi uniforme sur S n .
Ainsi, les P n pour n ≥ 1 sont compatibles 3 et le théorème de Kolmogorov
s’applique (voir Billingsley [28]), de sorte que les P n pour n ≥ 1 permettent de
définir une probabilité P sur l’ensemble B des arbres binaires complets en disant que
P restreinte aux arbres binaires complets de taille n est égale à P n . Nous travaillons
désormais sous P.
Remarque 2.12 Dans ce modèle des permutations uniformes, l’uniformité est sur
S n , le groupe des permutations, et non sur l’ensemble des arbres ; ce qui signifie que
les abr de taille n ne sont pas équiprobables. A l’inverse, dans le modèle uniforme
appelé aussi modèle de Catalan ou modèle combinatoire, les arbres binaires de
taille n sont équiprobables. Voir la figure 2.7.
Principe « diviser pour régner »
La proposition suivante est une instance du principe « diviser pour régner » dans le
cas particulier des abr.
3 ce qui signifie que P n+1 restreinte aux arbres binaires de taille n est égale à P n .