MAP432 : 1/4h Python

L'objectif des 1/4h python est d'illustrer par la simulation certains aspects du cours. Toutes les fenêtres de code peuvent (et doivent!) être exécutées en cliquant sur Evaluate. N'hésitez pas à éditer le code pour modifier les paramètres.

Marche aléatoire renforcée

Nous allons étudier un modèle aléatoire non-markovien le plus simple possible : la marche aléatoire renforcée à 2 états. Ce modèle est à la base d'un algorithme d'apprentissage par renforcement appelé algorithme du bandit¹. Il a été également été proposé pour modéliser l'exploration d'un milieu par des insectes sociaux².

La fourmi va emprunter le chemin $A$ avec probabilité $\frac{r(3)}{r(1)+r(3)}$ .

Soit

$r:\mathbb{N}\to (0,+\infty)$ une fonction telle que

$r(x)\geq x$ pour tout

$x$ ,

$r$ est appelée la fonction de renforcement.
On considère la suite de variables aléatoires

$(X_k)_{k\geq 1}$ à valeurs dans

$\{A,B\}$ définie de la façon suivante. Pour

$k\geq 1$ ,

$S^A_k$ désigne le nombre de passages en

$A$ :

$S^A_0=0,\qquad S^A_k=\sum_{i=1}^k \mathbf{1}_{X_i=A} \in\{0,1,\dots,k\}.$

L'évolution est alors définie par :

$\mathbb{P}(X_{k+1}=A|X_1,\dots,X_k)= \frac{r(S_k)}{r(S_k)+r(k-S_k)}.$

Plus la fonction

$r$ a de grandes variations, plus la marche est renforcée : la fourmi a une grande tendance à emprunter le chemin majoritaire jusque-là. On cherche à évaluer l'influence de la fonction

$r$ sur le renforcement. Nous allons tracer l'évolution de la proportion

$\frac{S^A_k}{k}$ .

1. Renforcement linéaire

On trace

$K$ trajectoires de

$\frac{S^A_n}{n}$ pour

$r$ de la forme

$r(x)=a+x$ .

xxxxxxxxxx
 
import numpy as np
import matplotlib.pyplot as plt
​
K=20        # Nombre de trajectoires
N=2000      # Durée de chaque simulation
​
def renforcement(x):    
    return 1+x      # renforcement linéaire
​
for k in range(K):
    PassagesenA=[]  # True = on passe en "A"
    NbPassagesenA=0
    for n in range(N): 
      biais = (renforcement(NbPassagesenA)+0.0)/(renforcement(NbPassagesenA)+renforcement(n-NbPassagesenA))
      OnPasseEnA=np.random.rand()<biais  # Passage en A aléatoire, suivant le biais
      PassagesenA.append(OnPasseEnA)
      NbPassagesenA=NbPassagesenA+OnPasseEnA
    plt.plot((np.cumsum(PassagesenA)+0.0)/np.array(range(1,N+1)))
​
plt.title('Trajectoires de $(S_n/n)$ pour un renforcement lineaire')
plt.axis([0,N,0,1])
plt.show()

On démontre dans la PC 7 que, pour ce choix de renforcement

$r$ ,

$\frac{S^A_n}{n}$ converge presque-sûrement vers une variable aléatoire à densité (si

$r(x)=1+x$ cette variable est uniforme sur

$[0,1]$ ).

2. Renforcement géométrique

On trace

$K$ trajectoires de

$\frac{S^A_n}{n}$ pour

$r$ de la forme

$r(x)=\rho^x$ , avec

$\rho >1$ .

xxxxxxxxxx
 
import numpy as np
import matplotlib.pyplot as plt
​
K=20        # Nombre de trajectoires
N=2000      # Durée de chaque simulation
​
def renforcement(x):    
    return 1.04**x # renforcement géométrique
​
for k in range(K):
    PassagesenA=[]  # True = on passe en "A"
    NbPassagesenA=0
    for n in range(N): 
      biais = (renforcement(NbPassagesenA)+0.0)/(renforcement(NbPassagesenA)+renforcement(n-NbPassagesenA))
      OnPasseEnA=np.random.rand()<biais  # Passage en A aléatoire, suivant le biais
      PassagesenA.append(OnPasseEnA)
      NbPassagesenA=NbPassagesenA+OnPasseEnA
    plt.plot((np.cumsum(PassagesenA)+0.0)/np.array(range(1,N+1)))
​
plt.title('Trajectoires de $(S_n/n)$ pour un renforcement geometrique')
plt.axis([0,N,0,1])
plt.show()

On peut démontrer que pour

$r(x)=\rho^x$ ,

$\frac{S^A_n}{n}$ converge presque-sûrement vers une variable aléatoire qui prend les valeurs

$0$ ou

$1$ avec probabilité

$0.5/0.5$ .

Références

¹Lien : Algorithme du bandit
²Voir par exemple cet article : Deneubourg, J. L., Aron, S., Goss, S., & Pasteels, J. M.. The self-organizing exploratory pattern of the argentine ant. Journal of insect behavior vol.3 (1990), n.2,p.159-168..

Liens

Moodle : Cours MAP432
Initiation à Python : Page web de l'initiation python du cours de tronc commun

1/4h Python : Phénomènes de renforcement (PC7)

Marche aléatoire renforcée

1. Renforcement linéaire

2. Renforcement géométrique

Références

Liens