Łańcuch Markowa: Różnice pomiędzy wersjami

Dodane 157 bajtów ,  2 lata temu
m
m (Bot poprawia nagłówki sekcji; zmiany kosmetyczne)
m (WP:SK+Bn)
'''Łańcuchy Markowa''' to procesy Markowa z czasem dyskretnym.
 
Łańcuch Markowa jest ciągiem <var>X<sub>1</submath>X_1, X<sub>2</sub>X_2, X<sub>3</sub>X_3, ...\dots</varmath> [[zmienna losowa|zmiennych losowych]]. Dziedzinę tych zmiennych nazywamy '''przestrzenią stanów''', a realizacje <varmath>X<sub>nX_n</sub></varmath> to stany w czasie <varmath>n.</varmath>. Jeśli [[rozkład warunkowy]] ''X''<submath>''X_{n''+1}</submath> jest funkcją wyłącznie zmiennej ''X''<submath>''n''X_n{:}</submath>:
: <math> P(X_{n+1}\leqslant y|X_0, X_1, X_2, \ldotsdots, X_n) = P(X_{n+1}\leqslant y|X_n) ,</math>
 
: <math> P(X_{n+1}\leqslant y|X_0, X_1, X_2, \ldots, X_n) = P(X_{n+1}\leqslant y|X_n) </math>
 
to mówimy, że [[proces stochastyczny]] posiada [[własność Markowa]].
 
Przedstawiona definicja zakłada [[czas]] dyskretny. Istnieją procesy Markowa z [[czas]]emczasem ciągłym, jednak nie są one przedstawione w tym artykule.
 
Procesy Markowa zawdzięczają swoją nazwę ich twórcy [[Andriej Markow (starszy)|Andriejowi Markowowi]], który po raz pierwszy opisał problem w [[1906]] roku. Uogólnienie na [[zbiór przeliczalny|przeliczalnie nieskończone]] przestrzenie stanów zostało opracowane przez [[Andriej Kołmogorow|Kołmogorowa]] w [[1936]]. Łańcuchy Markowa mają związek z [[ruchy Browna|ruchami Browna]] oraz [[hipoteza ergodyczna|hipotezą ergodyczną]], dwoma ważnymi w [[fizyka|fizyce]] tematami, ale powstały jako uogólnienie [[prawo wielkich liczb|prawa wielkich liczb]] na zdarzenia zależne.
== Własności łańcuchów Markowa ==
=== Rozkład początkowy ===
Rozkładem początkowym nazywamy rozkład ([[Dyskretny rozkład dyskretnyprawdopodobieństwa|dyskretny]]) zmiennej ''X''<submath>0X_0.</submath>.
 
=== Macierz przejść ===
==== Definicja ====
Jeśli łańcuch Markowa jest jednorodny, rozkład prawdopodobieństw przejść między poszczególnymi stanami może być przedstawiony jako [[macierz]], zwaną macierzą prawdopodobieństw przejścia. Jest to [[macierz stochastyczna]], oznaczamy zwykle literą '''<math>\mathbf{P'''},</math> gdzie wyraz <math>(''i'', ''j'')</math> wyraża się wzorem:
 
: <math>p_{i,j} = P(X_{n+1}=j\mid X_n=i).</math>
 
Z jednorodności wynika, że rzeczywiście ''p''<submath>''p_{i,j''}</submath> nie zależy od ''<math>n''.</math> Przykładowo element ''p''<submath>''p_{1,3''}</submath> oznacza prawdopodobieństwo przejścia ze stanu pierwszego do stanu trzeciego.
 
==== Równania Chapmana-Kołmogorowa ====
Prawdopodobieństwem przejścia ze stanu ''<math>i''</math> do stanu ''<math>j''</math> w ''<math>n''</math> krokach nazywa się prawdopodobieństwo warunkowe
: <math>p_{i,j}^{(n)} = P(X_{m+n}=j| X_m = i).</math>.
 
Dla prawdopodobieństw przejść spełnione są następujące równanie, nazywane ''równaniami Chapmana-Kołmogorowa'':
: <math>p_{i,j}^{(n + m)} = \sum_{k \in E} p_{i,k}^{(n)}p_{k,j}^{(m)}.</math>.
 
Intuicyjne jest jasne, że aby dojść do stanu ''<math>j''</math> można po drodze przejść przez dowolny inny stan skomunikowany z ''<math>j''</math> i ''<math>i''.</math> Stosując zapis macierzowy, równania Chapmana-Kołmogorowa można zapisać w postaci:
: <math> \mathbf{P}^{m+n} = \mathbf{P}^{m}\mathbf{P}^{n} ,</math>,
gdzie przez '''P'''<sup>''n''</sup> jest macierzą przejść w ''n'' krokach.
 
gdzie przez '''P'''<supmath>''\mathbf{P}^n''</supmath> jest macierzą przejść w ''<math>n''</math> krokach.
 
=== Klasyfikacja stanów ===
Mówi się, że:
* stan ''<math>i''</math> jest osiągalny ze stanu ''<math>j'',</math> jeśli ''p''<submath>''p_{j,i''</sub>} > 0;</math>
* stany ''<math>i''</math> i ''<math>j''</math> są skomunikowane, jeśli są wzajemnie osiągalne. Oznaczenie: ''<math>i'' &nbsp;↔&nbsp;\leftrightarrow ''j''.</math>
 
Można wykazać, że relacja skomunikowania jest [[relacja równoważności|relacją równoważności]]. Zatem zbiór możliwych stanów można podzielić na klasy abstrakcji względem tej relacji. Każda z klas tworzy zbiór stanów wzajemnie skomunikowanych.
 
==== Stany chwilowe i rekurencyjne ====
Niech ''f''<submath>''i''f_i</submath> oznacza prawdopodobieństwo tego, że startując ze stanu ''<math>i''</math> łańcuch kiedykolwiek do niego powróci.
* Jeśli ''f''<sub>''i''</submath>f_i = 1</math> to stan ''<math>i''</math> nazywany jest ''rekurencyjnym''.
* Jeśli ''f''<sub>''i''</submath>f_i < 1</math> to stan ''<math>i''</math> nazywany jest ''chwilowym''.
 
Każdy stan jest albo chwilowy albo rekurencyjny. Stan ''<math>i''</math> jest rekurencyjny wtedy i tylko wtedy, gdy:
: <math>\sum_{n=1}^{\infty} p_{i,i}^{(n)} = \infty. </math>
 
=== Rozkład stacjonarny ===
Rozkład prawdopodobieństw na przestrzeni stanów '''<math>\mathbf{S'''}</math> nazywany jest ''[[stacjonarnośćProces stacjonarny|stacjonarnym]]'' wtedy i tylko wtedy, gdy spełniony jest warunek:
: <math>\pi_{j}pi_j = \sum_{i \in S} \pi_i p_{ij},</math>
 
: <math>\pi_{j} = \sum_{i \in S} \pi_i p_{ij},</math>
tj.
: <math> \pi\mathbf{P} = \pi, </math>
 
gdzie π<math>\pi</math> jest takim wektorem wierszowym, że:
: <math>\sum_i \pi_i = 1 \quad \forall \pi_i \gegeqslant 0 .</math>.
 
Jeśli rozkład początkowy <math>\mathbf{x_0}</math> jest stacjonarny, to każdy kolejny rozkład <math>\mathbf{x_n}</math> również jest stacjonarny.
 
== Zobacz też ==
* [[Własnośćwłasność Markowa]]
 
== Bibliografia ==
* Maria Podgórska i in.: ''Łańcuchy Markowa w teorii i zastosowaniach''. Warszawa: Szkoła Główna Handlowa, Oficyna Wydawnicza, 2002.
* Anzelm Iwanik, Jolanta Katarzyna Misiewicz: ''Wykłady z procesów stochastycznych z zadaniami''. Cz. 1, ''Procesy Markowa''. Zielona Góra: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego, 2009.
 
== Linki zewnętrzne ==