Graphe probabiliste associé à une chaîne de Markov

Une chaîne de Markov est un processus qui passe par différents états, où la probabilité de passer à un état futur dépend uniquement de l'état présent et non des états précédents

Dans cette fiche, nous parlerons de Chaîne de Markov à deux ou trois États.

I. Le vocabulaire

États : Les états représentent les différentes situations possibles dans le système modélisé.

Distribution initiale $\pi_0$ : La distribution initiale est une matrice ligne qui représente la probabilité de se trouver dans chaque état au début du processus.

Matrice de transition (P) : La matrice de transition est une matrice carrée où chaque élément $P_{ij}$représente la probabilité de passer de l'état $i$ à l'état $j$ en une étape.

Graphe Pondéré Associé : pour une chaîne de Markov, le graphe pondéré associé est un graphe orienté où les sommets représentent les états, et les arêtes pondérées représentent les probabilités de transition entre les états.

Interprétation du coefficient (i,j) de $P^n$ : dans la matrice $P^n$, le coefficient $(i,j)$représente la probabilité de passer de l'état$i$ à l'état $j$ en exactement $n$ étapes.

Distribution après n transitions $(\pi_0 P^n)$: La distribution après $n$ transitions est obtenue en multipliant la distribution initiale $\pi_0$par la matrice $P^n$. Cela donne la probabilité de se trouver dans chaque état après $n$ étapes.

Distribution invariante $(\pi)$: Une distribution invariante est une distribution qui reste inchangée après une transition. Elle satisfait l'équation $\pi = \pi P$. Pour une chaîne de Markov, la distribution invariante représente l'état d'équilibre du système.

II. Chaîne de Markov

Définition :

Une chaîne de Markov est un processus dans lequel l’état futur ne dépend que de l’état actuel, et pas du passé. On parle de propriété de Markov.

Dans une chaîne à 2 ou 3 états, on considère un ensemble fini d’états, par exemple :

Pour 2 états : $A$ et $B$

Pour 3 états : $A$, $B$, et $C$

Les probabilités de transition entre ces états sont regroupées dans une matrice de transition $P$.

Exemple 1 :

Considérons une chaîne de Markov à deux états $A$et $B$ avec la matrice de transition suivante :

$P = \begin{pmatrix} 0.7 \quad 0.3 \\ 0.4 \quad 0.6 \end{pmatrix}$ et une distribution initiale $\pi_0 = \begin{pmatrix} 0.5 \quad 0.5 \end{pmatrix}$

La distribution après 2 Transitions est $\pi_2 = \pi_0 P^2$

La distribution invariante s'obtient en résolvant l'équation $\pi = \pi P$ pour trouver $\pi$.

Solution :

1. Distribution après 2 transitions

On calcule $P^2$ puis $\pi_2 = \pi_0 P^2$ :
Résultat obtenu :

$\pi_2 = \begin{pmatrix} 0.565 \quad 0.435 \end{pmatrix}$

Cela signifie qu’après deux transitions, la probabilité d’être en état $A$ est environ $0.565$ et en état $B$ environ $0.435$.

2. Distribution invariante

On cherche une distribution $\pi = (x, y)$ telle que :

$\pi P = \pi \quad \text{et} \quad x + y = 1$

La solution de ce système donne :

$\pi = \begin{pmatrix} 0.571429 \quad 0.428571 \end{pmatrix}$

C’est la distribution invariante : si la chaîne commence avec cette répartition, elle reste stable à chaque transition.Dans cet exemple précis, la chaîne de Markov converge très rapidement vers sa distribution invariante. Résultat :

$\pi_2 = \begin{pmatrix} 0.565 \quad 0.435 \end{pmatrix}$

Autrement dit : $\pi_2 \approx \pi$

Mais ce n’est pas une généralité. En réalité :

$\pi_2 = \pi_0 P^2$ → dépend de l’état initial.

$\pi$ vérifie l’équation $\pi = \pi P$ → ne dépend que de $P$.

Exemple 2 : Comportement d’un étudiant face à un devoir

Un étudiant peut être dans l’un des trois états suivants chaque jour :

$A$ : Il travaille sérieusement

$B$ : Il procrastine

$C$ : Il ne fait rien du tout

Matrice de transition

L’étudiant change (ou pas) d’état chaque jour selon les probabilités suivantes :

$P = \begin{pmatrix} 0.6 \quad 0.3 \quad 0.1 \\ 0.3 \quad 0.4 \quad 0.3 \\ 0.2 \quad 0.4 \quad 0.4 \end{pmatrix}$

Ligne 1 : s’il travaille sérieusement un jour ($A$), le lendemain il a 60% de chances de continuer ($A$), 30% de procrastiner ($B$), 10% de ne rien faire ($C$).

Ligne 2 : s’il procrastine ($B$), il a 30% de chances de se mettre au travail, 40% de rester en procrastination, etc.

Ligne 3 : s’il ne fait rien ($C$), il y a 20% de chances qu’il se remette à bosser, 40% de rester inactif, etc.

Distribution initiale

On suppose qu’au départ (jour 0), l’étudiant est motivé :

$\pi_0 = \begin{pmatrix} 1 \quad 0 \quad 0 \end{pmatrix}$

Questions qu’on peut poser :

À long terme, quelle est la répartition stable entre les 3 comportements ?
Cela revient à déterminer la distribution invariante $\pi$ telle que $\pi = \pi P$

Distribution invariante :

On considère la matrice de transition
$P = \begin{pmatrix} 0.6 \quad 0.3 \quad 0.1 \\ 0.3 \quad 0.4 \quad 0.3 \\ 0.2 \quad 0.4 \quad 0.4 \end{pmatrix}$

Nous cherchons à calculer $P^2$, c'est-à-dire le produit $P \cdot P$.

Calcul ligne par colonne :

Ce qui donne :

$P^2 = \begin{pmatrix} 0.47 \quad 0.34 \quad 0.19 \\ 0.36 \quad 0.37 \quad 0.27 \\ 0.32 \quad 0.38 \quad 0.30 \end{pmatrix}$

On vérifie que $P^2$ est bien une matrice de transition :
les lignes ont pour somme $1$ :

• Ligne 1 : $0.47 + 0.34 + 0.19 = 1$

• Ligne 2 : $0.36 + 0.37 + 0.27 = 1$

• Ligne 3 : $0.32 + 0.38 + 0.30 = 1$

On cherche maintenant le vecteur stationnaire $\pi = (x, y, z)$ tel que
$\pi P = \pi$ et $x + y + z = 1$

Cela revient à résoudre le système suivant :

$\begin{cases} 0.6x + 0.3y + 0.2z = x \\ 0.3x + 0.4y + 0.4z = y \\ 0.1x + 0.3y + 0.4z = z \\ x + y + z = 1 \end{cases}$

On simplifie :

$\begin{cases} -0.4x + 0.3y + 0.2z = 0 \\ 0.3x - 0.6y + 0.4z = 0 \\ 0.1x + 0.3y - 0.6z = 0 \\ x + y + z = 1 \end{cases}$

Résolution numérique du système :
$\pi = (x, y, z) \approx (0.348, 0.370, 0.282)$

Ce vecteur stationnaire signifie qu’à long terme, l'étudiant passera environ :

34.8 % du temps dans l’état 1

37.0 % dans l’état 2

28.2 % dans l’état 3