PL 
EnglishDomyślny
Українська🎲 Łańcuch Markowa — symulator macierzy przejść
Interaktywna wizualizacja łańcuchów Markowa. Edytuj macierz przejść, obserwuj ewolucję rozkładów stanów, wyznaczaj rozkłady stacjonarne i symuluj błądzenie losowe po grafie. Zawiera pogodę, PageRank i hazardzistę
O symulatorze łańcuchów Markowa
Ten symulator wizualizuje dyskretny w czasie łańcuch Markowa jako graf skierowany stanów połączonych prawdopodobieństwami przejścia. Cały układ jest zdefiniowany macierzą przejść P, w której każdy element Pᵢⱼ podaje prawdopodobieństwo przejścia ze stanu i do stanu j, a każdy wiersz sumuje się do 1. W każdej iteracji rozkład prawdopodobieństwa π jest aktualizowany przez iloczyn wektor-macierz π(t+1) = π(t)·P, a wielkość węzłów odzwierciedla zmieniający się rozkład.
Macierz można edytować bezpośrednio w tabeli (wiersze są automatycznie normalizowane), wybrać presety takie jak Pogoda, PageRank, Gracz i Losowy, oraz ustawić liczbę kroków wykonywanych na klatkę animacji. Pojedynczy losowy wędrowiec może też przemieszczać się przez łańcuch krok po kroku, pokazując konkretne zrealizowane trajektorie. Takie łańcuchy leżą u podstaw algorytmu PageRank, modelowania pogody, teorii kolejek oraz próbkowania MCMC w statystyce i uczeniu maszynowym.
Najczęściej zadawane pytania
Czym jest łańcuch Markowa?
Łańcuch Markowa to proces stochastyczny przeskakujący między skończonym zbiorem stanów, w którym prawdopodobieństwo kolejnego stanu zależy wyłącznie od stanu obecnego, a nie od wcześniejszej historii. Ta bezpamięciowość nazywana jest własnością Markowa. Łańcuch jest w pełni określony przez swoją macierz przejść P.
Do czego służy macierz przejść?
Każdy element Pᵢⱼ to prawdopodobieństwo przejścia ze stanu i do stanu j w jednym kroku. Każdy wiersz musi sumować się do 1, ponieważ łańcuch musi gdzieś przejść. W tym symulatorze można wpisać dowolne nieujemne wartości do tabeli, a wiersze są automatycznie renormalizowane, aby pozostały poprawnymi rozkładami prawdopodobieństwa.
Jak rozkład ewoluuje w każdym kroku?
Symulator utrzymuje rozkład prawdopodobieństwa π nad stanami i aktualizuje go regułą π(t+1) = π(t)·P, czyli zwykłym mnożeniem wektora przez macierz. Powtarzanie tego jest równoważne obliczeniu π(0)·Pᵗ. Procenty pokazane na węzłach i wykresie słupkowym to bieżące wartości tego rozkładu.
Czym jest rozkład stacjonarny?
Rozkład stacjonarny π* spełnia π* = π*·P, co oznacza, że nie zmienia się pod wpływem kolejnego kroku łańcucha. Jest to lewy wektor własny P dla wartości własnej 1, równoważnie wektor własny Pᵀ dla wartości własnej 1. Dla łańcucha ergodycznego rozkład zbiega do tego jednoznacznego π* niezależnie od punktu startowego.
Co pokazują cztery presety?
Pogoda to klasyczny model 3-stanowy słonecznie/pochmurno/deszczowo. PageRank to graf sieci webowej z 4 węzłami ilustrujący, jak Google szereguje strony według prawdopodobieństwa stacjonarnego. Gracz to łańcuch typu ruina gracza z dwoma stanami pochłaniającymi na 0 zł i 3 zł. Losowy generuje nowy łańcuch o 3 do 5 stanach z losowo wygenerowanymi, znormalizowanymi wierszami.
Co robi przycisk wędrowca krokowego?
Wędrowiec to pojedynczy znacznik, który przy każdym kliknięciu wykonuje jedno rzeczywiste losowe przejście, wybierając kolejny stan przez losowanie z bieżącego wiersza P. Jego trajektoria ilustruje jedną konkretną realizację łańcucha, w przeciwieństwie do gładkiego rozkładu π, który reprezentuje uśrednione zachowanie nieskończenie wielu takich wędrowców.
Co kontroluje suwak liczby kroków na klatkę?
Ten suwak ustawia, ile aktualizacji rozkładu (i kroków wędrowca) jest wykonywanych w każdej klatce animacji, od 1 do 50. Wyższa wartość przyspiesza łańcuch, dzięki czemu można szybciej zaobserwować zbieżność do rozkładu stacjonarnego, natomiast wartość 1 pozwala obserwować każdą iterację ze szczegółami.
Kiedy łańcuch zbiega do jednoznacznego rozkładu stacjonarnego?
Zbieżność do pojedynczego rozkładu stacjonarnego z dowolnego punktu startowego jest gwarantowana, gdy łańcuch jest ergodyczny, czyli nieprzywiedlny (każdy stan może osiągnąć każdy inny) i nieokresowy. Preset ruiny gracza nie jest ergodyczny, ponieważ 0 zł i 3 zł są stanami pochłaniającymi, więc jego długookresowe zachowanie zależy od stanu początkowego.
Co decyduje o szybkości zbieżności?
Tempo zbieżności, czyli mieszania, jest wyznaczane przez moduł drugiej co do wielkości wartości własnej P. Różnica między 1 a tą wartością to luka spektralna: duża luka spektralna oznacza, że błędy szybko maleją i łańcuch szybko się miesza, a mała luka oznacza wolną zbieżność. Dlatego niektóre łańcuchy stabilizują się w kilku krokach, a inne wymagają ich znacznie więcej.
Jak to się łączy z PageRank i MCMC?
PageRank traktuje strony internetowe jako stany, a losowego internautę jako wędrowca; ważność strony to jej prawdopodobieństwo stacjonarne. Markov chain Monte Carlo odwraca tę ideę, konstruując łańcuch, którego rozkład stacjonarny jest celem, z którego chcemy próbkować, a następnie pobiera próbki, uruchamiając łańcuch — fundament statystyki bayesowskiej i fizyki.