Graphe d'une chaîne de Markov

Graphe d'une chaîne de Markov

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.

Sommaire

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 : \scriptstyle\ \{1,3\}\ \leftarrow\ \{2\}\ et \scriptstyle\ \{4,5\}.\ Les classes \scriptstyle\ \{1,3\}\ et \scriptstyle\ \{4,5\}\ sont finales.

Le graphe \scriptstyle\ G\ d'une chaîne de Markov est un graphe orienté défini à partir de l'espace d'états \scriptstyle\ 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 \scriptstyle\ G\ sont les éléments de \scriptstyle\ E,
  • les arêtes de \scriptstyle\ G\ sont les couples \scriptstyle\ (i,j)\in E^2 vérifiant
pi,j > 0.

Classification des états

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

\{j\leftarrow i\}\quad\Leftrightarrow\quad\left\{\exists n\ge 0\text{ tel que }p^{(n)}_{i,j}>0\right\}.

On dit que \scriptstyle\ i\ et \scriptstyle\ j\ communiquent si et seulement s'il existe \scriptstyle\ (n,m)\in \mathbb{N}^2\ tels que \scriptstyle\ \mathbb{P}(X_{n}=j\mid X_0=i) >0\ et \scriptstyle\ \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 \scriptstyle\ \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éral aux classes d'équivalence pour la relation \scriptstyle\ \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 \scriptstyle\ \leftarrow,\ s'étend aux classes d'équivalence : pour deux classes \scriptstyle\ C\ et \scriptstyle\ 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 \scriptstyle\ \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 \scriptstyle\ \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 \scriptstyle\ i\ est le PGCD de l'ensemble \scriptstyle\ 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 \scriptstyle\ (\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 \scriptstyle\ (G,\oplus)\ et une mesure de probabilité \scriptstyle\ \mu\ sur ce groupe, ainsi qu'une suite \scriptstyle\ (Y_n)_{n\ge 1}\ de variables aléatoires indépendantes de loi \scriptstyle\ \mu.\ On pose

X_0=x_0\in G\quad\text{et}\quad\forall\,n\ge 1,\ X_n=X_{n-1}\oplus Y_n.

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

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

et notons \scriptstyle\ H\ le sous-groupe engendré par \scriptstyle\ \text{supp}(\mu).\ Alors les classes à droite modulo \scriptstyle\ H,\ (de type \scriptstyle\ xH=\{xh\ |\ h\in H\}\ ) sont aussi les classes pour la relation \scriptstyle\ \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 \scriptstyle\ (\mathbb{Z}_{2}^3,+),\ de pas \scriptstyle\ \mu_{0}=\tfrac13(\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 \scriptstyle\ H_{0}=\langle \text{supp}(\mu_0)\rangle=G,\ et la marche est irréductible.
  • Si le pas est \scriptstyle\ \mu_{1}=\tfrac12(\delta_{(1,0,0)}+\delta_{(0,1,0)}),\ \scriptstyle\ 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 \scriptstyle\ \mu_{2}=\delta_{(0,0,1)},\ \scriptstyle\ H_{2}=\{0\}^2\times\mathbb{Z}_{2},\ et la marche a 4 classes finales : les 4 arètes verticales.
  • Si le pas est \scriptstyle\ \mu_{3}=\tfrac12(\delta_{(0,1,1)}+\delta_{(1,0,1)}),\ \scriptstyle\ |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 \scriptstyle\ \mathbb{Z}_{8}\ et sur le groupe diédral \scriptstyle\ 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 \scriptstyle\ \mathbb{Z}_{8},\ de pas \scriptstyle\ \mu=p\delta_{1}+q\delta_{-1}.\ Dans cet exemple, \scriptstyle\ H=\langle \text{supp}(\mu)\rangle=\mathbb{Z}_{8}.\
  • La 2ème chaîne de Markov de la figure ci-contre est une marche aléatoire sur le groupe diédral \scriptstyle\ D_{4},\ de pas \scriptstyle\ \nu=p\delta_{\tau}+q\delta_{\rho},\ où \scriptstyle\ \tau=(b,d)\ est la symétrie du carré (abcd) par rapport à la diagonale (a,c), où \scriptstyle\ \rho=(a,b)(c,d)\ est la symétrie du carré par rapport à son axe horizontal, les deux autres symétries étant \scriptstyle\ \tau\circ\rho\circ\tau\ et \scriptstyle\ \rho\circ\tau\circ\rho\  ; \scriptstyle\ \sigma=\rho\circ\tau=(a,b,c,d)\ est la rotation d'angle \scriptstyle\ \pi/2.\ Dans cet exemple, \scriptstyle\ 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 \scriptstyle\ j\ est accessible à partir de l'état \scriptstyle\ i\ si et seulement si l'une des deux conditions suivantes est remplie :
    • il existe un chemin allant du sommet \scriptstyle\ i\ au sommet \scriptstyle\ j\ dans le graphe \scriptstyle\ G,\
    • \scriptstyle\ 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 \scriptstyle\ i\neq j\ de sommets du graphe il existe un chemin de \scriptstyle\ i\ à \scriptstyle\ j\ et un chemin de \scriptstyle\ j\ à \scriptstyle\ i.
  • Une classe d'une chaîne de Markov est une composante fortement connexe de son graphe. Dans l'exemple ci-dessus 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 \scriptstyle\ C\quad n'est pas finale, tous ses états sont transients (ou transitoires),
  • si une classe \scriptstyle\ C\quad est à la fois finale et finie, tous ses états sont récurrents positifs.

Par ailleurs,

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

On dit donc que la classe \scriptstyle\ C\quad 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.

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 \scriptstyle\ \mathbb{Z}),\quad ou bien être tous récurrents nuls (par exemple dans le cas de la marche simple symétrique sur \scriptstyle\ \mathbb{Z}).\quad 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.

Ce document provient de « Graphe d%27une cha%C3%AEne de Markov et classification des %C3%A9tats ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Graphe d'une chaîne de Markov de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • 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. Sommaire 1 Graphe d une chaîne de Markov 2 Classification des états 3 Lexi …   Wikipédia en Français

  • Probabilité stationnaire d'une chaîne de Markov — La probabilité stationnaire d une chaîne de Markov s interprète usuellement comme la fraction du temps passé en chaque état de l espace d états de cette chaîne de Markov, asymptotiquement. En effet, une version de la loi forte des grands nombres… …   Wikipédia en Français

  • Chaine De Markov — Chaîne de Markov Selon les auteurs, une chaîne de Markov est de manière générale un processus de Markov à temps discret ou un processus de Markov à temps discret et à espace d états discret. En mathématiques, un processus de Markov est un… …   Wikipédia en Français

  • Chaine de Markov — Chaîne de Markov Selon les auteurs, une chaîne de Markov est de manière générale un processus de Markov à temps discret ou un processus de Markov à temps discret et à espace d états discret. En mathématiques, un processus de Markov est un… …   Wikipédia en Français

  • Chaine de markov — Chaîne de Markov Selon les auteurs, une chaîne de Markov est de manière générale un processus de Markov à temps discret ou un processus de Markov à temps discret et à espace d états discret. En mathématiques, un processus de Markov est un… …   Wikipédia en Français

  • Chaîne De Markov — Selon les auteurs, une chaîne de Markov est de manière générale un processus de Markov à temps discret ou un processus de Markov à temps discret et à espace d états discret. En mathématiques, un processus de Markov est un processus stochastique… …   Wikipédia en Français

  • Chaîne de Markov à espace d'états discret — Chaîne de Markov Selon les auteurs, une chaîne de Markov est de manière générale un processus de Markov à temps discret ou un processus de Markov à temps discret et à espace d états discret. En mathématiques, un processus de Markov est un… …   Wikipédia en Français

  • Chaîne de markov — Selon les auteurs, une chaîne de Markov est de manière générale un processus de Markov à temps discret ou un processus de Markov à temps discret et à espace d états discret. En mathématiques, un processus de Markov est un processus stochastique… …   Wikipédia en Français

  • Récurrence et transience d'une chaîne de Markov — Un état d une chaîne de Markov est dit récurrent si une trajectoire « typique » de la chaîne de Markov passe par une infinité de fois, sinon l état est dit transient. Ces propriétés de transience ou de récurrence sont souvent partagées… …   Wikipédia en Français

  • Chaîne de Markov — Selon les auteurs, une chaîne de Markov est de manière générale un processus de Markov à temps discret ou un processus de Markov à temps discret et à espace d états discret. En mathématiques, un processus de Markov est un processus stochastique… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”