Markovův řetězec

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Jednoduchý diskrétní Markovův řetězec se dvěma stavy

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. Markovovská 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í.

Markovovské ř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[editovat | editovat zdroj]

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

  • vektorem absolutních pravděpodobností p(n) = [p1(n), p2(n),... pN(n)] pro n = 0,1,2.., kde pi(n) značí pravděpodobnost, že proces je v okamžiku n ve stavu i.
  • maticí pravděpodobností přechodu P(n) = [pij(n)] , kde i = 1, 2, .. N a j = 1, 2, .. N

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

  • pij >= 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)*Pn+1

Homogenní Markovův řetězec[editovat | editovat zdroj]

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

Nehomogenní Markovův řetězec[editovat | editovat zdroj]

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

Regulární řetězce[editovat | editovat zdroj]

Matici pravděpodobnostního přechodu P nazveme regulární, když Pn pro konečné n neobsahuje žádné nulové prvky. Matice P konverguje k limitní matici typu A, kde


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}.

kde její řádky tvoří stejné vektory a = (a1, a2,..., aN), které nazýváme stacionární vektory, někdy také limitní vektory.

Pro regulární matice platí následující tvrzení:

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

Limitní vektor[editovat | editovat zdroj]

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

\mathbf{a P = a}
\mathbf{\sum_{i=1}^N a_i = 1}

Interpretace hodnot limitního vektoru 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[editovat | editovat zdroj]

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.

\mathbf{Z} = \mathbf{[I - (P - A)]}^{-1} = {I + \sum_{n=1}^\infty (P^{n} - A)}

Vlastnosti fundamentální matice:

  • \mathbf{P Z = Z P}
  • \mathbf{Z \xi = \xi}, kde ξ je vektor z samých jedniček
  • \mathbf{a Z = a}
  • \mathbf{I - Z = a - P Z}

Absorpční řetězce[editovat | editovat zdroj]

Absorpční řetězce jsou takové řetězce, které obsahují mimo stavy transientní 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ů P můžeme přeuspořádat na následující blokovou matici:


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

Fundamentální matice absorpčního řetězce[editovat | editovat zdroj]

je matice ve tvaru:

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

Inverzní matice existuje, pokud konverguje \mathbf{Q^{n}} k nule a platí pro ni: \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.

Literatura[editovat | editovat zdroj]

  • 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.: Stochasické modely v ekonomii, Praha, SNTL 1970.
  • Hou, D.: Homogenous Denumerable Markov Processes, New York, Springer-Verlag 1988