Pré-requis
- Un graphe probabiliste est un graphe orienté et pondéré dont la somme des poids des arêtes issues de chaque sommet vaut .
- 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 de probabilité est représentée par une matrice ligne dont la somme des termes vaut .
On note ou la matrice ligne correspondant à l’état probabiliste à l’étape . - 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 . Il est égal à si cette arête n’existe pas. La somme des coefficients de chacune des lignes de est égale à .
- Si désigne un entier naturel non nul, la matrice de transition d’un graphe probabiliste, la matrice ligne décrivant l’état initial, l’état probabiliste à l’étape , alors
- Un état probabiliste est dit stable lorsque
Étude d’un exemple :
Le self le mercredi midi propose menus : Steak haché – frites ou Plat du jour.
On a remarqué que :
- Si un lycéen choisi le menu Steak haché – frites un mercredi, la probabilité qu’il le choisisse à nouveau le mercredi suivant est de .
- Si un lycéen choisi le menu Plat du jour un mercredi, la probabilité qu’il le choisisse à nouveau le mercredi suivant est de .
On sélectionne un lycéen au hasard et on note l’état « le lycéen choisit le menu Steak haché – frites » et l’état « le lycéen choisit le menu Plat du jour ».
Le premier mercredi des lycéens prennent le menu Steak haché – frites.
Etapes
Traduire les données de l’énoncé par un graphe probabiliste
Déterminer la matrice de transition de ce graphe
la ligne et la colonne
est le poids de l’arête
est le poids de l’arête
est le poids de l’arête
est le poids de l’arête
Donc ici la matrice est
Calculer l’état initial et
On a des lycéens qui prennent le premier jour le menu donc
donc des lycéens ont choisit le menu , donc
L’état probabiliste à l’instant est donc
Il suffira ensuite de remplacer par sa valeur pour effectuer les calculs.
Calculer l’état stable
Un état probabiliste est stable si .
Pour trouver l’état stable d’un graphe probabiliste d’ordre , on résout le système
Comme , l’état stable est solution du système :
L’état stable est donc .
Ce qui signifie : à long terme, le des lycéens choisiront le menu « steak haché – frites » et les restants le menu « plat du jour ».
Remarque : les états probabilistes à l’étape convergent vers l’état stable lorsque tend vers l’infini.