Graphe d'une chaîne de Markov et classification des états

Le graphe d'une chaîne de Markov et la classification des états sont des notions de la théorie des graphes utilisées en calcul des probabilités.

Graphe d'une chaîne de Markov

Graphe d'une chaîne de Markov non irréductible à espace d'états fini, possédant 3 classes : $\{2\}\to \{1,3\}$ et $\{4,5\}.$ Les classes $\{1,3\}$ et $\{4,5\}$ sont finales.

Le graphe $G$ d'une chaîne de Markov est le graphe orienté défini à partir de l'espace d'états $E$ et de la matrice de transition $P={\left(p_{i,j}\right)}_{(i,j)\in E^2}$ de cette chaîne de Markov :

• les sommets de $G$ sont les éléments de $E,$
• les arêtes de $G$ sont les couples $(i,j)\in E^2$ vérifiant $p_{i,j}>0.$

Classification des états

Pour $(i,j)\in E^2$, on dit que l'état $j$ est accessible à partir de l'état $i$ si et seulement s'il existe un entier $n\ge 0$ tel que $\mathbb{P}(X_n=j\mid X_0=i)>0.$ On note :

$\{j\leftarrow i\}\iff \{\mathrm{\exists }n\ge 0\text{ tel que }{p}_{i,j}^{(n)}>0\}.$

On dit que les états $i$ et $j$ communiquent si et seulement s'il existe $(n,m)\in {\mathbb{N}}^2$ tels que $\mathbb{P}(X_n=j\mid X_0=i)>0$ et $\mathbb{P}(X_m=i\mid X_0=j)>0.$ On note :

$\{j\leftrightarrow i\}\iff \{j\leftarrow i\text{ et }i\leftarrow j\}.$

La relation communiquer, notée $\leftrightarrow ,$ est une relation d'équivalence. Quand on parle de classe en parlant des états d'une chaîne de Markov, c'est généralement aux classes d'équivalence pour la relation $\leftrightarrow$ qu'on fait référence. Si tous les états communiquent, la chaîne de Markov est dite irréductible.

La relation être accessible, notée $\leftarrow ,$ s'étend aux classes d'équivalence : pour deux classes $C$ et $C^{\prime }$, on a

$\{C\leftarrow C^{\prime }\}\iff \{\mathrm{\exists }(i,j)\in C\times C^{\prime },i\leftarrow j\}\iff \{\mathrm{\forall }(i,j)\in C\times C^{\prime },i\leftarrow j\}.$

La relation $\leftarrow$ est une relation d'ordre entre les classes d'équivalence.

Une classe est dite finale si elle ne conduit à aucune autre, i.e. si la classe est minimale pour la relation $\leftarrow .$ Sinon, la classe est dite transitoire.

Soit

$M_{ij}=\{n\ge 0|P(X_n=j\mid X_0=i)>0\}.$

La période d'un état $i$ est le PGCD de l'ensemble $M_{ii}.$ Si deux états communiquent, ils ont la même période : on peut donc parler de la période d'une classe d'états. Si la période vaut 1, la classe est dite apériodique.

Classes, modulo différents sous-groupes, du cube vu comme le groupe $({\mathbb{Z}}_2^3,+),$ et classes finales de certaines marches aléatoires sur le cube.

La classification des états se lit de manière simple sur le graphe de la chaîne de Markov. Modèle:Exemple Modèle:Exemple

Graphe de 2 marches aléatoires élémentaires, respectivement sur le groupe cyclique ${\mathbb{Z}}_8$ et sur le groupe diédral $D_4.$

Lexique : graphes-chaînes de Markov

• L'état $j$ est accessible à partir de l'état $i$ si et seulement si l'une des deux conditions suivantes est remplie :
  • il existe un chemin allant du sommet $i$ au sommet $j$ dans le graphe $G,$
  • $i=j.$
• Une chaîne de Markov est irréductible si et seulement si son graphe est fortement connexe, i.e. si pour tout couple $i\ne j$ de sommets du graphe il existe un chemin de $i$ à $j$ et un chemin de $j$ à $i.$
• Une classe d'une chaîne de Markov est une composante fortement connexe de son graphe. Dans la première figure en haut de page (avec les états 1, 2, 3, 4, 5), le graphe non orienté induit par le graphe de la chaîne de Markov a 2 composantes connexes, mais le graphe de la chaîne de Markov (qui est un graphe orienté) a 3 composantes fortement connexes, car 2 ne communique ni avec 1, ni avec 3.

Graphe d'une chaîne de Markov et propriétés probabilistes

Certaines propriétés probabilistes des états d'une chaîne de Markov sont partagées par tous les états d'une même classe. Plus précisément:

• si une classe $C$ n'est pas finale, tous ses états sont transients (ou transitoires),
• si une classe $C$ est à la fois finale et finie, tous ses états sont récurrents positifs.

Les états d'une classe finale peuvent très bien être tous transients (par exemple dans le cas de la marche simple biaisée sur $\mathbb{Z}),$ ou bien être tous récurrents nuls (par exemple dans le cas de la marche simple symétrique sur $\mathbb{Z}).$ Tout au plus faut-il pour cela que la classe finale en question soit infinie. Il existe également des exemples de classe finale infinie récurrente positive.

Par ailleurs,

• s'il existe $i$ récurrent dans la classe $C$, alors tout état $j$ de $C$ est récurrent,
• s'il existe $i$ récurrent positif dans la classe $C$, alors tout état $j$ de $C$ est récurrent positif,
• s'il existe $i$ récurrent nul dans la classe $C$, alors tout état $j$ de $C$ est récurrent nul,
• s'il existe $i$ transient dans la classe $C$, alors tout état $j$ de $C$ est transient,
• s'il existe $i$ de période $d$ dans la classe $C$, alors tout état $j$ de $C$ est de période $d,$
• s'il existe $i$ apériodique dans la classe $C$, alors tout état $j$ de $C$ est apériodique.

On dit donc que la classe $C$ est transiente, récurrente, apériodique, etc. puisqu'il s'agit en fait de propriétés de la classe tout autant que de propriétés d'un état particulier.

Modèle:Portail