Clanțuri Markov

de Victor Powell

cu text de Lewis Lehe

Clanțurile Markov, denumite după Andrey Markov, sunt sisteme matematice care sar de la o „stare” (o situație sau un set de valori) la alta. De exemplu, dacă ați realiza un model de lanț Markov al comportamentului unui bebeluș, ați putea include ca stări „joaca”, „mâncatul”, „dormitul” și „plânsul”, care împreună cu alte comportamente ar putea forma un „spațiu de stări”: o listă a tuturor stărilor posibile. În plus, deasupra spațiului de stări, un lanț Markov vă spune probabilitatea de a sări, sau „tranziția”, de la o stare la orice altă stare – de ex, șansa ca un bebeluș care se joacă în prezent să adoarmă în următoarele cinci minute fără să plângă mai întâi.

Un lanț Markov simplu, cu două stări, este prezentat mai jos.

viteza

Cu două stări (A și B) în spațiul nostru de stări, există 4 tranziții posibile (nu 2, deoarece o stare poate trece înapoi în ea însăși). Dacă ne aflăm la „A”, putem trece la „B” sau putem rămâne la „A”. Dacă ne aflăm la „B”, putem trece la „A” sau putem rămâne la „B”. În această diagramă cu două stări, probabilitatea de tranziție de la orice stare la orice altă stare este de 0,5.

Desigur, modelatorii reali nu desenează întotdeauna diagrame de lanț Markov. În schimb, ei folosesc o „matrice de tranziție” pentru a contabiliza probabilitățile de tranziție. Fiecare stare din spațiul de stare este inclusă o dată ca un rând și din nou ca o coloană, iar fiecare celulă din matrice vă spune probabilitatea de tranziție de la starea rândului său la starea coloanei sale. Astfel, în matrice, celulele fac aceeași treabă pe care o fac săgețile în diagramă.

Dacă spațiul de stări adaugă o stare, adăugăm un rând și o coloană, adăugând o celulă la fiecare coloană și rând existent. Acest lucru înseamnă că numărul de celule crește în mod pătratic pe măsură ce adăugăm stări la lanțul nostru Markov. Astfel, o matrice de tranziție apare destul de repede la îndemână, cu excepția cazului în care doriți să desenați o diagramă a lanțului Markov de gimnastică în junglă.

O utilizare a lanțurilor Markov este de a include fenomene din lumea reală în simulările pe calculator. De exemplu, am putea dori să verificăm cât de frecvent se va revărsa un nou baraj, care depinde de numărul de zile ploioase la rând. Pentru a construi acest model, începem cu următorul tipar de zile ploioase (R) și însorite (S):

Un mod de a simula această vreme ar fi să spunem doar „Jumătate din zile sunt ploioase. Prin urmare, fiecare zi din simularea noastră va avea o probabilitate de cincizeci la sută de ploaie”. Această regulă ar genera următoarea secvență în simulare:

Ați observat cum secvența de mai sus nu arată chiar ca cea originală? A doua secvență pare să sară de colo-colo, în timp ce prima (datele reale) pare să aibă o „aderență”. În datele reale, dacă este însorit (S) într-o zi, atunci și ziua următoare este, de asemenea, mult mai probabil să fie însorită.

Putem minici această „stickyness” cu un lanț Markov cu două stări. Când lanțul Markov se află în starea „R”, are o probabilitate de 0,9 de a rămâne pe loc și o șansă de 0,1 de a pleca în starea „S”. De asemenea, starea „S” are o probabilitate de 0,9 de a rămâne pe loc și o șansă de 0,1 de a trece în starea „R”.

În mâinile metereologilor, ecologiștilor, informaticienilor, inginerilor financiari și ale altor persoane care trebuie să modeleze fenomene mari, lanțurile Markov pot ajunge să fie destul de mari și puternice. De exemplu, algoritmul pe care Google îl folosește pentru a determina ordinea rezultatelor căutărilor, numit PageRank, este un tip de lanț Markov.

Acesta este un tip de lanț Markov.

Am inclus un „loc de joacă” al lanțurilor Markov, unde vă puteți crea propriile lanțuri Markov, jucându-vă cu o matrice de tranziție. Iată câteva pe baza cărora puteți lucra ca exemplu: ex1, ex2, ex3 sau generați unul la întâmplare. Textul matricei de tranziție va deveni roșu dacă matricea furnizată nu este o matrice de tranziție validă. Rândurile matricei de tranziție trebuie să totalizeze 1. De asemenea, trebuie să existe același număr de rânduri ca și coloane.

Puteți accesa și o versiune fullscreen la setosa.io/markov

.