Matriser: Markovkjeder og likevekt

En likevektstilstand $\vec{v}$ er en egenvektor for overgangsmatrise $A$ med egenverdi 1:

A\vec{v} = \vec{v}
  • Dersom systemet er i likevekt, forblir det i likevekt

+ Metoder for å finne likevektstilstanden

Når vi har gjort uendelig mange iterasjoner, vil systemet havne i likevekt.

Vi kan bruke en av disse to uttrykkene for tilstandsvektoren $\vec{x}_k$:

Metode uten egenvektorer: Vi kan bruke en egenskap ved Markovkjeder:

\vec{x}_k = A^k \vec{x}_0

og la $k \to \infty$:

\vec{v} = \lim_{k \to \infty} \vec{x}_k = \lim_{k \to \infty}A^k \vec{x}_0

Dette er en tungvint metode, men den fungerer.

Metode med egenvektorer: Dersom vi har funnet egenverdiene og egenvektorene til $A$, kan bruke den generelle løsningen:

\vec{x}_k = c_1 \lambda_1^k \vec{v}_1 + c_2 \lambda_2^k \vec{v}_2 + \cdots + c_n \lambda_n^k \vec{v}_n

og la $k \to \infty$. 

\vec{v} = \lim_{k \to \infty} \vec{x}_k = \lim_{k \to \infty} \bigg( c_1 \lambda_1^k \vec{v}_1 + c_2 \lambda_2^k \vec{v}_2 + \cdots + c_n \lambda_n^k \vec{v}_n \bigg)

Dette er ganske enkelt fordi når $k \to \infty$ går $\lambda_i^k \to 0$ dersom $|\lambda_i| < 1$.

+ Eksempel 1: Vann-damp

Vann helles i et glass. I vannflaten vil molekyler fordampe og kondensere. Hvis 20% av gassmolekylene på grenseflaten kondenserer og 10% av vannmolekyler fordamper i løpet av hver sekund, kan vi sette opp overgangsmatrisen: 

A = \left( \begin{array}{cc} 
\textnormal{damp} \to \textnormal{damp} & \textnormal{vann} \to \textnormal{damp} \\
\textnormal{damp} \to \textnormal{vann} & \textnormal{vann} \to \textnormal{vann}
\end{array} \right)
= \left( \begin{array}{cc} 0.8 & 0.1 \\ 0.2 & 0.9 \end{array} \right)

Ved start er det kun vannmolekyler på grenseflaten:

\vec{x}_0 = \left( \begin{array}{c} \textnormal{damp} \\ \textnormal{vann} \end{array} \right)
= \left( \begin{array}{c} 0 \\ 1 \end{array} \right)

+ Metode uten egenvekorer

Etter ett sekund er tilstandsvektoren:

\vec{x}_1 = A \vec{x}_0 = \left( \begin{array}{cc} 0.8 & 0.1 \\ 0.2 & 0.9 \end{array} \right)
\left( \begin{array}{c} 0 \\ 1\end{array} \right)
= \left( \begin{array}{c} 0.1 \\ 0.9 \end{array} \right)

dvs. 10% damp og 90% vann. Etter to og tre sekunder:

\vec{x}_2 = A \vec{x}_1 = \left( \begin{array}{cc} 0.8 & 0.1 \\ 0.2 & 0.9 \end{array} \right)
\left( \begin{array}{c} 0.1 \\ 0.9 \end{array} \right)
= \left( \begin{array}{c} 0.17 \\ 0.83 \end{array} \right) \\
\vec{x}_3 = A \vec{x}_2 = \left( \begin{array}{cc} 0.8 & 0.1 \\ 0.2 & 0.9 \end{array} \right)
\left( \begin{array}{c} 0.17 \\ 0.83 \end{array} \right)
= \left( \begin{array}{c} 0.219 \\ 0.781 \end{array} \right)

Og slik kan vi fortsette. Når det har gått nok tid, finner vi likevektstilstanden:

\vec{v} = \lim_{k \to \infty} \vec{x}_k = \left( \begin{array}{c} 0.333\dots \\ 0.666 \dots \end{array} \right)

Merk at hvis vi hadde brukt en annen tilstandsvektor ved start, hadde vi likevel fått samme likevektstilstand.

+ Metode med egenvektorer

Dersom vi har funnet egenvektorene for dette problemet, kan vi bruke løsningen:

\vec{x}_k 
= \frac{1}{3} \left(\begin{array}{c} 1 \\ 2 \end{array} \right)
+ \frac{1}{3} \cdot 0.7^k \cdot \left(\begin{array}{c} -1 \\ 1 \end{array} \right)

Nå kan vi la $k \to \infty$:

\vec{v} = \lim_{k \to \infty} \vec{x}_k 
= \lim_{x \to \infty} \left( \frac{1}{3} \left(\begin{array}{c} 1 \\ 2 \end{array} \right)
+ \frac{1}{3} \cdot 0.7^k \cdot \left(\begin{array}{c} -1 \\ 1 \end{array} \right) \right)
= \frac{1}{3} \left(\begin{array}{c} 1 \\ 2 \end{array} \right)

siden $0.7^k \to 0$ når $k \to \infty$.

+ Eksempel 2: Ja eller nei?

En mann skifter mening hver gang han stilles et spørsmål. Sier han ja, er det 90% sannsynlighet for at han sier nei neste gang. Og sier han nei, er det 90% sannsynlighet for at han sier ja neste gang. Det gir overgangsmatrisen: 

A = \left( \begin{array}{cc} 
\textnormal{ja} \to \textnormal{ja} & \textnormal{nei} \to \textnormal{ja} \\
\textnormal{ja} \to \textnormal{nei} & \textnormal{nei} \to \textnormal{nei}
\end{array} \right)
= \left( \begin{array}{cc} 0.1 & 0.9 \\ 0.9 & 0.1 \end{array} \right)

La oss si at han sa ja, først:

\vec{x}_0 = \left( \begin{array}{c} \textnormal{ja} \\ \textnormal{nei} \end{array} \right)
= \left( \begin{array}{c} 1 \\ 0 \end{array} \right)

+ Metode uten egenvekorer

Neste spørsmål gir tilstandsvektoren:

\vec{x}_1 = A \vec{x}_0 = \left( \begin{array}{cc} 0.1 & 0.9 \\ 0.9 & 0.1 \end{array} \right)
\left( \begin{array}{c} 1 \\ 0 \end{array} \right)
= \left( \begin{array}{c} 0.1 \\ 0.9 \end{array} \right)

dvs. 10% sjanse for ja og 90% for nei. Etter andre og tredje spørsmål:

\vec{x}_2 = A \vec{x}_1 = \left( \begin{array}{cc} 0.1 & 0.9 \\ 0.9 & 0.1 \end{array} \right)
\left( \begin{array}{c} 0.1 \\ 0.9 \end{array} \right)
= \left( \begin{array}{c} 0.82 \\ 0.18 \end{array} \right) \\
\vec{x}_3 = A \vec{x}_2 = \left( \begin{array}{cc} 0.1 & 0.9 \\ 0.9 & 0.1 \end{array} \right)
\left( \begin{array}{c} 0.82 \\ 0.18 \end{array} \right)
= \left( \begin{array}{c} 0.244 \\ 0.756 \end{array} \right)

Og slik kan vi fortsette. Når det har gått nok tid, finner vi likevektstilstanden:

\vec{v} = \lim_{k \to \infty} \vec{x}_k = \left( \begin{array}{c} 0.5 \\ 0.5 \end{array} \right)

Merk at hvis vi hadde brukt en annen tilstandsvektor ved start, hadde vi likevel fått samme likevektstilstand.

+ Metode med egenvektorer

Dersom vi har funnet egenvektorene for dette problemet, kan vi bruke løsningen:

\vec{x}_k 
= \frac{1}{2} \left(\begin{array}{c} 1 \\ 1 \end{array} \right)
- \frac{1}{2} \cdot (-0.8)^k \cdot \left(\begin{array}{c} -1 \\ 1 \end{array} \right)

Nå kan vi la $k \to \infty$:

\vec{v} = \lim_{k \to \infty} \vec{x}_k 
= \lim_{x \to \infty} \left( \frac{1}{2} \left(\begin{array}{c} 1 \\ 2 \end{array} \right)
- \frac{1}{2} \cdot (-0.8)^k \cdot \left(\begin{array}{c} -1 \\ 1 \end{array} \right) \right)
= \frac{1}{2} \left(\begin{array}{c} 1 \\ 1 \end{array} \right)

siden $(-0.8)^k \to 0$ når $k \to \infty$.

← Matematikk

↓ Oppgaver

→ Markov-kjeder