Łańcuch Markowa — macierz przejścia i zastosowania

Łańcuch Markowa to model systemu, który przechodzi między stanami krok po kroku, na przykład między stanem słonecznym i deszczowym. Kluczowa zasada mówi, że następny krok zależy tylko od stanu bieżącego, jeśli jest to rozsądne założenie dla modelowanego systemu.

Te prawdopodobieństwa jednokrokowe zbiera się w macierzy przejścia. Jeśli proces znajduje się teraz w stanie $i$ i przechodzi następnie do stanu $j$ z prawdopodobieństwem $P_{ij}$, to

$$P = (P_{ij})$$

Dla skończonego łańcucha Markowa każdy wiersz macierzy $P$ sumuje się do $1$, ponieważ proces musi przejść do jednego z dozwolonych stanów następnych.

Co oznacza własność Markowa

Formalnie zapisuje się to tak:

$$P(X_{n+1} = j \mid X_n = i, X_{n-1}, \ldots, X_0) = P(X_{n+1} = j \mid X_n = i)$$

Oznacza to, że gdy znasz już bieżący stan $X_n = i$, wcześniejsza historia nie zmienia prawdopodobieństwa następnego kroku w tym modelu.

Ten warunek ma znaczenie. Niektóre rzeczywiste systemy mają pamięć, trendy albo opóźnione efekty, więc łańcuch Markowa jest dobrym modelem tylko wtedy, gdy przybliżenie „bieżący stan wystarcza” jest rozsądne.

Jak odczytywać macierz przejścia

Załóżmy, że prosty model pogody ma dwa stany:

• Słonecznie
• Deszczowo

Użyj tej macierzy przejścia:

$$P = \begin{bmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{bmatrix}$$

Każdy wiersz odczytuj jako stan bieżący, a każdą kolumnę jako stan następny.

Jeśli więc dziś jest słonecznie, model mówi, że jutro będzie słonecznie z prawdopodobieństwem $0.8$, a deszczowo z prawdopodobieństwem $0.2$. Jeśli dziś jest deszczowo, jutro będzie słonecznie z prawdopodobieństwem $0.4$, a deszczowo z prawdopodobieństwem $0.6$.

Przykład obliczeniowy: pogoda w ciągu dwóch dni

Załóżmy, że dzisiejszy rozkład ma postać

$$\mathbf{v}_0 = \begin{bmatrix} 1 & 0 \end{bmatrix}$$

Oznacza to, że model zaczyna w stanie słonecznym z prawdopodobieństwem $1$.

Rozkład jutro wynosi

$$\mathbf{v}_1 = \mathbf{v}_0 P = \begin{bmatrix} 1 & 0 \end{bmatrix} \begin{bmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{bmatrix} = \begin{bmatrix} 0.8 & 0.2 \end{bmatrix}$$

Po jednym kroku model daje więc $80\%$ szans na pogodę słoneczną i $20\%$ szans na pogodę deszczową.

Po jeszcze jednym kroku

$$\mathbf{v}_2 = \mathbf{v}_1 P = \begin{bmatrix} 0.8 & 0.2 \end{bmatrix} \begin{bmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{bmatrix} = \begin{bmatrix} 0.72 & 0.28 \end{bmatrix}$$

Teraz prawdopodobieństwo pogody słonecznej wynosi $0.72$, a deszczowej $0.28$.

Nie chodzi tylko o same rachunki. Macierz aktualizuje cały rozkład prawdopodobieństwa krok po kroku, dlatego łańcuchy Markowa są przydatne w procesach powtarzalnych.

Gdzie stosuje się łańcuchy Markowa

Łańcuchy Markowa są użyteczne wtedy, gdy system zmienia się etapami i chcesz znać prawdopodobieństwa tego, co stanie się dalej.

Typowe przykłady to modele pogody, ruch w grach planszowych, modele kolejkowe i uproszczona nawigacja po stronach internetowych. W każdym z tych przypadków model pomaga tylko wtedy, gdy stany są dobrze dobrane, a prawdopodobieństwa przejścia są realistyczne.

Typowe błędy przy łańcuchach Markowa

Traktowanie każdego procesu losowego jako procesu Markowa

Proces nie staje się automatycznie łańcuchem Markowa tylko dlatego, że jest losowy. Model wymaga, aby zachowanie w następnym kroku było wyznaczone przez stan bieżący w sposób zgodny z definicją stanów.

Zapominanie, co oznaczają wiersze

Ludzie często mylą wiersze z kolumnami. Trzeba trzymać się jednej spójnej konwencji. Na tej stronie wiersze oznaczają stany bieżące, a kolumny stany następne.

Używanie niepoprawnych prawdopodobieństw

Każdy element musi należeć do przedziału od $0$ do $1$, a każdy wiersz musi sumować się do $1$ w standardowej macierzy przejścia skończonego łańcucha Markowa.

Zakładanie, że model przewiduje jedną pewną przyszłość

Łańcuch Markowa zwykle daje prawdopodobieństwa, a nie pewność. Nawet jeśli jeden stan jest bardziej prawdopodobny, kilka stanów następnych może nadal być możliwych.

Zachowanie długookresowe zależy od łańcucha

Niektóre łańcuchy Markowa dążą do stabilnego rozkładu długookresowego, często nazywanego rozkładem stacjonarnym. Nie dzieje się tak jednak w każdym łańcuchu, a szczegóły zależą od własności łańcucha, takich jak komunikacja między stanami i okresowość wzorca przejść.

Dlatego można traktować wielokrotne mnożenie przez $P$ jako sposób badania zachowania długookresowego, ale nie należy zakładać zbieżności bez sprawdzenia odpowiednich warunków.

Kiedy łańcuch Markowa jest dobrym modelem

Użyj łańcucha Markowa, gdy wszystkie poniższe warunki są w przybliżeniu spełnione:

• Proces można opisać za pomocą rozsądnej liczby stanów.
• Czas przebiega w dyskretnych krokach albo zdecydowano się modelować go w ten sposób.
• Prawdopodobieństwa następnego kroku są sensownie wyznaczone przez stan bieżący.

Jeśli te warunki nie są spełnione, model może nadal być zgrubnym przybliżeniem, ale warto powiedzieć to wprost.

Spróbuj własnej wersji

Zbuduj model z trzema stanami, na przykład niski, średni i wysoki popyt. Wybierz prawdopodobieństwa w wierszach tak, aby każdy sumował się do $1$, ustal rozkład początkowy i oblicz następny krok za pomocą $\mathbf{v}_{n+1} = \mathbf{v}_n P$. Jeśli chcesz pójść dalej, wykonaj drugą aktualizację i sprawdź, czy rozkład zaczyna się stabilizować według pewnego wzorca.