Graf Markovova řetězce a klasifikace států

Graf Markov řetězu a klasifikace států jsou pojmy teorie grafů používané v pravděpodobnosti počtu .

Graf Markovova řetězce

Graf z Markov řetězu je orientovaný graf definovaný ze stavového prostoru a přechodové matice $G$ $E$

{\ displaystyle \ P = \ vlevo (p_ {i, j} \ vpravo) _ {(i, j) \ v E ^ {2}}}

tohoto markovského řetězce :

vrcholy jsou prvky $G$ ${\ displaystyle E,}$
okraje ověřují páry $G$ ${\ displaystyle (i, j) \ v E ^ {2}}$

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

Klasifikace států

Pro říkáme, že je přístupný z tehdy a jen tehdy, pokud existuje taková, že jsme se označují: ${\ displaystyle (i, j) \ v E ^ {2}}$ $j$ $i$ $n \ geq 0$ ${\ displaystyle \ mathbb {P} (X_ {n} = j \ mid X_ {0} = i)> 0.}$

\ {j \ leftarrow i \} \ quad \ Leftrightarrow \ quad \ left \ {\ existuje n \ geq 0 {\ text {jako například}} p _ {{i, j}} ^ {{(n)}}> 0 \ doprava \}.

Říkáme to a komunikujeme tehdy a jen tehdy, pokud takové existují a označujeme: $i$ $j$ ${\ displaystyle (n, m) \ v \ mathbb {N} ^ {2}}$ ${\ displaystyle \ mathbb {P} (X_ {n} = j \ mid X_ {0} = i)> 0}$ ${\ displaystyle \ mathbb {P} (X_ {m} = i \ střední X_ {0} = j)> 0.}$

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

Vztah ke komunikaci , známý je vztah ekvivalence . Když mluvíme o třídě, když hovoříme o stavech Markovova řetězce, obecně se jedná o třídy ekvivalence pro vztah , o kterém mluvíme. Pokud všechny státy komunikují, říká se, že markovský řetězec je neredukovatelný . ${\ displaystyle \ leftrightarrow,}$ $\ leftrightarrow$

Vztah, který má být přístupný , se vztahuje na třídy ekvivalence: pro dvě třídy a , máme ${\ displaystyle \ leftarrow,}$ $VS$ ${\ displaystyle C ^ {\ prime}}$

\ {C \ leftarrow C ^ {{\ prime}} \} \ quad \ Leftrightarrow \ quad \ left \ {\ existuje (i, j) \ v C \ krát C ^ {{\ prime}}, \ qquad i \ leftarrow j \ right \} \ quad \ Leftrightarrow \ quad \ left \ {\ forall (i, j) \ in C \ times C ^ {{\ prime}}, \ qquad i \ leftarrow j \ right \}.

Relace je relační řád mezi třídami ekvivalence. $\ šipka vlevo$

O třídě se říká, že je konečná, pokud nevede k žádné jiné, tj. Pokud je třída pro vztah minimální. Jinak se o třídě říká, že je přechodná . ${\ displaystyle \ leftarrow.}$

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

Období o stavu je GCD sady li oba státy komunikují, mají stejnou periodu: proto můžeme hovořit o období třídy stavů. Pokud je perioda rovna 1, říká se, že třída je neperiodická . $i$ ${\ displaystyle M_ {ii}.}$

Klasifikaci stavů lze snadno přečíst na grafu Markovova řetězce.

Náhodná procházka konečnou skupinou:

Vezměme si skupinu a míra pravděpodobnosti na této skupině a sadu z náhodných veličin nezávisle práva položena ${\ displaystyle (G, \ oplus)}$ $\ mu$ ${\ displaystyle (Y_ {n}) _ {n \ geq 1}}$ ${\ displaystyle \ mu.}$

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

Tak se nazývá náhodná procházka, ne ve skupině, stochastický proces je proces Markov . Je to Markovův řetězec, pokud je konečný nebo spočetný (v tomto případě ). Všimněte si podporu z : $(X_ {n}) _ {{n \ geq 0}}$ $\ mu$ ${\ displaystyle (G, \ oplus).}$ $(X_ {n}) _ {{n \ geq 0}}$ $G$ ${\ displaystyle \ mu = (\ mu _ {g}) _ {g \ v G}}$ ${\ displaystyle {\ text {supp}} (\ mu)}$ $\ mu$

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

a označte podskupinu generovanou Potom třídy na pravém modulo (typu ) jsou také třídami pro relaci. Tyto třídy jsou všechny konečné. $H$ ${\ displaystyle {\ text {supp}} (\ mu).}$ $H,$ ${\ displaystyle xH = \ {xh \ | \ h \ v H \}}$ ${\ displaystyle \ leftrightarrow.}$

Kroky na krychli:

Náhodný chod po okrajích krychle lze chápat jako chod po skupině kroků, ve skutečnosti přidání jednoho ze 3 vektorů kanonické základny znamená změnu jedné ze tří souřadnic počátečního bodu, tj. To znamená výpůjčku náhodně jedna ze 3 hran od počátečního bodu. V tomto případě je chůze neredukovatelná. ${\ 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,}$
Pokud krok je a má dva závěrečné třídy: 2 vodorovné plochy. ${\ 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 \},}$
Pokud je krok a chůze má 4 závěrečné třídy: 4 svislé okraje. ${\ displaystyle \ mu _ {2} = \ delta _ {(0,0,1)},}$ ${\ displaystyle H_ {2} = \ {0 \} ^ {2} \ times \ mathbb {Z} _ {2},}$
Pokud je krok a chůze má dvě závěrečné třídy: 2 vepsaný čtyřstěn. ${\ displaystyle \ mu _ {3} = {\ tfrac {1} {2}} (\ delta _ {(0,1,1)} + \ delta _ {(1,0,1)}),}$ ${\ displaystyle | H_ {3} | = 4,}$

Náhodné kroky na osmiúhelníku:

1 st Markov řetězce obrázku Proti je náhodná chůze na cyklické skupiny žádný V tomto příkladu, ${\ displaystyle \ mathbb {Z} _ {8},}$ ${\ displaystyle \ mu = p \ delta _ {1} + q \ delta _ {- 1}.}$ ${\ displaystyle H = \ langle {\ text {supp}} (\ mu) \ rangle = \ mathbb {Z} _ {8}.}$
2 e Markov řetěz obrázku proti je náhodná chůze na dihedral skupiny kroků, což je čtverec symetrie (ABCD) vzhledem k diagonále (a, c), který je symetrii čtvercové vzhledem na jeho horizontální osy , přičemž další dvě symetrie jsou a ; je rotace úhlu V tomto příkladu ${\ 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}.}$

Tyto dva řetězce jsou proto neredukovatelné a pozitivně se opakující, jednotného stacionárního práva.

Lexicon: Markovovy řetězové grafy

Zpráva je přístupná ze zprávy, pouze pokud je splněna jedna z následujících dvou podmínek: j{\ displaystyle j} $j$ i{\ displaystyle i} $i$
- tam je cesta jít z vrcholu na vrchol v grafu $i$ $j$ ${\ displaystyle G,}$
- ${\ displaystyle i = j.}$
Markovův řetězec je neredukovatelný právě tehdy, pokud je jeho graf silně propojen , tj. Pokud pro jakoukoli dvojici vrcholů grafu existuje cesta od do a cesta od do $i \ neq j$ $i$ $j$ $j$ ${\ displaystyle i.}$
Třída Markovova řetězce je silně propojenou součástí jeho grafu. Na prvním obrázku v horní části stránky (se stavy 1, 2, 3, 4, 5) má neřízený graf indukovaný Markovovým řetězovým grafem 2 spojené komponenty , ale Markovův řetězový graf (což je směrovaný graf) má 3 silně propojené komponenty , protože 2 nekomunikuje ani s 1, ani s 3.

Graf Markovova řetězce a pravděpodobnostní vlastnosti

Určité pravděpodobnostní vlastnosti stavů Markovova řetězce sdílí všechny státy stejné třídy. Přesněji:

pokud třída není konečná, všechny její stavy jsou přechodné (nebo přechodné), $VS$
pokud je třída konečná i konečná, všechny její stavy se pozitivně opakují . $VS$

Stavy finální třídy mohou velmi dobře být všechny přechodné stavy (například v případě zkresleného jednoduchého procházení nebo jinak všechny nulové opakující se (například v případě symetrického jednoduchého procházení). Nanejvýš je nutné, aby závěrečná třída je nekonečná Existují také příklady pozitivních opakujících se nekonečných závěrečných tříd. ${\ displaystyle \ mathbb {Z}),}$ ${\ displaystyle \ mathbb {Z}).}$

V opačném případě,

pokud existuje opakující se ve třídě , pak každý stát z opakují, $i$ $VS$ $j$ $VS$
pokud je pozitivní recidivující ve třídě , pak každý stát z je pozitivní recidivující, $i$ $VS$ $j$ $VS$
v případě, že je nulový opakující se ve třídě , pak jakýkoliv stav z null opakující se, $i$ $VS$ $j$ $VS$
v případě, že je přechodný ve třídě , pak každý stát ze je přechodná, $i$ $VS$ $j$ $VS$
Pokud je doba ve třídě , pak každý stát ze je období $i$ $d$ $VS$ $j$ $VS$ ${\ displaystyle d,}$
Pokud je aperiodické ve třídě , pak každý stát ze je aperiodické. $i$ $VS$ $j$ $VS$

Proto říkáme, že třída je přechodná, opakující se, neperiodická atd. protože jsou ve skutečnosti vlastnostmi třídy i vlastnostmi konkrétního státu. $VS$