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

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

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

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

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

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

• La marche aléatoire sur les arêtes du cube peut être vue comme la marche sur le groupe ${\displaystyle (\mathbb {Z} _{2}^{3},+),}$ de pas ${\displaystyle \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 ${\displaystyle H_{0}=\langle {\text{supp}}(\mu _{0})\rangle =G,}$ et la marche est irréductible.
• Si le pas est ${\displaystyle \mu _{1}={\tfrac {1}{2}}(\delta _{(1,0,0)}+\delta _{(0,1,0)}),}$ ${\displaystyle 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 ${\displaystyle \mu _{2}=\delta _{(0,0,1)},}$ ${\displaystyle H_{2}=\{0\}^{2}\times \mathbb {Z} _{2},}$ et la marche a 4 classes finales : les 4 arêtes verticales.
• Si le pas est ${\displaystyle \mu _{3}={\tfrac {1}{2}}(\delta _{(0,1,1)}+\delta _{(1,0,1)}),}$ ${\displaystyle |H_{3}|=4,}$ et la marche a deux classes finales : les 2 tétraèdres inscrits.

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

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