Fiche de révision : Chaînes de Markov

Graphes probabilistes et matrices associées

• On appelle graphe pondéré un graphe (orienté ou non) dont les arêtes sont affectées d’un nombre positif ou nul.
• Ces nombres s’appellent les poids des arêtes entre les sommets.
• $G$ est un graphe d’ordre $n$ orienté et pondéré. On numérote ses sommets par les nombres $1$, $2$, …, $n$.
• $G$ est un graphe probabiliste lorsque, pour tous entiers $i$ et $j$ de $\lbrace 1,\,…,\,n\rbrace$ :
• il y a au plus $1$ arête entre deux sommets $i$ et $j$ du graphe ;
• la somme des poids des arêtes partant d’un sommet $i$ est égale à $1$.
• Concrètement, le poids de chaque arête orientée de $i$ vers $j$ est la probabilité d’obtenir $j$ sachant $i$. C’est donc un nombre appartenant à $[0\ ;\, 1]$.

• Méthodologie pour construire un graphe probabiliste :
• on repère le nombre d’issues de l’univers ;
• c’est l’ordre du graphe ;
• on représente chaque issue par un sommet $i$ ;
• le poids de l’arête qui va du sommet $i$ vers $j$ est la probabilité d’avoir $j$ sachant $i$ ;
• on complète le graphe probabiliste sachant que la somme des poids des arêtes partant d’un même sommet vaut $1$.
• $G$ est un graphe probabiliste d’ordre $n$, de sommets numérotés de $1$ à $n$.
  $T$ est la matrice carrée d’ordre $n$ définie par : pour tous $i$ et $j$ de $\lbrace 1,\,…,\,n\rbrace$, $(T)_{i,j}$ est égal au poids de l’arête allant de $i$ vers $j$.
• $T$ est appelée la matrice de transition du graphe probabiliste $G$.
• La matrice de transition n’est pas la matrice d’adjacence, dont les coefficients donnent le nombre entier d’arêtes entre deux sommets. Dans la matrice de transition d’un graphe probabiliste, tous les coefficients appartiennent à $[0\ ;\, 1]$.
• Dans le cas d’un graphe probabiliste, le coefficient $(T)_{i,j}$ est égal à la probabilité d’obtenir l’événement représenté par le sommet $j$ sachant l’événement représenté par $i$.
• Soit $G$ un graphe probabiliste et $T$ la matrice de transition associée.
• La somme des coefficients d’une ligne de la matrice vaut $1$.

Chaînes de Markov

• Soit $(X_n)_{n\in \mathbb N}$ une suite de variables aléatoires définies sur un univers, et à valeurs dans un ensemble de nombres $E$.
• Les valeurs de $E$ s’appellent des états.
• $E$ porte le nom d’espace des états.
• Pour tout $n\in \mathbb N$ et pour tout état $i$ de $E$, l’événement $[X_n =i]$ se traduit par : « Le processus est dans l’état $i$ à l’étape $n$ ».
• Soit $(X_n)_{n\in \mathbb N}$ une suite de variables aléatoires à valeurs dans l’espace des états $E$.
• $(X_n)_{n\in \mathbb N}$ est une chaîne de Markov sur $E$ lorsque, pour tous $i$ et $j$ de $E$ :
• l’événement $[X_{n+1} = i]$ dépend uniquement de l’état antérieur de $X_n$, et pas des états qui précédent ;
• la probabilité de passer d’un état $i$ à un état $j$ ne dépend pas de $n$.
• Méthodologie pour reconnaître une chaîne de Markov :
• on identifie l’espace des états de la variable aléatoire ;
• on justifie que l’état de $X_{n+1}$ à l’étape $(n+1)$ ne dépend que de l’état de $X_n$ à l’étape $n$ ; et pas des états précédents ;
• on justifie que la probabilité pour passer d’un état à un autre ne dépend pas du numéro de l’étape.
• $(X_n)_{n \in \mathbb N}$ est une chaîne de Markov sur $E$ à $2$ (resp. $3$) états.
• La matrice de transition de cette chaîne de Markov est la matrice carrée $T$ d’ordre $2$ (resp. $3$), telle que, pour tous $i$ et $j$ de $E$ :
• $(T)_{i,j}$ vaut la probabilité de passer de l’état $i$ à l’état $j$ ;
• $(T)_{i,j}$ est le poids de l’arête allant de $i$ vers $j$ sur le graphe probabiliste associé.
• si cette arête n’existe pas, cette probabilité et le coefficient de la matrice associé valent $0$.
• $(X_n)_{n \in \mathbb N}$ est une chaîne de Markov sur $E$ à $2$ ou $3$ états.
• La loi de probabilité de la variable aléatoire $X_0$ est appelée la distribution initiale de la chaîne $(X_n)_{n \in \mathbb N}$.
• On la représente sous la forme d’une matrice ligne à $2$ ou $3$ colonnes et on la note $\pi_0$ :
• s’il y a $2$ états : $\pi_0=\begin{pmatrix} p(X_0=1) & p(X_0=2) \end{pmatrix}$ ;
• s’il y a $3$ états : $\pi_0=\begin{pmatrix} p(X_0=1) & p(X_0=2) & p(X_0=3) \end{pmatrix}$.
• $(X_n)_{n \in \mathbb N}$ est une chaîne de Markov sur $E$ à $2$ ou $3$ états.
• La loi de probabilité de la variable aléatoire $X_n$ est appelée la distribution après $n$ transitions de la chaîne $(X_n)_{n \in \mathbb N}$.
• On la représente sous la forme d’une matrice ligne à $2$ ou $3$ colonnes et on la note $\pi_n$ :
• s’il y a $2$ états : $\pi_n=\begin{pmatrix} p(X_n=1) & p(X_n=2) \end{pmatrix}$ ;
• s’il y a $3$ états : $\pi_n=\begin{pmatrix} p(X_n=1) & p(X_n=2) & p(X_n=3) \end{pmatrix}$.
• $\pi_0$ est la matrice ligne des probabilités d’avoir $A$ ou $B$ (ou éventuellement $C$) à la première expérience aléatoire. De même, $\pi_n$ est la matrice ligne des probabilités d’avoir $A$ ou $B$ (ou éventuellement $C$) à la $n \text{-ième}$ étape.
• $(X_n)_{n\in \mathbb N}$ est une chaîne de Markov sur $E$ à $2$ (ou $3$) états.
  Soit $\pi_0$ la matrice ligne représentant sa distribution initiale ; $\pi_n$ la matrice ligne représentant sa distribution après $n$ transitions ; et $T$ la matrice de transition de la chaîne $X_n$.
• Pour tout entier naturel $n$ : $\pi_{n+1}=\pi_n\times T$.
• Pour tout entier naturel $n$ : $\pi_n=\pi_0\times T^n$.
• La matrice $\pi_n=\pi_0\times T^n$ se calcule en faisant le produit de $\pi_0$ par $T^n$ dans cet ordre.
• $(X_n)_{n\in \mathbb N}$ est une chaîne de Markov sur $E$ à $2$ (ou $3$) états.
  Soit $T$ sa matrice de transition et $n\in \mathbb N^*$.
• Le coefficient $(T^n)_{i,j}$ situé à la $i \text{-ème}$ ligne et la $j \text{-ième}$ colonne de $T^n$ est la probabilité de passer de l’état $i$ à l’état $j$ en $n$ transitions.

Distributions invariantes d’une chaîne de Markov à $2$ ou $3$ états

• Soit $(X_n)_{n\in \mathbb N}$ une chaîne de Markov à $2$ (ou $3$) états et $T$ sa matrice de transition. Supposons qu’il existe $\pi$ une matrice ligne à $2$ (ou $3$) colonnes telle que :
• $\pi=\pi\times T$ ;
• et la somme des coefficients de $\pi$ est égale à $1$.
• Cette matrice est alors appelée distribution invariante de la chaîne de Markov.
• Pour prouver qu’une matrice ligne $\pi$ est une distribution invariante d’une chaîne de Markov, il suffit de calculer $\pi\times T$ et de montrer que cette matrice est $\pi$.
• Méthodologie pour chercher une distribution invariante pour une chaîne de Markov :
• Il faut résoudre l’équation matricielle $(E):\pi=\pi\times T$.
• On nomme les coefficients de $\pi=\begin{pmatrix} a & b & c \end{pmatrix}$ ($\pi=\begin{pmatrix} a & b \end{pmatrix}$ s’il y a $2$ états).
• On calcule la matrice ligne $\pi\times T$.
• L’équation $(E)$ devient un système de $3$ équations à $3$ inconnues (resp. de $2$ équations à $2$ inconnues), que l’on résout.
• On n’oublie pas de vérifier que la somme des coefficients de $\pi$ est égale à $1$.
• Soit $(X_n)_{n\in \mathbb N}$ une chaîne de Markov à $2$ (ou $3$) états et $T$ sa matrice de transition.
• Si la matrice $T$ n’a pas de coefficient égal à $0$, alors la suite des matrices lignes $(\pi_n)_{n\in \mathbb N}$ converge vers une distribution invariante.
• De plus, cette distribution est unique.
• Cette propriété nous permet de trouver les états stables des chaînes de Markov.

o