Déjà plus de
1 million
d'inscrits !
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 .
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 .
Cette loi est représentée par une matrice ligne dont la somme des termes vaut .
Définition : matrice de transition
La matrice de transition d’un graphe probabiliste d’ordre dont les sommets sont numérotés de à est la matrice carrée d’ordre , où le terme figurant en ligne et colonne est égal au poids de l’arête allant de vers , si cette arête existe ou à sinon.
Propriété : matrice de transition d’un graphe probabiliste
On a alors :
Recherche d’un état stable
Définition :
Un état probabiliste 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 , c’est-à-dire si :
Propriété admise :
Pour tout graphe probabiliste connexe à ou sommets, de matrice de transition , il existe un unique état stable ou , solution de l’équation matricielle .
Cet état stable est indépendant de l’état initial.
Et si tend vers l’infini, alors l’état probabiliste tend vers l’état stable .