Sammanfattning

Syftet med Laboration 1 är att undersöka egenskaperna hos Markovkedjor. Samtidigt ger det tillfälle att programmera i RStudio och öva rapportskrivning med hjälp av rapportgeneratorn R Markdown. Dessutom utvecklas elevernas matematisk-typografiska förmåga med stöd av Latex. Detta görs helt integrerat, genom undersökning och rapportering av ett praktiskt exempel på övergångsmatris, för simulering av tillstånd hos en automata. Systemets Markovkedja kan nyttjas för att undersöka hur tillstånden utvecklas över tid.

Uppgift 3 löses för jämförelses skull med två algoritmer, en egenhändig och en föreslagen i Björkström Kjellson. Resultaten synes vara lika. Simulering av Markovkedja (uppgift enligt 2b.) rekommenderas. Detta förfaringssätt motsvarar av en beräkning av egenvärde och egenvektor för aktuell övergångsmatris. Därför framstår den som den enklaste, effektivaste och mest vedertagna metoden.

Uppgift 1 - mocca-automatens tillståndsvektor för olika tider efter start

Automatens övergångsmatris antages defineras av “mocca-automata”- matrisen som är given som P enligt (i):

\[ \mathbf{P} : = \begin{pmatrix} 0 & 0 & 0 & 0.5 & 0 & 0.5\\ 0 & 0.2 & 0.2 & 0.3& 0 & 0.3 \\ 0 & 0.2 & 0.2 & 0.3 & 0 &0.3 \\ 0 & 0 & 0.3 & 0.5 & 0 & 0.2\\ 0 & 0 & 0 &0.4 & 0.6 & 0\\ 0 & 0 & 0 & 0 & 0.4 & 0.6 \end{pmatrix} \hskip 2cm \mathrm{(i)} \]

1.1 Analysen startar på måndag (dag 1), då fullgod automat-funktion råder

(d.v.s. automaten befinner sig i tillstånd 5). Därefter observeras tillstånden efter 3, 7, 14 och 90 dagar.

Tabell 1.1: tillståndsvektorn efter olika lång tid efter start. Start i tillstånd 5
Tid Tillstånd 0 Tillstånd 1 Tillstånd 2 Tillstånd 3 Tillstånd 4 Tillstånd 5
p.ons På torsdag 0.0000 0.0000 0.0480 0.2720 0.4320 0.2480
p.7d Om en vecka 0.0027 0.0276 0.1216 0.3153 0.2616 0.2711
p.14d Om två veckor 0.0026 0.0259 0.1165 0.3109 0.2723 0.2719
p.90d Om tre månader 0.0026 0.0259 0.1166 0.3109 0.2720 0.2720

1.2 Analysen startar på måndag (dag 1), då automaten befinnner sig i tillstånd “3”.

Tabell 1.2: tillståndsvektorn efter olika lång tid efter start. Start i tillstånd 3
Tid Tillstånd 0 Tillstånd 1 Tillstånd 2 Tillstånd 3 Tillstånd 4 Tillstånd 5
p.ons På torsdag 0.0060 0.0480 0.1440 0.2890 0.1720 0.3410
p.7d Om en vecka 0.0024 0.0245 0.1139 0.3109 0.2799 0.2685
p.14d Om två veckor 0.0026 0.0259 0.1166 0.3108 0.2719 0.2722
p.90d Om tre månader 0.0026 0.0259 0.1166 0.3109 0.2720 0.2720

Kommentar: enligt ovanstående Tabell 1.1 och 1.2, verkar samtliga tillstånd (0 t.o.m. 5) konvergera mot ett för respektive tillstånd bestämt gränsvärde, olika för de olika tillstånden och oberoende av valt starttillstånd (startdag). Efter tre månader (91 iterationer/dagar) kan för några tillstånd fyra siffrors noggrannhet noteras.

Uppgift 2 - undersök konvergens egenskapen hos den givna övergångsmatrisen P

2a. Undersök konvergenshastighet med tilläpning av potensmetoden. I uppgiften föreskriven noggranhet: fyra decimaler. 2^n är den exponent till P som leder till att konvergensvillkoret uppnås

Tabell 2: Tillståndsvektorn efter att fastställd konvergens noggranhet (fyra decimaler) uppnåtts
n Tillstånd 0 Tillstånd 1 Tillstånd 2 Tillstånd 3 Tillstånd 4 Tillstånd 5
6 0.00259 0.02591 0.11658 0.31088 0.27202 0.27202

2b. Räkna ut Markovkedjans stationära fördelning.

Problemt kan formuleras som följer: \[ \mathbf{\Pi \equiv [\pi_{1}, \pi_{2}, ..., \pi_{n}], \hskip .1cm är \hskip .1cm sökt \hskip .1cm stationär\hskip .1cm fördelning (egenvektor)\hskip .1cm för \hskip .2cm övergångsmatrisen \hskip .2cm P. \\ \\ \Pi \hskip .1cm skall \hskip .2cm uppfylla \hskip .1cm följande \hskip .1cm villkor: \\ \Pi * P = \Pi \hskip 1cm \sum_{i}^{n} \pi_{i} = 1 \hskip 1cm\pi_{i} > 0 \hskip .5 cm\forall \hskip .2cm i \hskip .1cm \in E \hskip .5cm (tillståndsrummet) \\ Lösningen \hskip .2cm blir \hskip .4cm \Pi} := \begin{bmatrix} 0.02591 & 0.1166 & 0.3109 & 0.272 & 0.272 \end{bmatrix} \\ \]

Metod enligt Ross S M, Introduction to Probability Models, 11th Ed, Theorem 4.1, s 206. Ekvationen (iii) har den formella lösningen (ii). Således skall enhetsmatrisen I minus den transponerade övergångsmatrisen inverteras. Detta är även standardmetoden för egenvärdesberäning. Resultatet för gränsfördelningen blir identiskt lika med det som fås från uppgift 1.1 och 1.2, räknat på 91 dagar, se tabell 1.2.

\[ \Pi := (I- P^{T})^{-1} \hskip 3cm \mathrm{(iii)} \]

Lösningen av matrisekvationen ger övergångsmatrisen P:s stationära fördelning (egenvektor): \[ \Pi = \]

(Latex is obviously not generating enough space between words in this document. Why?? I have to add necessary spaces manually, using “hskip”.)

Uppgift 3 - beräkna statistik över medeluppehållstiden i automatens olika tillstånd under ett år (365 d)

Relevant sample av tillstånd erhålls genom simulering av stokastiska markovkedjor, som beskriver hur automatens tillstånd utvecklas över tid. Statistisk analys ger efterfrågad medeluppehållstid i de sex tillstånden.

[1] 0.002739726 0.035616438 0.117808219 0.295890411 0.293150685 0.254794521

Använd alternativ metod (function gen_sim) för att generera tillståndsändringar (algoritm enl Kjellson och Björkström. “Simulering av diskreta Markovkedjor”)

function gen_sim (generell simulering)

x är initialtillståndet, kan vara 0, 1, …, nrow(P) - 1 (dvs antalet rader i P minus 1) P är övergångsmatrisen. Sannolikheter för övergång till tillstånd 0 hittas i kolumn 1, övergång till tillstånd 1 i kolumn 2, och så vidare. Källa: Kjellson B, Björkström A. “Laboration 1: Irreducibla Markovkedjor”

Notera konventionen att numrerar tillstånden från 0 och uppåt, medan index för vektorer och matriser börjar på 1 i R. Därför ser vi x + 1 och y + 1 i koden ovan.

[1] 0.002739726 0.035616438 0.117808219 0.298630137 0.290410959 0.254794521

Uppgift 4 - beräkna sannolikheten för automaten X:s vistelse i ett visst tillstånd en viss dag, betingat av tillståndet närmast efterföljande dag.

Vad är sannolikheten att automaten X i går var i tillstånd “1”, betingat att automaten idag är i tillstånd “5”?

Tillämpa Bayes formel:

\[ \mathbf{P[(X_{n-1}=1)|(X_{n}=5)] = \frac {P[(X_{n-1}=1)\cap P(X_{n}=5)]}{P(X_{n}=5)} } \hskip 2cm \mathrm{(iv)}\]

Från tabell 2: tillstånd “1” kommunicerar med tillstånd “5” med

övergångssannolikheten 0.4. Egenvektorns element

ger P(Xn = 5) = 0.2720207 och P(Xn = 1) = 0.0259067

Bayes formel (iv) ger sökt sannolikhet: 0.0380952

Var vänlig lämna följande följande garbage dump utan avseende {r, include=FALSE, echo=TRUE, comment = NA} Simulering av antalet eftersökta övergångar (används inte här/nu) scan results vector for transitions 1 -> 5, and count the number no of such transitions results3 <- numeric(366) # första elementet i resultatvektor no<- 0 for (i in 2: length(results3)) {no <- no + (results3[i] == 2) * (results3[i-1] == 6)} results3 <- results - results2