Matrice de transition et distribution invariante · Mathématiques et maths expertes Terminale (maths expertes)

Graphe probabiliste et matrice de transition

Dans la situation de Lina, le choix de demain ne dépend que du choix d'aujourd'hui, pas de ce qui s'est passé avant. On parle de chaîne de Markov. On représente la situation par un graphe probabiliste : les sommets sont les états, les flèches portent les probabilités de passer d'un état à l'autre.

On range ces probabilités dans une matrice de transition $P$. On ordonne les états (ici B, V). Le coefficient de la ligne $i$ et de la colonne $j$ est la probabilité de passer de l'état $i$ à l'état $j$.

$$P = \begin{pmatrix} 0{,}6 & 0{,}4 \\ 0{,}2 & 0{,}8 \end{pmatrix}$$

La ligne $i$ décrit tous les départs depuis l'état $i$ : c'est pour cela que sa somme vaut $1$. La somme d'une colonne, elle, n'a aucune raison de valoir $1$.

Entraîne-toi★☆☆

Un graphe probabiliste à deux états $A$ et $B$ est tel que : de $A$, on reste en $A$ avec la probabilité $0{,}7$ et on passe en $B$ avec la probabilité $0{,}3$ ; de $B$,…

Un graphe probabiliste à deux états $A$ et $B$ est tel que : de $A$, on reste en $A$ avec la probabilité $0{,}7$ et on passe en $B$ avec la probabilité $0{,}3$ ; de $B$, on passe en $A$ avec la probabilité $0{,}4$ et on reste en $B$ avec la probabilité $0{,}6$.

Écrire la matrice de transition $P$ de cette chaîne de Markov, en ordonnant les états $A$, $B$.

Résoudre

Distribution à l'étape n

Notons $\pi_n = (a_n\ \ b_n)$ la distribution à l'étape $n$ : $a_n$ est la probabilité d'être en B et $b_n$ celle d'être en V, avec $a_n + b_n = 1$. C'est une matrice ligne.

Pour être en B demain, il faut être en B aujourd'hui et y rester, ou être en V et passer en B (formule des probabilités totales) :

$$a_{n+1} = 0{,}6\,a_n + 0{,}2\,b_n \qquad b_{n+1} = 0{,}4\,a_n + 0{,}8\,b_n$$

Ce sont exactement les coefficients du produit matriciel $\pi_n P$.

Démonstration : le coefficient $(i\,;j)$ de $P^n$

Montrer par récurrence que, pour tout entier naturel $n$, le coefficient de la ligne $i$ et de la colonne $j$ de $P^n$ est la probabilité de passer de l'état $i$ à l'état $j$ en $n$ étapes.

Initialisation ($n = 1$) : par définition de $P$, le coefficient $(i\,;j)$ est la probabilité de passer de $i$ à $j$ en une étape. ✓

Hérédité : on suppose la propriété vraie pour un entier $n$. Pour aller de $i$ à $j$ en $n+1$ étapes, on passe par un état $k$ à l'étape $n$ (formule des probabilités totales) :

$$p^{(n+1)}_{ij} = \sum_{k} p^{(n)}_{ik}\,p_{kj}.$$

C'est exactement le coefficient $(i\,;j)$ du produit $P^n P = P^{n+1}$. La propriété est héréditaire, donc vraie pour tout $n$.

Conséquence : si $\pi_0$ est la distribution initiale, $\pi_n = \pi_0 P^n$ (on pondère les lignes de $P^n$ par les probabilités de départ).

Remarque : la probabilité de vélo augmente peu à peu : $0$, $0{,}4$, $0{,}56$, $0{,}624$… Où cela s'arrête-t-il ?

Entraîne-toi★☆☆

Soit la matrice de transition $P = \begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}5 & 0{,}5 \end{pmatrix}$ et la distribution initiale $\pi_0 = (1\ \ 0)$. Calculer…

Soit la matrice de transition $P = \begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}5 & 0{,}5 \end{pmatrix}$ et la distribution initiale $\pi_0 = (1\ \ 0)$.

Calculer $\pi_1 = \pi_0 P$ et $\pi_2 = \pi_1 P$.

Résoudre

Distribution invariante

Si la chaîne démarre avec la distribution $\pi$, elle la conserve à toutes les étapes : $\pi_1 = \pi P = \pi$, puis $\pi_2 = \pi$, etc.

Lina ira donc à vélo les $\dfrac23$ du temps à long terme, si la chaîne converge vers $\pi$ (voir plus loin).

Entraîne-toi★☆☆

Vérifier que $\pi = \left(\dfrac{5}{7}\ \ \dfrac{2}{7}\right)$ est une distribution invariante pour la matrice…

Vérifier que $\pi = \left(\dfrac{5}{7}\ \ \dfrac{2}{7}\right)$ est une distribution invariante pour la matrice $P = \begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}5 & 0{,}5 \end{pmatrix}$.

Résoudre

Entraîne-toi★★☆

À Nantes, un service de vélos en libre-service a deux stations, $A$ et $B$. Un vélo pris en $A$ est rendu en $A$ avec la probabilité $0{,}6$ ; un vélo pris en $B$ est…

À Nantes, un service de vélos en libre-service a deux stations, $A$ et $B$. Un vélo pris en $A$ est rendu en $A$ avec la probabilité $0{,}6$ ; un vélo pris en $B$ est rendu en $B$ avec la probabilité $0{,}7$. Un vélo est en $A$ au jour $0$.

a) Écrire la matrice de transition $P$.

b) Calculer la probabilité que le vélo soit en $A$ au jour $2$.

c) Déterminer la distribution invariante de la chaîne.

Résoudre

Entraîne-toi★★☆

Une chaîne à trois états $1$, $2$, $3$ a pour matrice de transition $P = \begin{pmatrix} 0{,}5 & 0{,}5 & 0 \\ 0 & 0{,}5 & 0{,}5 \\ 0{,}5 & 0 & 0{,}5 \end{pmatrix}$. a)…

Une chaîne à trois états $1$, $2$, $3$ a pour matrice de transition $P = \begin{pmatrix} 0{,}5 & 0{,}5 & 0 \\ 0 & 0{,}5 & 0{,}5 \\ 0{,}5 & 0 & 0{,}5 \end{pmatrix}$.

a) Calculer $P^2$.

b) La distribution initiale est $\pi_0 = (1\ \ 0\ \ 0)$. Calculer $\pi_2$.

c) Déterminer la distribution invariante.

Résoudre

Convergence vers la distribution invariante

Pourquoi les $\pi_n$ s'approchent-ils de $\pi$ ? Avec deux états, on peut le voir avec une suite arithmético-géométrique.

Convergence pour la chaîne de Lina

$P = \begin{pmatrix} 0{,}6 & 0{,}4 \\ 0{,}2 & 0{,}8 \end{pmatrix}$, $\pi_0 = (1\ \ 0)$, $\pi_n = (a_n\ \ b_n)$.

Comme $b_n = 1 - a_n$ :

$$a_{n+1} = 0{,}6\,a_n + 0{,}2\,(1 - a_n) = 0{,}4\,a_n + 0{,}2.$$

On obtient une suite de la forme $a_{n+1} = r\,a_n + c$, ce qui ramène à l'étude d'une suite géométrique.

Le point fixe de $x \mapsto 0{,}4x + 0{,}2$ est $\ell$ tel que $\ell = 0{,}4\ell + 0{,}2$, donc $\ell = \dfrac13$. On pose $v_n = a_n - \dfrac13$ :

$$v_{n+1} = 0{,}4\,a_n + 0{,}2 - \dfrac13 = 0{,}4\,a_n - \dfrac{0{,}4}{3} = 0{,}4\,v_n.$$

$(v_n)$ est géométrique de raison $0{,}4$ et $v_0 = 1 - \dfrac13 = \dfrac23$.

Donc $a_n = \dfrac13 + \dfrac23\,(0{,}4)^n$. Comme $-1 < 0{,}4 < 1$, $(0{,}4)^n \to 0$ et $a_n \to \dfrac13$ ; ainsi $b_n \to \dfrac23$.

Vérifie la formule pour $n = 2$ avec le calcul fait dans la section précédente.

$a_2 = \dfrac13 + \dfrac23 \times 0{,}16 = \dfrac13 + \dfrac{0{,}32}{3} = \dfrac{1{,}32}{3} = 0{,}44$ ✓.

Le raisonnement est général. Pour $P = \begin{pmatrix} 1-p & p \\ q & 1-q \end{pmatrix}$ avec $p, q \in\, ]0\,;1[$, on obtient $a_{n+1} = (1-p-q)\,a_n + q$. Comme $-1 < 1-p-q < 1$, la suite converge, quelle que soit la distribution initiale, vers la solution de $\ell = (1-p-q)\ell + q$. La vitesse est celle de la suite géométrique de raison $1-p-q$.

Pour utiliser ce critère, on calcule $P^2$ (ou $P^3$) et on regarde si un zéro subsiste.

Entraîne-toi★★☆

Une chaîne de Markov a pour matrice de transition $P = \begin{pmatrix} 0{,}9 & 0{,}1 \\ 0{,}2 & 0{,}8 \end{pmatrix}$ et pour distribution initiale…

Une chaîne de Markov a pour matrice de transition $P = \begin{pmatrix} 0{,}9 & 0{,}1 \\ 0{,}2 & 0{,}8 \end{pmatrix}$ et pour distribution initiale $\pi_0 = (0{,}5\ \ 0{,}5)$. On note $\pi_n = (a_n\ \ b_n)$.

a) Justifier que $a_{n+1} = 0{,}7\,a_n + 0{,}2$.

b) Montrer que la suite $(a_n - \tfrac{2}{3})$ est géométrique.

c) En déduire $a_n$ en fonction de $n$ et la limite de $(\pi_n)$.

Résoudre

Entraîne-toi★★★

Une chaîne de Markov à deux états a pour matrice de transition $P = \begin{pmatrix} 1-p & p \\ q & 1-q \end{pmatrix}$ avec $p, q \in\, ]0\,;1[$. a) Déterminer la…

Une chaîne de Markov à deux états a pour matrice de transition $P = \begin{pmatrix} 1-p & p \\ q & 1-q \end{pmatrix}$ avec $p, q \in\, ]0\,;1[$.

a) Déterminer la distribution invariante $\pi$ en fonction de $p$ et $q$.

b) Montrer que, pour toute distribution initiale $\pi_0 = (a_0\ \ b_0)$, $a_{n+1} = (1-p-q)\,a_n + q$.

c) En déduire que $(\pi_n)$ converge vers $\pi$ et préciser la vitesse de convergence.

Résoudre

Entraîne-toi★★★

Un site web de la SNCF propose trois pages : $1$ (accueil), $2$ (horaires), $3$ (réservation). Depuis la page $1$, un internaute va en $2$ avec la probabilité $0{,}6$ et…

Un site web de la SNCF propose trois pages : $1$ (accueil), $2$ (horaires), $3$ (réservation). Depuis la page $1$, un internaute va en $2$ avec la probabilité $0{,}6$ et en $3$ avec la probabilité $0{,}4$. Depuis la page $2$, il va en $1$ avec la probabilité $0{,}3$ et en $3$ avec la probabilité $0{,}7$. Depuis la page $3$, il revient en $1$ avec la probabilité $1$.

a) Écrire la matrice de transition $P$.

b) Déterminer la distribution invariante $\pi$.

c) Sur le long terme, quelle proportion de visites concerne la page de réservation ? Justifier que la chaîne converge vers $\pi$ en montrant que tous les coefficients de $P^4$ sont strictement positifs.

Résoudre

Puissances de P et récurrence

Comme $\pi_n = \pi_0 P^n$, connaître $P^n$ donne toutes les distributions d'un coup. On conjecture une formule à partir de quelques calculs, puis on la démontre par récurrence.

Une formule pour P^n

Pour $P = \begin{pmatrix} 0{,}6 & 0{,}4 \\ 0{,}2 & 0{,}8 \end{pmatrix}$, montrer que pour tout $n \in \mathbb{N}$ :

$$P^n = J + (0{,}4)^n K \quad \text{avec } J = \begin{pmatrix} \tfrac13 & \tfrac23 \\ \tfrac13 & \tfrac23 \end{pmatrix},\ K = \begin{pmatrix} \tfrac23 & -\tfrac23 \\ -\tfrac13 & \tfrac13 \end{pmatrix}.$$

Initialisation ($n = 0$) : $J + K = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = P^0$ ✓.

Hérédité : on suppose $P^n = J + (0{,}4)^n K$ pour un entier $n$ fixé. Alors $P^{n+1} = P^n P = JP + (0{,}4)^n KP$.

Les lignes de $J$ valent $\pi = \left(\tfrac13\ \ \tfrac23\right)$, qui est invariante : $\pi P = \pi$, donc $JP = J$.

Un calcul direct donne $KP = 0{,}4\,K$ : par exemple, la première ligne de $KP$ est $\tfrac23(0{,}6 - 0{,}2\ \ \ 0{,}4 - 0{,}8) = 0{,}4 \left(\tfrac23\ \ -\tfrac23\right)$.

Donc $P^{n+1} = J + (0{,}4)^{n+1} K$ : la propriété est héréditaire. Par récurrence, elle est vraie pour tout $n$.

Déduis-en la limite de $P^n$ quand $n \to +\infty$ et interprète-la.

$(0{,}4)^n \to 0$, donc $P^n \to J$. Toutes les lignes de $J$ valent $\pi$ : pour toute distribution initiale $\pi_0$, $\pi_0 P^n \to \pi_0 J = \pi$ (car $a_0 + b_0 = 1$). La chaîne « oublie » son départ.

Entraîne-toi★★★

On considère la matrice $P = \begin{pmatrix} 0{,}5 & 0{,}5 \\ 0{,}2 & 0{,}8 \end{pmatrix}$. a) Déterminer la matrice ligne $\pi$ invariante. b) Montrer par récurrence…

On considère la matrice $P = \begin{pmatrix} 0{,}5 & 0{,}5 \\ 0{,}2 & 0{,}8 \end{pmatrix}$.

a) Déterminer la matrice ligne $\pi$ invariante.

b) Montrer par récurrence que, pour tout entier naturel $n$, $P^n = \begin{pmatrix} \tfrac{2}{7} & \tfrac{5}{7} \\ \tfrac{2}{7} & \tfrac{5}{7} \end{pmatrix} + (0{,}3)^n \begin{pmatrix} \tfrac{5}{7} & -\tfrac{5}{7} \\ -\tfrac{2}{7} & \tfrac{2}{7} \end{pmatrix}$.

c) En déduire la limite de $P^n$ et l'interpréter pour une distribution initiale quelconque.

Résoudre

Retour au début : Lina ira à vélo environ $\dfrac23$ des jours à long terme, puisque $\pi = \left(\dfrac13\ \ \dfrac23\right)$.

À s'entraîner ! 9 exercices dans cette section

★☆☆ Un graphe probabiliste à deux états $A$ et $B$ est tel que : de $A$, on reste en $A$ avec…★☆☆ Soit la matrice de transition…★☆☆ Vérifier que $\pi = \left(\dfrac{5}{7}\ \ \dfrac{2}{7}\right)$ est une distribution…

L'essentiel

Une chaîne de Markov à $k$ états se décrit par un graphe probabiliste et une matrice de transition $P$ : ligne = état de départ, colonne = état d'arrivée, somme de chaque ligne égale à $1$.
La distribution (matrice ligne) évolue par $\pi_{n+1} = \pi_n P$, donc $\pi_n = \pi_0 P^n$.
Une distribution $\pi$ est invariante si $\pi P = \pi$ avec des coefficients positifs de somme $1$. On résout le système puis on ajoute la condition de somme.
À deux états, $a_{n+1} = (1-p-q)\,a_n + q$ : suite arithmético-géométrique, convergente vers $\dfrac{q}{p+q}$ si $-1 < 1-p-q < 1$.
Si une puissance de $P$ a tous ses coefficients strictement positifs, $(\pi_n)$ converge vers l'unique distribution invariante.
Une formule pour $P^n$ se conjecture puis se démontre par récurrence.