Médaille
N°1 pour apprendre & réviser du collège au lycée.
Graphes probabilistes

Déjà plus de

1 million

d'inscrits !

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

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

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

Définition : matrice de transition

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

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

  • nn désigne un entier naturel non nul.
  • MM est la matrice de transition d’un graphe probabiliste
  • P0P_0 est la matrice ligne décrivant l’état initial.
  • PnP_n est l’état probabiliste à l’étape nn.

On a alors : Pn=P0×MnPn=P0\times M^n

Recherche d’un état stable

Définition :

Un état probabiliste PP 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 MM, c’est-à-dire si :

P×M=PP\times M=P

Propriété admise :

Pour tout graphe probabiliste connexe à 22 ou 33 sommets, de matrice de transition MM, il existe un unique état stable P=(xy)\text P=\begin{pmatrix} x&y \end{pmatrix} ou P=(xyz)\text P=\begin{pmatrix} x&y&z \end{pmatrix}, solution de l’équation matricielle P×M=PP\times M=P.

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

Et si nn tend vers l’infini, alors l’état probabiliste PnP_n tend vers l’état stable PP.

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