Définition
On appelle graphe probabilisé : un graphe orienté et pondéré dont la somme des poids des arêtes issues de chaque sommet vaut .
Exemple
Le graphe suivant est un graphe probabiliste :
On peut voir qu’il s’agit bien d’un graphe orienter et pondéré et que :
- La somme des poids des arêts issus de est .
- La somme des poids des arêts issus de est .
Définition
Etat probabiliste d’un système : C’est la loi de probabilité sur l’ensemble des états possibles au cour d’une étape .
Cette loi est représentée par une matrice ligne dont la somme des termes vaut .
Exemple
avec et les probabilités.
Lorsque alors on a : qui représente l’état probabiliste initial.
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.
Exemple
La matrice de ce graphe probabiliste es t:
Propriété
Si est l’état probabiliste à l’étape et l’état probabiliste initial, alors on a:
Où est la matrice de transition du graphe.
sinon.