Markovův řetězec

Z Wikipedie, otevřené encyklopedie

Skočit na: Navigace, Hledání

Markovův řetězec označuje stochastický (náhodný či pravděpodobnostní) proces, který má Markovovskou vlastnost. Ta říká, že v každém stavu procesu je pravděpodobnost navštívení dalších stavů nezávislá na dříve navštívených stavech. To znamená, že chování v Markovových řetězcích je „bezpaměťové“: V každém konkrétním stavu je možno zapomenout historii (posloupnost stavů předcházející stavu současnému). Markovovy řetězce dostaly jméno po matematiku Andreji Markovovi.

Obsah

[editovat] Popis Markovova řetezce

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 p_i(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

[editovat] Homogenní Markovovův řetězec

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

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

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

[editovat] Regulární řetězce

Matici pravděpodobostní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}

[editovat] Limitní vektor

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.

[editovat] 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.

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

[editovat] Absorpční řetězce

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

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

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.

[editovat] 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.: Stochasické modely v ekonomii, Praha, SNTL 1970.
  • Hou, D.: Homogenous Denumerable Markov Processes, New York, Springer-Verlag 1988
Citováno z „http://cs.wikipedia.org/wiki/Markov%C5%AFv_%C5%99et%C4%9Bzec“