Markovkedjor

av Victor Powell

med text av Lewis Lehe

Markovkedjor, uppkallade efter Andrey Markov, är matematiska system som hoppar från ett ”tillstånd” (en situation eller en uppsättning värden) till ett annat. Om man till exempel gör en Markovkedje-modell av ett barns beteende kan man inkludera ”leka”, ”äta”, ”sova” och ”gråta” som tillstånd, som tillsammans med andra beteenden kan bilda ett ”tillståndsutrymme”: en lista över alla möjliga tillstånd. Utöver tillståndsrummet kan en Markovkedja dessutom ange sannolikheten för att hoppa, eller ”övergå”, från ett tillstånd till ett annat tillstånd – t.ex, chansen att ett barn som leker kommer att somna under de kommande fem minuterna utan att först gråta.

En enkel Markovkedja med två tillstånd visas nedan.

hastighet

Med två tillstånd (A och B) i vårt tillståndsutrymme finns det fyra möjliga övergångar (inte två, eftersom ett tillstånd kan övergå tillbaka till sig självt). Om vi befinner oss i ”A” kan vi övergå till ”B” eller stanna i ”A”. Om vi befinner oss i ”B” kan vi övergå till ”A” eller stanna i ”B”. I detta diagram med två tillstånd är sannolikheten att övergå från något tillstånd till något annat tillstånd 0,5.

Visst, riktiga modellbyggare ritar inte alltid upp Markovkedjediagram. I stället använder de en ”övergångsmatris” för att räkna ihop övergångssannolikheterna. Varje tillstånd i tillståndsrummet ingår en gång som en rad och en gång som en kolumn, och varje cell i matrisen talar om sannolikheten för att övergå från sin rads tillstånd till sin kolumns tillstånd. I matrisen gör cellerna alltså samma jobb som pilarna gör i diagrammet.

Om tillståndsutrymmet lägger till ett tillstånd lägger vi till en rad och en kolumn och lägger till en cell till varje befintlig kolumn och rad. Detta innebär att antalet celler växer kvadratiskt när vi lägger till tillstånd till vår Markovkedja. Därför blir en övergångsmatris ganska snabbt användbar, om man inte vill rita ett Markovkedjediagram i djungelgymnastik.

En användning av Markovkedjor är att inkludera verkliga företeelser i datorsimuleringar. Vi kan till exempel vilja kontrollera hur ofta en ny damm kommer att svämma över, vilket beror på antalet regniga dagar i rad. För att bygga denna modell börjar vi med följande mönster av regniga (R) och soliga (S) dagar:

Ett sätt att simulera detta väder skulle vara att bara säga ”Hälften av dagarna är regniga. Därför kommer varje dag i vår simulering att ha en femtioprocentig chans att det regnar”. Denna regel skulle generera följande sekvens i simuleringen:

Märkte du att ovanstående sekvens inte riktigt ser ut som originalet? Den andra sekvensen verkar hoppa runt, medan den första (de verkliga uppgifterna) verkar ha en ”stickyness”. Om det är soligt (S) en dag i de verkliga uppgifterna är det mycket troligare att det är soligt nästa dag.

Vi kan minska denna ”stickyness” med en Markov-kedja med två tillstånd. När Markovkedjan befinner sig i tillståndet ”R” har den en sannolikhet på 0,9 att stanna kvar och en sannolikhet på 0,1 att lämna tillståndet ”S”. På samma sätt har tillståndet ”S” 0,9 sannolikhet att stanna kvar och 0,1 chans att övergå till tillståndet ”R”.

I händerna på metereologer, ekologer, datavetare, finansingenjörer och andra personer som behöver modellera stora fenomen kan Markovkedjor bli ganska stora och kraftfulla. Den algoritm som Google använder för att bestämma ordningen på sökresultaten, kallad PageRank, är till exempel en typ av Markovkedja.

Ovan har vi inkluderat en ”lekplats” för Markovkedjor, där du kan skapa dina egna Markovkedjor genom att leka med en övergångsmatris. Här är några att arbeta utifrån som exempel: ex1, ex2, ex3 eller generera en slumpmässigt. Texten i övergångsmatrisen blir röd om den tillhandahållna matrisen inte är en giltig övergångsmatris. Raderna i övergångsmatrisen måste summera till 1. Det måste också finnas lika många rader som kolumner.

Du kan också få tillgång till en fullskärmsversion på setosa.io/markov

.