En Markov-kjede er en følge av tilstandsvektorer:
\vec{x}_0, \; \vec{x}_1, \; \vec{x}_2, \; \cdots \; \vec{x}_k, \; \cdotsder hver tilstand avhenger av forrige tilstand:
\vec{x}_{k+1} = A \vec{x}_k- $\vec{x}_k$ er en tilstandsvektor ved tidspunkt (eller iterasjon) $k$
- $A$ kalles en overgangsmatrise og er en stokastisk matrise
Morsomme egenskaper:
- Tilstandsvektoren ved tidspunkt $\textcolor{red}{k}$, er $\vec{x}_{\textcolor{red}{k}} = A^{\textcolor{red}{k}} \vec{x}_0$
- Dersom systemet er i likevekt, forblir det i likevekt, dvs. $\vec{v} = A \vec{v}$
- Tilstandsvektoren ved tidspunkt $k$, $\vec{x}_k$, kan skrives som en sum av egenvedier og egenvektorer
+ Hva brukes Markov-kjeder til?
Markov-kjeder brukes til å modellere systemer hvor fremtidige tilstander avhenger av nåværende tilstand, for eksempel:
- Økonomi og finans: modellering av aksjekurser og prisendringer, kredittvurdering, og risikostyring.
- Telekommunikasjon: forstå og forbedre telefon- og datanettverk, for eksempel hvordan køer i nettverk håndteres
- Språkbehandling: oversette språk, kjenne igjen tale og analysere tekst
- Biologi: studere gener og hvordan sykdommer sprer seg i en befolkning
- Fysikk: modellere systemer i termodynamisk likevekt
- Samfunnsøkonomi: forutsi økonomiske trender, som inflasjon og arbeidsledighet
- Kjemi: forstå tidsforløpet til kjemiske reaksjoner
- Spillteori: utvikle optimale strategier i spill og konkurranser
- Kunstig intelligens: beslutningsprosesser for roboter og dataprogrammer, spesielt når de lærer av erfaring
- Vær og klima: forutsi værmønstre og klimaforandringer.
- Maskinlæring: modeller som kan forutsi hva som vil skje i en serie hendelser
- Logistikk: planlegge og optimalisere transport og levering av varer
+ Hva er en tilstandsvektor $\vec{x}_k$?
En tilstandsvektor kalles også en sannsynlighetsvektor.
- Elementene i $\vec{x}_k$ er ikke-negative
- Summen av elementene i $\vec{x}_k$ er 1
Eksempel: Hvis du må velge ett av tre alternativer ved tidspunkt $k$, er:
\vec{x}_k = \left( \begin{array}{c}
\textnormal{Sannsynlighet for alternativ 1 ved tid } k \\
\textnormal{Sannsynlighet for alternativ 2 ved tid } k \\
\textnormal{Sannsynlighet for alternativ 3 ved tid } k
\end{array} \right)En sannsynlighet kan ikke være negativ og summen av alle utfall er 1 (dvs. 100%).
+ Hva er en overgangsmatrise $A$?
En overgangsmatrise $A$ inneholder informasjon om sannsynlighetene for at neste utfall basert på forrige utfall. Krav til en gyldig overgangsmatrise:
- $A$ er en kvadratisk matrise
- Elementene i $A$ er ikke-negative
- Summen av elementene i hver kolonne er 1
Eksempel: Hvis du kan velge ett av tre alternativer, og neste alternativ du velger avhenger av hva du valgte sist, blir $A$:
A = \left( \begin{array}{ccc}
\textnormal{alt. 1} \to \textnormal{alt. 1} & \textnormal{alt. 2} \to \textnormal{alt. 1} & \textnormal{alt. 3} \to \textnormal{alt. 1} \\
\textnormal{alt. 1} \to \textnormal{alt. 2} & \textnormal{alt. 2} \to \textnormal{alt. 2} & \textnormal{alt. 3} \to \textnormal{alt. 2} \\
\textnormal{alt. 1} \to \textnormal{alt. 3} & \textnormal{alt. 2} \to \textnormal{alt. 3} & \textnormal{alt. 3} \to \textnormal{alt. 3}
\end{array} \right)Hvis du valgte alternativ 1 sist og det er 20% sannsynlighet for at du kommer til å velge alternativ 1 igjen, 50% sannsynlighet for at du velger alternativ 2 og 30% sannsynlighet for at du velger alternativ 3, blir første kolonne:
A = \left( \begin{array}{ccc}
0.2 & * & * \\ 0.5 & * & * \\ 0.3 & * & *
\end{array} \right)Siden du må velge noe, er er summen i hver kolonne 1 og sannsynligheter kan ikke være negative.
+ Hvorfor er $\vec{x}_k = A^k \vec{x}_0$?
$\vec{x}_0$ er utgangspunktet. Tilstandsvektoren etter en iterasjon er:
\vec{x}_ {\textcolor{red}{1}} = A\vec{x}_0 \quad (= A^ {\textcolor{red}{1}}\vec{x}_0)Tilstandsvektoren etter to iterasjoner er:
\vec{x}_ {\textcolor{red}{2}} = A \textcolor{blue}{\vec{x}_1} = A \textcolor{blue}{A\vec{x}_0} = A^ {\textcolor{red}{2}} \vec{x}_0Tilstandsvektoren etter tre iterasjoner er:
\vec{x}_{\textcolor{red}{3}} = A \textcolor{blue}{\vec{x}_2} = A \textcolor{blue}{A^2\vec{x}_0} = A^ {\textcolor{red}{3}} \vec{x}_0Og slik kan vi fortsette helt til vi finner tilstandsvektoren etter $k$ iterasjoner:
\vec{x}_{\textcolor{red}{k}} = A^ {\textcolor{red}{k}} \vec{x}_0+ Eksempel 1: Et barn fargelegger
Et barn fargelegger, men har kun tre farger: Blå, grønn og rød.
- Dersom barnet brukte den blå fargen, er det 10% sannsynlighet for at hen velgeren blå for å tegne noe nytt, 40% for at hen velger den grønne og 50% for at hen velger den røde.
- Dersom barnet brukte den grønne fargen, er det 30% sannsynlighet for at hen velger den grønne for å tegne noe nytt, 30% for at hen velger den blå og 40% for at hen velger den røde.
- Dersom barnet brukte den røde fargen, er det 50% sannsynlighet for at hen velger den røde for å tegne noe nytt, 30% for at hen velger den blå og 20% for at hen velger den grønne.
Overgagnsmatrisen $A$ inneholder informasjon om sannsynlighetene for hvilken farge barnet velger basert på den forrige fargen:
A = \left( \begin{array}{ccc}
\textcolor{blue}{\textnormal{blå}} \to \textnormal{blå} & \textcolor{green}{\textnormal{grønn}} \to \textnormal{blå} & \textcolor{red}{\textnormal{rød}} \to \textnormal{blå} \\
\textcolor{blue}{\textnormal{blå}} \to \textnormal{grønn} & \textcolor{green}{\textnormal{grønn}} \to \textnormal{grønn} & \textcolor{red}{\textnormal{rød}} \to \textnormal{rød} \\
\textcolor{blue}{\textnormal{blå}} \to \textnormal{rød} & \textcolor{green}{\textnormal{grønn}} \to \textnormal{rød} & \textcolor{red}{\textnormal{rød}} \to \textnormal{rød}
\end{array} \right)
= \left( \begin{array}{ccc}
\textcolor{blue}{0.1} & \textcolor{green}{0.3} & \textcolor{red}{0.3} \\
\textcolor{blue}{0.4} & \textcolor{green}{0.3} & \textcolor{red}{0.2} \\
\textcolor{blue}{0.5} & \textcolor{green}{0.4} & \textcolor{red}{0.5}
\end{array} \right)Legg merke til at summen i hver kolonne er 1 og at alle elementene er ikke-negative.
Tilstandsvektoren $\vec{v}_k$ inneholder sannsynligheten for hver farge på tidspunkt $k$:
\vec{x}_k = \left( \begin{array}{c}
\textcolor{blue}{\textnormal{blå}} \\
\textcolor{green}{\textnormal{grønn}} \\
\textcolor{red}{\textnormal{rød}}
\end{array} \right)Merk at rekkefølgen på fargene er den samme som i overgangsmatrisen.
Dersom barnet begynner med blå, er:
\vec{x}_0 = \left( \begin{array}{c} \textcolor{blue}{1} \\ \textcolor{green}{0} \\ \textcolor{red}{0} \end{array} \right)Sannsynligheten for neste farge kan vi finne ved matrisemultiplikasjon:
\vec{x}_1 = A \vec{x}_0 =
\left( \begin{array}{ccc}
\textcolor{blue}{0.1} & \textcolor{green}{0.3} & \textcolor{red}{0.3} \\
\textcolor{blue}{0.4} & \textcolor{green}{0.3} & \textcolor{red}{0.2} \\
\textcolor{blue}{0.5} & \textcolor{green}{0.4} & \textcolor{red}{0.5}
\end{array} \right)
\left( \begin{array}{c} \textcolor{blue}{1} \\ \textcolor{green}{0} \\ \textcolor{red}{0} \end{array} \right)
= \left( \begin{array}{c} \textcolor{blue}{0.1} \\ \textcolor{green}{0.4} \\ \textcolor{red}{0.5} \end{array} \right)dvs. 10% for blå, 40% for grønn og 50% for rød. Neste gang barnet skal velge farge, er sannsynligheten:
\vec{x}_2 = A \vec{x}_1 =
\left( \begin{array}{ccc}
\textcolor{blue}{0.1} & \textcolor{green}{0.3} & \textcolor{red}{0.3} \\
\textcolor{blue}{0.4} & \textcolor{green}{0.3} & \textcolor{red}{0.2} \\
\textcolor{blue}{0.5} & \textcolor{green}{0.4} & \textcolor{red}{0.5}
\end{array} \right)
\left( \begin{array}{c} \textcolor{blue}{0.1} \\ \textcolor{green}{0.4} \\ \textcolor{red}{0.5} \end{array} \right)
= \left( \begin{array}{c} \textcolor{blue}{0.28} \\ \textcolor{green}{0.26} \\ \textcolor{red}{0.46} \end{array} \right)dvs. 28% for blå, 26 for grønn og 46% for rød.
+ Eksempel 2: Meldinger på telefonen
En person skriver en melding på telefonen. Telefonen bruker Markovkjeder til å foreslå de tre ordene som har størst sannsynlighet for at personen skriver nest basert på hvilke ord som ble skrevet sist.
Dersom det er $n$ ord i ordboka, har overgangsmatrisen og tilstandsvektoren $n$ rader:
A = \left( \begin{array}{cccc}
\textnormal{ord 1} \to \textnormal{ord 1} & \textnormal{ord 2} \to \textnormal{ord 1} & \cdots & \textnormal{ord }n \to \textnormal{ord 1} \\
\textnormal{ord 1} \to \textnormal{ord 2} & \textnormal{ord 2} \to \textnormal{ord 2} & \cdots & \textnormal{ord }n \to \textnormal{ord 2} \\
\vdots & \vdots & & \vdots \\
\textnormal{ord 1} \to \textnormal{ord }n & \textnormal{ord 2} \to \textnormal{ord }n & \cdots & \textnormal{ord }n \to \textnormal{ord }n \\
\end{array} \right)\vec{x}_k = \left( \begin{array}{c}
\textnormal{Sannsynlighet for ord 1 som ord nummer } k \\
\textnormal{Sannsynlighet for ord 2 som ord nummer } k \\
\vdots \\
\textnormal{Sannsynlighet for ord $n$ som ord nummer } k
\end{array} \right)+ Eksempel 3: Demografi
Markov-kjeder kan brukes til å regne på befolkningens alder, bosettingsmønster, innflytning- og utflytting, og mye mer. Hvis du vet fordelingen et år, kan du regne ut sannsynligheten for fordelingen de neste årene.