Łańcuch Markowa

Przykład procesu Markowa

Proces Markowa – ciąg zdarzeń, w którym prawdopodobieństwo każdego zdarzenia zależy jedynie od wyniku poprzedniego. W ujęciu matematycznym, procesy Markowa to takie procesy stochastyczne, które spełniają własność Markowa.

Łańcuchy Markowa to procesy Markowa z czasem dyskretnym.

Łańcuch Markowa jest ciągiem ${\displaystyle X_{1},X_{2},X_{3},\dots }$ zmiennych losowych. Dziedzinę tych zmiennych nazywamy przestrzenią stanów, a realizacje ${\displaystyle X_{n}}$ to stany w czasie ${\displaystyle n.}$ Jeśli rozkład warunkowy ${\displaystyle X_{n+1}}$ jest funkcją wyłącznie zmiennej ${\displaystyle X_{n}{:}}$

${\displaystyle P(X_{n+1}\leqslant y|X_{0},X_{1},X_{2},\dots ,X_{n})=P(X_{n+1}\leqslant y|X_{n}),}$

to mówimy, że proces stochastyczny posiada własność Markowa.

Przedstawiona definicja zakłada czas dyskretny. Istnieją procesy Markowa z czasem ciągłym, jednak nie są one przedstawione w tym artykule.

Procesy Markowa zawdzięczają swoją nazwę ich twórcy Andriejowi Markowowi, który po raz pierwszy opisał problem w 1906 roku. Uogólnienie na przeliczalnie nieskończone przestrzenie stanów zostało opracowane przez Kołmogorowa w 1936. Łańcuchy Markowa mają związek z ruchami Browna oraz hipotezą ergodyczną, dwoma ważnymi w fizyce tematami, ale powstały jako uogólnienie 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) zmiennej ${\displaystyle X_{0}.}$

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ą ${\displaystyle \mathbf {P} ,}$ gdzie wyraz ${\displaystyle (i,j)}$ wyraża się wzorem:

${\displaystyle p_{i,j}=P(X_{n+1}=j\mid X_{n}=i).}$

Z jednorodności wynika, że rzeczywiście ${\displaystyle p_{i,j}}$ nie zależy od ${\displaystyle n.}$ Przykładowo element ${\displaystyle p_{1,3}}$ oznacza prawdopodobieństwo przejścia ze stanu pierwszego do stanu trzeciego.

Równania Chapmana-Kołmogorowa

Prawdopodobieństwem przejścia ze stanu ${\displaystyle i}$ do stanu ${\displaystyle j}$ w ${\displaystyle n}$ krokach nazywa się prawdopodobieństwo warunkowe

${\displaystyle p_{i,j}^{(n)}=P(X_{m+n}=j|X_{m}=i).}$

Dla prawdopodobieństw przejść spełnione są następujące równanie, nazywane równaniami Chapmana-Kołmogorowa:

${\displaystyle p_{i,j}^{(n+m)}=\sum _{k\in E}p_{i,k}^{(n)}p_{k,j}^{(m)}.}$

Intuicyjne jest jasne, że aby dojść do stanu ${\displaystyle j}$ można po drodze przejść przez dowolny inny stan skomunikowany z ${\displaystyle j}$ i ${\displaystyle i.}$ Stosując zapis macierzowy, równania Chapmana-Kołmogorowa można zapisać w postaci:

${\displaystyle \mathbf {P} ^{m+n}=\mathbf {P} ^{m}\mathbf {P} ^{n},}$

gdzie przez ${\displaystyle \mathbf {P} ^{n}}$ jest macierzą przejść w ${\displaystyle n}$ krokach.

Klasyfikacja stanów

Mówi się, że:

• stan ${\displaystyle i}$ jest osiągalny ze stanu ${\displaystyle j,}$ jeśli ${\displaystyle p_{j,i}^{(n)}>0}$ dla pewnego ${\displaystyle n\geqslant 0.}$
• stany ${\displaystyle i}$ i ${\displaystyle j}$ są skomunikowane, jeśli są wzajemnie osiągalne. Oznaczenie: ${\displaystyle i\leftrightarrow j.}$

Można wykazać, że relacja skomunikowania jest 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 ${\displaystyle f_{i}}$ oznacza prawdopodobieństwo tego, że startując ze stanu ${\displaystyle i}$ łańcuch kiedykolwiek do niego powróci.

• Jeśli ${\displaystyle f_{i}=1}$ to stan ${\displaystyle i}$ nazywany jest rekurencyjnym.
• Jeśli ${\displaystyle f_{i}<1}$ to stan ${\displaystyle i}$ nazywany jest chwilowym.

Każdy stan jest albo chwilowy albo rekurencyjny. Stan ${\displaystyle i}$ jest rekurencyjny wtedy i tylko wtedy, gdy:

${\displaystyle \sum _{n=1}^{\infty }p_{i,i}^{(n)}=\infty .}$

Rozkład stacjonarny

Rozkład prawdopodobieństw na przestrzeni stanów ${\displaystyle \mathbf {S} }$ nazywany jest stacjonarnym wtedy i tylko wtedy, gdy spełniony jest warunek:

${\displaystyle \pi _{j}=\sum _{i\in S}\pi _{i}p_{ij},}$

tj.

${\displaystyle \pi \mathbf {P} =\pi ,}$

gdzie ${\displaystyle \pi }$ jest takim wektorem wierszowym, że:

${\displaystyle \sum _{i}\pi _{i}=1\quad \forall \pi _{i}\geqslant 0.}$

Jeśli rozkład początkowy ${\displaystyle \mathbf {x_{0}} }$ jest stacjonarny, to każdy kolejny rozkład ${\displaystyle \mathbf {x_{n}} }$ również jest stacjonarny.

Może nie istnieć żaden, istnieć jeden lub więcej niż jeden rozkład stacjonarny dla danego procesu.

Zobacz też

• 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

• O łańcuchach Markowa na stronach wydziału MIM Uniwersytetu Warszawskiego

Kontrola autorytatywna (model statystyczny):

• LCCN: sh85081369
• GND: 4134948-9
• BnF: 11932425d
• BNCF: 19104
• BNE: XX540042
• J9U: 987007553386405171

Encyklopedie internetowe:

• Britannica: topic/Markov-chain
• БРЭ: 2187018
• ЕСУ: 63754