Łańcuch 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  zmiennych losowych. Dziedzinę tych zmiennych nazywamy przestrzenią stanów, a realizacje  to stany w czasie  Jeśli rozkład warunkowy  jest funkcją wyłącznie zmiennej 
 

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

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ą  gdzie wyraz  wyraża się wzorem:
 

Z jednorodności wynika, że rzeczywiście  nie zależy od  Przykładowo element  oznacza prawdopodobieństwo przejścia ze stanu pierwszego do stanu trzeciego.

Równania Chapmana-Kołmogorowa 
Prawdopodobieństwem przejścia ze stanu  do stanu  w  krokach nazywa się prawdopodobieństwo warunkowe
 

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

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

gdzie przez  jest macierzą przejść w  krokach.

Klasyfikacja stanów 
Mówi się, że:
 stan  jest osiągalny ze stanu  jeśli 
 stany  i  są skomunikowane, jeśli są wzajemnie osiągalne. Oznaczenie: 

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  oznacza prawdopodobieństwo tego, że startując ze stanu  łańcuch kiedykolwiek do niego powróci.
 Jeśli  to stan  nazywany jest rekurencyjnym.
 Jeśli  to stan  nazywany jest chwilowym.

Każdy stan jest albo chwilowy albo rekurencyjny. Stan  jest rekurencyjny wtedy i tylko wtedy, gdy:

Rozkład stacjonarny 
Rozkład prawdopodobieństw na przestrzeni stanów  nazywany jest stacjonarnym wtedy i tylko wtedy, gdy spełniony jest warunek:
 

tj.
 

gdzie  jest takim wektorem wierszowym, że:
 

Jeśli rozkład początkowy  jest stacjonarny, to każdy kolejny rozkład  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

Ekonomia matematyczna
Transmisja danych
Procesy stochastyczne
Rachunek prawdopodobieństwa