Markovkedjor och sannolikhetsmatriser

#matematik/linjär-algebra

Definition: Markovkedja

En Markovkedja är en slags stokastisk process som vid varje tidpunkt befinner sig i ett av ett ändligt antal möjliga tillstånd, och där sannolikheten att vid en viss tidpunkt befinna sig i ett visst tillstånd endast beror på tillståndet i föregående tidpunkt.

En Markovkedja med stycken möjliga tillstånd bestäms alltså unikt av sannolikheterna att gå från tillstånd till tillstånd för alla . Vi kan ordna dessa sannolikheter i en kvadratisk matris som vi kallar för en sannolikhetsmatris. I en sådan matris beskriver alltså kolumn sannolikheterna att gå till de olika möjliga tillstånden om det aktuella tillståndet är tillstånd .

Definition: Sannolikhetsvektor, sannolikhetsmatris

En sannolikhetsvektor är en reell kolumnvektor sådan att varje element är ickenegativt och sådan att summan av alla element är .

En sannolikhetsmatris är en kvadratisk matris där varje kolumn är en sannolikhetsvektor.

Sats: Markovkedjor beskrivs av sannolikhetsmatriser

Om en Markovkedja med stycken tillstånd vid tidpunkten befinner sig i tillstånd med sannolikheten där är en kolumnvektor, så finns en sannolikhetsmatris sådan att
för alla .

Bevis:
Vi ordnar enligt tidigare så att är sannolikheten att gå från tillstånd till tillstånd , som vi vet finns enligt definitionen av en Markovkedja. Då är
å

I många fall kommer en Markovkedja gå mot ett stationärt tillstånd, där alltså gränsvärdet
existerar. Isåfall vet vi alltså att , så är en egenvektor med egenvärde . Vi ser dock att vi inte alltid kommer gå mot ett stationärt tillstånd, eftersom vi kan bilda en Markovkedja och välja ett utgångsläge så att den med hundra procents sannolikhet går i en bestämd cykel mellan flera tillstånd. Däremot kan vi visa att det åtminstone alltid finns ett stationärt tillstånd.

Lemma

Om är en sannolikhetsmatris och är egenvektor med egenvärde där , och så är en sannolikhetsvektor och egenvektor med egenvärde .

Bevis:
För alla har vi att men vi vet också att eftersom är en sannolikhetsmatris, och eftersom alla termer är ickenegativa måste alltså . När detta skaleras med blir det en sannolikhetsvektor.

Sats: Stationärt tillstånd finns alltid

Om är en sannolikhetsmatris så finns en sannolikhetsvektor som är en egenvektor med egenvärde .

Bevis:
Om vi låter så vet vi att eftersom varje kolumn i är en sannolikhetsvektor. Ekvivalent har vi alltså att , och eftersom har samma egenvärden som måste även ha egenvärdet ( och har samma karaktäristiska polynom eftersom determinanten inte påverkas av transponering). Det finns alltså en egenvektor med egenvärde till , och enligt Lemma är vi klara.

Definition: Irreducibel sannolikhetsmatris

En sannolikhetsmatris kallas irreducibel om det för varje finns ett sådant att , eller ekvivalent om det från varje tillstånd går att nå varje tillstånd efter ett ändligt antal steg.

Definition: Reguljär sannolikhetsmatris

En sannolikhetsmatris kallas reguljär om det finns ett sådant att är positiv, alltså sådant att varje element i är positivt.

En tolkning av vad som menas med en Markovkedja som beskrivs av en reguljär sannolikhetsmatris är att det finns en tidpunkt där kedjan oavsett utgångsläge kan vara i vilket tillstånd som helst. Detta eftersom vi efter att ha applicerat en positiv sannolikhetsmatris på en sannolikhetsvektor får en positiv sannolikhetsvektor, vilket betyder att vi kan vara varsomhelst.

Vi ser direkt från dessa definitioner att alla reguljära sannolikhetsmatriser också är irreducibla.

Sats

Om är en irreducibel sannolikhetsmatris så gäller

  1. Om är en egenvektor med egenvärde där så är samtliga koordinater i nollskilda.
  2. Det finns en positiv sannolikhetsvektor som är en egenvektor med egenvärde .
  3. Om är ett egenvärde där så är där och är algebraisk respektive geometrisk multiplicitet.
  4. De komplexa egenvärdena med belopp är precis de :e enhetsrötterna för något .

Bevis:

  1. Enligt Sats är en egenvektor med egenvärde . är inte nollvektorn, så det finns ett s.a. . Eftersom är irreducibel vet vi att det för alla finns ett så att , vilket ger att , alltså är .
  2. Vi vet enligt Sats att det finns en sannolikhetsvektor som är en egenvektor med egenvärde . Ovan såg vi att också är positiv.
  3. Givet ett egetvärde där , om det finns två oberoende egenvektorer kan vi bilda en linjärkombination som också är en egenvektor med egenvärde , där en men inte alla koordinater är , vilket är en motsägelse, alltså är . Om så finns en generaliserad egenvektor s.a. där är en egenvektor, vilket ger att vars norm går mot när går mot eftersom och . Detta är en motsägelse eftersom och därmed även är sannolikhetsmatriser och normerna av kolumnerna därför inte kan gå mot . Därmed är .
Sats: Perron-Frobenius sats

Om är en reguljär sannolikhetsmatris så gäller

  1. Det finns en positiv egenvektor med egenvärde .
  2. där och är algebraisk respektive geometrisk multiplicitet.
  3. Alla egenvärden förutom uppfyller att .
  4. finns och är oberoende av .

Bevis:

  1. Vi vet att är irreducibel eftersom den är reguljär, alltså stämmer påståendet enligt Sats.
  2. Följer från samma Sats.
  3. Låt vara sannolikhetsvektorn med egenvärde , låt 𝟙 och bilda 𝟙. Vi får då att 𝟙𝟙, och 𝟙𝟙, alltså är . Både och är positiva, alltså finns ett s.a. är positiv. Den är dock inte en sannolikhetsmatris, så vi bildar som då alltså blir en sannolikhetsmatris. Vi betraktar potenserna av och får att Från detta får vi och eftersom är en sannolikhetsmatris är även alla det, så därför går mot när . Därmed, om är en egenvektor med egenvärde så får vi att ska gå mot när , men det kan endast ske om eller om , eftersom om så går detta mot oändligheten och om men så går detta i en cykel och alltså inte mot något gränsvärde.
  4. Vi får att 𝟙𝟙