TP 14 : Marche aléatoire et chaîne de Markov#

Question

Exécuter le code suivant pour importer les modules nécessaires

import matplotlib.pyplot as plt
import numpy as np
import random

Marche aléatoire en 1D#

On rappelle que random.random() permet d’obtenir un flottant (nombre à virgule) aléatoire entre 0 et 1 :

random.random()

0.7359502472103266

On définit une marche aléatoire à une dimension par des variables aléatoires \(X_1\), \(X_2\), … indépendantes et de même loi :

\[\mathbb{P}(X_k = 1) = \mathbb{P}(X_k = -1) = \frac{1}{2}\]

Question

Écrire une fonction X() qui renvoie 1 ou -1 avec une probabilité de 1/2 chacune.

Solution

def X():
    if random.random() < 0.5:
        return 1
    else:
        return -1

X()

-1

On définit ensuite la variable aléatoire \(S_n = X_1 + X_2 + \cdots + X_n\).

Question

Écrire une fonction S(n) qui renvoie \(S_n\).

Solution

def S(n):
    s = 0
    for i in range(n):
        s += X()
    return s

S(100)

-18

Exercice

Écrire une fonction S_liste(n) qui renvoie la liste des sommes partielles \(S_1\), \(S_2\), … \(S_n\). Il s’agit donc de la même fonction que précédemment, mais qui renvoie une liste.
Exécuter le code suivant pour afficher la marche aléatoire.

Solution

def S_liste(n):
    L = [0]
    for i in range(n):
        L.append(L[-1] + X())
    return L

L = S_liste(1000)
plt.plot(L, label="S(n)")
plt.legend()
plt.show()

Distance à l’origine#

Un théorème affirme que la distance à l’origine \(|S_n|\) vérifie :

\[\mathbb{E}(|S_n|) \sim \sqrt{\frac{2n}{\pi}}\]

On veut vérifier ce résultat informatiquement.

Exercice

Écrire une fonction distance_origine(n, p) qui calcule p fois abs(S(n)) et renvoie la moyenne de ces valeurs.
Comparer graphiquement avec \(\sqrt{\frac{2n}{\pi}}\) en exécutant le code ci-dessous.

Solution

def distance_origine(n, p):
    m = 0
    for i in range(p):
        m += abs(S(n))
    return m/p

plt.plot([distance_origine(i, 100) for i in range(300)], label="distance_origine(n, 100)")
plt.plot([(2*i/np.pi)**.5 for i in range(300)], 'r', label="(2n/pi)**.5")
plt.xlabel("n")
plt.legend()
plt.show()

Théorème de la limite centrale#

En notant \(\mu\) et \(\sigma\) l’espérance et l’écart-type de chaque variable \(X_k\), le théorème de la limite centrale affirme que :

\[\frac{S_n - n\mu}{\sigma\sqrt{n}} \sim \mathcal{N}(0, 1)\]

où \(\mathcal{N}(0, 1)\) est la loi normale centrée réduite, dont la densité de probabilité est :

\[f(x) = \frac{1}{\sqrt{2\pi}}\exp\left(-\frac{x^2}{2}\right)\]

Exercice

Calculer \(\mu\) et \(\sigma\) à la main (sans ordinateur). On rappelle que \(\sigma = \sqrt{\mathbb{E}(X^2) - \mathbb{E}(X)^2}\).
Écrire une fonction limite_centrale(n) renvoyant \(\frac{S_n - n\mu}{\sigma\sqrt{n}}\), avec \(\mu\) et \(\sigma\) remplacés par leurs valeurs.
Écrire la fonction de densité f de la loi normale centrée réduite. On pourra utiliser np.exp et np.pi.
Vérifier en exécutant le code ci-dessous.

Solution

# on trouve mu = 0 et sigma = 1

def limite_centrale(n):
    return S(n)/n**.5

def f(x):
    return 1/(2*np.pi)**.5*np.exp(-x**2/2)

n = 1000
L = [limite_centrale(n) for i in range(n)]
plt.hist(L, bins=20, density=True)
R = np.linspace(min(L), max(L), 100)
plt.plot(R, [f(x) for x in R], 'r')
plt.show()

Marche aléatoire en 2D#

On se place en dimension 2. On définit le point \(P_n\) par récurrence sur \(n\) :

\(P_0 = (0, 0)\)
\(P_{n + 1}\) est un des \(4\) points voisins de \(P_n\) (en se déplaçant d’une case vers le haut, le bas, la gauche ou la droite) avec une probabilité de \(1/4\) chacune.

Question

Écrire une fonction P(n) qui renvoie le point \(P_n\).
On pourra définir r = random.random() et distinguer \(4\) cas : \(0 \leq r < 1/4\), \(1/4 \leq r < 2/4\), \(2/4 \leq r < 3/4\) et \(3/4 \leq r < 1\).

Solution

def P(n):
    Pk = (0, 0)
    for i in range(n):
        r = random.random()
        if r < 1/4:
            Pk = (Pk[0]+1, Pk[1])
        elif r < 1/2:
            Pk = (Pk[0]-1, Pk[1])
        elif r < 3/4:
            Pk = (Pk[0], Pk[1]+1)
        else:
            Pk = (Pk[0], Pk[1]-1)
    return Pk

P(100)

(-7, -7)

Exercice

Écrire une fonction P_liste(n) qui renvoie la liste des points \(P_0\), \(P_1\), … \(P_n\). Il s’agit donc de la même fonction que précédemment, mais qui renvoie une liste.
Exécuter le code ci-dessous pour afficher la marche aléatoire.

Solution

def P_liste(n):
    Pk = (0, 0)
    L = [(0, 0)]
    for i in range(n):
        r = random.random()
        if r < 1/4:
            Pk = (Pk[0]+1, Pk[1])
        elif r < 1/2:
            Pk = (Pk[0]-1, Pk[1])
        elif r < 3/4:
            Pk = (Pk[0], Pk[1]+1)
        else:
            Pk = (Pk[0], Pk[1]-1)
        L.append(Pk)
    return L

X, Y = zip(*P_liste(100))
plt.plot(X, Y)
plt.show()

On peut prouver que la marche aléatoire en 2D est récurrent : il revient une infinité de fois au point d’origine \((0, 0)\).

Question

Écrire une fonction retour_origine(n) qui renvoie une liste L telle que L[i] est le nombre de fois où la marche aléatoire revient au point d’origine après i étapes.

Solution

def retour_origine(n):
    L = [1]
    for p in P_liste(n)[1:]:
        L.append(L[-1])
        if p == (0, 0):
            L[-1] += 1
    return L

retour_origine(10)

Chaîne de Markov#

On considère un chat qui peut être dans \(3\) états possibles : manger (0), jouer (1) ou dormir (2). À chaque étape, le chat peut changer d’état avec une certaine probabilité donnée par le graphe suivant :

Par exemple, si le chat est en train de manger à l’étape \(n\), il continuera de manger à l’étape \(n + 1\) avec probabilité \(0.2\), il se mettra à dormir avec probabilité \(0.5\) et jouer avec probabilité \(0.3\).

Question

Écrire une fonction chat(n) qui commence dans l’état \(0\) et effectue \(n\) étapes du chat et renvoie une liste L telle que L[i] la proportion du nombre de fois que le chat a été dans l’état i.

Solution

def chat(n):
    L = [0, 0, 0]
    etat = 0
    for i in range(n):
        r = random.random()
        if etat == 0:
            if r < .3:
                etat = 1
            elif r < .8:
                etat = 2
        elif etat == 1:
            if r < .3:
                etat = 0
            elif r < .8:
                etat = 2
        else:
            if r < .4:
                etat = 0
            elif r < .6:
                etat = 1
        L[etat] += 1/n
    return L

chat(100)

[0.25000000000000006, 0.24000000000000007, 0.5100000000000002]

Question

Définir la matrice de transition \(M\) de ce problème, de taille \(3\times 3\) et telle que \(m_{i, j}\) est la probabilité de passer de l’état \(i\) à l’état \(j\).

Solution

M = [
    [.2, .3, .5],
    [.3, .2, .5],
    [.4, .2, .4]
]

M[1][2] # probabilité de passer de l'état 1 à l'état 2

0.5

On peut montrer (théorème de Perron-Frobenius) que \(M^n\) converge vers une matrice dont chaque ligne est la distribution stationnaire, c’est-à-dire la proportion de temps que le chat passe dans chaque état.

On veut vérifier ce théorème.

Question

Écrire une fonction produit(A, B) effectuant le produit matriciel des matrices \(A\) et \(B\). On rappelle que les coefficients de \(C = AB\) vérifient :

\[c_{i, j} = \sum_{k = 1}^n a_{i, k}b_{k, j}\]

On pourra utiliser np.zeros pour créer une matrice C de \(0\) qu’on remplira avec la formule ci-dessus.

Solution

def produit(A, B):
    C = np.zeros((len(A), len(B[0])))
    for i in range(len(A)):
        for j in range(len(B[0])):
            for k in range(len(B)):
                C[i][j] += A[i][k]*B[k][j]
    return C

produit(M, M)

array([[0.33, 0.22, 0.45],
       [0.32, 0.23, 0.45],
       [0.3 , 0.24, 0.46]])

Question

Écrire une fonction puissance(M, n) qui renvoie \(M^n\).
Calculer puissance(M, 10) et vérifier qu’on obtient un résultat proche de chat(10000).

Solution

def puissance(M, n):
    A = M
    for i in range(n-1):
        A = produit(A, M)
    return A

print(puissance(M, 10))
chat(10000)

[0.3133999999999818, 0.23119999999999086, 0.45539999999996617]

Informatique en 2ème année de BCPST

TP 14 : Marche aléatoire et chaîne de Markov

Contents

TP 14 : Marche aléatoire et chaîne de Markov#

Marche aléatoire en 1D#

Distance à l’origine#

Théorème de la limite centrale#

Marche aléatoire en 2D#

Chaîne de Markov#