Matrices : chaînes de Markov

Graphes probabilistes

Définition

Un graphe pondéré est un graphe où chaque arête est associée à un nombre réel, appelé poids de l’arête. Un graphe probabiliste est un graphe orienté et pondéré, où le poids de chaque arrête est positif et où la somme des arêtes partant d’un sommet est toujours égale à 1.

Exemple

Graphe probabiliste

Matrice de transition

Chaque ligne et chaque colonne de la matrice de transition représente un sommet du graphe probabiliste. 

La valeur du coefficient $$a_{i,j}$$​ est égal au poids de l’arête partant du sommet $$I$$​ (ligne) et allant au sommet $$j$$​ (colonne).

Exemple

Sommet ​$$A$$​​ ​$$B$$​​ ​ $$C$$​​ Ligne/colonne ​$$1$$​​ ​$$2$$​​ ​$$3$$​​

$$\left(\begin{matrix}0&0&1\\0,2&0&0,8\\0,4&0,6&0\\\end{matrix}\right)$$​​

Note : La somme des coefficients d’une ligne est toujours égale à 1.

Chaîne de Markov

Imagine une expérience que tu répètes plusieurs fois. La variable aléatoire $$X_n$$​ associe à chaque élément de l’univers $$\Omega$$​ la valeur qu’il prend dans $$E\subseteq\mathbb{R}$$​ à la n-ième répétition. On peut ainsi construire une suite $$X_0,\ X_1,\ X_2,\ldots$$​ de variables aléatoires.

​

Note : L’ensemble $$E$$ s’appelle l’espace des états.

Une chaîne de Markov est une suite de variables aléatoires $$X_n$$​ telle que chaque événement $$X_n$$​ dépend uniquement de l’état de $$X_{n-1}$$​, c’est-à-dire qu’il dépend de l’état antérieur mais pas des états qui précèdent et pas de l’étape $$n$$​ à laquelle on se trouve.

Exemple

Dans un village, chaque famille part tous les étés en vacances, soit à la mer, soit à la montagne. La décision du lieu de vacances dépend uniquement de l’endroit où la famille est allée l’année précédente. L’ensemble des états est $$\left\{mer\left(1\right),\ montagne\ \left(2\right)\right\}$$​ (on associe arbitrairement $$mer$$​​ au nombre 1 et $$montagne$$​ au nombre 2).

Si une famille est allée à la mer l’année précédente, il y a $$25\%$$​ de chance qu’elle y retourne, et  de chance qu’elle choisisse la montagne.

Si une famille est allée à la montagne l’année précédente, il y a $$60\%$$​ de chance qu’elle y retourne, et $$40\%$$​ de chance qu’elle aille au bord de la mer à la place.

Chaque  représente la destination choisie par la famille l’année . Il s’agit d’une chaîne de Markov puisque la décision ne dépend que de la valeur prise par $$X_{n-1}$$​. Le graphe suivant représente cette situation :

Tu peux aussi construire la matrice de transition de ce graphe :

$$\left(\begin{matrix}0,25&0,75\\0,4&0,6\\\end{matrix}\right)$$​​

Note : On appelle ce graphe le graphe probabiliste associé et cette matrice la matrice de transition de la chaîne de Markov.

Distribution initiale

La loi de probabilité de  est appelée la distribution initiale de la chaîne de Markov. Elle est généralement représentée par une matrice ligne notée .

De manière analogue, la loi de probabilité de $$X_n$$​ est appelée la distribution après $$n$$​ transitions de la chaîne de Markov. Elle est généralement représentée par une matrice ligne notée $$\pi_n$$​.

On dit que la distribution est invariante si tous les $$\pi_n$$​ sont les mêmes.

PROPRIÉTÉ

Une propriété des distributions d’une chaîne de Markov est que :

$$\pi_n=\pi_0\times T^n$$​​

où $$T$$​ est la matrice de transition de la chaîne de Markov.

Exemple

Reprends l’exemple précédent. Imagine que l’an $$0, 30\%$$​ des familles sont allées à la mer et $$70\%$$​ à la montagne. Calcule la distribution après 2 ans :

$$\pi_2=\pi_0\times\left(\begin{matrix}0,25&0,75\\0,4&0,6\\\end{matrix}\right)^2$$​​

$$=\left(0,3\ \ \ 0,7\right)\times\left(\begin{matrix}0,25&0,75\\0,4&0,6\\\end{matrix}\right)\times\left(\begin{matrix}0,25&0,75\\0,4&0,6\\\end{matrix}\right)=\left(0,355\ \ \ 0,645\right)\times\left(\begin{matrix}0,25&0,75\\0,4&0,6\\\end{matrix}\right)=(0,34675\ \ \ 0,65325)$$​​

Après deux ans, environ $$\underline{35\%}$$​ des familles partiront à la mer et $$\underline{65\%}$$​ iront à la montagne.