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\}\rightarrow \{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\geq 0$ tel que $\mathbb {P} (X_{n}=j\mid X_{0}=i)>0.$ On note :

$\{j\leftarrow i\}\quad \Leftrightarrow \quad \left\{\exists n\geq 0{\text{ tel que }}p_{i,j}^{(n)}>0\right\}.$

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\}\quad \Leftrightarrow \quad \left\{j\leftarrow i{\text{ et }}i\leftarrow j\right\}.$

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 }\}\quad \Leftrightarrow \quad \left\{\exists (i,j)\in C\times C^{\prime },\qquad i\leftarrow j\right\}\quad \Leftrightarrow \quad \left\{\forall (i,j)\in C\times C^{\prime },\qquad i\leftarrow j\right\}.$

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\geq 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.

Marche aléatoire sur un groupe fini :

On se donne un groupe $(G,\oplus )$ et une mesure de probabilité $\mu$ sur ce groupe, ainsi qu'une suite $(Y_{n})_{n\geq 1}$ de variables aléatoires indépendantes de loi $\mu .$ On pose

$X_{0}=x_{0}\in G\quad {\text{et}}\quad \forall \,n\geq 1,\ X_{n}=X_{n-1}\oplus Y_{n}.$

Alors $(X_{n})_{n\geq 0}$ est appelée marche aléatoire de pas $\mu$ sur le groupe $(G,\oplus ).$ Le processus stochastique $(X_{n})_{n\geq 0}$ est un processus de Markov. C'est une chaîne de Markov si $G$ est fini ou dénombrable (en ce cas $\mu =(\mu _{g})_{g\in G}$). Notons ${\text{supp}}(\mu )$ le support de $\mu$ :

${\text{supp}}(\mu )=\{g\in G\quad |\quad \mu _{g}>0\},$

et notons $H$ le sous-groupe engendré par ${\text{supp}}(\mu ).$ Alors les classes à droite modulo $H,$ (de type $xH=\{xh\ |\ h\in H\}$) sont aussi les classes pour la relation $\leftrightarrow .$ Ces classes sont toutes finales.

Marches sur le cube :

• La marche aléatoire sur les arêtes du cube peut être vue comme la marche sur le groupe $(\mathbb {Z} _{2}^{3},+),$ de pas $\mu _{0}={\tfrac {1}{3}}(\delta _{(1,0,0)}+\delta _{(0,1,0)}+\delta _{(0,0,1)}):$ en effet ajouter un des 3 vecteurs de la base canonique revient à changer une des trois coordonnées du point de départ, i.e. cela revient à emprunter, au hasard, une des 3 arêtes issues du point de départ. En ce cas $H_{0}=\langle {\text{supp}}(\mu _{0})\rangle =G,$ et la marche est irréductible.
• Si le pas est $\mu _{1}={\tfrac {1}{2}}(\delta _{(1,0,0)}+\delta _{(0,1,0)}),$ $H_{1}=\langle {\text{supp}}(\mu _{1})\rangle =\mathbb {Z} _{2}^{2}\times \{0\},$ et la marche a deux classes finales : les 2 faces horizontales.
• Si le pas est $\mu _{2}=\delta _{(0,0,1)},$ $H_{2}=\{0\}^{2}\times \mathbb {Z} _{2},$ et la marche a 4 classes finales : les 4 arêtes verticales.
• Si le pas est $\mu _{3}={\tfrac {1}{2}}(\delta _{(0,1,1)}+\delta _{(1,0,1)}),$ $|H_{3}|=4,$ et la marche a deux classes finales : les 2 tétraèdres inscrits.

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

Marches aléatoires sur l'octogone :

• La 1^re chaîne de Markov de la figure ci-contre est une marche aléatoire sur le groupe cyclique $\mathbb {Z} _{8},$ de pas $\mu =p\delta _{1}+q\delta _{-1}.$ Dans cet exemple, $H=\langle {\text{supp}}(\mu )\rangle =\mathbb {Z} _{8}.$
• La 2^e chaîne de Markov de la figure ci-contre est une marche aléatoire sur le groupe diédral $D_{4},$ de pas $\nu =p\delta _{\tau }+q\delta _{\rho },$ où $\tau =(b,d)$ est la symétrie du carré (abcd) par rapport à la diagonale (a,c), où $\rho =(a,b)(c,d)$ est la symétrie du carré par rapport à son axe horizontal, les deux autres symétries étant $\tau \circ \rho \circ \tau$ et $\rho \circ \tau \circ \rho$ ; $\sigma =\rho \circ \tau =(a,b,c,d)$ est la rotation d'angle $\pi /2.$ Dans cet exemple, $H=\langle {\text{supp}}(\nu )\rangle =D_{4}.$

Les deux chaînes sont donc irréductibles et récurrentes positives, de loi stationnaire uniforme.

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\neq 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.