Un graphe pondéré est un graphe dans lequel chaque arête est affectée d’un nombre réel positif appelé poids de cette arête.
Définition
Un graphe probabiliste est un graphe orienté pondéré par des réels compris entre 0 et 1 et dans lequel la somme des poids des arêtes issues de chaque sommet est égale à 1.
Exemple
Le graphe suivant est un graphe probabiliste à deux états (C et T). On a 0,22+0,78=1 et 0,47+0,53=1.
Définitions
Une suite (Xn)n⩾0 de variables aléatoires est une chaîne de Markov à deux états a et b (respectivement à trois états a, b et c) lorsque, pour tous x0, x1, … , xk, xk+1 dans {a;b} (respectivement dans {a;b;c}), on a :
La probabilité pXk=xk(Xk+1=xk+1) s’appelle probabilité de transition de l’état xk à l’état xk+1.
L’ensemble {a;b} (respectivement {a;b;c}) est appelé espace des états.
Remarques
La définition d’une chaîne de Markov signifie que les états passés n’ont aucune influence sur les états futurs : seul l’état présent a son importance.
Remarques
Les variables aléatoires (Xn) ne sont pas nécessairement à valeurs réelles.
Remarques
La somme des probabilités de transition issues d’un même état est égale à 1.
Illustration à l’aide d’un graphe probabiliste :
On peut représenter une chaîne de Markov à l’aide d’un graphe probabiliste. Chaque sommet représente un état de la chaîne de Markov et les poids portés par les arêtes orientées représentent les probabilités de transitions.
Graphe d’une chaîne de Markov à deux états
pXk=a(Xk+1=b)=pa,b
Graphe d’une chaîne de Markov à trois états
pXk=c(Xk+1=b)=pc,b
Définition
La distribution initiale d’une chaîne de Markov (Xn) est la loi de probabilité de X0.
Application et méthode - 3
Énoncé
Ike n’aime pas prendre le bus pour aller à l’école et préfère prendre son vélo. Il n’utilise pas d’autre moyen de locomotion.
Chaque jour de la semaine, il va à l’école en bus avec une probabilité de 0,8 s’il ne l’a pas emprunté la fois précédente et avec une probabilité de 0,3 sinon.
Représenter la situation par un graphe probabiliste.
On repère en premier lieu le nombre d’états : on en a ici deux.
On construit alors un graphe probabiliste à deux sommets (un pour chaque état) et on traduit les probabilités de l’énoncé sous forme de pondérations dans le graphe
On complète en utilisant le fait que la somme des probabilités portées par les arêtes issues d’un même état vaut 1.
B
Représentation matricielle d’une chaîne de Markov
Définition
On considère une chaîne de Markov à n états, numérotés 1 ; … ; n, et on note E={1;…;n} l’espace des états.
La matrice de transition P associée à cette chaîne de Markov est la matrice carrée d’ordre n telle que, pour tout i∈E et pour tout j∈E, le coefficient pi,j correspond à la probabilité de transition de l’état i vers l’état j.
Remarque
Dans le programme, on se limite au cas où n=2 ou n=3.
Exemples
1. La chaîne de Markov représentée ci‑dessous par un graphe probabiliste a pour matrice de transition (0,50,80,50,2).
Le coefficient surligné 0,8 indique que la probabilité de passer de l’état 2 à l’état 1 vaut 0,8.
2. La chaîne de Markov représentée par le graphe probabiliste ci‑dessous a pour matrice de transition ⎝⎛0,50,70,30,10,20,40,40,10,3⎠⎞.
Remarque
La distribution initiale peut être représentée par une matrice ligne, souvent notée π0, dont le k‑ième coefficient correspond à la probabilité de l’état k à l’instant initial.
Propriétés
1. Les coefficients de la matrice de transition d’une chaîne de Markov sont des nombres appartenant à l’intervalle [0;1].
2. La somme des coefficients d’une ligne donnée de la matrice de transition est égale à 1.
Utilisation des cookies
En poursuivant votre navigation sans modifier vos paramètres, vous acceptez l'utilisation des cookies permettant le bon fonctionnement du service. Pour plus d’informations, cliquez ici.