Accueil  / Semaine 11 / Les chaînes de Markov

Les chaînes de Markov

Petit rappel

Il est possible que vous sentiez le besoin de revoir le texte sur les vecteurs et matrices et le texte sur les probabilités de la première semaine avant de lire le présent texte. Dans ce cas, n’hésitez pas à les revoir.

Introduction aux chaînes de Markov

Une chaîne de Markov est un processus aléatoire portant
sur un nombre fini d’états, avec des probabilités de transition sans mémoire.

Exemple (chaîne de Markov à deux états).
On pense qu’un individu non endetté a une possibilité sur 3 de devenir endetté. Un individu endetté a une possibilité sur 6 de régler ses dettes.

On représente une chaîne de Markov avec une matrice de transition.
Chaque rangée de la matrice correspond à un état et donne la probabilité
de passer à un autre état. Dans le cas de notre individu endetté,
la matrice de transition est :

\left [ \begin{array}{lll}
 & \textrm{Sans dette} & \textrm{Avec dette} \\
\textrm{Sans dette} & 2/3 & 1/3 \\
\textrm{Avec dette} & 1/6 & 5/6
\end{array}  \right ].

Une matrice de transition se reconnaît parce que toutes les valeurs sont entre 0 et 1 inclusivement et que la somme de chaque rangée est 1.

Naturellement, pour avoir une chaîne de Markov, il faut répéter
le nombre de transitions possibles. Dans notre cas, supposons qu’à chaque
jour qui passe, la matrice de transition s’applique. Si l’individu n’est pas endetté au départ, après un jour il y aura une probabilité de 1/3 qu’il soit endetté :


\left [ \begin{array}{ll}
1 & 0
\end{array} \right ]
\left [ \begin{array}{ll}
 2/3 & 1/3 \\
 1/6 & 5/6
\end{array}  \right ]=
\left [ \begin{array}{ll}
2/3 & 1/3
\end{array} \right ]
.

Après deux jours, il aura autant de possibilités d’être endetté que de ne pas l’être :


\left [ \begin{array}{ll}
1 & 0
\end{array} \right ]
\left [ \begin{array}{ll}
 2/3 & 1/3 \\
 1/6 & 5/6
\end{array}  \right ]^2=
\left [ \begin{array}{ll}
1/2 & 1/2
\end{array} \right ]
.

Et ainsi de suite. On peut se demander ce qui se passera après un très long délai, disons un an ?


\left [ \begin{array}{ll}
1 & 0
\end{array} \right ]
\left [ \begin{array}{ll}
 2/3 & 1/3 \\
 1/6 & 5/6
\end{array}  \right ]^{356}= ?

Il suffit alors de savoir calculer les puissances de la matrice de transition. Dans tous les cas qui nous concernent, ces puissances convergent rapidement vers une matrice fixe : cela signifie qu’après avoir calculé 2, 3, 10 ou 20 puissances, la matrice ne change pratiquement plus :


\left [ \begin{array}{ll}
 2/3 & 1/3 \\
 1/6 & 5/6
\end{array}  \right ]^2=
\left [ \begin{array}{ll}
 1/2 & 1/2 \\
 1/4 & 3/4
\end{array}  \right ]


\left [ \begin{array}{ll}
 2/3 & 1/3 \\
 1/6 & 5/6
\end{array}  \right ]^5=
\left [ \begin{array}{ll}
 0.34375 & 0.65625 \\
 0.328125 & 0.671875
\end{array}  \right ]


\left [ \begin{array}{ll}
 2/3 & 1/3 \\
 1/6 & 5/6
\end{array}  \right ]^{10}=
\left [ \begin{array}{ll}
 0.33365885 & 0.66634115 \\
 0.33317057 & 0.66682943
\end{array}  \right ]


\left [ \begin{array}{ll}
 2/3 & 1/3 \\
 1/6 & 5/6
\end{array}  \right ]^{100}=
\left [ \begin{array}{ll}
 0.33333333 & 0.66666667 \\
 0.33333333 & 0.6666666
\end{array}  \right ]
.

On voit, par ces matrices, qu’après un an, 2 ans ou 10 ans, un individu, qu’il débute avec une dette ou sans dette, aura une probabilité de 2/3 d’être endetté !

Définition. Une matrice de transition est dite régulière si elle ne contient aucun zéro.

Définition. Une matrice de transition est dite ergodique si elle permet de passer de n’importe quel état à n’importe quel autre (mais pas nécessairement en une seule étape).

Observez que si la matrice de transition n’a aucun zéro, alors, dans une seule étape, il est possible de passer de n’importe quel état à n’importe quel autre.

Proposition. Une matrice de transition régulière est ergodique.

Proposition. Les puissances d’une matrice de transition régulière convergent vers une matrice où chaque colonne a une seule valeur.

À cause de cette proposition, nous savons qu’avec une chaîne de Markov dotée d’une matrice de transition régulière, les probabilités vont nécessairement converger, sans égard à l’état de départ. Et cet état final
vers lequel les probabilités convergent constitue le seul vecteur propre unitaire de la matrice :


\left [ \begin{array}{ll}
1/3 & 2/3
\end{array} \right ]
\left [ \begin{array}{ll}
 2/3 & 1/3 \\
 1/6 & 5/6
\end{array}  \right ]=
\left [ \begin{array}{ll}
1/3 & 2/3
\end{array} \right ]
.

Proposition. Une matrice ergodique, non nécessairement régulière, a un seul vecteur propre unitaire.

Lectures complémentaires

Article amusant (et utile ?) sur les chaînes de Markov :

- Doing the Martin Shuffle (with your iPod).