graphe probabiliste

Imaginez une machine qui est soit en marche, soit en panne. À chaque contrôle, elle peut rester dans le même état ou passer dans l'autre. Une flèche indique chaque passage possible et le nombre porté par la flèche donne sa probabilité.

Depuis un même état, les nombres totalisent 1 : toutes les possibilités du prochain contrôle sont ainsi réparties. Ce dessin est un graphe probabiliste. Il rend visibles les états et les changements en une étape, puis permet de prévoir plusieurs étapes successives.

Un graphe probabiliste est un graphe orienté pondéré dont les sommets sont les états possibles d'un système. Pour deux états donnés, il existe au plus un arc dans un sens fixé. Le poids porté par l'arc allant de l'état i à l'état j est un réel compris entre 0 et 1 : il représente la probabilité de passer de i à j en une étape. Une boucle représente donc la probabilité de rester dans le même état.

Pour chaque sommet, la somme des poids de tous les arcs sortants vaut exactement 1. Si p_ij désigne la probabilité de passer de l'état i à l'état j et si le système possède n états, les deux conditions numériques s'écrivent : Une transition de probabilité nulle peut être représentée par un arc de poids 0 ou, selon la convention de dessin retenue, par l'absence d'arc.

En rangeant les nombres p_ij dans une matrice, avec l'état de départ en ligne et l'état d'arrivée en colonne, on obtient une matrice de transition stochastique par lignes. Le graphe décrit alors une chaîne de Markov à temps discret lorsque la loi du prochain état ne dépend du passé qu'à travers l'état présent. Les puissances de la matrice donnent les probabilités de transition en plusieurs étapes.

Le graphe réunit quatre éléments nécessaires. Les sommets nomment les états possibles. Les arcs orientés indiquent quels passages peuvent avoir lieu en une étape. Les poids, compris entre 0 et 1, quantifient ces passages. Enfin, la normalisation impose un total de 1 à tous les poids qui partent d'un même sommet.

L'origine et l'extrémité d'un arc déterminent la case correspondante de la matrice de transition ; son poids fournit la valeur de cette case. Réciproquement, une ligne de la matrice donne tous les arcs issus de l'état associé. L'emplacement des sommets, la courbure des flèches et les couleurs facilitent la lecture, mais ne définissent pas le modèle. Les états, les orientations et les poids suffisent à construire la matrice. Pour calculer l'évolution des probabilités, il faut aussi connaître la loi initiale et supposer que le processus vérifie la propriété de Markov.

Une machine est observée à intervalles réguliers. Ses deux états sont M, « en marche », et P, « en panne ». Depuis M, elle reste en marche avec la probabilité 0,9 et tombe en panne avec la probabilité 0,1. Depuis P, elle redémarre avec la probabilité 0,4 et reste en panne avec la probabilité 0,6. Au départ, elle est en marche avec certitude.

1. Dans l'ordre M, P, la matrice de transition est : Chaque ligne totalise 1. La figure reprend exactement les quatre transitions.

2. Après un contrôle, les probabilités des états M et P sont respectivement 0,9 et 0,1.

3. Pour être en marche après deux contrôles, la machine peut suivre M → M → M ou M → P → M. La probabilité cherchée vaut 0,9 × 0,9 + 0,1 × 0,4 = 0,85.

4. La probabilité d'être en panne vaut de même 0,9 × 0,1 + 0,1 × 0,6 = 0,15. Le contrôle final est immédiat : 0,85 + 0,15 = 1. La distribution après deux étapes est donc (0,85 ; 0,15).

Pour représenter un système comportant peu d'états, dessinez un sommet par état et une flèche par transition possible. Le graphe est préférable à une matrice lorsque l'objectif est de voir rapidement les passages autorisés et les retours vers un même état.

Pour vérifier le modèle, additionnez les poids qui quittent chaque sommet. Un total différent de 1 signale une possibilité oubliée ou des probabilités incohérentes ; il faut corriger les données avant tout calcul.

Pour prévoir plusieurs étapes, rangez les poids dans la matrice de transition, puis multipliez la distribution initiale par les puissances successives de cette matrice. Cette écriture devient plus maniable que le dessin lorsque le nombre d'états ou d'étapes augmente.

Si les probabilités du prochain état dépendent d'un passé plus long que le seul état présent, le graphe sur les états initiaux ne suffit pas à décrire une chaîne de Markov. On peut parfois élargir les états pour y inclure l'information nécessaire ; sinon, un autre modèle probabiliste est requis.

Graphe orienté pondéré et graphe probabiliste. Un graphe orienté pondéré accepte des poids quelconques. Il devient probabiliste si chaque poids est compris entre 0 et 1 et si les poids sortant de tout sommet totalisent 1. Des poids 2 et 3 peuvent décrire des coûts, mais pas des probabilités de transition.

Graphe probabiliste et matrice de transition. Ils peuvent encoder les mêmes passages, mais sous deux formes. Le graphe rend les états et les arcs visibles ; la matrice range les probabilités pour le calcul. Dans l'exemple, la boucle M → M de poids 0,9 devient la case de la ligne M et de la colonne M.

Somme sortante incorrecte. Si les poids quittant un sommet totalisent 0,9 ou 1,1, le dessin ne donne pas une loi de probabilité à partir de cet état. Le symptôme se lit ligne par ligne dans la matrice ; il faut retrouver la transition absente ou corriger les poids.

Plusieurs mécanismes pour le même passage. La définition retient au plus un arc d'un sommet donné vers un autre. Si deux causes distinctes conduisent de M à P, leurs probabilités ne deviennent pas deux arcs parallèles : il faut les regrouper en une probabilité totale, lorsqu'elles décrivent des événements disjoints.

Convention de matrice inversée. Certaines présentations placent l'état de départ en colonne plutôt qu'en ligne. Les colonnes, et non les lignes, totalisent alors 1. Avant une multiplication, vérifiez l'ordre des états et le côté où agit la matrice ; sinon, même des nombres justes produisent une évolution fausse.

Transition en plusieurs étapes. Une probabilité sur deux étapes n'est ni la somme des poids d'un seul trajet, ni le produit choisi sans examiner les autres trajets. Il faut multiplier les poids le long de chaque chemin possible, puis additionner les produits des chemins qui ont les mêmes départ et arrivée.

chaîne de Markov — Approfondir la propriété de mémoire et l'évolution aléatoire à temps discret que le graphe représente.

matrice de transition — Passer du dessin au calcul matriciel des probabilités après plusieurs étapes.

Markov : les chaînes de l'espoir — Découvrir un article consacré aux chaînes de Markov et à leur portée.