3.3 Taille de l’arbre en régimes critique et sous-critique
51
1
2
6 7
3
4
8
9
11
12
10
5
n
Sn
1 2 3 4 5 6 7 8 9 10 11 12
-1
0
1
2
3
4
5
Fig. 3.2. Arbre et marche aléatoire associée.
La figure 3.2 donne un exemple d’association. Le mode de numérotation étant
fixé, l’arbre se reconstruit aisément à partir de la trajectoire de S. La suite
(S i ) 0in a la loi d’une marche aléatoire d’accroissement (U i ) i1 issue de
0 arrêtée au temps d’atteinte T −1 de −1. Comme les accroissements sont de
moyenne négative m−1 et que les sauts négatifs de la marche sont d’amplitude
1, ce temps est fini presque sûrement. Cette bijection fournit l’égalité en loi
N
loi
= T −1 . Enfin, la loi de T −1 est fournie par le lemme 3.18.
Lemme 3.18 (Principe de rotation). Soit (S n ) n0 une marche aléatoire issue
de 0 d’incréments (U n ) n1 i.i.d. à valeurs entières, et
T −1 := inf{n 1 : S n = −1}.
Alors pour tout n 1,
P(T −1 = n) =
1
n
P(S n = −1).
Démonstration du lemme 3.18. Soit n 1 et U 1 , . . . , U n tels que S n = −1.
Pour tout entier k, notons σ(k) l’entier compris entre 1 et n égal à k modulo
n. Pour tout l = 1, . . . , n, on définit S
(l) par
S
(l)
0 = 0 et S
(l)
k+1 = S
(l)
k + U σ(k+1+l) .
Remarquons que pour tout l = 1, . . . , n, S
(l)
n = S n = −1 et que les trajectoires
S
(n) et S coïncident. La figure 3.3 fournit un exemple avec n = 8.
La trajectoire S atteint son minimum en un ou plusieurs instants. Notons
l 0 le plus petit d’entre eux (dans l’exemple de la figure 3.3, l 0 = 4). Alors S
(l0)
est la seule trajectoires parmi S
(1) , . . . , S
(n) qui reste positive ou nulle jusqu’à
l’instant n − 1. On a donc bien le résultat attendu.
51
1
2
6 7
3
4
8
9
11
12
10
5
n
Sn
1 2 3 4 5 6 7 8 9 10 11 12
-1
0
1
2
3
4
5
Fig. 3.2. Arbre et marche aléatoire associée.
La figure 3.2 donne un exemple d’association. Le mode de numérotation étant
fixé, l’arbre se reconstruit aisément à partir de la trajectoire de S. La suite
(S i ) 0in a la loi d’une marche aléatoire d’accroissement (U i ) i1 issue de
0 arrêtée au temps d’atteinte T −1 de −1. Comme les accroissements sont de
moyenne négative m−1 et que les sauts négatifs de la marche sont d’amplitude
1, ce temps est fini presque sûrement. Cette bijection fournit l’égalité en loi
N
loi
= T −1 . Enfin, la loi de T −1 est fournie par le lemme 3.18.
Lemme 3.18 (Principe de rotation). Soit (S n ) n0 une marche aléatoire issue
de 0 d’incréments (U n ) n1 i.i.d. à valeurs entières, et
T −1 := inf{n 1 : S n = −1}.
Alors pour tout n 1,
P(T −1 = n) =
1
n
P(S n = −1).
Démonstration du lemme 3.18. Soit n 1 et U 1 , . . . , U n tels que S n = −1.
Pour tout entier k, notons σ(k) l’entier compris entre 1 et n égal à k modulo
n. Pour tout l = 1, . . . , n, on définit S
(l) par
S
(l)
0 = 0 et S
(l)
k+1 = S
(l)
k + U σ(k+1+l) .
Remarquons que pour tout l = 1, . . . , n, S
(l)
n = S n = −1 et que les trajectoires
S
(n) et S coïncident. La figure 3.3 fournit un exemple avec n = 8.
La trajectoire S atteint son minimum en un ou plusieurs instants. Notons
l 0 le plus petit d’entre eux (dans l’exemple de la figure 3.3, l 0 = 4). Alors S
(l0)
est la seule trajectoires parmi S
(1) , . . . , S
(n) qui reste positive ou nulle jusqu’à
l’instant n − 1. On a donc bien le résultat attendu.