PL 
EnglishDomyślny
Українська🔗 Łańcuchy Markowa
Edytuj macierz przejść, przemieszczaj losowego wędrowca między stanami i obserwuj, jak rozkład zbiega do wektora stacjonarnego stojącego za algorytmem PageRank.
O łańcuchach Markowa
Ta symulacja animuje dyskretny w czasie łańcuch Markowa na skończonym zbiorze stanów. Losowy wędrowiec przeskakuje między stanami zgodnie z macierzą przejść P, w której każdy wiersz zawiera prawdopodobieństwa przejścia do wszystkich pozostałych stanów i sumuje się do 1. Diagram stanów rysuje węzły na okręgu ze strzałkami o grubości proporcjonalnej do prawdopodobieństwa, a wykres słupkowy porównuje obserwowane częstości odwiedzin z rozkładem stacjonarnym π, wyznaczanym metodą iteracji potęgowej π = πP.
Menu presetów wczytuje gotowe łańcuchy (Pogoda, PageRank, Ruina gracza, Hardy'ego-Weinberga, losowy łańcuch 4-stanowy), suwak opóźnienia kroku ustawia tempo od 50 do 2000 ms, a przyciski Krok, Uruchom i Restart sterują wędrówką. Łańcuchy Markowa leżą u podstaw algorytmu PageRank Google, rozpoznawania mowy, modeli kolejkowych i genetyki populacyjnej, co czyni je jednym z najszerzej stosowanych narzędzi teorii prawdopodobieństwa.
Najczęściej zadawane pytania
Czym jest łańcuch Markowa?
Łańcuch Markowa to proces stochastyczny przemieszczający się między zbiorem stanów, w którym prawdopodobieństwo kolejnego stanu zależy wyłącznie od stanu obecnego, a nie od drogi, jaką do niego dotarto. Ta bezpamięciowa właściwość nazywana jest własnością Markowa. Każdy krok jest wyznaczany przez macierz przejść wczytaną z wybranego presetu.
Co pokazuje wykres słupkowy na dole?
Fioletowe słupki pokazują empiryczne częstości odwiedzin, jakie faktycznie zgromadził wędrowiec, natomiast złote słupki pokazują teoretyczny rozkład stacjonarny π. W miarę wykonywania kolejnych kroków fioletowe słupki powinny zbiegać do złotych, ilustrując długookresowe zachowanie łańcucha.
Jak obliczany jest rozkład stacjonarny?
Symulacja korzysta z iteracji potęgowej: zaczyna od rozkładu jednostajnego i wielokrotnie mnoży go przez macierz przejść P, aż zmiana między kolejnymi iteracjami spadnie poniżej 1e-8, maksymalnie przez 2000 iteracji. Wynikiem jest wektor π spełniający równanie π = πP, czyli prawdopodobieństwa równowagi łańcucha.
Co robią przyciski Krok, Uruchom i Restart?
Krok przesuwa wędrówkę dokładnie o jedno przejście. Uruchom rozpoczyna ciągłe wykonywanie kroków z wybranym opóźnieniem i zmienia się w przycisk Pauza. Restart wczytuje ponownie bieżący preset, czyszcząc licznik kroków i historię odwiedzin, dzięki czemu można rozpocząć losową wędrówkę od nowa.
Co kontroluje suwak opóźnienia kroku?
Ustawia czas między automatycznymi przejściami podczas działania, od 50 ms (szybko) do 2000 ms (wolno), w krokach co 50 ms, z wartością domyślną 600 ms. Zmiana suwaka podczas działania restartuje timer z nowym tempem, dzięki czemu można obserwować każdy skok lub przyspieszyć zbieżność.
Co oznacza statystyka zbieżności?
Po wykonaniu ponad 20 kroków symulacja podaje średnią bezwzględną różnicę między empirycznymi częstościami odwiedzin a rozkładem stacjonarnym π, wyrażoną jako procent. Mniejsze wartości oznaczają, że losowa wędrówka coraz ściślej odpowiada teoretycznej równowadze.
Dlaczego preset Ruina gracza zachowuje się inaczej?
Ruina gracza ma dwa stany pochłaniające, 0 zł i 4 zł, do których łańcuch może wejść, ale nigdy ich nie opuści. Takie łańcuchy nie mają w zwykłym sensie jednego wewnętrznego rozkładu stacjonarnego, więc wędrówka w końcu zostaje uwięziona na jednej z granic, modelując gracza bankrutującego lub osiągającego swój cel.
Czym jest preset PageRank?
Modeluje internautę losowo podążającego za linkami między czterema stronami. PageRank, algorytm stojący za wczesną wyszukiwarką Google, traktuje sieć jako gigantyczny łańcuch Markowa i szereguje strony według ich prawdopodobieństwa stacjonarnego, czyli tego, jak często losowy internauta na nich ląduje w długim okresie.
Czy symulacja jest fizycznie i matematycznie dokładna?
Tak, jeśli chodzi o przedstawione metody: przejścia są poprawnie losowane z każdego wiersza macierzy P za pomocą losowania skumulowanego prawdopodobieństwa, a π jest wyznaczane przez rzeczywistą iterację potęgową. Macierze w presetach są przykładami ilustracyjnymi, a nie zmierzonymi danymi rzeczywistymi, więc jakościowe zachowanie jest wierne, nawet jeśli konkretne liczby są stylizowane.
Czy każdy łańcuch Markowa osiągnie jednoznaczny rozkład stacjonarny?
Nie zawsze. Jednoznaczny rozkład stacjonarny, do którego zbiega wędrówka, jest gwarantowany, gdy łańcuch jest nieprzywiedlny i nieokresowy. Łańcuchy ze stanami pochłaniającymi, rozłącznymi składowymi lub ścisłą okresowością mogą nie spełniać tego warunku, dlatego presety takie jak Ruina gracza zachowują się jakościowo inaczej niż łańcuch Pogoda.