Markovkedja

Från Wikipedia
Hoppa till: navigering, sök

En Markovkedja är inom matematiken en tidsdiskret stokastisk process med Markovegenskapen, det vill säga att processens förlopp kan bestämmas utifrån dess befintliga tillstånd utan kännedom om det förflutna. En Markovkedja som är tidskontinuerlig kallas en Markovprocess.

En Markovkedja som antar ändligt många värden kan representeras av en övergångsmatris. Givet en sannolikhetsvektor, erhålles sannolikhetsvektorn för nästa steg i kedjan av multiplikation med övergångsmatrisen. Flera steg kan beräknas genom exponentiering av övergångsmatrisen. Det är även möjligt att beräkna processens stationära fördelning, det vill säga vad som händer då processen fortsätter i oändligheten, med hjälp av egenvektorer.

Markovkedjor har många tillämpningsområden, bland annat för att beskriva befolkningsprocesser och inom bioinformatik. Resultaten som ligger till grund för teorin om Markovkedjor framlades 1906 av Andrej Markov.

Matematisk modell[redigera | redigera wikitext]

Tillstånd och övergångar[redigera | redigera wikitext]

Antag att den process vi vill beskriva kan anta n olika tillstånd, L1, L2, ... Ln. Vi anger sannolikheten för dess tillstånd vid tidpunkten t i form av en kolumnvektor med n element:


    \mathbf{x}_t = \begin{bmatrix}
        x_1 \\
        x_2 \\
        \vdots \\
        x_n
    \end{bmatrix}

Elementet xn är ett tal mellan 0 och 1 som beskriver sannolikheten för att processen befinner sig i tillståndet Ln. Summan av alla element är 1. Om vi med säkerhet vet att processen vid tiden t befinner sig i tillståndet Lk, är xk = 1 och övriga element 0.

Att processen är stokastisk med Markovegenskapen innebär att vi för varje tillstånd kan ange sannolikheten för att processen ska hoppa till varje annat tillstånd. Sannolikheterna för de enskilda fallen kan ställas upp i en övergångsmatris, som är en kvadratisk matris med dimensionen n × n. Om vi här låter xy beteckna sannolikheten för en övergång från tillståndet Lx till Ly, har övergångsmatrisen P formen


P = \begin{bmatrix}
    1 \to 1  &  2 \to 1  &  \cdots  & n \to 1 \\
    1 \to 2  &  2 \to 2  &  \cdots  & n \to 2 \\
     \vdots  &   \vdots  &  \ddots  & \vdots \\
    1 \to n  &  2 \to n  &  \cdots  & n \to n \\
\end{bmatrix}

Precis som i en sannolikhetsvektor, är alla element i övergångsmatrisen reella tal mellan 0 och 1, och summan längs en kolumn måste vara 1 (eftersom den totala sannolikheten av varje möjligt utfall av en övergång är 1). Värdena längs diagonalen anger sannolikheterna för att ingen förändring sker under ett steg.

Vi kan nu beräkna sannolikhetsvektorn för tidpunkten t+1 genom att multiplicera sannolikhetsvektorn för tidpunkten t med övergångsmatrisen (observera att operandernas ordning spelar roll, eftersom matrismultiplikation inte är kommutativ):

\mathbf{x}_{t+1} = P \mathbf{x}_{t}

Genom att upprepa multiplikationen kan nästföljande sannolikhetsvektor bestämmas. Tillståndet för en tidpunkt t+n godtycklig långt in i framtiden kan beräknas genom att multiplicera xt med matrisens n:te potens:

\mathbf{x}_{t+n} = P^n \mathbf{x}_{t}.

Stationär fördelning[redigera | redigera wikitext]

Betrakta en Markovkedja med tillstånden 1,2,...,k och övergångsmatrisen P. En vektor \pi = (\pi_1,\ldots ,\pi_k) sägs vara en stationär fördelning för Markovkedjan om den uppfyller dels att alla element är större än eller lika med 0, dels att summan av talen \pi_1,\ldots ,\pi_k är lika med 1 och slutligen att produkten av vektorn \pi med övergångsmatrisen P resulterar i \pi, dvs. P\pi=\pi så att \pi är en egenvektor med egenvärdet 1.

Exempel[redigera | redigera wikitext]

Diagram över en enkel Markovmodell för vädret. I vänstra kolumnen visas en kedja med vackert väder (blått) under den första dagen, i den högra en kedja med dåligt väder (mörkgrått) som utgångspunkt. Bägge processerna fortlöper under tre dagar. I varje övergång bevaras 90% av sannolikheten för vackert väder medan varje andel sannolikhet för dåligt väder övergår till en 50/50 procents chans. I det långa loppet blir sannolikheten för vackert väder ungefär 83%, oberoende av vädret första dagen.

Betrakta följande mycket enkla stokastiska modell för att beskriva vädret:

  • Det finns två olika tillstånd: antingen skiner solen, eller så regnar det. Vi betraktar vädret en dag i taget.
  • Om solen skiner är det 90% sannolikt att det blir vackert väder också nästa dag.
  • Om det regnar är det 50% sannolikt att det fortsätter regna dagen efter.

Modellen beskrivs av följande övergångsmatris:


    P = \begin{bmatrix}
        0,\!9 & 0,\!5 \\
        0,\!1 & 0,\!5
    \end{bmatrix}

Om vi vet att solen skiner under dag 0 (med andra ord att sannolikheten för att solen skiner är 100%, respektive 0% för att det regnar) representeras tillståndet för denna dag av sannolikhetsvektorn

\mathbf{x}_0 = \begin{bmatrix} 1 \\ 0 \end{bmatrix}.

Nu kan det sannolika vädret under dag 1 beräknas genom


    \mathbf{x}_1 = P \mathbf{x}_0 = \begin{bmatrix}
        0,\!9 & 0,\!5 \\
        0,\!1 & 0,\!5
    \end{bmatrix}
    \begin{bmatrix}
        1 \\
        0
    \end{bmatrix}
    = \begin{bmatrix}
        0,\!9 \\
        0,\!1
    \end{bmatrix},

och sannolikheten är alltså 90% att solen skiner även den dagen. På samma sätt kan vädret under dag 2 förutspås genom


    \mathbf{x}_2 = P \mathbf{x}_1 = P^2 \mathbf{x}_0
    = \begin{bmatrix}
        0,\!9 & 0,\!5 \\
        0,\!1 & 0,\!5
    \end{bmatrix}^2
    \begin{bmatrix}
        1 \\
        0
    \end{bmatrix}
    \approx \begin{bmatrix}
        0,\!86 \\
        0,\!14
    \end{bmatrix}.

Övergångsmatrisen har egenvektorn (normaliserad så att summan av elementen är 1)

\begin{bmatrix}
    0,\!833 \\
    0,\!167
\end{bmatrix},

med tolkningen att 83% av alla dagar i det långa loppet har vackert väder.

Tidsreversibel Markovkedja[redigera | redigera wikitext]

Betrakta en stationär ergodisk Markovkedja med övergångssannolikheter Pij samt stationära sannolikheter πi. Antag samtidigt att man vid kedjans startpunkt spårar sekvensen av tillstånd bakåt i tiden. Alltså, mer formellt kan man säga att vid startpunkten n betraktar man sekvensen Xn, Xn-1, Xn-2, … . Det visar sig då att den sekvensen av tillstånd i sig själv är en Markovkedja med övergångssannolikheter Qij som definieras enligt


\begin{align}
Q_{ij} & = P( X_{m}=j | X_{m+1}=i ) \\
& = \frac{ P( X_{m}=j \cap X_{m+1}=i )}{ P( X_{m+1} = i ) } \\
& = \frac{ P( X_{m}=j ) P( X_{m+1}=i | X_{m}=j )}{ P( X_{m+1}=i )} \\
& = \frac{ \pi_{j} P_{ji} }{ \pi_{i} }
\end{align}

Om Qij = Pij gäller för alla i, j så kallar man Markovkedjan för tidsreversibel.

Tillämpningar[redigera | redigera wikitext]

Teorin om Markovkedjor kan tillämpas i bland annat vid design av webbplatser. I så fall antas sannolikheten att användaren besöker en webbsida bara bero på vilken sida användaren ser just nu. Genom att statistiskt uppskatta dessa sannolikheter går det att öka användbarheten av webbsidan.

Generaliseringar till flera dimensioner[redigera | redigera wikitext]

Huvudartikel: Markovfält

En Markovkedja utvecklar sig i en enda dimension, tiden. Inom bildanalys uppkommer en naturlig generalisering av Markovkedjor till två eller flera dimensioner. För en Markovkedja gäller

p(x_j \,|\, x_k,\,k\neq j) = p(x_j \,|\, x_{j-1},x_{j+1}).

De två punkterna x_{j-1} och x_{j+1} ligger nära x_{j} och vi definierar grannskapet till x_{j} som:

\mathcal{N}_j = \{x_{j-1},x_{j+1}\} \,.

Detta grannskap kan sedan generaliseras till flera dimensioner och för ett Markovfält gäller alltså

p(x_{i,j} \,|\, x_{k,l},\,(k,j)\neq (i,j)) = p(x_j \,|\, \mathcal{N}_{i,j} )

Referenser[redigera | redigera wikitext]

  • Introduction to probability models, Sixth edition, Sheldon M. Ross, Academic press, 1997.
Venn A intersect B.svg Matematikportalen – portalen för matematik på svenskspråkiga Wikipedia.