• Manuel
 | 
• Feuille de route
 | 
• Glossaire
 | 
• FAQ
 | 
• Pense-bête
 | 
• Travaux notés
• Bibliowebographie

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 :

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é :

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

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

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 :

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.

Soit la matrice de transition, soit n’importe quel vecteur. Nous avons que les composantes du vecteur sont des moyennes pondérées des valeurs du vecteur . La valeur maximale des composantes de () ne peut que diminuer (), alors que la valeur minimale () ne peut qu’augmenter (). Il est facile de vérifier que si ou , alors ce qui implique que toutes les composantes du vecteur ont la même valeur. Si on suppose que (et ), alors est une séquence de valeurs strictement décroissante bornée par la bas par et par le théorème de la convergence monotone, existe () ; on peut en déduire que est un vecteur dont toutes les composantes sont égales à . Puisque cela est vrai pour tout vecteur , on en déduit que converge vers une matrice ayant toutes ses rangées égales à un même vecteur.

À 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 :

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).