6.1 Analyses de la longueur de cheminement et du profil
233
Le profil renseigne sur l’« allure » d’un abr (qui est visible sur la figure 6.3) : le
comportement asymptotique est concentré sur les niveaux k proportionnels à log n,
ce qui est indiqué par
k
2 log n dans la limite M ∞ .
6.1.3 Méthode de contraction
Par le théorème 6.11 de la section précédente, nous avons obtenu la convergence
presque sûre de la longueur de cheminement d’un abr, renormalisée :
Y n :=
1
n + 1
(lce(τ n ) − E (lce(τ n )))
(6.11)
vers une variable aléatoire Y . Comme souvent, le fait d’obtenir Y comme limite de
martingale ne renseigne pas sur sa loi. Dans cette section, des renseignements sur
la loi de Y sont obtenus par la méthode dite de contraction. Cette méthode repose
sur le principe « diviser pour régner » et sur le théorème de point fixe de Banach
appliqué dans un bon espace métrique.
Dans de nombreuses situations [192, 224, 225], la méthode de contraction sert
à la fois à démontrer la convergence d’une suite de variables aléatoires (Y n ) et à
caractériser sa limite. Dans la suite de cette section, nous supposons ne pas connaître
le résultat de convergence du théorème 6.11, afin d’exposer les étapes successives
de la méthode (comme dans Drmota [68, chap. 8]). Lorsque la convergence a été
obtenue par une autre méthode, la caractérisation de la limite se réduit à l’étape 3.
Repartons de Y n défini par l’équation (6.11) pour exposer les étapes de la
méthode. Comme souvent, pour une variable aléatoire X, nous écrirons parfois par
abus de langage X au lieu de L(X) pour désigner la loi de X. Et pour deux variables
aléatoires X et Y , nous écrivons X
L
= Y pour dire que X et Y ont même loi.
Etape 1. Soit v(τ n ) une fonction d’un arbre τ n de taille n. Pour tout n, supposons
que v(τ n ) vérifie une équation de récurrence grâce au principe « diviser pour
régner ». Il existe alors une renormalisation du type Y n =
v(τ n ) − a n
b n
qui vérifie
une autre relation de récurrence.
Etape 2. En passant à la limite sur les coefficients de cette dernière équation,
l’équation qui serait satisfaite par une limite se déduit. Elle s’écrit sous la forme
d’une équation de point fixe Y = S(Y ), où S est une transformation.
Etape 3. La transformation S : F −→ S(F ) est un opérateur de (M, d) dans
(M, d) où M est un espace de mesures de probabilités dans lequel se trouvent
les lois de Y n et où d est une distance qui rend cet espace métrique et complet
(c’est-à-dire de Banach).
233
Le profil renseigne sur l’« allure » d’un abr (qui est visible sur la figure 6.3) : le
comportement asymptotique est concentré sur les niveaux k proportionnels à log n,
ce qui est indiqué par
k
2 log n dans la limite M ∞ .
6.1.3 Méthode de contraction
Par le théorème 6.11 de la section précédente, nous avons obtenu la convergence
presque sûre de la longueur de cheminement d’un abr, renormalisée :
Y n :=
1
n + 1
(lce(τ n ) − E (lce(τ n )))
(6.11)
vers une variable aléatoire Y . Comme souvent, le fait d’obtenir Y comme limite de
martingale ne renseigne pas sur sa loi. Dans cette section, des renseignements sur
la loi de Y sont obtenus par la méthode dite de contraction. Cette méthode repose
sur le principe « diviser pour régner » et sur le théorème de point fixe de Banach
appliqué dans un bon espace métrique.
Dans de nombreuses situations [192, 224, 225], la méthode de contraction sert
à la fois à démontrer la convergence d’une suite de variables aléatoires (Y n ) et à
caractériser sa limite. Dans la suite de cette section, nous supposons ne pas connaître
le résultat de convergence du théorème 6.11, afin d’exposer les étapes successives
de la méthode (comme dans Drmota [68, chap. 8]). Lorsque la convergence a été
obtenue par une autre méthode, la caractérisation de la limite se réduit à l’étape 3.
Repartons de Y n défini par l’équation (6.11) pour exposer les étapes de la
méthode. Comme souvent, pour une variable aléatoire X, nous écrirons parfois par
abus de langage X au lieu de L(X) pour désigner la loi de X. Et pour deux variables
aléatoires X et Y , nous écrivons X
L
= Y pour dire que X et Y ont même loi.
Etape 1. Soit v(τ n ) une fonction d’un arbre τ n de taille n. Pour tout n, supposons
que v(τ n ) vérifie une équation de récurrence grâce au principe « diviser pour
régner ». Il existe alors une renormalisation du type Y n =
v(τ n ) − a n
b n
qui vérifie
une autre relation de récurrence.
Etape 2. En passant à la limite sur les coefficients de cette dernière équation,
l’équation qui serait satisfaite par une limite se déduit. Elle s’écrit sous la forme
d’une équation de point fixe Y = S(Y ), où S est une transformation.
Etape 3. La transformation S : F −→ S(F ) est un opérateur de (M, d) dans
(M, d) où M est un espace de mesures de probabilités dans lequel se trouvent
les lois de Y n et où d est une distance qui rend cet espace métrique et complet
(c’est-à-dire de Banach).