15.3 Marche aléatoire renforcée
209
— Absence de renforcement. Dans ce cas (A n ) n0 et (B n ) n0 sont des
suites constantes et égales à 1. On retrouve les tirages avec remise, le
processus de Bernoulli (jeu de pile ou face). La suite (Y n ) n0 est un
processus de Bernoulli sur N issu de 0 dont les incréments sont de loi
de Bernoulli sur {0, 1} de paramètre A 0 /(A 0 + B 0 ) = 1/2. D’après
la loi forte des grands nombres, presque sûrement, Y n /n → 1/2 et
Z n /n = 1 − Y n /n → 1/2 quand n → ∞. La suite (Y n − Z n ) n0 est une
marche aléatoire sur Z issue de 0 dont les incréments sont de loi de
Rademacher sur {−1, 1} de paramètre 1/2. C’est une chaîne de Markov
irréductible récurrente : presque sûrement chaque état est visité une
infinité de fois, et en particulier l’état 0, d’où lim |Y n − Z n | = 0 p.s. Le
résultat sur lim provient de la loi du logarithme itéré de Strassen ;
— Renforcement linéaire. Dans ce cas A n = 1 + Y n et B n = 1 + Z n pour
tout n ∈ N. On retrouve l’urne de Pólya et le résultat attendu découle
alors directement du cas uniforme dans le théorème 15.2. Effectuons
malgré tout le raisonnement allégé avec les notations actuelles. La relation Y n + Z n = n réduit le problème à l’étude de Y n . Soit (F n ) n0 la
filtration définie par F n = σ(U 1 , . . . , U n ). On a
E(1 + Y n+1 | F n ) = 1 + Y n + E(1 {Xn+1=α} | F n )
= 1 + Y n + E(1 {Un+1
1+Yn
n+2 } | F n )
= 1 + Y n +
1 + Y n
n + 2
= (2 + (n + 1))
1 + Y n
2 + n
,
et donc ((1 + Y n )/(n + 2)) n0 est une martingale pour (F n ) n0 . À valeurs dans [0, 1], elle est uniformément bornée et converge donc presque
sûrement (et en moyenne) vers une variable aléatoire U à valeurs dans
[0, 1]. On montre enfin par récurrence sur n que (1 + Y n )/(n + 2) suit
la loi uniforme sur {1/(n + 2), . . . , (n + 1)/(n + 2)} ;
— Renforcement géométrique. Dans ce cas A n = ρ
Yn et B n = ρ
Zn pour
tout n ∈ N. La variable aléatoire Δ n := Y n − Z n vérifie Δ 0 = 0 et
Δ n+1 = Δ n + 1 {Un+11/(1+ρ −Δn )} − 1 {Un+1>1/(1+ρ −Δn )} .
Posons F n = σ(U 1 , . . . , U n ). Il en découle que
P(|Δ n+1 | = |Δ n | + 1 | F n ) =
ρ
|Δn|
1 + ρ |Δn| 1 {Δn =0} + 1 {Δn=0}
P(|Δ n+1 | = |Δ n | − 1 | F n ) =
1
1 + ρ |Δn| 1 {Δn =0} .
Si f : N → R vérifie f (1) f (0) et pour tout n 1,
ρ
n (f (n + 1) − f (n)) = f (n) − f (n − 1),
alors
209
— Absence de renforcement. Dans ce cas (A n ) n0 et (B n ) n0 sont des
suites constantes et égales à 1. On retrouve les tirages avec remise, le
processus de Bernoulli (jeu de pile ou face). La suite (Y n ) n0 est un
processus de Bernoulli sur N issu de 0 dont les incréments sont de loi
de Bernoulli sur {0, 1} de paramètre A 0 /(A 0 + B 0 ) = 1/2. D’après
la loi forte des grands nombres, presque sûrement, Y n /n → 1/2 et
Z n /n = 1 − Y n /n → 1/2 quand n → ∞. La suite (Y n − Z n ) n0 est une
marche aléatoire sur Z issue de 0 dont les incréments sont de loi de
Rademacher sur {−1, 1} de paramètre 1/2. C’est une chaîne de Markov
irréductible récurrente : presque sûrement chaque état est visité une
infinité de fois, et en particulier l’état 0, d’où lim |Y n − Z n | = 0 p.s. Le
résultat sur lim provient de la loi du logarithme itéré de Strassen ;
— Renforcement linéaire. Dans ce cas A n = 1 + Y n et B n = 1 + Z n pour
tout n ∈ N. On retrouve l’urne de Pólya et le résultat attendu découle
alors directement du cas uniforme dans le théorème 15.2. Effectuons
malgré tout le raisonnement allégé avec les notations actuelles. La relation Y n + Z n = n réduit le problème à l’étude de Y n . Soit (F n ) n0 la
filtration définie par F n = σ(U 1 , . . . , U n ). On a
E(1 + Y n+1 | F n ) = 1 + Y n + E(1 {Xn+1=α} | F n )
= 1 + Y n + E(1 {Un+1
1+Yn
n+2 } | F n )
= 1 + Y n +
1 + Y n
n + 2
= (2 + (n + 1))
1 + Y n
2 + n
,
et donc ((1 + Y n )/(n + 2)) n0 est une martingale pour (F n ) n0 . À valeurs dans [0, 1], elle est uniformément bornée et converge donc presque
sûrement (et en moyenne) vers une variable aléatoire U à valeurs dans
[0, 1]. On montre enfin par récurrence sur n que (1 + Y n )/(n + 2) suit
la loi uniforme sur {1/(n + 2), . . . , (n + 1)/(n + 2)} ;
— Renforcement géométrique. Dans ce cas A n = ρ
Yn et B n = ρ
Zn pour
tout n ∈ N. La variable aléatoire Δ n := Y n − Z n vérifie Δ 0 = 0 et
Δ n+1 = Δ n + 1 {Un+11/(1+ρ −Δn )} − 1 {Un+1>1/(1+ρ −Δn )} .
Posons F n = σ(U 1 , . . . , U n ). Il en découle que
P(|Δ n+1 | = |Δ n | + 1 | F n ) =
ρ
|Δn|
1 + ρ |Δn| 1 {Δn =0} + 1 {Δn=0}
P(|Δ n+1 | = |Δ n | − 1 | F n ) =
1
1 + ρ |Δn| 1 {Δn =0} .
Si f : N → R vérifie f (1) f (0) et pour tout n 1,
ρ
n (f (n + 1) − f (n)) = f (n) − f (n − 1),
alors