Mathematical Engineering - Probabilità

Lezione 13

Divided by topic

CATENE DI MARKOV effsio.E un insieme finito e Xo Xi una successione di variabili casuali a valori in E Xu neo si dice catena di Markov con spazio di stato e legge iniziale e matrice stocastica p se PlXoeil _ct.ttieE VnzOttj.i io in i C E vale Xuti JIXn cjxn n.in Noi'd Plinti Il Xiii p proprieta di Markov in assenza di memoria Ricordiamo che gli stati di una catena di Markov sono classificati sulla base di 3 diverse proprietà non riguarda tanto il sing N stato quanto La classificazione RIDUCIBILITÀ più la comuni di tra stati si dice che c'e j intercomunicano ie j se ci comunica con J c g e g comunica con i g il ie se ti µ mzos.tn Pig 0 PÌÙ O CCE è una classe chiusa se hee Igea s E c g E e'sempre una classe chiusa se ti e'una classe chiusa si dice stato assorto una classe chiusa C si dice irriducibile se ti g E C c j Una catena di Markov si dice irriducibile se l'unica classe irriducibile e E Pss se l intercomunicabilita induce più di una classe di equivalenza allora la catena e detto riducibile e al riguardo la prob di tornare nello 2 CLASSIFICAZIONE PERIODO stato il partendo dai in n pass Il periodo di uno stato ci è d NCD senza P so se D 1 ad es g Pii sol allora c'e aperiodic Tu o i gli stati di una classe irriducibile hanno lo stesso periodo 3A CLASSIFICAZIONE RICORRENZA per ie E sia G Inf vizi Xiii lo stato c'è ricorrente se PIG.at IX i L PC lingua Xiii 1 Tu t t i gli stadi di una classe irriducibile sono ricorrenti lo stato c'è transiente se PIG ct IXO.it e 1 DI lineup tu i O j set c g ma J i fessi sia tu o una catena di Marceau offe con spazio degli Stati E 0 1,23 e matrice di transizione D 12 la 0 1 d Disegnare il grafo della catena e classificarne gli stati a Io Osserviamo che la catena e irriducibile Infanti O 1 2 0 e da questo si capisce che tout gli stati oli E sono intercomunicanti sappiamo che tua gli stati di una classe irriducibile sono ricorrenti Deduciamo quindi immediatamente che Eviti gli stati di E sono ricorrenti sappiamo che tua gli stati di una classe irriducibile hanno lo stesso periodo Deduciamo quindi immediatamente che tutti gli stati d E hanno lo stesso periodo ma calcoliamo aol.es il periodo di 0 Poo Pooh 12 O i e D 1 i e la catena e aperiodica b Determinare la matrice di transizione a due passi Pine Det sia CIA P uno spazio di probabilità Sia Xu new il IR una catena di Markov omogenea c i KEN la matrice stocastica a K passi e PIK È E is i i Equivalentemente in forma matriciale V Ke IN pari Pk ie la matrice stocastica a K passi è la potenza K Sima della matrice stocastica Abbiamo allora poi P SÌ È supponendo che la legge di Xo sia descritta dal lettore calcolate c legge E var di Xi sappiamo che Xo 0 Puo D Pike 21 e f f ie conosciamo la densità d probabilità di Xo in altre parole ci viene data la distribuzione iniziale della nostra catena di Markov conosciamo la matrice stocastica Pie conosciamo il modo in cui evolve la nostra catena di Markov e P sono Sullivans per determinare la legge delle Xu ne 1 Xe è v c discreto con Ink E 0,12 Per determinarne la legge è soltanto determinarne la densità di prob discreto Piu E 0,1 Sia J C E 0 1,2 allora Pj Xd Pur D PIX J E interseca con un evento certo che però mi fornisce informazioni Pixie J È X ei Pixie J Xo it e È plxr j IX.ec Pilo il nota nota legge iniziale probabilità di della catena transizione matrice stocastica È P. j o JEE Quindi Paesi Piatti Poirot Puoi Paio I t 0 14 È 2 4 2 2 Risi È si È 11 se J 2 24 E IN iPad 2 È vartxd E xil E.info iapxiiI EIXife 3ffz d la legge congiunta di Xo Xe e Xi Xs calcoliamo solo la legge congiunta di Xp XD XD è un vettore discreto con densità discreta pxr.is Ex E Io D dal punto precedente Dati e C EXE sappiamo la disti di X Pin id Pike i Xs J e ftp.jlxn i lPlXr i pif'Pxniil lP4igPxiil C Exe Quindi o 1 2 o 74 8 712 1 7 72 7 216 35 216 2 11 48 11 96 11 96 pxnxdadelpyo.opxidef.f jpxa.nl 2I P4a.zPxr 2 f C lettura IN tt no 1 R IETYIXIe dehuitocoui meE.LY XI flX con fcni EIYIX.se aeE Sia nesso n fissato Xu C E 0,123 9 c Calcoliamo allora LEI Xntahn JIV je.ee 0,123 IEIXntzlxn.ge eiPxu aixnlilo ETT fhiyidpmxyixi.ge hldPyixh Yr caso discreto 1 PIXni.am Xn dt2PlXnta 2lXn o po t 2 Pf F o t 2 4oz 72 2 E 2 EIXni.sn Xn 1I EeiPxn aixulilsI 1 PIXntz.li Xn n t2P Xnt2 2IXu 1 p tap t 2 e 11g lettura 1 Xu 2 papi 2Pa 2 Allora 1,31 se 5 0 E Kral Xu j se j i FG 3 4 se J 2 a s EIXntzlxnj.fm Fa se Xiao 1g se Xu 1 3 4 se Xu 2 ie per me 0,1 E fiuta Nu 1 211 03 Asini.is Hai Oss Possiamo osservare che grazie alla proprietà di Markov tutte le quantita che dipendono da leggi di v c distava ne passi dipendono dalla matrice di transizione ad un passi fess sei palline di cui 3 bianche e 3 nere Eff sono inserite casualmente in 2 urne indicate con A e B In ciascuna come sono posizionate 3 polline Ad ogni prova si estrae a casa ed indipendentemente una pallina dall'urna a ed una dall'urna B e si scambiano di urina la pallina estratta dall urna a e inserita nell'urna B e e quella estinta dall'urna B è posizionato nell'urna a Sia Xu neo la successione di v c con Xu numero palline bianche contenute nell'urna a dopo n Simo Estrazione l'estrazione neo coincide con il posizionamento iniziale delle palline Si vede facilmente che Hutu e una catena di Markov a Xor Osserviamo innanzitutto che lo spazio degli Stati della catena e E 0,1 2,3 Possiamo avere alaciuminino di 0 ad un Max d 3 palline bianche L istante iniziale n o coincide con il posizionamento delle palline nell'urna all'istante iniziale possiamo pensare di avere 3 palline bianche e 3 nere in una urna a parte e di estrarne simultanee te 3 da da posizionare nell'urna a di conseguenza avro le rimanenti palline nell'urna B Il numero di palline bianche estraete avra legge iper geometrica X Il Dtm b 3 26,3 3 ie 3 3 1 PUO K e b K Io se Keo 6 tù Pj serie MX h È o altrimenti Oss abbiamo determinato la legge al iniziale della catena di Markov b Determinare la matrice di transizione della ina e tracciarne il grato E irriducibile 1 49 1 a Gg CI 4 CASI ESTREMI 9 se parto da 0 palline bianche nell'urna a possiamo solo scambiare con una nera LÌ al tempo a µ al tempo htt a B i e Poi Plinti 11 Xu 01 1 evento certo ma Pao O se partiamo da 3 palline bianche possiamo solo scambiare con una nera LÌ al tempo a µ al tempo nei O a 3 ie Ps Plinti 21 Xu 3 1 evento certo n Ps3 0 CASI INTERMEDI se partiamo da 1 pallina bianca nell'urna B solo una nera possiamo arrivare a 0 1,2 palline bianche tempo n n pro Plinti e 01 Xu 1 I I vuol dire che nell'urna a pesco la pallina bianca con prob e nell'urna B pesco quella a nera con prob 13 Per Plinti 21 Xu 11 vuol dire che nell'urna a ho pescato una nera con prob 2g e nell'urna 8 una bianca con prob Pm 1 pro per 1 LY Pm P Xuti alxn.se t pesco nere pesco da A e B bianche da A e B se partiamo da 2 palline bianche nell urna a l'urna B gioca il ruolo dell'urna a nel punto precedente aerei Quindi per simmetria Pas p tutt 31 Xu L per simmetria nell'urna a passo da 2 bianche e 3 bianche ie nell'urna B passo da 1 bianca a Zero bianche caso pro del caso precedente Per Plinti 11 Xu 2 per simmetria nell'urna a passo da 2 bianche a 1 bianca ie nell'urna B passo da 1 bianca a 2 fianchi Piz del caso precedente Per 1 pas par 4cg La matrice di transizione è quindi 0 1 0 0 i D 1 49 1g 1g CI 1 4 9 Dal grafo si vede immediatamente che gli stati sono intercomunicanti 0 1 1 e 2 3 2 1 O no la catena di Marceau è irriducibile c Determinare la probabilità che dopo la seconda estrazione tutte le palline nell urna B siano bianche sapendo che all inizio l'urna a contiene più palline bianche dell'urna B All'inizio Mi orna a contiene più palline bianche dell urna B all'inizio numero palline bianche in a 22 Xo 72 questo e l'evento condizionante Dopo la 2 estrazione tutte le palline nell urna B sono bianche Dopo la 2 estrazione tutte le palline nell urna A sono nere ic ho 0 bianche Ha 03 Dobbiamo quindi calcolare PIKE otto 22 PIX 01 022 Pila O X 22 Puo 22 Oss Osserviamo che PUO 2g P IX 2 t PIX 3 fatelo I opto quindi posso effettuar scrivere X2 0 Xo 22 Plinio Xo e 2 t PIX Xò PIX no Xo 2IPlXo 2 ttPIXa oIXso 3 PlXo 3 p Paola tp Raid Palo Io t BE Io Osserviamo ora che Pg O lo si vede dal grafo in 3 passi non è possibile cambiare completamente la composizione delle urne dato che si sposta una pallina per volta 3 Pad Pappa o Jo a 2 Chapman Kolmogorov J paoPo tPzrP.atPzzPznotPzsP O t 4g t o to Quindi Pixar o No 2 PI Io t BY Io 1 45 4 0 81 p X2 01 0 2 PIXzeo.to 2 2PCXoz2 45 i LES Af sia dato una Cdm a tempo discreto Tien con spazio di stato E 1 2,3 e matrice di transizione p ta ta 0 1 D Disegnare il fiato della catena e classificarne gli stati si 1 1 H 2 3 1 quindi la car è irriducibile tua gli Stati sono ricorrenti ed hanno stesso periodo Osserviamo piu 0 ie gli stati sono aperiodic Cdr irriducibile e aperiodica c Tr o v a r e eventuali distribuzioni invarianti Ricordiamo che i elf un vettore di probabilità F Citi ice line tale che III 1 ti E 0,1 ti si c'C E IE 5 IIs wiT iTP n In termini dinamici questo significa che l i iJ È Ì se la Cdm è irriducibile allora 2 prob inv ogni classe irriducibile supporta una unica prob invariante Se abbiamo in classi irriducibile determini prima la prob invariante IT f ieee su le risolvendo il sistema lineare Ti Pig poi estendiamo tali probabilità a Zero sul complementare d ogni Ca infine ne prendiamo una combinazione convessa Dato che la catena è irriducibile sappiamo che a invariant measure it e la troviamo risolvendo pop IT jetties fiso Vi In t its Te l Tn t Ita t its 1 i e Tr e dita Its Ita Ritz t 211T 1 te È D Ti 1 2 i l it 1412,411 invariant measure si supponga che la calm porta dallo stato 2 d Determinare la legge di Xo Xo d'zag ma 0 1,0 disti iniziale IPIXo.IR Xo d PHEH e calcolare il tempo medio di attesa per tornare per la prima volta nello stato 2 Per rispondere a questa domanda dobbiamo osservare che la catena è IRRIDUCIBILE e ricordarci il seguente risultato per calm irriducibili É ÈT Allora G 7 misura invariante IT fi È intimi I ftp liiglknI ti hee.HN feop.emaezao.ae Oss L' i p o te s i di irriducibilità e e nF ONDA MENTALE per avere l'esisto di un jue misura invariante it n CONFRONTARE ad es con es 11 fi in questo caso la catena NON è irriducibile n I as misure invarianti e si trovano facendo la combina concessa delle distribuzioni invarianti esistenti uniche su ciascuna classe chiusa irriducibile Oss In Cb Eisai è il tempo medio F di primo ritorno in c partendo da i b ci dice che questo può essere trovato nel caso di calle irride facendo l'inverso della componente esima della dista inv it Quindi grazie ad i risultati ricordati sopra sappiamo che in presenza de un uniche misura invariante IT il tempo medio di attesa per tornare in uno stato partendo da quello e l'inverso del corrispondente eleven della misura invariante i e fatta Elga IX 2 1 4 tt i 1 2 tempo di Pto c ritorno nello stato 2 f scrivere la legge del tempo di attesa per tornare la prima volta nello stato 2 Vo g l i a m o capire come è distribuito lavoriamo sotto 62 Inf n 71 Xu 2 l'ipotesi che Xo Ozzy it 1 tempo di primo ritorno DI Xo 2 1 in 2 portandola Possiamo scrivere esplicitamente la legge di 82 guardando come evolve la calm ma guardiamo il grato l 1 2 1 Partendo dallo stato 2 mi muovo nei so 3 9 C poi mi muovo verso 1 9 c arrivata in 1 posso tornare in 2 in 1 passo prob E stare in 1 per K i passi e poi muovermi in 1 passo verso 2 ma abbiamo quindi che 82 3,4 9 c E fissato KE 1,2 possiamo calcolarci esplicitamente ptga.tt 2 prob di tornare in 2 in rete passi traducendo in linguaggio matematico quanto detto sopra a parole supponiamo sempre di partire da 2 ie XII ez e l'evento certo iPhone 1 Plea 3 PIK 3 Xa 1 3 2 PIÙ 21 2 1 Xi 3 Xiii in 3 PC Xs 21 2 1 Plaza 1 Xi 3 assenza di memoria Pa PC Xd e 11 1 3 PIK 3 edn f Tha Pss Pg 1 1 12 PUO 21 1 Pl Xi 3 PIK 3 Xo 2 P Xi 3 1 0 2 Pilo 2 e Pz 1 P È Please Kt 2 P Xi 3 X2 1 Kit p Here 2 P Xuxa 21 XK.tn e 1 X2 1 Xi 3 P XK.tn e 1 X2 1 Xi 3 IP Xu 2 21 Xuan 1 o assenza di IP Xke e 1 X2 1 Xi 3 memoria tuta 21 Xun I Plinti 11 Xu P Xs 11 2 1 PCXse.li Xr 3 PlXn 3 PznPnY Papa f E k Quindi 82 Ammette densità discreta Per i 3 4,5 50,1 J Per data da Pealktd ptgz.kz E KEN O altri'm i e 82 41 2 con Yo u GCE Oss Plaza to 1 Pleas too e F s Pp Kid 1 È pigra Kid a È Zenit È.IE o me 1 2 1 t ie Pier to 0 ma questo lo sapevamo gia perche i ricorrente Pillar to 1 E dato che stiamo considerando una Cdm irriducibile ogni stato è ricorrente in particolare 2 lo è p Dato che ora sappiamo come è distribuito 62 possiamo calcolare il suo valore atteso Ieri Etat Y at EED 4 Yo g h i EED 2 ed il risultato e in accordo con g Indicata con XT 1h È XK new lava media campionaria determinarne il limite 9 c in P in 2 Ricordiamo il Un TEOREMA ERGODIC O Sia f E IR e it la distribuzione i È.fm IL film Poiche la colte e irriducibile possiamo usare il turn ergodic Considerando la funzione fin se si ottiene È.fm him E in lei e quindi anche in Pe 2 515 Xu stato di un semaforo al tempo 4 i e dopo neo scaldi Il semaforo può presentarsi in anodalità verde a arancio Re rosso C completamente acceso E YA R spazio stati Xu evolve markovianate con meati sto cas gli scout avvengono ogni 3 minuti senatori molto numerosi semafori accesi contempo 01 01 2020 ore 00.00 equamente ripartiti tra i 4 stati possibili Da allora clonico indipendente 1 Se un semaforo è completamente acceso ad un dato istante pon quale probabilita rimarra completate acceso anche all istante successivo Plinti CI Xu c po 2 Disegnare il grado della catena classificare gli stati ad elencarne tutte le classi chiuse irriducibili 1 1 1 DE c a R C i e la catena di Markov è irriducibile tutti gli stati sono ricorrenti ed hanno stesso Pei ioda ne Acc O stati aperiodic na catena di Markov irriducibile aperiodica L' u n i c a classe chiusa e irriducibile c'E 3 Calcolare le distribuzioni invarianti della catena della catena Dato che la catena e irriducibile 7 invariant measure N e La si trova risolvendo TEMP Ti 70 Igt zitta In Tn t Ita ittita 1 Ti 20 Hi en 4 TE 1 1,13 Vo g l i a m o ora prevedere la percentuale di semafori che sarai completamente accesa il 1510112020 Ore 0000 4 Quale quantità relativa alla catena ci può dare tale percentuale sappiamo che ci sono un numero elevato d semafori Supponiamo che i semafori siano KEN con K grande Di questi K semafori vogliamo prevedere lucenti saranno nello stato C al tempo h 14 24 60 6720 numero di Cambi di 1 3 stato accaduti nè fissato in 14 gg uno agli 3 minuti conviene allora introdurre le v c IN n c dove Xiu indica lo stato del semaforo i cieli K al tempo h Abbiamo È Blanca Pl Yi 1 PI Xin c Plinio il prob che il semaforo e i semafori J C si comportano li sia acceso al allo stesso o nic tempo in modo Noi siamo interessati alla percentuale di semafori accesi al tempo vi ie Q 11km È Yi I poiché i semafori sono molto numerosi possiamo fare uni approx per te too Dato che È di 8C cranica possiamo usare la IGN e quindi 9 c YI E 14 vince Pane c K too Yin BIO In conclusione abbiano che È È thx neiie Pineda venuto pace 1 Percentuale di semafori completati accesi al tempo h 6720 dove va e la legge della catena al Genero in i e non ti p ma approssimativamente la percentuale di semafori in C al tempo m e data da vini op 5 Calcolare eventualmente in modo approssimato la percentuale di semafori che sarà nello stato e il 1510112020 Ore 0000 In caso di calcolo approssimato giustificare l'approssimazione Dal punto 4 sappiamo che supponendo che il numero di semafori k sia sulticientemente grande la le di semafori nello stato C al tempo U e vini c OHP c Pan c Possiamo calcolare il valore approx di tale quantita usando il seguente Thing sia 3hr3m o una catena di Markov irriducibile caperiodica allora vini it Hood h co n possiamo usare questo risultato perché siamo nel caso irriducibile aperiodic qua stanno poi supponendo plausibile che vi sia grande abbasti da usare li approx per n too allora abbiamo che pila c oh via ph e Tlc N 57 semafori nello stato Calkenpon Vo g l i a m o ora calcolare la percentuale d'temp che il semaforo all incrocio tra Mad Street and wild Road passa alla lunga nello stato e 6 Quale quantità relativa alla catena di Markov 2hr3m2s ci può dare questa informazione Giustificare Sia Xu lo stato al tempo n proprio del semaforo all'incrocio di interesse Per rispondere alla domanda usiamo il hai TEOREMA ERGO DICO non Sia 3hr3 neo catena di Markov irriducibile 2 Allora È ÌL him jekilte.tn e R In particolare È 1am.is frazione di tempo frazione di tempo che che alla lunga la la catena passa nello stato Cdr passa in c tra il tempo 0 e il tempo n avremo quindi che È Isaac È Ncd Pan c 4 7 Percentuale di tempo che il nostro semaforo alla lunga passi nello stato c