Devoir de la semaine 8

À rendre avant le 04 avril 2022, 15h00

Exercice 1 : marche aléatoire sur $\mathbb{Z}$

On considère un pion qui se déplace sur l'ensemble des entiers relatifs de la manière suivante :

  • À l'instant $t=0$, sa position initiale est l'entier $x_0 = 0$.
  • À tout instant $t$, il se déplace ou bien en avant, ou bien en arrière, avec probabilité $1/2$. Autrement dit, sa position $x_{t+1}$ à l'instant $t+1$ vaut : $$ x_{t+1} = \left\{\begin{array}{ll} x_t + 1 & \text{ avec probabilité } 1/2 \\ x_t - 1 & \text{ avec probabilité } 1/2 \\ \end{array}\right. $$

La suite des positions du pion est appelée une marche aléatoire.

Question 1 : Écrire une fonction deplacement(N) qui calcule le déplacement aléatoire d'un pion jusqu'à l'instant $N$. La fonction retournera la liste des $N+1$ positions du pion au cours du temps.

In [ ]:

Question 2 : Afficher une marche aléatoire comme une liste de points de coordonnées $(t, x_t)$, où $t$ parcourt $[0, 1000]$.

In [ ]:

Pour une marche aléatoire jusqu'à un instant $N$, on cherche à estimer la valeur de l'éloignement final du pion par rapport à son emplacement d'origine. Autrement dit, si ${\bf x} = (x_0, \dots, x_N)$ représente la marche aléatoire jusqu'à l'instant $N$, cherche à estimer le comportement "moyen" de $|x_N|$ en fonction de $N$.

La première manière de comprendre ce comportement moyen consiste à exécuter $M$ marches aléatoires (avec $M$ assez grand), puis à retourner la valeur moyenne des $|x_N|$ obtenus. Autrement dit, on calcule $$ A_N = \frac{1}{M} \sum_{i=1}^M |x^{(i)}_N| $$ où ${\bf x}^{(1)}, \dots, {\bf x}^{(M)}$ représentent $M$ marches aléatoires tirées indépendamment.

Question 3 : Écrire une fonction moyenne_1_distance(N, M) qui retourne la valeur de $A_N$ après le tirage de $M$ marches aléatoires.

In [ ]:

Question 4 : Pour une valeur de $M = 400$ fixée, tracer la courbe de la valeur de $A_N$ en fonction de $N$. On choisira, par exemple, des valeurs de $N$ variant de $10$ en $10$, entre $10$ et $500$.

Puis, superposer ce tracé avec celui de la fonction $t \mapsto \sqrt{2t/\pi}$. Commenter sur la valeur moyenne de l'éloignement final du pion en fonction de $N$.

In [ ]:

Une seconde manière de comprendre ce comportement moyen consiste à exécuter $M$ marches aléatoires (avec $M$ assez grand), puis à retourner $$ B_N = \sqrt{\frac{1}{M} \sum_{i=1}^M |x^{(i)}_N|^2} $$ où ${\bf x}^{(1)}, \dots, {\bf x}^{(M)}$ représentent $M$ marches aléatoires tirées indépendamment.

Question 5 : Écrire une fonction moyenne_2_distance(N, M) qui retourne la valeur de $B_N$ après le tirage de $M$ marches aléatoires.

In [ ]:

Question 6 : Pour une valeur de $M = 400$ fixée, tracer la courbe de la valeur de $B_N$ en fonction de $N$. On choisira, par exemple, des valeurs de $N$ variant de $10$ en $10$, entre $10$ et $500$.

Puis, superposer ce tracé avec celui de la fonction $t \mapsto \sqrt{t}$. Commenter.

In [ ]:

Exercice 2 : marche aléatoire dans $\mathbb{Z}^2$.

Le pion effectue cette fois une marche aléatoire dans la grille infinie $\mathbb{Z}^2$ (la grille du plan). L'emplacement initial du pion est le point $P_0 = (0, 0)$. Puis, si le pion est à l'emplacement $P_t$ à l'instant $t$, alors à l'instant $t+1$, son emplacement est :

  • $P_{t+1} = P_t + (1, 0)$ avec probabilité $1/4$,
  • $P_{t+1} = P_t + (0, 1)$ avec probabilité $1/4$,
  • $P_{t+1} = P_t + (-1, 0)$ avec probabilité $1/4$,
  • $P_{t+1} = P_t + (0, -1)$ avec probabilité $1/4$.

Question 1 : Écrire une fonction deplacement_2D(N) qui calcule le déplacement aléatoire d'un pion dans $\mathbb{Z}^2$, jusqu'à l'instant $N$. La fonction retournera la liste des $N+1$ positions du pion au cours du temps.

In [ ]:

Question 2 : Afficher dans le plan les points de passage du pion lors de sa marche aléatoire sur $N = 10000$ temps.

In [ ]: