Hva er en Markov-kjede?

En Markov-kjede beskriver et system som til enhver tid befinner seg i én av $n$ tilstander, og der sannsynligheten for neste tilstand bare avhenger av tilstanden nå. Systemet beskrives av en tilstandsvektor $\mathbf{x}_k$ (en sannsynlighetsvektor: ikke-negative komponenter med sum 1) og en overgangsmatrise $P$, med oppdateringsregelen

$$\mathbf{x}_{k+1}=P\mathbf{x}_k\qquad\Longrightarrow\qquad \mathbf{x}_k=P^k\mathbf{x}_0.$$

Dette er en fast eksamensoppgave i TMA4110 — den forekommer i 7 av de 12 ordinære settene H2013–H2024, alltid som en hel tekstoppgave med en beskrivelse som skal oversettes til en matrise.

Konvensjonen (Lay): $P$ er kolonnestokastisk. Elementet $p_{ij}$ er sannsynligheten for å gå FRA tilstand $j$ TIL tilstand $i$. Kolonne $j$ er derfor sannsynlighetsfordelingen for hvor man havner etter ett steg fra $j$, og hver kolonnesum er 1. Bytter du om rad og kolonne, får du feil svar — kontroller alltid kolonnesummene før du regner videre.

Fra tekst til matrise

Oppskriften er alltid den samme: velg en rekkefølge på tilstandene, lag én kolonne per «hvor vi er nå», og les setningene «hvis vi er i $j$ i dag, er sannsynligheten for $i$ i morgen …». Ofte er ett tall utelatt, og du må regne ut det som «blir igjen» slik at kolonnesummen blir 1.

Eksempel 1. Hver måned bytter 20 % av $A$-kundene til $B$, og 30 % av $B$-kundene til $A$. Med rekkefølgen $(A,B)$ blir

$$P=\begin{pmatrix}0{,}8&0{,}3\\0{,}2&0{,}7\end{pmatrix}.$$

Starter alle hos $A$, er $\mathbf{x}_0=(1,0)^T$, $\mathbf{x}_1=(0{,}8;\ 0{,}2)^T$ (første kolonne i $P$) og $\mathbf{x}_2=(0{,}64+0{,}06;\ 0{,}16+0{,}14)^T=(0{,}70;\ 0{,}30)^T$. Legg merke til snarveien: $P\mathbf{e}_j$ er nøyaktig kolonne $j$.

Likevektsvektoren

En likevektsvektor (steady-state-vektor) er en sannsynlighetsvektor $\mathbf{q}$ med $P\mathbf{q}=\mathbf{q}$. Dette er identisk med at $\mathbf{q}$ er en egenvektor for egenverdien $\lambda=1$, altså at $\mathbf{q}\in\mathrm{Nul}(P-I)$. Fremgangsmåten:

Skriv opp $P-I$ (gjerne ganget med 10 eller 100 for å slippe desimaler).
Radreduser og skriv nullrommet på parameterform.
Normaliser slik at komponentene summerer til 1 — ikke til euklidsk lengde 1.
Kontroller: regn ut $P\mathbf{q}$ og se at du får $\mathbf{q}$ tilbake.

Eksempel 2. For matrisen over gir $P-I=\begin{pmatrix}-0{,}2&0{,}3\\0{,}2&-0{,}3\end{pmatrix}$ likningen $2q_1=3q_2$, altså $q_1=1{,}5q_2$. Normalisering: $2{,}5q_2=1$, så $\mathbf{q}=(0{,}6;\ 0{,}4)^T$.

Eksempel 3 (tre tilstander). En værmodell med tilstandene (sol, skyet, regn) har

$$P=\begin{pmatrix}0{,}5&0{,}4&0{,}3\\0{,}3&0{,}4&0{,}3\\0{,}2&0{,}2&0{,}4\end{pmatrix}.$$

Gang $P-I$ med 10. Rad 2 gir $q_1-2q_2+q_3=0$ og rad 3 gir $q_1+q_2-3q_3=0$. Fra disse: $q_2=\tfrac43q_3$ og $q_1=\tfrac53q_3$. Rad 1 er automatisk oppfylt (den er alltid avhengig av de andre, siden $\det(P-I)=0$). Normalisering med $4q_3=1$ gir $\mathbf{q}=\left(\tfrac{5}{12},\ \tfrac13,\ \tfrac14\right)^T$ — det regner altså 25 % av dagene i det lange løp.

Hvorfor finnes likevekten alltid?

La $\mathbf{e}=(1,\dots,1)^T$. At kolonnesummene i $P$ er 1, betyr nøyaktig at $\mathbf{e}^TP=\mathbf{e}^T$, altså at $P^T\mathbf{e}=\mathbf{e}$. Da er $\det(P^T-I)=0$, og siden $\det(P-I)=\det\bigl((P-I)^T\bigr)=\det(P^T-I)$, har også $P-I$ et ikke-trivielt nullrom. Identiteten $\mathbf{e}^TP=\mathbf{e}^T$ viser også umiddelbart at $P\mathbf{x}$ er en sannsynlighetsvektor når $\mathbf{x}$ er det, og at produktet av to stokastiske matriser er stokastisk.

Videre har alle egenverdier $|\lambda|\le 1$: velger man komponenten $v_i$ med størst tallverdi i en egenvektor til $P^T$, gir trekantulikheten $|\lambda||v_i|\le\sum_j (P^T)_{ij}|v_j|\le |v_i|$.

Regularitet og konvergens

Hovedsetningen: En stokastisk matrise $P$ kalles regulær hvis en potens $P^k$ har bare strengt positive elementer. Er $P$ regulær, finnes det nøyaktig én likevektsvektor $\mathbf{q}$ (med bare positive komponenter), og $\mathbf{x}_k\to\mathbf{q}$ for enhver startsannsynlighetsvektor. I tillegg går $P^k$ mot matrisen der HVER kolonne er $\mathbf{q}$.

Merk at $P$ selv gjerne kan ha nuller — det holder at én potens er positiv. For $P=\begin{pmatrix}0{,}5&1\\0{,}5&0\end{pmatrix}$ er $P^2=\begin{pmatrix}0{,}75&0{,}5\\0{,}25&0{,}5\end{pmatrix}$ positiv, så kjeden er regulær.

To situasjoner ødelegger konklusjonen. Periodiske kjeder: $P=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ har likevektsvektoren $(\tfrac12,\tfrac12)^T$, men $\mathbf{x}_k$ svinger fram og tilbake og konvergerer ikke. Absorberende tilstander: har $P$ en kolonne lik $\mathbf{e}_i$, forlater man aldri tilstand $i$, og den kolonnen forblir $\mathbf{e}_i$ i alle potenser. Med to absorberende tilstander får man en hel linje av likevektsvektorer, for eksempel $(t,\ 0,\ 1-t)^T$ for $P=\begin{pmatrix}1&0{,}3&0\\0&0{,}4&0\\0&0{,}3&1\end{pmatrix}$.

Markov-kjeder som egenverdioppgave

Er $P$ diagonaliserbar med $P=SDS^{-1}$, er $P^k=SD^kS^{-1}$, og siden alle egenverdier utenom $\lambda=1$ har tallverdi under 1 (for en regulær kjede), dør alle andre ledd ut. Dette gir både grensen og konvergensfarten.

Eksempel 4. $P=\begin{pmatrix}0{,}8&0{,}3\\0{,}2&0{,}7\end{pmatrix}$ har $\operatorname{sp}(P)=1{,}5$ og $\det P=0{,}5$, altså $\lambda^2-1{,}5\lambda+0{,}5=(\lambda-1)(\lambda-0{,}5)$. Egenvektorer: $(3,2)^T$ for $\lambda=1$ og $(1,-1)^T$ for $\lambda=0{,}5$. Med $\mathbf{x}_0=(1,0)^T=\mathbf{q}+0{,}4(1,-1)^T$ blir

$$\mathbf{x}_k=\mathbf{q}+0{,}4\,(0{,}5)^k\begin{pmatrix}1\\-1\end{pmatrix},$$

så feilen halveres hvert steg. Vil vi ha avvik under $0{,}01$, trenger vi $0{,}4\cdot 0{,}5^k<0{,}01$, altså $k>\ln 40/\ln 2\approx 5{,}3$ og dermed $k=6$ steg. Generelt styres konvergensfarten av den nest største egenverdien i tallverdi.

Til slutt en nyttig spesialregel: er $P$ dobbeltstokastisk (både rad- og kolonnesummer lik 1), er $P\mathbf{e}=\mathbf{e}$, og likevekten er den uniforme vektoren $\frac1n(1,\dots,1)^T$.

Studieguide: Markov-kjeder og stokastiske matriser