Fiche de révision : Graphes probabilistes

Graphes probabiliste et matrice de transition

Définition : graphe probabiliste

Un graphe probabiliste est un graphe orienté et pondéré dont la somme des poids des arêtes issues de chaque sommet vaut $1$.

Définition : état probabiliste

L’état probabiliste d’un système est une loi de probabilité sur l’ensemble des états possibles au cours d’une étape $n$.

Cette loi est représentée par une matrice ligne dont la somme des termes vaut $1$.

Définition : matrice de transition

La matrice de transition d’un graphe probabiliste d’ordre $n$ dont les sommets sont numérotés de $1$ à $n$ est la matrice carrée d’ordre $n$, où le terme figurant en ligne $i$ et colonne $j$ est égal au poids de l’arête allant de $i$ vers $j$, si cette arête existe ou à $0$ sinon.

Propriété : matrice de transition d’un graphe probabiliste

• $n$ désigne un entier naturel non nul.
• $M$ est la matrice de transition d’un graphe probabiliste
• $P_0$ est la matrice ligne décrivant l’état initial.
• $P_n$ est l’état probabiliste à l’étape $n$.

On a alors : $P_n=P_0\times M^n$

Recherche d’un état stable

Définition :

Un état probabiliste $P$ est dit stable lorsqu’il se conserve lors de la répétition de l’expérience aléatoire décrite par la matrice de transition $M$, c’est-à-dire si :

$$P\times M=P$$

Propriété admise :

Pour tout graphe probabiliste connexe à $2$ ou $3$ sommets, de matrice de transition $M$, il existe un unique état stable $\text P=\begin{pmatrix} x&y \end{pmatrix}$ ou $\text P=\begin{pmatrix} x&y&z \end{pmatrix}$, solution de l’équation matricielle $P\times M=P$.

Cet état stable est indépendant de l’état initial.

Et si $n$ tend vers l’infini, alors l’état probabiliste $P_n$ tend vers l’état stable $P$.

• La somme des termes d’une matrice ligne associée à un état probabiliste est toujours égale à $1$.