Chaînes de Markov

I Chaînes de Markov

Définition 1 : On dit qu’un graphe est pondéré si toutes ses arêtes (ou arcs) sont affectées d’un nombre réel positif appelé le poids de cette arête.

Exemples :

Définition 2 : Un graphe probabiliste est un graphe pondéré orienté tel que la somme des poids des arcs issus de chacun des sommets est égale à $1$.

Remarque :

Les poids d’un graphe pondéré étant des nombres positifs, les poids d’un graphe probabiliste sont donc des réels compris entre $0$ et $1$.
On utilise les graphes probabilistes pour modéliser des phénomènes (ou processus) aléatoires.

Définition 3 : Dans un graphe probabiliste les sommets du graphe sont les états du phénomène qu’on observe.

Remarques :

Le poids d’un arc allant du sommet $s_i$ au sommet $s_j$ représente la probabilité de passer de l’état $s_i$ à l’état $s_j$.
S’il n’y a pas d’arête allant du sommet $s_i$ au sommet $s_j$ cela signifie que la probabilité de passer de l’état $s_i$ à l’état $s_j$ est égale à $0$.

$\quad$

Dans la suite de ce chapitre on n’évoquera que des situations à 2 ou 3 états.

$\quad$

Définition 4 : On considère une suite de variables aléatoires $\left(X_n\right)$ définies sur un même espace fini muni d’une probabilité. On dit que $\left(X_n\right)$ est une chaîne de Markov à deux états $a$ et $b$ (respectivement à trois états $a$, $b$ et $c$) si :

pour tout entier naturel $n$ et tout $x\in \lbrace a,b\rbrace$ $\Big($respectivement $x\in \lbrace a,b,c\rbrace\Big)$ $P\left(X_{n+1}=x\right)$ ne dépend que de l’état du processus à l’instant $n$;
la probabilité de passer d’un état à un autre (éventuellement le même) de dépend pas de $n$

Remarques :

On dit que $E=\lbrace a,b\rbrace$ (respectivement $E=\lbrace a,b,c\rbrace$) est l’espace des états.
La probabilité $P_{x_n=x_n}\left(X_{n+1}=x_{n+1}\right)$ est appelé probabilité de transition de l’état $x_n$ à l’état $x_{n+1}$.
Dans une chaîne de Markov les états passés n’ont aucune influence sur les états futurs. Seul l’état présent compte.

Définition 5 : On appelle distribution initiale d’une chaîne de Markov $\left(X_n\right)$ la loi de probabilité de $X_0$.

Exemple : La mairie d’une ville propose une carte jeune annuelle donnant droit aux 12-18 ans à des réductions sur les activités culturelles et de loisirs.

Ces dernières années, lors du renouvellement de la carte, on a constaté que $10 \%$ des possesseurs de la carte ne la rachètent pas. Dans le même temps, $30 \%$ de la population des 12-18 ans qui ne la possédaient pas l’année précédente achètent la carte. On fait l’hypothèse que l’effectif de la population des 12-18 ans est constant et que l’évolution va rester la même pour les prochaines années.
En 2018, 80 % des jeunes de 12-18 ans ne possédaient pas la carte.

Voici le graphe probabiliste de sommets $A$ et $B$ où le sommet $A$ représente l’état « posséder une carte jeune » et $B$ l’état « ne pas posséder une carte jeune » associé à ce phénomène.

La distribution initiale est $P\left(X_0=A\right)=0,2$ et $P\left(X_0=A\right)=0,8$ où $\left(X_n\right)$ est la chaîne de Markov associée à ce processus.
$\quad$

$\quad$

II Lien avec les matrices

À toute étape $k$, $k\in \N$, on représente la loi de probabilité de la variable aléatoire $X_k$ d’une chaîne de Markov à l’aide d’une matrice ligne $\pi_k=\begin{pmatrix}a_k&b_k\end{pmatrix}$ $\Big($respectivement $\pi_k=\begin{pmatrix} a_k&b_k&c_k\end{pmatrix}\Big)$.
La matrice $\pi_0$ représente donc la distribution initiale.

Exemple : Dans l’exemple précédent on a donc $\pi_0=\begin{pmatrix}0,2&0,8\end{pmatrix}$

Définition 7 : La matrice de transition associée à une chaîne de Markov à $n$ états, $n\in \N^*$, est la matrice carrée $T=\left(t_{ij}\right)$ d’ordre $n$ dont le coefficient $t_{ij}$ est le poids de l’arête allant du sommet $s_i$ au sommet $s_j$ (si l’arête n’existe pas alors $t_{ij}=0$).

Exemples :

Cas $n=2$

La matrice de transition est $T=\begin{pmatrix}0,9&0,1\\0,3&0,7\end{pmatrix}$
Cas $n=3$

La matrice de transition est $T=\begin{pmatrix}0,5&0,4&0,1\\0,1&0,2&0,7\\0,2&0,2&0,6\end{pmatrix}$

Propriété 1 : On considère une chaîne de Markov $\left(X_n\right)$ de distribution initiale $\pi_0$ et de matrice de transition $T$.
La matrice ligne donnant la distribution à l’étape $k+1$, $k\in \N$, est $\pi_{k+1}=\pi_kT$.

Preuve Propriété 1

On va montrer la propriété dans le cas d’une chaîne de Markov à $3$ états $a$, $b$ et $c$ mais cela se généralise facilement aux chaînes de Markov à $q$ états.

Pour tout entier naturel $k$, les événements $\lbrace X_k=a\rbrace$, $\lbrace X_k=b\rbrace$ et $\lbrace X_k=c\rbrace$ forment un système complet d’événement fini.
D’après la formule des probabilités totales on a pour tout $x_j\in\brace a,b,c\rbrace$ :
$$\left(X_{k+1}=x_j\right)=P_{\left(X_k=a\right)}\left(X_{k+1}=x_j\right)P\left(X_k=a\right)+P_{\left(X_k=b\right)}\left(X_{k+1}=x_j\right)P\left(X_k=b\right)+P_{\left(X_k=c\right)}\left(X_{k+1}=x_j\right)P\left(X_k=c\right)$$
Ainsi $\left(X_{k+1}=x_j\right)$ est le $j$-ième coefficient de la matrice ligne $\pi_kT$.
Par conséquent $\pi_{k+1}=\pi_kT$.
$\quad$

[collapse]

$\quad$

Propriété 2 : On considère une chaîne de Markov $\left(X_n\right)$ de distribution initiale $\pi_0$ et de matrice de transition $T$.
La matrice ligne donnant la distribution à l’étape $k$, $k\in \N$, est $\pi_k=\pi_0T^k$.

Preuve Propriété 2

On considère une chaîne de Markov à $p$ état.
On va raisonner par récurrence sur $k$.

Initialisation : Si $k=0$ alors $T^0=I_p$ car $T\neq O_p$ (la somme des coefficients, tous positifs, de chacune des lignes vaut $1$; il y a donc au moins un coefficient de $T$ non nul par ligne.)
Par conséquent $\pi_0T^0=\pi_0$.
La propriété est vraie au rang $0$.

Hérédité : On suppose la propriété vraie au rang $k$ : $\pi_k=\pi_0T^k$.
$\begin{align*} \pi_{k+1}&=\pi_kT\\
&=\pi_0T^kT\\
&=\pi_0T^{k+1}\end{align*}$
La propriété est vraie au rang $k+1$.

Conclusion : La propriété est vraie au rang $0$ et est héréditaire.
Pour tout entier naturel $k$ on a donc $\pi_k=\pi_0T^k$.
$\quad$

[collapse]

$\quad$

Exemple : Deux grossistes A et B se partagent la clientèle d’un liquide industriel.
On suppose que le nombre total de clients reste fixe d’une année sur l’autre.
En 2017, $45 \%$ des clients se fournissaient chez le grossiste A et $55 \%$ chez le grossiste B.
D’une année sur l’autre, $6 \%$ des clients du grossiste A deviennent clients du grossiste B tandis que le grossiste B conserve $86 \%$ de ses clients.
Chaque année, on choisit au hasard un client ayant acheté le liquide.
Pour tout entier naturel $n$ on note :

$a_n$ la probabilité qu’il soit client du grossiste A en (2017$+n$),
$b_n$ la probabilité qu’il soit client du grossiste B en (2017$+n$).

Pour tout entier naturel $n$, on note $P_n = \begin{pmatrix}a_n&b_n\end{pmatrix}$ la matrice ligne représentant l’état probabiliste de l’année (2017$+n$).
On a donc $P_0 = \begin{pmatrix}0,45& 0,55\end{pmatrix}$.

On obtient le graphe probabiliste suivant :

Ainsi la matrice de transition est $T=\begin{pmatrix} 0,94&0,06\\0,14&0,86\end{pmatrix}$
$\quad$
En 2020 on a $n=3$.
Ainsi, $P_3=P_0T^3=\begin{pmatrix}0,572&0,428\end{pmatrix}$.
Le grossiste A possédera donc, en 2020, $57,2\%$ des parts de marché et le grossiste B $42,8\%$.

Définition 8 : On dit qu’une distribution $\pi$, représentée à l’aide d’une matrice ligne, est stationnaire pour une chaîne de Markov dont la matrice de transition est $T$ si $\pi=\pi T$.

Remarque : On parle parfois d’état stable.

Exemple : on considère la matrice de transition $T=\begin{pmatrix} 0,94&0,06\\0,14&0,86\end{pmatrix}$ d’une chaîne de Markov $\left(X_n\right)$. Si cette chaîne possède un état stable $\pi=\begin{pmatrix}x&y\end{pmatrix}$ alors $\pi=\pi T$ et $x+y=1$
$\ssi \begin{cases} 0,94x+0,14y=x\\0,06x+0,86y=y\\x+y=1\end{cases}$
$\ssi \begin{cases}0,14y=0,06x\\0,06x=0,14y\\x+y=1\end{cases}$
$\ssi \begin{cases} y=\dfrac{3}{7}x\\x+y=1\end{cases}$
$\ssi \begin{cases} y=\dfrac{3}{7}x\\x+\dfrac{3}{7}x=1\end{cases}$
$\ssi \begin{cases}y=\dfrac{3}{7}x\\\dfrac{10}{7}x=1\end{cases}$
$\ssi \begin{cases}x=0,7 \\y=0,3\end{cases}$
La distribution stationnaire est donc, si elle existe, $\pi=\begin{pmatrix} 0,7&0,3\end{pmatrix}$.

Remarque : Dans les problèmes étudiés, la distribution stationnaire correspondra souvent à l’état probabiliste du processus sur le long terme.
Dans l’exemple précédent, sur le long terme, $70\%$ des clients se fourniront chez le grossiste A.

$\quad$