Graphe pondéré

Un graphe est dit pondéré si chacune de ses arêtes est affecté d’un nombre positif (ou nul) que l’on appelle poids.

Le poids d’une chaîne (ou d’un chemin) est la somme des poids de ses arêtes.

Graphe probabiliste

On appelle graphe probabiliste un graphe orienté et pondéré tel que :

• Pour chaque sommet, la somme des poids des arcs issus de ce sommet vaut $1$.

• Il y a au plus $1$ arrête orientée reliant chaque sommet.

Définition

Soit $G$ un graphe probabiliste d’ordre $n$. On appelle matrice de transition du graphe $G$, la matrice carrée d’ordre $n$ dont le coefficient à la ligne $i$ et à la colonne $j$ est égal au poids de l’arête reliant le sommet $i$ au sommet $j$.

Une telle matrice est qualifiée de stochastique car la somme des coefficients de chacune de ses lignes vaut $1$.

Définition

Soit $(X_n)$ une suite de variables aléatoires discrètes définies sur un même univers $\Omega$ et à valeurs dans un ensemble $E$. On dit que $(X_n)$ définit une chaîne de Markov sur $E$ si pour tout $n\in \mathbb{N}$ et tout $x_0,x_1,x_2,\dots ,x_n\in E$, l’événement $(X_n=x_n)$ ne dépend que de l’événement antérieur $(X_{n-1}=x_{n-1})$ (et pas des précédents) ; autrement dit, si $P_{(X_{n-1}=x_{n-1})\cap \cdots \cap (X_0=x_0)}(X_n=x_n)=P_{(X_{n-1}=x_{n-1})}(X_n=x_n)$.

De plus, l’ensemble $E$ est appelé espace des états de la chaîne de Markov.

Chaîne de Markov homogène

Soit $(X_n)$ une chaîne de Markov dont on note $E$ l’espace des états. Alors $(X_n)$ est dite homogène si pour tout $n\in \mathbb{N}$ et pour tout $x$, $y\in E$, la probabilité $P_{(X_n=x)}(X_{n+1}=y)$ est indépendante de $n$.

En termes mathématiques, cela signifie que pour tout $n\in \mathbb{N}$ et pour tout $x$, $y\in E$, $P_{(X_n=x)}(X_{n+1}=y)=P_{(X_0=x)}(X_1=y)$.

Matrice de transition

Soit $(X_n)$ une chaîne de Markov homogène dont on note $E=\{x_1,x_2,\dots ,x_m\}$ l’espace des états. La matrice de transition de $(X_n)$ est la matrice carrée d’ordre $m$ dont le coefficient situé à la $i$-ième ligne et à la $j$-ième colonne est égal à $p_{i,j}=P_{(X_n=x_i)}(X_{n+1}=x_j)$.

Graphe associé à une chaîne de Markov

Soit $(X_n)$ une chaîne de Markov homogène dont on note $E=\{x_1,x_2,\dots ,x_m\}$ l’espace des états. On associe à cette chaîne de Markov un graphe probabiliste $G$ d’ordre $m$ dont les sommets sont les états $x_i$ et dont les arêtes $x_i-x_j$ sont pondérées par les poids $p_{i,j}=P_{(X_n=x_i)}(X_{n+1}=x_j)$.

La matrice de transition de $(X_n)$ est égale à la matrice de transition du graphe probabiliste $G$ : il s’agit donc aussi d’une matrice stochastique.

Proposition

Soit $(X_n)$ une chaîne de Markov homogène dont on note $E=\{x_1,x_2,\dots ,x_m\}$ l’espace des états. On pose $p_{i,j}^{(k)}=P_{(X_0=x_i)}(X_k=x_j)$ pour tout $k\in {\mathbb{N}}^{\ast }$ (qui représente la probabilité que la chaîne de Markov $(X_n)$ passe de l’état $x_i$ à l’état $x_j$ en $k$ étapes). On a : $$p_{i,j}^{(k)}=\sum _{q=1}^m{p}_{i,q}^{(k-1)}\times p_{q,j}^{(1)}=p_{i,1}^{(k-1)}\times p_{1,j}^{(1)}+p_{i,2}^{(k-1)}\times p_{2,j}^{(1)}+\cdots +p_{i,m}^{(k-1)}\times p_{m,j}^{(1)}$$ De plus, comme $(X_n)$ est homogène, $p_{i,j}^{(k)}=p_{i,j}^{(n+k)}$ pour tout $n\in \mathbb{N}$.

Lien avec la matrice de transition

En reprenant les notations précédentes et en notant $M$ la matrice de transition de $(X_n)$, alors $p_{i,j}^{(k)}$ est le coefficient à la ligne $i$ et à la colonne $j$ de la matrice $M^k$.

Définition

Soit $(X_n)$ une chaîne de Markov homogène dont on note $E=\{x_1,x_2,\dots ,x_m\}$ l’espace des états. On appelle suite des distributions de $(X_n)$ la suite de matrices $({\pi }_n)$, définie pour tout $n\in \mathbb{N}$ par ${\pi }_n=\left(\begin{array}{cccc}P(X_n=x_1)& P(X_n=x_2)& \dots & P(X_n=e_m)\end{array}\right)$.

${\pi }_n$ est donc une matrice ligne d’ordre $m$ et est appelée distribution au temps $n$.

${\pi }_0$ (la distribution au temps $0$) est appelée distribution initiale.

Relation entre ${\pi }_{n+1}$ et ${\pi }_n$

En reprenant les notations de la définition précédente et en notant $M$ la matrice de transition de $(X_n)$, alors la suite $({\pi }_n)$ vérifie une relation de récurrence donnée pour tout $n\in \mathbb{N}$ par ${\pi }_{n+1}={\pi }_{n}M$.

On en déduit que pour tout $n\in \mathbb{N}$, ${\pi }_n={\pi }_0{M}^n$.

Définition

Soit $(X_n)$ une chaîne de Markov homogène de matrice de transition $M$. Une distribution $\pi$ est invariante si les deux conditions suivantes sont respectées :

• $\pi M=\pi$ (donc si $\pi$ est une distribution à un temps $n$, on a $\pi ={\pi }_n$ et cette condition se résume à avoir ${\pi }_n={\pi }_{n}M={\pi }_{n+1}$).

• La somme des coefficients de $\pi$ vaut $1$.

Existence et unicité de la distribution invariante au temps $n$

Soit $(X_n)$ une chaîne de Markov homogène de matrice de transition $M$.

Si $M$ ne possède aucun coefficient non nul autre que sur sa diagonale, alors $(X_n)$ admet une unique distribution invariante $\pi$.

Convergence de la distribution

Soit $(X_n)$ une chaîne de Markov homogène dont on note $({\pi }_n)$ la suite des distributions.

• Si $({\pi }_n)$ est une suite de matrices convergente, alors elle converge vers une distribution invariante $\pi$.

• Si le cardinal de l’ensemble des états de $(X_n)$ est $2$, alors $({\pi }_n)$ est convergente (et converge vers la distribution invariante $\pi$).