15.3 Marche aléatoire renforcée
207
n
0
100
200
300
0.0
0.5
1.0
San/n
Marches renforcées géométriquement.
Fig. 15.3. Occupation d’un chemin pour la marche renforcée géométriquement.
par une variable aléatoire X n à valeur dans {α, β} le chemin emprunté lors
du n-ième passage. On code par des v.a. A n et B n l’attractivité des chemins
α et β au moment du (n + 1)
e passage : pour les humains, il peut s’agir par
exemple de la raréfaction de l’herbe, tandis que pour les fourmis, il peut s’agir
de la quantité de phéromone. On se donne (A 0 , B 0 ), ainsi qu’une fonction
r : ]0, ∞[→ ]0, ∞[ appelée fonction de renforcement telle que r(x) x pour
tout x > 0, et on modélise (X n ) n1 par
(X n+1 , A n+1 , B n+1 ) =
(α, r(A n ), B n ) si U n+1
An
An+Bn ;
(β, A n , r(B n )) si U n+1 >
An
An+Bn ,
où (U n ) n1 est une suite de variables aléatoires indépendantes et identiquement distribuées de loi uniforme sur [0, 1]. La suite récurrente aléatoire
((X n , A n , B n )) n0 est une chaîne de Markov (la valeur de X 0 ne joue aucun
rôle dans la récurrence). Lorsque A 0 , B 0 , et r prennent des valeurs entières,
tout se passe comme si nous avions une urne contenant, à tout instant n, A n
boules argentées et B n boules blanches : on tire une boule au hasard dans
cette urne, puis on introduit dans l’urne r(A n ) boules de la même couleur, de
sorte qu’on obtient le cas des tirages sans remise si r(x) = x, l’urne de Pólya
si r(x) = x + 1, et une sorte d’urne de Pólya non-linéaire dans le cas général.
La suite (X n ) n1 constitue une marche aléatoire non markovienne sur
l’ensemble à deux points {α, β}. Ses transitions dépendent les unes des autres
via le mécanisme de renforcement lié au temps passé sur chaque site. On parle