Catene di Markov - Il Regno di Oz PDF

Preview

Summary

svolgimento personale (verificato) di un esercizio dato per casa durante il corso di Bioinformatica...

Description

yita · your it assistant

catene di markov > il r egno di o z

esercizio https://www.facebook.com/YourITAssistant/

1 novembre 2017

colophon Testo redatto con LATEX 2ε su sistema operativo Linux usando lo stile ArsClassica di Lorenzo Pantieri, che rivisita in chiave meno classica il suo precursore ClassicThesis di André Miede ispirato a Gli elementi dello stile tipografico di Robert Bringhurst.

contatti [email protected] · Scrivi a YITA | Your IT Assistant

I L REGN O DI OZ quesito Il mago di Oz vive in un posto dove il tempo è sempre pessimo, però è anche markoviano, perché nella terra di Oz non si possono mai avere 2 giorni di sole consecutivi: • se oggi c’è sole , domani può o piovere o nevicare di probabilità), ma non può esserci di nuovo sole

(con il 50%

• se oggi piove , con la stessa probabilità può continuare a piovere oppure tornare sereno oppure nevicare • se oggi nevica , con uguale probabilità può piovere a nevicare , ma non tornare sereno Domanda x : se oggi piove sia sereno ? 1

o continuare

, qual è la probabilità che tra 3 giorni Ä

soluzione Riassumiamo i 3 stati del sistema nella tabella 1:

Tabella 1: Stati del sistema

Oggi

Domani

Sole (S) Pioggia (P) Neve (N) Transizioni metereologiche nel Regno di Oz

Per risolvere il problema va estrapolata la matrice di transizione della catena di Markov dai dati forniti: Domani

z  S S 0           Oggi P  13           N 0

}| { P N 1 1  2 2    1 1 3 3    1 1

1 In riferimento al post di YourITAssistant su Facebook

1

2

2

2

0.0.1

Primo metodo risolutivo

La rappresentazione grafica di questa catena di Markov si ottiene segnando un cerchio per ogni stato (Sole, Pioggia, Neve) della catena e una freccia orientata da un cerchio ad un altro, se la probabilità di transizione in un altro stato è positiva (> 0), indicando il valore della probabilità di transizione accanto alla freccia:

S

1/2

1/3 1/2 1/3

P

N 1/2

1/3

1/2

Questa rappresentazione grafica ci consente di calcolare rapidamente la probabilità di transizione in più passi: nel nostro caso, il numero di passi è pari a 3 (3 giorni), per cui la risposta al quesito si trova facendo la sommatoria di tutti i possibili cammini lunghi 3 passi (3 giorni), che partendo dal giorno di pioggia (corrente) portino al sereno, calcolando il prodotto dei valori scritti sulle frecce per ogni cammino da sommare:

Secondo cammino Terzo cammino z }| { z }| { z }| { (S · P · S) + (P · P · S) = = (N · P · S) + Primo cammino

(3) PPS

=



1 1 1 · · 3 2 3

=



1 18



1 18

=



3+3+2 54





+



1 1 1 · · 3 2 3



+



1 1 1 · · 3 3 3



= (1)



+



+



=



8 54

(3)

1 27



=

=





(3)

4 27



1 : 100 = 0.148 : PPS → PPS = 14.8% %

%

= 0.148

(2)

Quindi la probabilità (P) che, dopo 3 giorni, dalla pioggia (P) di oggi ritorni il sole (S) è del 14.8% (2).

3

0.0.2

Secondo metodo risolutivo

Dopo un giorno Al tempo iniziale (t = 0) si è detto che piove, per cui il vettore di stato (S P N) (con S = sole, P = pioggia ed N = neve) sarà (0 1 0) che vado a moltiplicare per la matrice di transizione della catena di Markov, scritta precedentemente, per ottenere il vettore di stato al tempo t + 1 (cioè dopo 1 giorno) (3):

(0

 0     0) ·  13    0

1

1 2 1 3 1 2

1  2

  

1 3

=

   1



1 3

1 3

1 3



(3)

2

Si è trattato di moltiplicare il vettore di stato del tempo t = 0 per la prima colonna della matrice di transizione e sommarne i valori, per ottenere il primo elemento del nuovo vettore di stato riferito al tempo t + 1, e così lo stesso per le altre due colonne della matrice di transizione: 1 a colonna → ֒ 0 · 0 = 0,

1·

1 1 +0 = 3 3

1 1 = , 3 3

0·0 = 0

1 1 = , 3 3

0·

1 =0 2

→

0+

1 1 +0 = 3 3

1 1 = , 3 3

0·

1 =0 2

→

0+

1 1 +0 = 3 3

0+

→

2 a colonna → ֒ 0·

1 = 0, 2

1·

3 a colonna → ֒ 0·

1 = 0, 2

1·

Dopo due giorni Per calcolare il vettore di stato al tempo t + 2 (cioè dopo 2 giorni), moltiplico la matrice di transizione della catena dei Markov per il vettore di stato trovato per il tempo t + 1, analogamente a quanto fatto prima (4):



1 3

1 3

 0      1 · 13 3    0

1 2 1 3 1 2

1  2

    1 1 3 = 9    1

4 9

4 9



(4)

2

Analogamente a prima, si è trattato di moltiplicare il vettore di stato del tempo t = 1 per la prima colonna della matrice di transizione e sommarne i valori, per ottenere il primo elemento del nuovo vettore di stato riferito al tempo t + 2, e così lo stesso per le altre due colonne della matrice di transizione:

4

1 a colonna → ֒ 1 · 0 = 0, 3

1 1 1 · = , 9 3 3

1 ·0 = 0 3

0+

→

1 1 +0 = 9 9

2 a colonna → ֒ 1 1 1 · = , 3 2 6

1 1 1 · = , 3 3 9

1 1 1 · = 3 2 6

→

4 1 1 1 + + = 9 6 9 6

1 1 1 · = , 3 3 9

1 1 1 · = 3 2 6

→

4 1 1 1 + + = 9 6 9 6

3 a colonna → ֒ 1 1 1 · = , 3 2 6 Dopo tre giorni Per calcolare infine il vettore di stato al tempo t + 3 voluto (cioè dopo 3 giorni), moltiplico la matrice di transizione della catena dei Markov per il vettore di stato trovato per il tempo t + 2, analogamente a quanto fatto prima (5):



1 9

4 9

1 a colonna → ֒ 1 · 0 = 0, 9

 0      4 · 13 9    0

1 2 1 3 1 2

4 1 4 · = , 9 3 27

1 2



    4 1 = 3 27    1

23 54

23 54



(5)

2

4 ·0 = 0 9

→

0+

4 4 +0 = 27 27

2 a colonna → ֒ 1 1 1 · = , 9 2 18

4 1 4 · = , 9 3 27

4 1 4 · = 9 2 18

→

23 4 4 1 = + + 54 18 27 18

4 1 4 · = , 27 9 3

4 1 4 · = 18 9 2

→

23 4 4 1 = + + 18 27 18 54

3 a colonna → ֒ 1 1 1 , · = 18 9 2

Questo vettore di stato al tempo t + 3 ci dice che c’è una probabilità di 23 23 4 (= 0.148) di avere il sole, di avere pioggia e di avere neve dopo 3 27 54 54 giorni a partire da un giorno di pioggia . Convertendo il dato in percentuale, avrò la (6):

1 : 100 =

4 (3) (3) : PPS% → PPS% = 14.8% 27

(6)

valore coincidente con quello trovato nel metodo grafico precedente (2)....