Explained Visually
By Victor Powell
with text by Lewis Lehe
Markov chains, nazwane po Andrey Markov, są matematycznymi systemami, które przeskakują z jednego „stanu” (sytuacja lub zestaw wartości) do innego. Na przykład, jeśli zrobiłeś model łańcucha Markowa zachowania dziecka, możesz włączyć „zabawę”, „jedzenie”, „spanie” i „płacz” jako stany, które wraz z innymi zachowaniami mogą tworzyć „przestrzeń stanów”: listę wszystkich możliwych stanów. Dodatkowo, na szczycie przestrzeni stanów, łańcuch Markowa mówi o prawdopodobieństwie przeskoczenia, lub „przejścia”, z jednego stanu do innego stanu – np, szansa, że bawiące się dziecko zaśnie w ciągu następnych pięciu minut bez wcześniejszego płaczu.
Prosty, dwustanowy łańcuch Markowa pokazany jest poniżej.
prędkość
Mając dwa stany (A i B) w naszej przestrzeni stanów, istnieją 4 możliwe przejścia (nie 2, ponieważ stan może przejść z powrotem w siebie). Jeśli jesteśmy w 'A’ możemy przejść do 'B’ lub pozostać w 'A’. Jeśli jesteśmy w stanie 'B’, możemy przejść do 'A’ lub pozostać w 'B’. W tym dwustanowym diagramie prawdopodobieństwo przejścia z dowolnego stanu do dowolnego innego stanu wynosi 0,5.
Oczywiście, prawdziwi modelarze nie zawsze rysują diagramy łańcuchów Markowa. Zamiast tego używają „macierzy przejść”, aby policzyć prawdopodobieństwa przejść. Każdy stan w przestrzeni stanów jest zawarty raz jako wiersz i ponownie jako kolumna, a każda komórka w macierzy mówi o prawdopodobieństwie przejścia ze stanu w jej wierszu do stanu w jej kolumnie. Tak więc w macierzy komórki wykonują tę samą pracę, co strzałki na diagramie.
A B
Jeśli przestrzeń stanów dodaje jeden stan, dodajemy jeden wiersz i jedną kolumnę, dodając jedną komórkę do każdej istniejącej kolumny i wiersza. Oznacza to, że liczba komórek rośnie czterokrotnie w miarę dodawania stanów do naszego łańcucha Markowa. Tak więc, macierz przejść przydaje się dość szybko, chyba że chcesz narysować diagram łańcucha Markowa w dżungli.
Jednym z zastosowań łańcuchów Markowa jest uwzględnienie rzeczywistych zjawisk w symulacjach komputerowych. Na przykład, możemy chcieć sprawdzić, jak często nowa tama będzie się przelewać, co zależy od liczby deszczowych dni z rzędu. Aby zbudować ten model, zaczynamy od następującego schematu deszczowych (R) i słonecznych (S) dni:
Jednym ze sposobów symulacji tej pogody byłoby po prostu powiedzenie „Połowa dni jest deszczowa. Dlatego każdy dzień w naszej symulacji będzie miał pięćdziesiąt procent szans na deszcz.” Ta reguła wygenerowałaby następującą sekwencję w symulacji:
Czy zauważyłeś jak powyższa sekwencja nie wygląda całkiem jak oryginał? Druga sekwencja wydaje się skakać dookoła, podczas gdy pierwsza (prawdziwe dane) wydaje się mieć „lepkość”. W rzeczywistych danych, jeśli jest słonecznie (S) jednego dnia, to następny dzień jest również o wiele bardziej prawdopodobny, że będzie słoneczny.
Możemy zminimalizować tę „lepkość” za pomocą dwustanowego łańcucha Markowa. Kiedy łańcuch Markowa jest w stanie „R”, ma 0.9 prawdopodobieństwa pozostania w miejscu i 0.1 szansy odejścia do stanu „S”. Podobnie, stan „S” ma 0,9 prawdopodobieństwa pozostania w miejscu i 0,1 szansy przejścia do stanu „R”.
W rękach metereologów, ekologów, informatyków, inżynierów finansowych i innych ludzi, którzy muszą modelować duże zjawiska, łańcuchy Markowa mogą stać się dość duże i potężne. Na przykład algorytm, którego Google używa do określania kolejności wyników wyszukiwania, zwany PageRank, jest rodzajem łańcucha Markowa.
Powyżej zamieściliśmy „plac zabaw” z łańcuchami Markowa, gdzie możesz tworzyć własne łańcuchy Markowa, bawiąc się macierzą przejść. Oto kilka przykładów do pracy: ex1, ex2, ex3 lub wygeneruj jeden losowo. Tekst macierzy przejścia zmieni kolor na czerwony, jeśli podana macierz nie jest poprawną macierzą przejścia. Wiersze macierzy przejścia muszą mieć sumę 1. Musi być również taka sama liczba wierszy jak kolumn.
Możesz również uzyskać dostęp do wersji pełnoekranowej na setosa.io/markov
.