208
15 Renforcement
de marche aléatoire renforcée par sites. Le mécanisme de renforcement peut
également être vu comme une sorte d’algorithme stochastique.
Pour simplifier, on suppose que A 0 = B 0 = 1 (X 0 est inutile). Le nombre
de passages par le chemin α et par le chemin β à l’instant n sont donnés par
Y n =
n
k=1
1 {X k =α} et Z n =
n
k=1
1 {X k =β} .
On pose par commodité Y 0 = 0 et Z 0 = 0 de sorte que Y n + Z n = n pour tout
n ∈ N. Le théorème suivant précise le comportement de ces deux suites pour
trois cas de fonction de renforcement r.
Théorème 15.8 (Comportement asymptotique presque sûr quand n → ∞).
— Absence de renforcement. Si r(x) = x pour tout x > 0, alors presque
sûrement lim inf |Y n − Z n | = 0, et
Y n ∼
n
2
, Z n ∼
n
2
, lim sup
|Y n − Z n |
2n log(log(n))
= 1.
— Renforcement linéaire. Si r(x) = x + 1 pour tout x > 0 alors il existe
une variable aléatoire U uniforme sur [0, 1] telle que presque sûrement,
Y n
n
→ U et
Z n
n
→ 1 − U.
— Renforcement géométrique. Si r(x) = ρx pour tout x > 0 où ρ > 1
est une constante alors presque sûrement la suite aléatoire (X n ) n0 est
constante à partir d’un certain rang sur n, et sa valeur limite suit la
loi de Bernoulli symétrique sur {α, β}.
En l’absence de renforcement ou dans le cas du renforcement linéaire, la
fréquence d’emprunt de chacun des deux chemins converge au fil du temps
vers 1/2 dans le premier cas et vers un nombre aléatoire uniforme sur [0, 1]
dans le second. Intuitivement, un renforcement sur-linéaire pourrait forcer la
fréquence d’emprunt des chemins à converger vers les valeurs extrêmes 0 ou
1. Cela est confirmé pour le renforcement géométrique, pour lequel au bout
d’un certain temps, l’un des deux chemins est emprunté systématiquement.
Le modèle du renforcement linéaire coïncide avec l’urne de Pólya étudiée
précédemment. Le modèle du renforcement géométrique est particulièrement
attrayant, car il fait apparaître un chemin privilégié, choisi aléatoirement au
fil du renforcement. Il s’agit en quelque sorte d’une urne de Pólya généralisée
non-linéaire, plus précisément sur-linéaire. Le théorème 15.9 de Rubin ci-après
fournit un critère sur le renforcement pour que ce phénomène apparaisse.
Démonstration. On traite les trois cas séparément.
15 Renforcement
de marche aléatoire renforcée par sites. Le mécanisme de renforcement peut
également être vu comme une sorte d’algorithme stochastique.
Pour simplifier, on suppose que A 0 = B 0 = 1 (X 0 est inutile). Le nombre
de passages par le chemin α et par le chemin β à l’instant n sont donnés par
Y n =
n
k=1
1 {X k =α} et Z n =
n
k=1
1 {X k =β} .
On pose par commodité Y 0 = 0 et Z 0 = 0 de sorte que Y n + Z n = n pour tout
n ∈ N. Le théorème suivant précise le comportement de ces deux suites pour
trois cas de fonction de renforcement r.
Théorème 15.8 (Comportement asymptotique presque sûr quand n → ∞).
— Absence de renforcement. Si r(x) = x pour tout x > 0, alors presque
sûrement lim inf |Y n − Z n | = 0, et
Y n ∼
n
2
, Z n ∼
n
2
, lim sup
|Y n − Z n |
2n log(log(n))
= 1.
— Renforcement linéaire. Si r(x) = x + 1 pour tout x > 0 alors il existe
une variable aléatoire U uniforme sur [0, 1] telle que presque sûrement,
Y n
n
→ U et
Z n
n
→ 1 − U.
— Renforcement géométrique. Si r(x) = ρx pour tout x > 0 où ρ > 1
est une constante alors presque sûrement la suite aléatoire (X n ) n0 est
constante à partir d’un certain rang sur n, et sa valeur limite suit la
loi de Bernoulli symétrique sur {α, β}.
En l’absence de renforcement ou dans le cas du renforcement linéaire, la
fréquence d’emprunt de chacun des deux chemins converge au fil du temps
vers 1/2 dans le premier cas et vers un nombre aléatoire uniforme sur [0, 1]
dans le second. Intuitivement, un renforcement sur-linéaire pourrait forcer la
fréquence d’emprunt des chemins à converger vers les valeurs extrêmes 0 ou
1. Cela est confirmé pour le renforcement géométrique, pour lequel au bout
d’un certain temps, l’un des deux chemins est emprunté systématiquement.
Le modèle du renforcement linéaire coïncide avec l’urne de Pólya étudiée
précédemment. Le modèle du renforcement géométrique est particulièrement
attrayant, car il fait apparaître un chemin privilégié, choisi aléatoirement au
fil du renforcement. Il s’agit en quelque sorte d’une urne de Pólya généralisée
non-linéaire, plus précisément sur-linéaire. Le théorème 15.9 de Rubin ci-après
fournit un critère sur le renforcement pour que ce phénomène apparaisse.
Démonstration. On traite les trois cas séparément.