Łańcuchy Markowa: Przyszłość Zależy tylko od Teraz

Proces zapominający o swojej historii

Większość sekwencji zdarzeń zależy od całej swojej przeszłości. Markowowska lancuch to wyjątkowa, łatwa do rozwiązywania sytuacja, w której nie zależy: prawdopodobieństwo następnego stanu zależy tylko od bieżącego stanu, nigdy nie zwraca się do tego, jak proces osiągnął ten stan. Formalnie, ciąg zmiennych losowych X₀, X₁, X₂, … nad przestrzenią stanów S ma własność Markowa, gdy

P(X_(n+1)=j | X_n=i, X_(n-1)=i_(n-1), ..., X_0=i_0) = P(X_(n+1)=j | X_n=i) // wszystko, co przeszłość może powiedzieć o przyszłości // jest już podsumowane bieżącym stanem i Ta jedna „nie pamiętająca” założenie jest to, co sprawia, że ogromny zakres rzeczywistych systemów jest matematycznie łatwy do rozwiązywania — sekwencje pogodowe, gry planszowe, reakcje chemiczne, przeglądanie stron internetowych i algorytmy próbkowania, które podpinają współczesną statystykę bayesowską.

P(X_(n+1)=j | X_n=i, X_(n-1)=i_(n-1), ..., X_0=i_0) = P(X_(n+1)=j | X_n=i)

// everything the past could tell you about the future
// is already summarised by the current state i

Macierz przejścia

Wszystkie jednokrorotne prawdopodobieństwa są zbierane w macierzy przejścia P, gdzie wpis P[i][j] reprezentuje prawdopodobieństwo przechodu z stanu i do stanu j, a każda linia sumuje się do 1. Przykład małego modelu pogody z dwoma stanami pozwala wyróżnić ideę:

stanów: {Słońce, Deszcz} P = | 0.8 0.2 | // linia „Słońce”: pozostanie słończe 80%, zmieni się na deszcz 20% | 0.4 0.6 | // linia „Deszcz”: zmieni się na słońce 40%, pozostanie deszcz 60% dystrybucja po n krokach: π_n = π_0 · P^n Stanów można podzielić według ich długoterminowego zachowania: stałe stany są gwarantowane powrót do nich nieskończenie wiele razy, transitoriowe stany mogą nigdy więcej nie pojawić się po pewnym momencie, a absorbujące stany – raz wprowadzone – nigdy nie zostaną opuszczone (P[i][i] = 1). Łańcuch jest niespójny, jeśli każdy stan może dotrzeć do każdego innego stanu, a aperiodyczny, jeśli nie jest zablokowany na odwiedzanie stanów w ustalonej długości cyklu. Obie właściwości gwarantują coś mocnego: jednoznaczne długoterminowe rozkład.

states: {Sunny, Rainy}
P = | 0.8  0.2 |     // row "Sunny": stay sunny 80%, turn rainy 20%
    | 0.4  0.6 |     // row "Rainy": turn sunny 40%, stay rainy 60%

distribution after n steps:  π_n = π_0 · P^n

Stacjonarne rozkłady i szybkość ich osiągania

Rozkład π* jest stacjonarny, jeśli po jednym dodatkowym przejściu pozostaje on niezmieniony: π* = π* · P. Twierdzenie Perrona-Frobeniusa gwarantuje, że irreducybilna i bezokresowa macierz stochastyczna ma jednoznaczny taki π*, osiągalny z dowolnego początkowego rozkładu. W przypadku przykładu pogodowego, rozwiązując równania równowagi, otrzymujemy π*[Sunny] = 0,4 / (0,2 + 0,4) = 2/3 i π*[Rainy] = 1/3 — niezależnie od tego, z którego dnia cyklu pogodowego zaczęliśmy.

Dla większych przestrzeni stanów rozwiązanie równań równowagi ręcznie jest niemożliwe, więc standardowym narzędziem jest iteracja potęgowa: rozpoczęcie się od dowolnego rozkładu i powtarzane mnożenie przez P aż do momentu zatrzymania zmian. Szybkość zatrzymania zmian to czas mieszania łańcucha, regulowany przez przestronność spektralną — odległość między największym wartościowym własnym (zawsze równe 1) a drugim największym. łańcuch o bliskich stanach absorbujących lub przejściach brzegowych mieszany jest wolno; dobrze połączony łańcuch szybko się miesza.

PageRank: a random surfer as a Markow chain

Algorytm oryginalny PageRanka firmy Google jest ukrytym Markowemowym ciągiem: wyobraź sobie "losowego surfera", który, z dowolnej strony internetowej, klikając losowo jedno z wychodzących linków. Graf łączyńcy sieci web definiuje macierz przejść, a rank każdej strony jest prosto jego prawdopodobieństwem w rozkładzie stacjonarnym tego ciągu — strony, do których wiele dobrze połączonych stron wskaże linki, akumulują więcej tego prawdopodobieństwa. Dwa praktyczne poprawki pozwalają na działanie modelu w rzeczywistej sieci: strony z brakiem wychodzących łączy rozprowadzają swoje prawdopodobieństwo równomiernie, a nie blokują surfera, a czynnik opóźniający d (zwyczajnie 0,85) sprawia, że surfarz czasami teleportuje się do losowo wybranej strony zamiast kliknąć link.

G = d · P + (1 − d)/n · 1·1ᵀ        // the "Google matrix"
PageRank = stationary distribution of G

// G is irreducible & aperiodic no matter what the link graph looks like,
// so ~50-100 rounds of power iteration reliably converge on real web scale

Randomne chwile i zagubienie gracza

Najprostszym ciągiem Markowa jest jednowymiarowy random walk: przesuwanie się o +1 z prawdopodobieństwem p, o −1 z prawdopodobieństwem q = 1 − p. Gdy p = q = 0,5, chwilę jest rekurencyjną — zwraca się do punktu wyjścia z prawdopodobieństwem 1, ale jak tylko p ≠ q, zaczyna się odchylać w kierunku +∞ lub −∞ i staje się przelączna. To matematyka za tajną zagubienie gracza: gracz z kwotą £k powtarzająco gra przeciwko kasynu o niemal nieskończonych finansach, wygrywając £1 z prawdopodobieństwem p, aż osiągnie cel na kwocie £N lub przegra wszystko. Prawdopodobieństwo zagubienia ma postać zamkniętą i drastycznie spada w chwili, gdy p spadnie nawet nieco poniżej 0,5 — dokładnie dlatego każde kasyno zaprojektowane jest tak, aby p < 0,5. Zaskakujący fakt związany z tym, twierdzenie Pólyi, mówi, że symetryczny random walk jest rekurencyjny w jednowymiarowej i dwuwymiarowej przestrzeni, ale przelączny w trójwymiarowej i wyższych: przypuszczalnie pijany człowiek zawsze znajdzie sposób do domu, a pijański ptak latający w 3D niezwykle rzadko to robi.

Jak symulacja tutaj wykorzystuje teorie

Symulacja na tej stronie pozwala edytować bezpośrednio mały macierz przejść i obserwować przepływ masy prawdopodobieństwa między stanami krok po kroku, zbiegając wizualnie ku rozkładowi stałemu przewidzianemu przez teorię powyżej. Ponieważ łańcuch rysuje nowe przejścia na ekranie, możesz obserwować zjawisko mieszania, a nie tylko je liczyć: graf dobrze połączony osiąga stały rozkład w kilku krokach, podczas gdy graf z niewielkim przeszkodnictwem między dwiema grupami stanów widocznie wymaga znacznie więcej czasu na równowagę — spektralny dziurawik staje się dotycznym.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Markov Chains i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.