Markovův řetězec

Markovův řetězec popisuje obvykle diskrétní náhodný (stochastický či pravděpodobnostní) proces, pro který platí, že pravděpodobnosti přechodu do následujícího stavu závisejí pouze na současném stavu, ne na předchozích stavech. Tato tzv. Markovova vlastnost dovoluje proces znázornit stavovým diagramem, kde z každého stavu (uzlu grafu) vycházejí hrany možných přechodů do dalšího stavu s připsanou pravděpodobností.

Obrázek říká, že je-li systém ve stavu E, přejde s pravděpodobností 0,7 do stavu A, kdežto s pravděpodobností 0,3 zůstane ve stavu E. Podobně po stavu A bude s pravděpodobností 0,4 následovat stav E, kdežto s pravděpodobností 0,6 systém zůstane ve stavu A. Chování takového systému je tedy „bezpaměťové“: není potřeba si pamatovat historii, stačí pouze aktuální stav. Reprezentací takového systému tedy může být konečný automat. Markovovy řetězce dostaly jméno po matematiku Andreji Markovovi.

Příklad: Pokud je známo, s jakou pravděpodobností následují např. v angličtině po určitém znaku abecedy jiné znaky, lze automaticky generovat náhodné řetězce znaků, které sice zpravidla nedávají smysl, ale na pohled se anglickým větám velmi podobají.

Markovovy řetězce mají mnoho praktických použití, zejména v informatice, v chemii, v ekonomii i v dalších společenských vědách.

Popis Markovova řetězce

Markovův řetězec je popsán dvěma strukturami:

• vektorem absolutních pravděpodobností p(n) = [p₁(n), p₂(n),... p_N(n)] pro n = 0,1,2..., kde p_i(n) značí pravděpodobnost, že proces je v okamžiku n ve stavu i.

• maticí pravděpodobností přechodu P(n) = [p_ij(n)] , kde i = 1, 2, ... N a j = 1, 2, ... N

Pravděpodobnosti p_ij musí splňovat podmínky:

• p_ij >= 0
• součet každého jednotlivé řádku matice P musí být roven 1, protože jde o úplnou soustavu jevů

Markovův řetězec dokážeme popsat pomocí vztahu: p(n+1) = p(n) * P

a postupným dosazováním můžeme dojít ke vztahu: p(n+1) = p(0) * Pⁿ⁺¹

Homogenní Markovův řetězec

Homogenní Markovův řetězec je takový Markovův řetězec, pro který platí, že p_ij(n) nezávisí na n.

Nehomogenní Markovův řetězec

Nehomogenní Markovův řetězec je takový Markovův řetězec, pro který platí, že p_ij(n) závisí na n.

Regulární řetězce

Matici pravděpodobnostního přechodu ${\displaystyle \mathbf {P} }$ nazveme regulární^[zdroj?], když ${\displaystyle \mathbf {P} ^{n}}$ pro konečné ${\displaystyle n}$ neobsahuje žádné nulové prvky. Matice ${\displaystyle \mathbf {P} }$ konverguje k limitní matici typu ${\displaystyle \mathbf {A} }$, kde

${\displaystyle {\mathbf {A} }={\begin{pmatrix}a_{1}&a_{2}&\dots &a_{N}\\a_{1}&a_{2}&\dots &a_{N}\\\dots &\dots &\dots &\dots \\a_{1}&a_{2}&\dots &a_{N}\\\end{pmatrix}}.}$

Její řádky jsou tvořeny stejnými vektory ${\displaystyle \mathbf {a} =(a_{1},a_{2},\ldots ,a_{N})}$, které nazýváme stacionární vektory, někdy také limitní vektory.

Pro regulární matice platí následující tvrzení^[zdroj?]:

• Nechť ${\displaystyle \mathbf {P} }$ je regulární, ${\displaystyle \mathbf {p} }$ je libovolný vektor absolutních pravděpodobností, ${\displaystyle \mathbf {A} }$ je limitní matice a ${\displaystyle \mathbf {a} }$ je limitní vektor, pak platí, že s rostoucím ${\displaystyle n}$ se ${\displaystyle \mathbf {pP} ^{n}}$ blíží k ${\displaystyle \mathbf {a} }$.
• ${\displaystyle \mathbf {PA=AP=A} }$
• ${\displaystyle \mathbf {aP=a} }$

Limitní vektor

Limitní vektor je možné stanovit ze soustavy rovnic:

${\displaystyle \mathbf {aP=a} }$

${\displaystyle \mathbf {\sum _{i=1}^{N}a_{i}=1} }$

Interpretace hodnot limitního vektoru ${\displaystyle \mathbf {a} }$ jsou jednotlivé doby strávené v jednotlivých stavech. Udané hodnoty jsou hodnoty pravděpodobností setrvání v těchto stavech.

Fundamentální matice regulárního řetězce

Fundamentální matici definujeme pomocí matice A. Umožňuje nám například výpočet střední doby prvního přechodu do určitého stavu a rozptyl tohoto přechodu.

${\displaystyle \mathbf {Z} =\mathbf {[I-(P-A)]} ^{-1}={\mathbf {I} +\sum _{n=1}^{\infty }({\mathbf {P} }^{n}-\mathbf {A} )}}$

Vlastnosti fundamentální matice:

• ${\displaystyle \mathbf {PZ=ZP} }$

• ${\displaystyle \mathbf {Z\xi =\xi } }$, kde ξ je vektor z samých jedniček

• ${\displaystyle \mathbf {aZ=a} }$

• ${\displaystyle \mathbf {I-Z=a-PZ} }$

Absorpční řetězce

Absorpční řetězce jsou takové řetězce, které obsahují mimo stavy tranzientní i stavy absorpční. Tzn., že pravděpodobnost setrvání v takovém stavu je rovna 1.

Každou matici pravděpodobnostních přechodů ${\displaystyle P}$ můžeme přeuspořádat na následující blokovou matici:

${\displaystyle P={\begin{pmatrix}I&0\\R&Q\\\end{pmatrix}}.}$

Fundamentální matice absorpčního řetězce

je matice ve tvaru:

${\displaystyle \mathbf {N=(I-Q)^{-1}} }$

Inverzní matice existuje, pokud konverguje ${\displaystyle \mathbf {Q^{n}} }$ k nule a platí pro ni: ${\displaystyle \mathbf {(I-Q)^{-1}=I+Q+Q^{2}+...=\sum _{k=0}^{\infty }Q^{k}} }$

Prvky fundamentální matice N udávají, kolikrát se proces v průměru ocitne v tranzientních stavech.

Odkazy

Související články

• Stochastická matice
• PageRank

Externí odkazy

• Obrázky, zvuky či videa k tématu Markovův řetězec na Wikimedia Commons

Literatura

• Ing. Václav Kořenář, CSc. – Stochastické procesy – Praha 2002, Vysoká škola ekonomická v Praze – ISBN 80-245-0311-5
• Walter, J.: Stochastické procesy. SPN, Praha 1983
• Walter, J.: Stochastické modely v ekonomii, Praha, SNTL 1970.
• Hou, D.: Homogenous Denumerable Markov Processes, New York, Springer-Verlag 1988