Chaînes de Markov : graphe probabiliste, matrice de transition~3 min
Un système passe d'un état à un autre à chaque étape, au hasard. On note $X_n$ l'état à l'étape $n$. La suite $(X_n)$ est une chaîne de Markov si la probabilité de passer de l'état $i$ à l'état $j$, $p_{ij}=P_{(X_n=i)}(X_{n+1}=j)$, ne dépend que de $i$ et $j$ (ni de $n$, ni des états antérieurs).
• Graphe probabiliste : graphe orienté pondéré dont les sommets sont les états et l'arc $i\to j$ porte $p_{ij}$ (on omet les arcs de poids $0$). La somme des poids des arcs sortant d'un sommet vaut $1$.
• Matrice de transition $P=(p_{ij})$ : carrée d'ordre $N$, à coefficients dans $[0\,;1]$, chaque ligne de somme $1$ (matrice stochastique).
• Distribution à l'étape $n$ : la matrice ligne $\pi_n=\bigl(P(X_n=1)\ \cdots\ P(X_n=N)\bigr)$, de somme $1$ ; $\pi_0$ est la distribution initiale.
Pour tout $n\in\mathbb{N}$ : $\boldsymbol{\pi_{n+1}=\pi_nP}$ et donc $\boldsymbol{\pi_n=\pi_0P^n}$.
Le coefficient $(i,j)$ de $P^n$ est la probabilité de passer de l'état $i$ à l'état $j$ en $n$ transitions : $(P^n)_{ij}=P_{(X_0=i)}(X_n=j)$.
Montrons par récurrence que, pour tout $n\geq1$ et tous états $i,j$ : $P_{(X_0=i)}(X_n=j)=(P^n)_{ij}$.
Initialisation. $P_{(X_0=i)}(X_1=j)=p_{ij}$ par définition : c'est le coefficient $(i,j)$ de $P^1$.
Hérédité. Supposons la propriété vraie au rang $n$. Les événements $(X_n=k)$, $k=1,\dots,N$, forment une partition de l'univers ; d'après la formule des probabilités totales (dans l'univers conditionné par $X_0=i$) : $$\begin{aligned}P_{(X_0=i)}(X_{n+1}=j)&=\sum_{k=1}^{N}P_{(X_0=i)}(X_n=k)\times P_{(X_0=i)\cap(X_n=k)}(X_{n+1}=j)\\&=\sum_{k=1}^{N}(P^n)_{ik}\,p_{kj}=(P^nP)_{ij}=(P^{n+1})_{ij},\end{aligned}$$ car, par la propriété de Markov, la probabilité de passer de $k$ à $j$ ne dépend pas de l'état initial : $P_{(X_0=i)\cap(X_n=k)}(X_{n+1}=j)=p_{kj}$. La propriété est donc vraie pour tout $n\geq1$.
Distribution. Par les probabilités totales avec la partition $(X_0=i)_{1\leq i\leq N}$ : $P(X_n=j)=\sum_{i}P(X_0=i)\,P_{(X_0=i)}(X_n=j)=\sum_i\pi_0(i)\,(P^n)_{ij}$, qui est le coefficient $j$ de la ligne $\pi_0P^n$ : $\pi_n=\pi_0P^n$. Le même calcul entre les étapes $n$ et $n+1$ donne $\pi_{n+1}=\pi_nP$.
Météo. Après un jour de soleil (S), il fait soleil le lendemain avec la probabilité $0{,}8$ ; après un jour de pluie (R), il pleut le lendemain avec la probabilité $0{,}6$. Matrice de transition (ordre S, R) : $P=\begin{pmatrix}0{,}8&0{,}2\\0{,}4&0{,}6\end{pmatrix}$, $P^2=\begin{pmatrix}0{,}72&0{,}28\\0{,}56&0{,}44\end{pmatrix}$.
S'il fait soleil aujourd'hui ($\pi_0=(1\ \ 0)$), la probabilité qu'il pleuve dans deux jours est $(P^2)_{SR}=0{,}8\times0{,}2+0{,}2\times0{,}6=0{,}28$ (probabilités totales : soleil puis pluie, ou pluie puis pluie) ; $\pi_2=\pi_0P^2=(0{,}72\ \ 0{,}28)$ et $\pi_3=\pi_2P=(0{,}688\ \ 0{,}312)$.
import numpy as np P = np.array([[0.8, 0.2], [0.4, 0.6]]) pi0 = np.array([[1, 0]]) pi0 @ np.linalg.matrix_power(P, 10) # -> [[0.6667 0.3333]] environ
from random import random
def simulation(P, etat, n):
for k in range(n):
u = random() # tirage dans [0,1[
if u < P[etat][0]: etat = 0
else: etat = 1
return etat # etat apres n transitions
En répétant simulation(P, 0, 10) un grand nombre de fois, la fréquence de l'état $1$ (la pluie R : le programme numérote les états $0$ et $1$) approche $0{,}333$ : c'est le second coefficient de $\pi_{10}$, $P(X_{10}=R)\approx0{,}333$ (loi des grands nombres).