Markovkæder

af Victor Powell

med tekst af Lewis Lehe

Markovkæder, opkaldt efter Andrey Markov, er matematiske systemer, der hopper fra en “tilstand” (en situation eller et sæt af værdier) til en anden. Hvis man f.eks. lavede en Markov-kæde-model af en babys adfærd, kunne man f.eks. medtage “leg”, “spisning”, “søvn” og “gråd” som tilstande, som sammen med andre adfærdsmønstre kunne danne et “tilstandsrum”: en liste over alle mulige tilstande. Derudover fortæller en Markov-kæde oven på tilstandsrummet sandsynligheden for at hoppe, eller “overgå”, fra en tilstand til en anden tilstand – f.eks, chancen for, at en baby, der er i gang med at lege, falder i søvn inden for de næste fem minutter uden at græde først.

En simpel Markov-kæde med to tilstande er vist nedenfor.

hastighed

Med to tilstande (A og B) i vores tilstandsrum er der 4 mulige overgange (ikke 2, fordi en tilstand kan overgå tilbage til sig selv). Hvis vi befinder os i “A”, kan vi gå over til “B” eller forblive i “A”. Hvis vi befinder os i “B”, kan vi gå over til “A” eller forblive i “B”. I dette diagram med to tilstande er sandsynligheden for at overgå fra en tilstand til en anden tilstand 0,5.

Selvfølgelig tegner rigtige modelbyggere ikke altid Markov-kædediagrammer. I stedet bruger de en “overgangsmatrix” til at opgøre overgangssandsynlighederne. Hver tilstand i tilstandsrummet er medtaget én gang som en række og igen som en kolonne, og hver celle i matricen fortæller sandsynligheden for at overgå fra sin rækkes tilstand til sin kolonnes tilstand. I matrixen gør cellerne altså det samme, som pilene gør i diagrammet.

Hvis tilstandsrummet tilføjer en tilstand, tilføjer vi en række og en kolonne, idet vi tilføjer en celle til hver eksisterende kolonne og række. Det betyder, at antallet af celler vokser kvadratisk, efterhånden som vi tilføjer tilstande til vores Markov-kæde. Derfor er en overgangsmatrix ret hurtigt praktisk, medmindre man ønsker at tegne et Markov-kædediagram i en junglegymnastiksal.

En af anvendelsesmulighederne for Markov-kæder er at inkludere fænomener fra den virkelige verden i computersimuleringer. Vi kan f.eks. ønske at kontrollere, hvor ofte en ny dæmning vil løbe over, hvilket afhænger af antallet af regnvejrsdage i træk. For at opbygge denne model starter vi med følgende mønster af regnfulde (R) og solrige (S) dage:

En måde at simulere dette vejr på ville være blot at sige: “Halvdelen af dagene er regnfulde. Derfor vil hver dag i vores simulering have en halvtreds procent chance for regn.” Denne regel ville generere følgende sekvens i simuleringen:

Lagde du mærke til, at ovenstående sekvens ikke helt ligner den oprindelige? Den anden sekvens ser ud til at hoppe rundt, mens den første (de reelle data) ser ud til at have en “klæbrighed”. I de virkelige data er det sådan, at hvis der er solskin (S) den ene dag, så er det også meget mere sandsynligt, at der er solskin den næste dag.

Vi kan minisere denne “stickyness” med en Markov-kæde med to tilstande. Når Markov-kæden befinder sig i tilstanden “R”, har den en sandsynlighed på 0,9 for at blive stående og en chance på 0,1 for at gå til tilstanden “S”. På samme måde har tilstanden “S” 0,9 sandsynlighed for at blive siddende og 0,1 chance for at overgå til tilstanden “R”.

I hænderne på metereologer, økologer, dataloger, finansingeniører og andre personer, der har brug for at modellere store fænomener, kan Markovkæder blive ret store og kraftfulde. F.eks. er den algoritme, som Google bruger til at bestemme rækkefølgen af søgeresultater, kaldet PageRank, en type Markov-kæde.

Ovenfor har vi inkluderet en Markov-kæde-“legeplads”, hvor du kan lave dine egne Markov-kæder ved at rode rundt med en overgangsmatrix. Her er et par stykker at arbejde ud fra som et eksempel: ex1, ex2, ex3 eller generer en tilfældigt. Teksten for overgangsmatrixen bliver rød, hvis den angivne matrix ikke er en gyldig overgangsmatrix. Rækkerne i overgangsmatricen skal i alt være 1. Der skal også være det samme antal rækker som kolonner.

Du kan også få adgang til en fuldskærmsversion på setosa.io/markov