Markov Chains

Door Victor Powell

met tekst van Lewis Lehe

Markov ketens, genoemd naar Andrey Markov, zijn wiskundige systemen die van de ene “toestand” (een situatie of een verzameling waarden) naar de andere springen. Als u bijvoorbeeld een Markov-ketenmodel van het gedrag van een baby zou maken, zou u “spelen”, “eten”, “slapen” en “huilen” als toestanden kunnen opnemen, die samen met andere gedragingen een “toestandsruimte” zouden kunnen vormen: een lijst van alle mogelijke toestanden. Bovenop de toestandsruimte vertelt een Markov-keten je bovendien de waarschijnlijkheid dat je van de ene toestand naar de andere springt, of “overgaat” – bv, de kans dat een baby die op dat moment aan het spelen is, in de komende vijf minuten in slaap valt zonder eerst te huilen.

Een eenvoudige Markov-keten met twee toestanden ziet u hieronder.

snelheid

Met twee toestanden (A en B) in onze toestandsruimte, zijn er 4 mogelijke overgangen (geen 2, want een toestand kan weer in zichzelf overgaan). Als we in ‘A’ zijn, kunnen we naar ‘B’ gaan of in ‘A’ blijven. Als we in ‘B’ zijn, kunnen we naar ‘A’ gaan of in ‘B’ blijven. In dit diagram met twee toestanden is de waarschijnlijkheid van een overgang van een toestand naar een andere toestand 0,5.

Natuurlijk tekenen echte modelleurs niet altijd Markov-ketting diagrammen. In plaats daarvan gebruiken zij een “overgangsmatrix” om de overgangskansen te tellen. Elke toestand in de toestandsruimte wordt één keer opgenomen als rij en één keer als kolom, en elke cel in de matrix vertelt je de waarschijnlijkheid van een overgang van de toestand in de rij naar de toestand in de kolom. In de matrix doen de cellen dus hetzelfde als de pijlen in het diagram.

Als de toestandsruimte één toestand toevoegt, voegen we één rij en één kolom toe, en voegen we één cel toe aan elke bestaande kolom en rij. Dit betekent dat het aantal cellen kwadratisch toeneemt naarmate we meer toestanden aan onze Markov-keten toevoegen. Een overgangsmatrix komt dus vrij snel van pas, tenzij je een jungle gym Markov ketting diagram wilt tekenen.

Een gebruik van Markov ketens is het opnemen van echte verschijnselen in computersimulaties. We willen bijvoorbeeld nagaan hoe vaak een nieuwe stuwdam zal overlopen, wat afhangt van het aantal regendagen achter elkaar. Om dit model te bouwen, beginnen we met het volgende patroon van regenachtige (R) en zonnige (S) dagen:

Een manier om dit weer te simuleren zou zijn om gewoon te zeggen “De helft van de dagen is regenachtig. Daarom zal elke dag in onze simulatie een kans van vijftig procent op regen hebben.” Deze regel zou in de simulatie de volgende reeks opleveren:

Heb je gemerkt dat de bovenstaande reeks niet helemaal op het origineel lijkt? De tweede reeks lijkt rond te springen, terwijl de eerste (de echte gegevens) een “stickyness” lijkt te hebben. In de echte gegevens is het zo dat als het de ene dag zonnig (S) is, het de volgende dag ook veel waarschijnlijker is dat het zonnig is.

We kunnen deze “stickyness” miniseren met een Markov-keten met twee toestanden. Wanneer de Markov-keten in toestand “R” is, heeft hij een kans van 0,9 om te blijven staan en een kans van 0,1 om naar de toestand “S” te gaan. Evenzo heeft de “S”-toestand 0,9 kans om te blijven en 0,1 kans om over te gaan naar de “R”-toestand.