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

Z Wikipedii, wolnej encyklopedii
[wersja przejrzana][wersja przejrzana]
Usunięta treść Dodana treść
EinsBot (dyskusja | edycje)
m →‎Linki zewnętrzne: Robot zamienia kategorię
Linia 19: Linia 19:
=== Macierz przejść ===
=== Macierz przejść ===
==== Definicja ====
==== 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ą '''P''', gdzie wyraz (''i'', ''j'') wyraża się wzorem
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ą '''P''', gdzie wyraz (''i'', ''j'') wyraża się wzorem:


: <math>p_{i,j} = P(X_{n+1}=j\mid X_n=i).</math>
: <math>p_{i,j} = P(X_{n+1}=j\mid X_n=i).</math>
Linia 29: Linia 29:
:<math>p_{i,j}^{(n)} = P(X_{m+n}=j| X_m = i)</math>.
:<math>p_{i,j}^{(n)} = P(X_{m+n}=j| X_m = i)</math>.


Dla prawdopodobieństw przejść spełnione są następujace równanie, nazywane ''równaniami Chapmana-Kołmogorowa'':
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>.
:<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 ''j'' można po drodze przejść przez dowolny inny stan skomunikowany z ''j'' i ''i''. Stosując zapis macierzowy, równania Chapmana-Kołmogorowa można zapisać w postaci:
Intuicyjne jest jasne, że aby dojść do stanu ''j'' można po drodze przejść przez dowolny inny stan skomunikowany z ''j'' i ''i''. Stosując zapis macierzowy, równania Chapmana-Kołmogorowa można zapisać w postaci:
Linia 36: Linia 36:


=== Klasyfikacja stanów ===
=== Klasyfikacja stanów ===
Mówi się, że
Mówi się, że:
* stan ''i'' jest osiągalny ze stanu ''j'', jeśli ''p''<sub>''j,i''</sub> >0;
* stan ''i'' jest osiągalny ze stanu ''j'', jeśli ''p''<sub>''j,i''</sub> >0;
* stany ''i'' i ''j'' są skomunikowane, jeśli są wzajemnie osiągalne. Oznaczenie: ''i'' &nbsp;↔&nbsp; ''j''.
* stany ''i'' i ''j'' są skomunikowane, jeśli są wzajemnie osiągalne. Oznaczenie: ''i'' &nbsp;↔&nbsp; ''j''.
Linia 47: Linia 47:
* Jeśli ''f''<sub>''i''</sub> < 1 to stan ''i'' nazywany jest ''chwilowym''.
* Jeśli ''f''<sub>''i''</sub> < 1 to stan ''i'' nazywany jest ''chwilowym''.


Każdy stan jest albo chwilowy albo rekurencyjny. Stan ''i'' jest rekurencyjny wtedy i tylko wtedy, gdy
Każdy stan jest albo chwilowy albo rekurencyjny. Stan ''i'' jest rekurencyjny wtedy i tylko wtedy, gdy:
:<math>\sum_{n=1}^{\infty} p_{i,i}^{(n)} = \infty. </math>
:<math>\sum_{n=1}^{\infty} p_{i,i}^{(n)} = \infty. </math>


=== Rozkład stacjonarny ===
=== Rozkład stacjonarny ===
Rozkład prawdopodobieństw na przestrzeni stanów '''S''' nazywany jest ''[[stacjonarność|stacjonarnym]]'' wtedy i tylko wtedy, gdy spełniony jest warunek
Rozkład prawdopodobieństw na przestrzeni stanów '''S''' nazywany jest ''[[stacjonarność|stacjonarnym]]'' wtedy i tylko wtedy, gdy spełniony jest warunek:


: <math>\pi_{j} = \sum_{i \in S} \pi_i p_{ij},</math>
: <math>\pi_{j} = \sum_{i \in S} \pi_i p_{ij},</math>
tj.
tj.
: <math> \pi\mathbf{P} = \pi, </math>
: <math> \pi\mathbf{P} = \pi, </math>
gdzie π jest takim wektorem wierszowym, że
gdzie π jest takim wektorem wierszowym, że:
: <math>\sum_i \pi_i = 1 \quad \forall \pi_i \ge 0 </math>.
: <math>\sum_i \pi_i = 1 \quad \forall \pi_i \ge 0 </math>.



Wersja z 14:49, 19 mar 2015

Przykład procesu Markowa

Proces Markowacią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 X1, X2, X3, ... zmiennych losowych. Dziedzinę tych zmiennych nazywamy przestrzenią stanów, a realizacje Xn to stany w czasie n. Jeśli rozkład warunkowy Xn+1 jest funkcją wyłącznie zmiennej Xn:

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

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

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

Równania Chapmana-Kołmogorowa

Prawdopodobieństwem przejścia ze stanu i do stanu j w n 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 j można po drodze przejść przez dowolny inny stan skomunikowany z j i i. Stosując zapis macierzowy, równania Chapmana-Kołmogorowa można zapisać w postaci:

,

gdzie przez Pn jest macierzą przejść w n krokach.

Klasyfikacja stanów

Mówi się, że:

  • stan i jest osiągalny ze stanu j, jeśli pj,i >0;
  • stany i i j są skomunikowane, jeśli są wzajemnie osiągalne. Oznaczenie: i  ↔  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 fi oznacza prawdopodobieństwo tego, że startując ze stanu i łańcuch kiedykolwiek do niego powróci.

  • Jeśli fi = 1 to stan i nazywany jest rekurencyjnym.
  • Jeśli fi < 1 to stan i nazywany jest chwilowym.

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

Rozkład stacjonarny

Rozkład prawdopodobieństw na przestrzeni stanów S 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ż

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