Graf af en Markov-kæde og klassificering af stater

Den graf over en Markov kæde og klassificering af stater er forestillinger om grafteori anvendes i sandsynlighed calculus .

Graf af en Markov-kæde

Grafen for en Markov-kæde er en rettet graf defineret fra tilstandsrummet og overgangsmatrixen $G$ $E$

{\ displaystyle \ P = \ left (p_ {i, j} \ right) _ {(i, j) \ in E ^ {2}}}

af denne Markov-kæde :

hjørner af er elementerne i $G$ ${\ displaystyle E,}$
kanterne på er parene, der verificerer $G$ ${\ displaystyle (i, j) \ i E ^ {2}}$

{\ displaystyle p_ {i, j}> 0.}

Klassificering af stater

For vi siger, at det er tilgængeligt fra hvis og kun hvis det eksisterer sådan, at vi betegner: ${\ displaystyle (i, j) \ i E ^ {2}}$ $j$ $jeg$ $n \ geq 0$ ${\ displaystyle \ mathbb {P} (X_ {n} = j \ mid X_ {0} = i)> 0.}$

\ {j \ leftarrow i \} \ quad \ Leftrightarrow \ quad \ left \ {\ findes n \ geq 0 {\ tekst {såsom}} p _ {{, i}} ^ {{(n)}}> 0 \ højre \}.

Vi siger det og kommunikerer, hvis og kun hvis de eksisterer sådan, og vi betegner: $jeg$ $j$ ${\ displaystyle (n, m) \ in \ mathbb {N} ^ {2}}$ ${\ displaystyle \ mathbb {P} (X_ {n} = j \ mid X_ {0} = i)> 0}$ ${\ displaystyle \ mathbb {P} (X_ {m} = i \ mid X_ {0} = j)> 0.}$

\ {j \ leftrightarrow i \} \ quad \ Leftrightarrow \ quad \ left \ {j \ leftarrow i {\ text {and}} i \ leftarrow j \ right \}.

Forholdet til kommunikation , bemærket er en ækvivalensrelation . Når vi taler om klasse, når vi taler om staterne i en Markov-kæde, er det generelt til ækvivalensklasser for den relation , vi henviser til. Hvis alle stater kommunikerer, siges Markov-kæden at være irreducerbar . ${\ displaystyle \ leftrightarrow,}$ $\ venstresteg$

Forholdet til at være tilgængeligt , betegnet, strækker sig til ækvivalensklasser: for to klasser, og det har vi ${\ displaystyle \ leftarrow,}$ $VS$ ${\ displaystyle C ^ {\ prime}}$

\ {C \ leftarrow C ^ {{\ prime}} \} \ quad \ Leftrightarrow \ quad \ left \ {\ findes (i, j) \ i C \ gange C ^ {{\ prime}}, \ qquad i \ leftarrow j \ right \} \ quad \ Leftrightarrow \ quad \ left \ {\ forall (i, j) \ in C \ times C ^ {{\ prime}}, \ qquad i \ leftarrow j \ right \}.

Forholdet er en ordenforhold mellem ækvivalensklasser. $\ venstre pil$

En klasse siges at være endelig, hvis den ikke fører til noget andet, dvs. hvis klassen er minimal for forholdet. Ellers siges det, at klassen er forbigående . ${\ displaystyle \ leftarrow.}$

{\ displaystyle M_ {ij} = \ {n \ geq 0 \ | \ P (X_ {n} = j \ mid X_ {0} = i)> 0 \}.}

Den periode af en stat er GCD af sættet. Hvis to stater kommunikere, de har samme periode: Vi kan derfor tale om den periode af en klasse af stater. Hvis perioden er 1, siges klassen at være aperiodisk . $jeg$ ${\ displaystyle M_ {ii}.}$

Klassificeringen af stater kan læses på en enkel måde på grafen af Markov-kæden.

Tilfældig tur på en begrænset gruppe:

Overvej en gruppe og et sandsynlighedsmål på denne gruppe, og en suite af tilfældige variabler uafhængig af loven er stillet ${\ displaystyle (G, \ oplus)}$ $\ mu$ ${\ displaystyle (Y_ {n}) _ {n \ geq 1}}$ ${\ displaystyle \ mu.}$

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

Så kaldes tilfældig gang ikke på gruppen, den stokastiske proces er en Markov-proces . Det er en Markov-kæde, hvis den er endelig eller kan tælles (i dette tilfælde ). Bemærk den støtte af : $(X_ {n}) _ {{n \ geq 0}}$ $\ mu$ ${\ displaystyle (G, \ oplus).}$ $(X_ {n}) _ {{n \ geq 0}}$ $G$ ${\ displaystyle \ mu = (\ mu _ {g}) _ {g \ in G}}$ ${\ displaystyle {\ text {supp}} (\ mu)}$ $\ mu$

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

og betegne den undergruppe, der er genereret af. Derefter er klasserne til højre modulo (af typen ) også klasserne for forholdet. Disse klasser er alle endelige. $H$ ${\ displaystyle {\ text {supp}} (\ mu).}$ $H,$ ${\ displaystyle xH = \ {xh \ | \ h \ i H \}}$ ${\ displaystyle \ leftrightarrow.}$

Trin på terningen:

Den tilfældige gåtur på terningens kanter kan ses som gangen i gruppen af trin , der faktisk tilføjer en af de 3 vektorer på det kanoniske basis svarer til at ændre en af startpunktets tre koordinater, dvs. dette svarer til låntagning tilfældigt en af de 3 kanter fra startpunktet. I dette tilfælde og gå er irreducible. ${\ displaystyle (\ mathbb {Z} _ {2} ^ {3}, +),}$ ${\ displaystyle \ mu _ {0} = {\ tfrac {1} {3}} (\ delta _ {(1,0,0)} + \ delta _ {(0,1,0)} + \ delta _ {(0,0,1)}):}$ ${\ displaystyle H_ {0} = \ langle {\ text {supp}} (\ mu _ {0}) \ rangle = G,}$
Hvis trinnet er, og trinnet har to sidste klasser: de 2 vandrette ansigter. ${\ 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 \},}$
Hvis trinnet er, og turen har 4 sidste klasser: de 4 lodrette kanter. ${\ displaystyle \ mu _ {2} = \ delta _ {(0,0,1)},}$ ${\ displaystyle H_ {2} = \ {0 \} ^ {2} \ times \ mathbb {Z} _ {2},}$
Hvis trinnet er, og turen har to sidste klasser: de 2 indskrevne tetraeder. ${\ displaystyle \ mu _ {3} = {\ tfrac {1} {2}} (\ delta _ {(0,1,1)} + \ delta _ {(1,0,1)}),}$ ${\ displaystyle | H_ {3} | = 4,}$

Tilfældige trin på ottekant:

Den 1 st Markovkæde af figuren mod er en tilfældig gåtur på cykliske gruppe af ikke I dette eksempel ${\ displaystyle \ mathbb {Z} _ {8},}$ ${\ displaystyle \ mu = p \ delta _ {1} + q \ delta _ {- 1}.}$ ${\ displaystyle H = \ langle {\ text {supp}} (\ mu) \ rangle = \ mathbb {Z} _ {8}.}$
Den 2 e Markovkæde af figuren mod er en tilfældig gåtur på dihedrale gruppe af trin , der er kvadratet på symmetri (ABCD) i forhold til diagonalen (a, c), der er symmetrien af pladsen forhold på sin vandrette akse , de to andre symmetrier er og ; er vinkelrotationen I dette eksempel er ${\ displaystyle D_ {4},}$ ${\ displaystyle \ nu = p \ delta _ {\ tau} + q \ delta _ {\ rho},}$ ${\ displaystyle \ tau = (b, d)}$ ${\ displaystyle \ rho = (a, b) (c, d)}$ ${\ displaystyle \ tau \ circ \ rho \ circ \ tau}$ ${\ displaystyle \ rho \ circ \ tau \ circ \ rho}$ ${\ displaystyle \ sigma = \ rho \ circ \ tau = (a, b, c, d)}$ ${\ displaystyle \ pi / 2.}$ ${\ displaystyle H = \ langle {\ text {supp}} (\ nu) \ rangle = D_ {4}.}$

De to kæder er derfor irreducerbare og positive tilbagevendende af ensartet stationær lov.

Leksikon: Markov-kædediagrammer

Rapporten er tilgængelig fra rapporten, hvis og kun hvis en af følgende to betingelser er opfyldt: j{\ displaystyle j} $j$ jeg{\ displaystyle i} $jeg$
- der er en sti, der går fra toppen til toppen i grafen $jeg$ $j$ ${\ displaystyle G,}$
- ${\ displaystyle i = j.}$
En Markov-kæde er irreducerbar, hvis og kun hvis dens graf er stærkt forbundet , dvs. hvis der for et par hjørner i grafen findes en sti fra til og en sti fra til $i \ neq j$ $jeg$ $j$ $j$ ${\ displaystyle i.}$
En klasse af en Markov-kæde er en stærkt forbundet komponent i dens graf. I den første figur øverst på siden (med tilstande 1, 2, 3, 4, 5) har den ikke-rettede graf induceret af Markov-kædegrafen 2 tilsluttede komponenter , men Markov-kædegrafen (som er en rettet graf) har 3 stærkt tilsluttede komponenter , fordi 2 kommunikerer hverken med 1 eller med 3.

Graf af en Markov-kæde og sandsynlige egenskaber

Visse probabilistiske egenskaber for staterne i en Markov-kæde deles af alle stater i samme klasse. Mere præcist:

hvis en klasse ikke er endelig, er alle dens tilstande forbigående (eller forbigående), $VS$
hvis en klasse er både endelig og endelig, er alle dens tilstande positive tilbagevendende . $VS$

Tilstandene i en endelig klasse kan meget vel være alle transienter (for eksempel i tilfælde af den forudindtagne enkle gang eller ellers alle nul tilbagevendende (for eksempel i tilfælde af den symmetriske enkle gang på) Det er højst nødvendigt, at sidste klasse i spørgsmålet er uendelig Der er også eksempler på positiv tilbagevendende uendelig slutklasse. ${\ displaystyle \ mathbb {Z}),}$ ${\ displaystyle \ mathbb {Z}).}$

Ellers,

hvis det findes tilbagevendende i klassen , så er enhver tilstand af tilbagevendende, $jeg$ $VS$ $j$ $VS$
hvis der er en positiv tilbagevendende i klassen , så er enhver tilstand af positiv tilbagevendende, $jeg$ $VS$ $j$ $VS$
hvis der er null tilbagevendende i klassen , så er enhver tilstand af null tilbagevendende, $jeg$ $VS$ $j$ $VS$
hvis der er forbigående i klassen , så er enhver tilstand af forbigående, $jeg$ $VS$ $j$ $VS$
hvis der er en periode i klassen , så er enhver tilstand af en periode $jeg$ $d$ $VS$ $j$ $VS$ ${\ displaystyle d,}$
hvis der er aperiodisk i klassen , så enhver stat af er aperiodisk. $jeg$ $VS$ $j$ $VS$

Vi siger derfor, at klassen er forbigående, tilbagevendende, aperiodisk osv. da de faktisk er egenskaber i klassen såvel som egenskaber i en bestemt tilstand. $VS$