5.2 Modèle de Catalan et arbres de Galton-Watson
203
de taille n + 1 sous le modèle de Catalan peut être vu aussi comme une marche
aléatoire simple (même probabilité 1/2 de monter ou de descendre) de longueur 2n,
conditionnée à rester positive et à revenir en 0.
Le théorème de Donsker (1951) établit qu’une marche aléatoire (S n ) n
à incréments i.i.d. de moyenne nulle et de variance finie σ 2 , une fois
renormalisée pour obtenir une fonction s n continue sur [0, 1]
s n (t) =
S nt + {nt}
S nt +1 − S nt
σ
√
n
(5.11)
converge en distribution et en processus vers un mouvement brownien 10
(rappelons que la notation {nt} désigne la partie fractionnaire de nt) :
(s n (t), 0 ≤ t ≤ 1)
D
−→
n→∞
(B t , 0 ≤ t ≤ 1).
Dans la même veine, le résultat suivant établit la convergence en distribution
d’un chemin de Dyck de longueur 2n renormalisé vers une excursion brownienne. Une définition possible de l’excursion brownienne (e t ) sur [0, 1] est : un
mouvement brownien standard entre deux zéros, renormalisé et rendu positif
sur [0, 1]. Si c n est la renormalisation analogue à (5.11) de la fonction de
contour C n , alors
(c n (t), 0 ≤ t ≤ 1)
D
−→
n→∞
(2e t , 0 ≤ t ≤ 1).
Une conséquence immédiate de (a) est alors que pour un arbre de taille n sous
le modèle de Catalan,
h(τ n )
√
n
loi
−→
n→∞
2
σ
max
0≤t ≤1
e t .
10 Un mouvement brownien (B t ) t≥0 est un processus aléatoire à temps continu, qui peut être défini
comme la limite d’une marche aléatoire renormalisée (!) ou bien plus classiquement comme un
processus à accroissements indépendants, de lois gaussiennes, tel que pour tous instants 0 ≤ s < t,
B t − B s est de loi gaussienne centrée de variance t − s. Voir par exemple le livre de Revuz et
Yor [221].
203
de taille n + 1 sous le modèle de Catalan peut être vu aussi comme une marche
aléatoire simple (même probabilité 1/2 de monter ou de descendre) de longueur 2n,
conditionnée à rester positive et à revenir en 0.
Le théorème de Donsker (1951) établit qu’une marche aléatoire (S n ) n
à incréments i.i.d. de moyenne nulle et de variance finie σ 2 , une fois
renormalisée pour obtenir une fonction s n continue sur [0, 1]
s n (t) =
S nt + {nt}
S nt +1 − S nt
σ
√
n
(5.11)
converge en distribution et en processus vers un mouvement brownien 10
(rappelons que la notation {nt} désigne la partie fractionnaire de nt) :
(s n (t), 0 ≤ t ≤ 1)
D
−→
n→∞
(B t , 0 ≤ t ≤ 1).
Dans la même veine, le résultat suivant établit la convergence en distribution
d’un chemin de Dyck de longueur 2n renormalisé vers une excursion brownienne. Une définition possible de l’excursion brownienne (e t ) sur [0, 1] est : un
mouvement brownien standard entre deux zéros, renormalisé et rendu positif
sur [0, 1]. Si c n est la renormalisation analogue à (5.11) de la fonction de
contour C n , alors
(c n (t), 0 ≤ t ≤ 1)
D
−→
n→∞
(2e t , 0 ≤ t ≤ 1).
Une conséquence immédiate de (a) est alors que pour un arbre de taille n sous
le modèle de Catalan,
h(τ n )
√
n
loi
−→
n→∞
2
σ
max
0≤t ≤1
e t .
10 Un mouvement brownien (B t ) t≥0 est un processus aléatoire à temps continu, qui peut être défini
comme la limite d’une marche aléatoire renormalisée (!) ou bien plus classiquement comme un
processus à accroissements indépendants, de lois gaussiennes, tel que pour tous instants 0 ≤ s < t,
B t − B s est de loi gaussienne centrée de variance t − s. Voir par exemple le livre de Revuz et
Yor [221].