CATENE DI MARKOV - dei.unipd.itfornasini/10Ter_Catene di Markov.pdf · In alternativa a descrivere...

Capitolo 13

CATENE DI MARKOV

Le catene di Markov sono sistemi dinamici discreti che presentano caratteristiche alquantodiverse rispetto a quelli considerati finora. Nell’accezione piu semplice, si tratta di sistemia stati finiti (catene di Markov finite1) nei quali - e cio rappresenta un essenziale punto dinovita rispetto ai modelli precedentemente analizzati - la transizione da uno stato all’altroavviene su base probabilistica, anziche deterministica. In altre parole, l’informazionedisponibile circa una catena al generico istante t e fornita dalle probabilita che essa sitrovi in uno qualsiasi degli stati, e l’evoluzione temporale della catena viene specificataprecisando in qual modo tali probabilita si aggiornino passando dall’istante t all’istantet+ 1. La trattazione delle catene di Markov puo ricondursi allora a quella dei sistemi di-screti positivi quando si interpreti il comportamento dinamico di una catena in termini dievoluzione temporale dei vettori che esprimono la distribuzione di probabilita sui suoi varistati. Tale evoluzione, come vedremo, si ottiene infatti trasformando i vettori di probabilitamediante l’azione di matrici positive di una classe particolare (matrici stocastiche).

13.1 Definizioni e concetti introduttivi

Una catena di Markov (finita) C fornisce un modello teorico per descrivere il comporta-mento di un sistema a tempo discreto che puo trovarsi ad ogni istante in qualche statoappartenente ad un assegnato insieme finito S = {S1, S2, . . . , Sn} di stati. Passando da unistante al successivo, il sistema “salta” da uno stato ad un altro, e la legge - di carattereprobabilistico - secondo cui avviene la transizione di stato e formulabile in questi termini:

“qualunque sia stata l’evoluzione della catena prima dell’istante t, se il sistema altempo t si trova nello stato Si, la transizione lo portera all’istante t + 1 nello statoSj con probabilita pij”.

L’insieme delle probabilita di transizione {pij , i, j = 1, 2, . . . , n} e assegnato e determina ilcomportamento (probabilistico) della catena, una volta che siano note le condizioni iniziali(i.e. qual e al tempo t = 0 lo stato in cui la catena si trova o, piu in generale, qual e altempo t = 0 la distribuzione di probabilita sui vari stati).In termini piu formali, una catena di Markov (finita) C consiste di

1la teoria delle catene di Markov si estende tuttavia anche a sistemi con un’infinita numerabile di stati.

451

452 CAPITOLO 13. CATENE DI MARKOV

• un insieme S = {S1, S2, . . . , Sn}, chiamato “spazio di stato”,

• una sequenza di variabili casuali X(0), X(1), X(2), . . . che prendono valori in S (il valore di X(t)rappresenta lo stato che la catena “visita” nell’istante t), aventi la seguente proprieta di “marko-vianita”:

pr{X(t+ 1) = Sνt+1 |X(t) = Sνt , X(t− 1) = Sνt−1 , . . . X(0) = Sν0

}= pr

{X(t+ 1) = Sνt+1 |X(t) = Sνt

}purche si abbia2 pr

{X(t) = Sνt , X(t− 1) = Sνt−1 , . . . X(0) = Sν0

}> 0.

La markovianita equivale ad asserire che l’evoluzione delle probabilita future (i.e. la distribuzione diprobabilita al tempo t + 1 sui possibili valori che X(t + 1) puo assumere) e determinata completamentedalla conoscenza delle condizioni attuali della catena (i.e. dalla conoscenza di quale valore assume X(t)),non dipendendo dal comportamento del processo (i.e. da quali stati ha visitato) negli istanti precedenti t.La probabilita pr {X(t+ 1) = Sk|X(t) = Si} sara qui assunta indipendente da t (catena di Markov omo-genea), sara chiamata “probabilita di transizione” dallo stato Si allo stato Sk, e sara denotata con pik.

L’informazione disponibile circa il comportamento di una catena di Markov e quindi com-pletamente contenuta nella matrice di transizione

P =

p11 p12 . . . p1n

p21 p22 . . . p2n

. . . . . .pn1 pn2 . . . pnn

Si tratta di una matrice positiva nella quale e unitaria la somma degli elementi di ciascunariga. Infatti, gli elementi della riga i-esima sono le probabilita che la catena, trovandosinello stato Si all’istante t, transiti in S1 o in S2, . . . o in Sn all’istante successivo, e tali eventi(di transizione) risultano mutuamente esclusivi ed esaustivi di tutte le possibilita. Unamatrice siffatta (positiva con righe a somma unitaria) si dira “stocastica”, e chiameremo“stocastico” ogni vettore riga positivo xT = [x1 x2 . . . xn ] nel quale la somma deglielementi assuma valore unitario:

∑ni=1 xi = 1.

In alternativa a descrivere una catena di Markov C mediante la sua matrice di transizione,si puo associare a C un grafo orientato nel quale

• i vertici sono (etichettati da)gli stati S1, S2, . . . , Sn (o dagli indici 1, 2, . . . , n deglistati);

• c’e un arco orientato che connette il vertice Si al vertice Sj se e solo se e positiva laprobabilita pij di transizione da Si a Sj (probabilita che viene a sua volta utilizzatacome “etichetta” dell’arco stesso.

E chiaro che matrice di transizione e grafo forniscono la medesima informazione sullacatena C.

Esempio 13.1.1 [Condizioni meteorologiche sulla vetta di Utopia] Nel paese di Utopia c‘euna sola vetta degna di questo nome, e su questa vetta non ci sono mai due giorni consecutivi dibel tempo. Le pazienti osservazioni dei migliori meteorologi di Utopia hanno portato alle seguenticonclusioni:

2se pr{B} = 0, pr{A|B} non e definita

13.1. DEFINIZIONI E CONCETTI INTRODUTTIVI 453

- se c’e’ sole, il giorno dopo ci sono eguali probabilita che sulla vetta tempesti o nevichi;

- se tempesta o nevica, ci sono eguali probabilita che il tempo sulla vetta rimanga lo stesso il giornosuccessivo, oppure che il tempo cambi;

- se tempesta o nevica e il tempo cambia, ci sono eguali probabilita che il giorno successivo la vettasia coperta di sole o che la tempesta (la neve) del giorno prima si volga in neve (in tempesta).

Indicando nell’ordine con S, T,N (o con 1, 2, 3)le tre possibili condizioni meteorologiche (sole,tempesta, neve), si ricavano la matrice di tran-sizione

P =

0 1/2 1/2

1/4 1/2 1/4

1/4 1/4 1/2

=

[p11 p12 p13

p21 p22 p23

p31 p32 p33

]

e il grafo orientato corrispondente di figura13.1.1.

u

u u��-PP

�PP ��6

��6

��7��

��/

��

��

SSSSSSSSo

@@

SSSSSSSw

CCC

ZZT = 2 N = 3

S = 1

p12 p13

p21 p31

p23

p32p22 p33

figura 13.1.1

Esempio 13.1.2 Supponiamo che uno studente frequenti un certo corso di laurea triennale e as-sumiamo come stati possibili della sua carriera i sei seguenti:

1 essere iscritto al primo anno di corso

2 essere iscritto al secondo anno di corso

3 essere iscritto al terzo anno di corso

4 essere fuori corso

5 conseguire la laurea

6 ritirarsi dal corso di laurea

Trascorso un anno dall’iscrizione al primo anno di corso, egli ha probabilita 0, 60 di iscriversi alsecondo, 0, 20 di ritirarsi, 0, 20 di ripetere l’iscrizione al primo anno;

trascorso un anno dall’iscrizione al secondo anno di corso, con probabilita 0, 80 si iscrive al terzoanno, con probabilita 0, 05 si ritira, con probabilita 0, 15 ripete l’iscrizione al secondo anno;

trascorso un anno dall’iscrizione al terzo anno di corso, con probabilita 0, 7 si laurea, con probabilita0, 02 si ritira, con probabilita 0, 28 diventa fuori corso;

alla conclusione di un anno di fuori corso, con probabilita 0, 6 consegue la laurea, con probabilita0, 38 si reiscrive come fuori corso, con probabilita 0, 02 si ritira dagli studi.

Con riferimento alla numerazione degli stati che abbiamo scelto, la matrice di transizione e laseguente

P =

a anno I II III FC Lau Rit

da anno I

anno II

anno III

fuoricorso

laureato

ritirato

0, 20 0, 60 0 0 0 0, 20

0 0, 15 0, 80 0 0 0, 05

0 0 0 0, 28 0, 70 0, 02

0 0 0 0, 38 0, 60 0, 02

0 0 0 0 1 0

0 0 0 0 0 1


Se la catena al tempo 0 si trova (deterministicamente) nello stato Si, al tempo 1 potratrovarsi in ciascuno degli stati Sj , j = 1, 2, . . . , n con probabilita pij . Il vettore stocasticoxT (1), che fornisce le probabilita dei vari stati di C

xT (1) = [ pi1 pi2 . . . pin ]

si ottiene moltiplicando eTi , che possiamo interpretare come distribuzione di probabilitasui vari stati della catena al tempo t = 0, per la matrice di transizione:

xT (1) = eTi P

Se lo stato al tempo 0 e noto solo in termini probabilistici, ovvero se l’informazione disponi-bile e costituita dalle probabilita πj che lo stato del sistema sia Sj , j = 1, 2, . . . , n, posto

xT (0) = [π1 π2 . . . πn ]

abbiamoxT (1) = [π1 π2 . . . πn ]P. (13.1)

Infatti, l’evento che la catena C al tempo t = 1 si trovi in Sj puo verificarsi secondo leseguenti modalita, mutuamente esclusive ed esaustive di tutte le possibilita:

- per t = 0 lo stato e S1 e si ha la transizione S1 → Sj- per t = 0 lo stato e S2 e si ha la transizione S2 → Sj. . .

- per t = 0 lo stato e Sn e si ha la transizione Sn → Sj

La prima eventualita ha probabilita π1p1j , la seconda ha probabilita π2p2j , . . . , l’ultimaha probabilita πnpnj , da cui la (13.1): il prodotto di xT (0) per la j-esima colonna di P daquindi la probabilita che lo stato della catena all’istante t = 1 sia Sj .Un ragionamento sostanzialmente analogo al precedente consente di determinare le proba-bilita dei vari stati della catena al generico istante t ≥ 1. Tramite la (13.1), infatti, siesprime in funzione di xT (t − 1) il vettore stocastico xT (t) le cui componenti fornisconole probabilita che la catena al tempo t si trovi in uno degli n stati possibili, a sua volta infunzione di xT (t − 2) si esprime il vettore stocastico xT (t − 1) , e cosı via..., pervenendoinfine alla relazione

xT (t) = xT (t− 1)P =(xT (t− 2)P

)P = . . . = xT (0)P t (13.2)

In particolare, se lo stato al tempo t = 0 e Si e quindi se xT (0) = eTi , si ha

xT (t) = eTi Pt,

ovvero le probabilita che la catena si trovi in ciascuno degli n stati Sj al tempo t sonofornite dalle componenti della riga i-esima di P t.

Le probabilita di transizione in 2 passi, da uno stato Si in uno stato Sk sono suscettibilidi una interpretazione particolarmente suggestiva sul grafo della catena di Markov. Ilpassaggio da Si al tempo t = 0 a Sk al tempo t = 2 puo avvenire secondo n modalita

13.2. CATENE DI MARKOV REGOLARI 455

mutuamente esclusive ed esaustive, passando prima da Si in Sj , j = 1, 2, . . . , n, e succes-sivamente da Sj ad Sk. La j-esima di queste modalita ha probabilita pijpjk, positiva se esolo se entrambi i fattori sono positivi, ovvero se nel grafo c’e un cammino di due archi checonnette Si a Sk passando per Sj . La probabilita complessiva di passare da Si al tempot = 0 ad Sk al tempo t = 2 e quindi

∑j pijpjk, elemento di posizione (i, k) nella matrice

P 2, corrispondente alla somma di tutte le probabilita associate ai cammini di lunghezza 2che nel grafo di C connettono Si a Sk.Il ragionamento svolto si estende alla transizione da Si a Sk in t passi, con t ≥ 3: sul grafosi dovranno considerare tutti i cammini di lunghezza t che connettono Si a Sk, camminicorrispondenti agli addendi della sommatoria

∑ν1,ν2,...νt−1

pi,ν1pν1,ν2 · · · pνt−1,k

che fornisce l’elemento p(t)ij in posizione (i, k) nella matrice P t.

Da quanto precede, appare chiaramente come il comportamento delle catene di Markovsia riconducibile all’analisi delle proprieta delle matrici stocastiche, e quindi a quello dellematrici positive che abbiamo svolto nel capitolo precedente. Di interesse generale e ilfatto espresso nella seguente proposizione, la cui prova consegue dalle proposizioni 10.6.1e 10.6.3, ricordando che le somme di riga di P sono tutte unitarie.

Proposizione 13.1.1 [Autovalore e autovettore massimale di una matrice sto-castica] Se P ∈ Rn×n e una matrice stocastica, allora il suo autovalore massimale eλ0 = 1, cui corrisponde un autovettore sinistro stocastico pT0 e l’autovettore destro stret-tamente positivo 1 (che puo essere reso stocastico mediante divisione per n):

pT0 P = pT0 , P1 = 1 (13.3)

13.2 Catene di Markov regolari

Definizione 13.2.1 Una catena di Markov C si dice “regolare” se la sua matrice ditransizione P e primitiva.

La regolarita, ovvero l’esistenza di un intero positivo h per cui P h >> 0, ha comeconseguenza che gli elementi p(h)

ik di P h sono tutti positivi, per ogni i, k ∈ {1, 2, . . . , n}:qualunque sia lo stato Si in cui si trova la catena all’istante t = 0, c’e una probabilitapositiva - appunto p(h)

ik - che essa si trovi nello stato Sk al tempo t = h, qualunque sia Sk.Sul grafo orientato della catena cio equivale ad assumere che per ogni coppia di verticiSi ed Sk esista almeno un cammino orientato di h archi che connette il primo vertice alsecondo (e almeno un altro cammino orientato di h archi che connette il secondo verticeal primo).


13.2.1 Comportamento asintotico

Dal teorema di Perron sulle matrici primitive consegue la seguenteProposizione 13.2.2 [Comportamento asintotico delle catene regolari] Sia Cuna catena regolare, con matrice di transizione P .

i) [Autovalore e autovettore dominante] La matrice P ha l’autovalore domi-nante λ0 = 1 con molteplicita algebrica 1 e tutti gli altri autovalori di P hannomodulo minore di 1. L’autovettore dominante sinistro pT0 e strettamente positivo eunivocamente determinato dalla condizione di essere stocastico

pT0 = [ γ1 γ2 · · · γn ] ,n∑i=1

γi = 1

pT0 = pT0 P.

Il vettore 1n e, a meno di una costante moltiplicativa non nulla, l’unico autovettoredominante destro: P1n = 1n.

ii) [Rappresentazione dei vettori stocastici] Se pT0 ,pT1 , . . . ,p

Tn−1 sono una base

di Jordan di autovettori e autovettori generalizzati sinistri di P , ogni vettore stoca-stico uT ha una rappresentazione del tipo

uT = pT0 + α1pT1 + . . .+ αn−1pTn−1, αi ∈ C (13.4)

iii) [Distribuzione asintotica di probabilita] Se xT (0) = uT e un’arbitraria di-stribuzione iniziale di probabilita della catena, la distribuzione xT (t) all’istante tsoddisfa

limt→+∞

xT (t) = limt→+∞

uTP t = pT0 (13.5)

iv) [Matrice asintotica] Quando t tende a infinito, si ha

limt→+∞

P t =

pT0pT0. . .pT0

= 1pT0 := P (13.6)

La matrice P

– e idempotente, i.e. P 2 = P ,

– commuta con P e la assorbe, i.e. PP = PP = P .

Prova Il punto (i) consegue immediatamente dalla Proposizione 10.4.2: la primitivita diP comporta infatti che λ0 abbia molteplicita algebrica 1 e che gli autovettori dominantidestri e sinistri siano strettamente positivi, e univocamente individuati quando si impongaloro la condizione di essere stocastici o si specifica il valore di una loro componente.Per il punto (ii), il teorema di Perron riferito a basi di Jordan sinistre comporta che ilvettore stocastico uT = [u1 u2 . . . un ] sia esprimibile nella forma

uT = α0pT0 + α1pT1 + . . .+ αn−1pTn−1, α0 > 0, α1, . . . , αn−1 ∈ C (13.7)


Postmoltiplicando entrambi i membri di (13.7) per l’autovettore dominante destro e tenutoconto che pTi 1 = 0 per i = 1, 2, . . . , n− 1 perche pTi sono autovettori, anche generalizzati,relativi ad autovalori diversi da λ0 = 1, si ha

1 =n∑i=1

ui = uT1 = α0pT0 1 = α0

n∑i=1

γi = α0

e quindi (13.4).Il punto (iii) e una conseguenza del comportamento asintotico di un sistema dotato diautovettore dominante. Poiche gli autovalori diversi dall’autovalore di Perron hanno mod-ulo minore di 1, i trasformati secondo P t degli autovettori non dominanti, pTi P

t, i =1, . . . , n− 1, sono infinitesimi al divergere di t e si ha

limt→+∞

xT (t) = limt→+∞

uTP t

= limt→+∞

(pT0 + α1pT1 + . . .+ αn−1pTn−1

)P t

= limt→+∞

(pT0 + α1pT1 P

t + . . .+ αn−1pTn−1Pt)

= pT0 .

Per il punto (iv) basta prendere in (13.5) uT = ei, ottenendo pT0 = limt→+∞ eTi Pt.

Pertanto la riga i-esima di P t converge a pT0 , e cio vale per i = 1, 2, . . . , n.Quindi la matrice asintotica limt P

t ha tutte le righe eguali a pT0 e si esprime nella forma1pT0 .L’idempotenza di P deriva da

P 2 = (1pT0 )(1pT0 ) = 1(pT0 1)pT0 = 1pT0 = P

mentre da

P = limt→+∞

P t = limt→+∞

P t+1 = P

(lim

t→+∞P t)

= PP =(

limt→+∞

P t)P = PP (13.8)

segue che P commuta con P e la “assorbe” nel prodotto.

Esempio 13.1.1 Continuazione La catena di Markov delle condizioni meteorologiche sulla vettadi Utopia e regolare: infatti P 2 e strettamente positiva.

L’autovettore sinistro dominante pT0 si ottiene risolvendo in γ1, γ2, γ3 l’equazione matriciale

[ γ1 γ2 γ3 ] = [ γ1 γ2 γ3 ]

0 1/2 1/2

1/4 1/2 1/4

1/4 1/4 1/2

ovvero, eguagliando le prime due componenti di riga (per la terza componente si ottiene un’equazionedipendente dalle prime due), il sistema lineare omogeneo

γ1 = γ2/4 + γ3/4γ2 = γ1/2 + γ2/2 + γ3/4

Imponendo che la soluzione sia un vettore stocastico, si ricava

pT0 = [ 1/5 2/5 2/5 ] .


Esempio 13.2.1 [Passeggiate casuali] Si consideri una particella che si muove fra 5 posizioniS1, S2, S3, S4, S5 allineate su un segmento

u u u u u-

�S1 S2 S3 S4 S5

q

p

Si supponga che, se al tempo t la particella si trova in una delle posizioni “interne”, all’istante suc-cessivo essa si sposti verso la posizione immediatamente a sinistra con probabilita p, (0 < p < 1) overso la posizione immediatamente a destra con probabilita q = 1− p.Per quanto attiene al comportamento nelle posizioni estreme, consideriamo varie ipotesi:

1. [estremi assorbenti] la particella rimane “intrappolata” nella posizione estrema alla quale egiunta;

2. [estremi riflettenti] se all’istante t la particella si trova in una delle posizioni estreme, conprobabilita 1 all’istante t+ 1 viene riflessa nella posizione interna piu vicina;

3. [ritorno al centro] se all’istante t la particella si trova in una delle posizioni estreme, conprobabilita 1 all’istante t+ 1 viene riflessa nella posizione centrale S3.

Le matrici di transizione nei tre casi sono

P1 =

1 0 0 0 0p 0 q 0 00 p 0 q 00 0 p 0 q0 0 0 0 1

, P2 =

0 1 0 0 0p 0 q 0 00 p 0 q 00 0 p 0 q0 0 0 1 0

, P3 =

0 0 1 0 0p 0 q 0 00 p 0 q 00 0 p 0 q0 0 1 0 0

,Evidentemente P1 non e primitiva, e nemmeno irriducibile, poiche in tutte le sue potenze la primae l’ultima riga rimangono eguali ai vettori eT1 ed eT5 . Non e primitiva nemmeno P2. Infatti le suepotenze di grado 2,3,4 hanno struttura

P 22 =

+ 0 + 0 00 + 0 + 0+ 0 + 0 +0 + 0 + 00 0 + 0 +

, P 32 =

0 + 0 + 0+ 0 + 0 +0 + 0 + 0+ 0 + 0 +0 + 0 + 0

, P 42 =

+ 0 + 0 +0 + 0 + 0+ 0 + 0 +0 + 0 + 0+ 0 + 0 +

,quindi, per k > 1, tutte le matrici P 2k+1 e P 2k hanno rispettivamente la struttura booleana di P 3 edi P 4. Tuttavia, essendo I5 + P2 + P 2

2 + P 32 + P 4

2 strettamente positiva, la matrice P2 e irriducibile(quindi, come vedremo in seguito, la catena corrispondente e ergodica).

P3 invece e primitiva, risultando P 53 >> 0. Per determinarne l’autovettore sinistro dominante pT0 =

[ γ1 γ2 γ3 γ4 γ5 ] si risolve l’equazione

[ γ1 γ2 γ3 γ4 γ5 ] = [ γ1 γ2 γ3 γ4 γ5 ]

0 0 1 0 0p 0 q 0 00 p 0 q 00 0 p 0 q0 0 1 0 0

ottenendo le relazioni

γ1 = pγ2 = p2γ3

γ2 = pγ3

γ4 = qγ3

γ5 = qγ4 = q2γ3

Il vettore pT0 puo essere quindi espresso in funzione di γ3

pT0 = [ p2γ3 pγ3 γ3 qγ3 q2γ3 ]


e successivamente determinato completamente imponendo la condizione di stocasticita

(p2 + p+ 1 + q + q2)γ3 = 1

che individua il valore di γ3

γ3 =1

1 + (p+ q) + (p2 + q2)=

1

3− 2pq.

Se nella catena di Markov regolare C si ha P h >> 0, per ogni scelta di i e k risulta p(h)ik > 0,

ovvero e positiva la probabilita che la catena, partendo dallo stato Si all’istante t = 0, sitrovi nello stato Sk all’istante t = h. A maggior ragione, e positiva la probabilita che lacatena, partendo dallo stato Si all’istante t = 0, si trovi nello stato Sk in almeno uno degliistanti 1, 2, . . . , h. Se denotiamo con π

(h)ik tale probabilita, abbiamo

0 < mini=1,2,...,nk=1,2,...n

{p(h)ik } ≤ min

i=1,2,...,nk=1,2,...n

{π(h)ik } := p

ovvero, comunque si scelgano gli stati Si e Sk, e positiva e non inferiore a p la probabilitache, partendo da Si, in almeno uno degli istanti t = 1, 2, . . . , h la catena visiti lo stato Sk.Equivalentemente e minore o eguale a 1 − p la probabilita che la catena non visiti Sk innessuno degli istanti t = 1, 2, . . . , h.Affinche la catena non visiti lo stato Sk in nessuno degli istanti t = 1, 2, . . . , 2h, occorreche essa

• non visiti Sk per t = 1, 2, . . . , h;

• a partire in t = h dallo stato, qualunque esso sia, in cui e giunta al tempo t = h, nonvisiti Sk negli h istanti successivi h+ 1, h+ 2, . . . , 2h,

quindi la probabilita che C non visiti Sk (comunque si scelga lo stato iniziale) e minore oeguale a (1− p)2. Induttivamente si verifica che la probabilita che la catena non visiti unostato Sk arbitrariamente scelto in nessuno degli istanti t = 1, 2, . . . , hs non eccede (1− p)s,probabilita che converge a 0 quando l’intervallo di tempo diverge. Conseguentemente, seil tempo a disposizione e infinito, e zero la probabilita che lo stato Sk non sia mai visitato.

13.2.2 Tempi medi di attesa

Consideriamo ora la variabile casuale a valori interi fik, che fornisce l’istante in cui lacatena C che parte dallo stato Si all’istante t = 0 transita per la prima volta3 attraversolo stato Sk. Il resto del paragrafo e dedicato all’analisi di alcuni caratteri statistici di fik.

Proposizione 13.2.3 [fik ha media finita] Si consideri una catena regolare C e siindichi con mik il valor medio della variabile casuale fik che fornisce il primo istante in cuila catena, partendo in Si, entra nello stato Sk:

E(fik) := mik =+∞∑ν=1

ν pr{fik = ν} . (13.9)

Si ha sempre mik <∞.

3nel caso in cui Si = Sk, non si considera come istante di “transito” l’istante t = 0


Prova Supponiamo che la potenza h-esima della matrice di transizione P della catena siastrettamente positiva.Trattandosi di una serie a termini non negativi, la somma della serie (13.9) puo esserevalutata accorpando i termini a gruppi di h

mik =h∑ν=1

ν pr{fik = ν}+2h∑

ν=h+1

ν pr{fik = ν}+3h∑

ν=2h+1

ν pr{fik = ν}+ . . .

Per maggiorare i termini della seconda sommatoria, osserviamo che il primo passaggio perSk potra verificarsi in un istante ν compreso fra h + 1 e 2h solo se fino all’istante h lacatena non avra mai visitato lo stato Sk. Quindi la probabilita che il primo passaggio siverifichi nell’istante ν compreso fra h+1 e 2h e minore o eguale a quella che fino all’istanteh lo stato Sk non sia mai stato visitato, ovvero e minore o eguale a 1− p.Con un ragionamento analogo, nella terza sommatoria le probabilita che il primo passaggioper Sk avvenga in un istante ν compreso fra 2h+ 1 e 3h non supera (1− p)2, etc.Si ha quindi

mik ≤h∑ν=1

ν +2h∑

ν=h+1

ν(1− p) +3h∑

ν=2h+1

ν((1− p)2 + . . .

≤ h2 + 2h2(1− p) + 3h2(1− p)2 + . . .

= h2(1 + 2(1− p) + 3(1− p)2 + . . .

)in cui la serie dell’ultima riga converge per il criterio del rapporto.

Vogliamo ora determinare esplicitamente, per ogni coppia (i, k), il valore (finito) di mik.A tale scopo riuniremo tutte le medie in un’unica matrice M = [mik] di dimensione n× ne procederemo secondo i passi seguenti:

1. ricaveremo un’equazione lineare matriciale che deve essere soddisfatta dalla matricedelle medie M ;

2. dimostreremo che tutte le matrici che risolvono l’equazione hanno la medesima diago-nale e ricaveremo esplicitamente diag(M);

3. verificheremo che e unica la soluzione dell’equazione del punto 1;

4. come esercizio, proporremo una costruzione dell’(unica) matrice M che risolve l’equa-zione.

Proposizione 13.2.4 [Equazione per la matrice delle medie] Si consideri unacatena regolare con matrice di transizione P e sia M = [mik] la matrice n × n dei valorimedi delle variabili casuali fik.

Allora M e soluzione della seguente equazione nella matrice incognita X, di dimensionen× n,

X = 1n1Tn + P (X − diag(X)) (13.10)


Prova Assumendo che lo stato iniziale della catena sia S(0) = Si, la media mik dellavariabile fik si puo ottenere come media delle sue medie condizionate dall’esito del primopasso della catena. In altri termini, si assumera la condizione che al primo passo la catenaC visiti lo stato Sj , j = 1, 2, . . . , n e si peseranno con le probabilita pij (di transizione inun passo) i tempi medi per la prima visita di Sk sotto la condizione S(1) = Sj :

mik =n∑j=1

E(fik|S(1) = Sj)pr{S(1) = Sj}

= E(fik|S(1) = Sk)pr{S(1) = Sk}+∑j 6=k

E(fik|S(1) = Sj)pr{S(1) = Sj}

= 1 · pik +∑j 6=k

(1 +mjk)pij . (13.11)

Ma allora per ogni i e k valgono le relazioni

mik =n∑j=1

pij +∑j 6=k

pijmjk = 1 +n∑j=1

pijmjk − pikmkk,

che in termini matriciali si esprimono nella scrittura

M = 1n1Tn + P (M − diag(M)) . (13.12)

Quindi M e soluzione dell’equazione (13.10).

Lemma 13.2.5 [Unicita della diagonale nelle soluzioni dell’equazione] SiapT0 = [ γ1 γ2 . . . γn ] la distribuzione asintotica di probabilita della catena regolare Ce sia M una arbitraria soluzione di (13.10). Allora la matrice dei termini diagonali di Me data da

diag(M) =[ 1γ1

1γ2

. . .1γn

](13.13)

Prova Premoltiplicando primo e secondo membro di M = 1n1Tn + P(M − diag(M)

)per

pT0 si ottiene

pT0 M = pT0 11T + pT0 P(M − diag(M)

)= 1T + pT0

(M − diag(M)

)e quindi

pT0 diag(M) = [ γ1 γ2 . . . γn ]

m11

m22. . .

mnn

= [ 1 1 . . . 1 ] ,

da cui segue mii = 1/γi per 1 = 1, 2, . . . , n.

Il lemma 13.2.5 fornisce, in particolare, i valori diagonali della matrice delle medie M ,ovvero, per ogni i, il valore medio del tempo richiesto affinche una catena regolare inizializ-zata in un certo stato Si lo rivisiti per la prima volta. Tale media, come si vede, e il


reciproco della probabilita asintotica che la catena si trovi nello stato Si. La proposizionesuccessiva, dimostrando che la soluzione dell’equazione lineare (13.10) e unica, garantiscela sua risolubilita con la regola di Cramer (o con metodi equivalenti). Negli esercizisuccessivi, si fornisce una traccia per ricavare la struttura esplicita della matrice dellemedie a partire dalla matrice di transizione P e dalla matrice asintotica P = 1pT0

Proposizione 13.2.6 [Unicita della soluzione per l’equazione delle medie] SiaM una soluzione dell’equazione (13.10). Allora M coincide con la matrice delle medie:M = M .

Prova Per la Proposizione precedente M soddisfa la condizione

diag(M) = diag(M) =

1γ1

1γ2

. . .1γn

Sottraendo membro a membro le identita

M = 11T + P (M − diag(M))M = 11T + P

(M − diag(M)

)si ottiene

M − M = P (M − M).

Per ogni i, la colonna i-esima v di M − M soddisfa la relazione v = Pv, quindi e nulla oe un autovettore destro di P relativo all’autovalore massimale λ0 = 1. Nel secondo casov dovrebbe essere proporzionale all’autovettore dominante destro 1, ma la sua i-esimacomponente e nulla. Quindi la colonna v e identicamente nulla.

• Esercizio 13.2.1 [Matrice fondamentale di una catena regolare] Chiamiamo matrice fon-damentale della catena regolare C, con matrice di transizione P e matrice asintotica P = limt→∞ P

t,la matrice n× n

Z :=(In − (P − P )

)−1(13.14)

Si dimostri che(i) [Autovalori di P − P ] la matrice P − P ha tutti gli autovalori con modulo minore di 1;(ii) [rappresentazione di Z] la matrice

(In − (P − P )

)e invertibile e la sua inversa e esprimibile

comeZ = I + (P − P ) + (P − P )2 + (P − P )3 + . . . (13.15)

(iii) [Proprieta di Z] La matrice fondamentale Z ha le seguenti proprieta:

ZP = PZP = PZP = In − Z + PZ

] Suggerimento: (i) Utilizzando le proprieta di P e di P dimostrate nella proposizione 13.2.2, si ha

(P − P )t =

t−1∑ν=0

(t

ν

)(−1)t−νP ν P t−ν + P t =

t−1∑ν=0

(t

ν

)(−1)t−νP ν P + P t

13.3. CATENE DI MARKOV IRRIDUCIBILI 463

= [

t−1∑ν=0

(t

ν

)(−1)t−ν ]P + P t = [

t∑ν=0

(t

ν

)(−1)t−ν −

(t

t

)(−1)0]P + P t = −P + P t

Ma allora limt→+∞(P − P )t = 0 implica |Λ(P − P )| < 1

(ii) l’invertibilita della matrice In − (P − P ) e immediata. Per la rappresentazione in serie di Z siutilizza il lemma 10.5.6 valutando il risolvente (λIn − (P − P ))−1 di P − P per λ = 1.

(iii) da (P − P )P = P − P 2 = P − P = 0 e da (P − P )P = P (P − P ) segue

ZP = [I + (P − P ) + (P − P )2 + . . .]P = PZP = [I + (P − P ) + (P − P )2 + . . .]P = P [I + (P − P ) + (P − P )2 + . . .] = PZ

In − Z = −(P − P )− (P − P )2 − (P − P )3 . . .= −(P − P )[I + (P − P ) + (P − P )2 + . . .] = −(P − P )Z = −PZ + PZ = −PZ + P

• [Struttura della matrice delle medie] Per la catena regolare C, con matrice di transizione P ,

siano pT0 = [ γ1 γ2 . . . γn ] la distribuzione asintotica e quindi diag(M) =[

1

γ1

1

γ2. . .

1

γn

],

sia la diagonale della matrice M delle medie dei tempi di attesa fik. Posto

M :=(In − Z + 11Tdiag(Z)

)diag(M) (13.16)

si verifichi che

(i) diag(M) = diag(M);

(ii) M soddisfa l’equazione (13.10)

(iii) M coincide con la matrice M delle medie dei tempi di attesa fik.

] Suggerimento: (i) si applichi diag(Adiag(B)) = diag(A) diag(B):

diag(M) = diag([In − Z + 11Tdiag(Z)]diag(M)

)= diag

((In − Z + 11Tdiag(Z)

)diag(M)

=(In − diag(Z) + diag(11T )diag(Z)

)diag(M) = (In − diag(Z) + In diag(Z)) diag(M)

= diag(M)

(ii) si ha l’identita

M − diag(M) = M − diag(M) =(−Z + 11Tdiag(Z)

)diag(M)

segue

P (M − diag(M)) =(−PZ + 11Tdiag(Z)

)diag(M)

= M −(In − Z + 11Tdiag(Z)

)diag(M)−

(PZ − 11Tdiag(Z)

)diag(M)

= M − (In − Z + PZ)diag(M) = M − Pdiag(M) = M − 1pT0 diag(M)= M − 11T

(iii) Per la proposizione 13.2.6 M coincide con la matrice delle medie M .

13.3 Catene di Markov irriducibili

Definizione 13.3.1 Una catena di Markov C si dice irriducibile (o ergodica) quando lasua matrice di transizione P e irriducibile.

Poiche le matrici primitive rappresentano un caso speciale di matrici irriducibili, le cateneregolari sono una sottoclasse (propria) della classe delle catene irriducibili. Anche in unacatena irriducibile, come gia per una regolare, la transizione da Si a Sk in un opportunonumero di passi ha probabilita positiva, qualunque siano Si e Sk; tuttavia, a differenza dalcaso regolare, non e piu garantito che tale probabilita sia positiva per qualsiasi numero di


passi, purche sufficientemente grande. Cio e conseguenza del fatto che , salvo nel caso diuna P primitiva, non esiste una potenza m tale che Pm, e con essa Pm+1, Pm+2 . . ., sianostrettamente positive.

Quello che possiamo ancora affermare e che, se η e l’indice di imprimitivita di P e se m eabbastanza grande, risulta strettamente positiva la somma Pm + Pm+1 + . . . + Pm+η−1,ovvero che per tempi sufficientemente grandi ciascuno stato ha probabilita positiva diessere visitato ogni η passi. Dal corollario 10.5.4 sappiamo infatti che la matrice di tran-sizione irriducibile P con indice di imprimitivita η > 1 puo essere portata in forma ciclicadi Frobenius con una trasformazione di cogredienza. In altre parole, pur di riordinaregli stati possiamo supporre che la matrice P con indice di imprimitivita η > 1 abbia laseguente struttura

P =

0 P1,2 0 . . . 00 0 P2,3 . . . 0

. . .0 0 0 . . . Pη−1,η

Pη,1 0 0 . . . 0

(13.17)

in cui i blocchi diagonali hanno dimensione ν1 × ν1, ν2 × ν2, . . . , νη × νη.E ovvio che le potenze di P hanno struttura ciclica a blocchi, ovvero, per ogni ≥ 0,

P kη =

? 0 0 0 . . . 00 ? 0 0 . . . 00 0 ? 0 . . . 00 0 0 ? . . . 0

. . .

0 0 0 0 . . . ?

, P 1+kη =

0 ? 0 0 . . . 00 0 ? 0 . . . 00 0 0 ? . . . 0

. . .

0 0 0 0 . . . ?? 0 0 0 . . . 0

, P 2+kη =

0 0 ? 0 . . . 00 0 0 ? . . . 0

. . .

0 0 0 0 . . . ?? 0 0 0 . . . 00 ? 0 0 . . . 0

, . . .

Se lo stato della catena al tempo t = 0 e nella prima classe {S1, S2, . . . Sν1}, la catenaal passo successivo potra trovarsi solo in stati della seconda {Sν1+1, Sν1+2 . . . Sν1+ν2},nell’istante t = 2 solo in stati della terza {Sν1+ν2+1, Sν1+ν2+2 . . . Sν1+ν2+ν3} e cosı via.All’istante t = η potranno essere rivisitati stati della prima classe, etc per t+ 1, . . ..Le η classi sono dette “classi cicliche” della catena ergodica, perche con il trascorrere deltempo vengono visitate ciclicamente.Questa peculiarita, tuttavia, non coglie ancora in modo completo il comportamento dellacatena, perche non specifica secondo quali modalita i singoli stati di ciascuna delle classicicliche siano “visitati”. L’irriducibilita di P garantisce che tutti gli stati debbano avereprobabilita positiva di essere visitati in qualche istante, quindi che all’interno dei blocchiasteriscati tutte le posizioni in qualche istante debbano assumere valore positivo e che unvalore positivo vi verra assunto anche in infiniti istanti successivi. Ma rimane aperta laquestione se esistano istanti in cui tutti gli stati di una delle classi cicliche abbiano simul-taneamente probabilita positiva di essere visitati, ovvero se uno o piu blocchi asteriscatiin qualche istante possano diventare strettamente positivi.Al riguardo, un risultato fondamentale per quanto riguarda il comportamento di unacatena irriducibile e fornito dall’esercizio 10.5.2, relativo alle potenze della forma ciclica

13.3. CATENE DI MARKOV IRRIDUCIBILI 465

di Frobenius (13.17). In particolare, la primitivita di tutti i blocchi diagonali di

P η =

P12 · · ·Pη1

P23 · · ·P12. . .

Pη1 · · ·P(η−1)η

:=

P

(η)11

P(η)22

. . .P

(η)ηη

dimostrata nell’esercizio garantisce che, per k sufficientemente grande,

a) i blocchi diagonali di P kη sono strettamente positivi: quindi, l’inizializzazione dellacatena all’interno di una particolare classe ciclica comporta probabilita positiva divisitare tutti gli stati di quella classe nell’istante kη, e quindi in tutti i successiviistanti multipli di η;

b) i blocchi asteriscati in P 1+kη, P 2+kη, . . . sono tutti strettamente positivi (altrimenti Pdovrebbe avere una colonna nulla, impossibile per una matrice irriducibile): nell’istantesuccessivo all’istante kη, la catena potra visitare con probabilita positiva tutti gli statidella classe ciclica successiva a quella dello stato iniziale (nell’ordinamento che abbi-amo scelto), e nessuno stato delle altre classi, etc.

c) se lo stato iniziale Si appartiene alla prima classe ciclica, per t = η la distribuzionedi probabilita e fornita dalla i-esima riga di P η e le sue componenti non nulle ap-partengono alla riga i-esima del blocco stocastico e primitivo P

(η)11 . Una situazione

analoga si ripete negli istanti kη, qualunque sia k > 0. Dalla teoria delle cateneregolari sappiamo che

limk→∞

(P

(η)11

)k= 1ν1p

T01

dove pT01 >> 0T rappresenta la distribuzione asintotica della catena con matrice ditransizione P (η)

11 . Quindi, negli istanti multipli di η, la distribuzione di probabilitasi concentra sugli stati della prima classe ciclica e asintoticamente assume i valoriespressi dal vettore strettamente positivo pT01.

d) Sempre nell’ipotesi che Si appartenga alla prima classe ciclica, negli istanti kη+1, kη+2, . . . la distribuzione di probabilita si concentra sugli stati della seconda classe, dellaterza,. . . e al divergere di k tende ai vettori strettamente positivi

pT01P12, pT01P12P23, . . . .

• Esercizio 13.3.1 Si consideri una catena con matrice di transizione

P =

0 0 0 0 1 00 0 0 1/2 0 1/20 0 0 1 0 00 1 0 0 0 00 0 1 0 0 0

1/2 1/2 0 0 0 0

Si verifichi che

- la matrice P , e quindi la catena, sono irriducibili;

- l’indice di imprimitivita e η = 2;


- se all’istante t = 0 lo stato appartiene all’insieme {S1, S2, S3} (all’insieme {S4, S5, S6}) all’istantet = 8 e positiva la probabilita di visitare tutti gli stati dell’insieme {S1, S2, S3} (dell’insieme{S4, S5, S6});

Se in t = 0 lo stato iniziale e S1, in quale stato potra trovarsi la catena all’istante t = 1? quantotempo si dovra attendere perche il medesimo stato possa essere rivisitato dalla catena? e perchepossa esserlo per una terza volta? Qual e la distribuzione di probabilita negli istanti 2t al divergeredi t?

13.4 Classificazione degli stati e classi di comunicazione

Il comportamento di una catena di Markov puo assumere caratteristiche sostanzialmentediverse in corrispondenza a configurazioni diverse degli zeri nella matrice di transizione,ovvero in corrispondenza alla presenza o all’assenza di certi archi nel grafo orientato as-sociato alla catena. I particolari valori positivi di probabilita associati agli archi del grafodeterminano in termini quantitativi i rapporti fra le diverse componenti positive delledistribuzioni di probabilita nei vari istanti, ma non influiscono su aspetti di carattere“strutturale” o qualitativo, quali la possibilita di raggiungere con probabilita positiva daun certo istante in avanti tutti gli stati (come accade se P e primitiva), oppure di rag-giungerli periodicamente (come accade se P e irriducibile con indice η > 1), oppure di nonraggiungerne mai alcuni, oppure di doverli abbandonare definitivamente, etc.

13.4.1 Accessibilita e comunicazione

La comprensione di una catena di Markov richiede di procedere preliminarmente aduna classificazione degli stati che la compongono dal punto di vista della possibilita odell’impossibilita di transitare verso altri stati.

Definizione 13.4.1 [Accessibilita] Diciamo che uno stato Sk e accessibile dallo statoSi se e positiva la probabilita che la catena, partendo al tempo t = 0 dallo stato Si, visitiin qualche istante t ≥ 0 lo stato Sk

L’accessibilta di Sk da Si richiede che l’elemento in posizione (i, k) sia positivo in qualchepotenza della matrice P , ovvero che p(t)

ik > 0 per qualche t ≥ 0. Sul grafo orientato lacondizione equivale all’esistenza di almeno un cammino orientato che porti dal vertice Sial vertice Sk.La relazione di accessibilita non e simmetrica (l’esistenza di un cammino orientato daSi a Sk non implica quella di uno da Sk a Si), mentre e riflessiva, quando si convengadi includere fra i cammini quello di lunghezza 0, e transitiva (se da Si c’e un camminoorientato verso Sk e da Sk uno verso Sj , allora c’e un cammino orientato da Si a Sj).

Definizione 13.4.2 [Comunicazione] Diciamo che due stati Si e Sk comunicano se Ske accessibile da Si e Si e accessibile da Sk.

Se Si comunica con Sk, devono essere positivi l’elemento in posizione (i, k) in qualchepotenza t1-esima e l’elemento in posizione (k, i) in qualche potenza t2-esima4 della ma-trice P . Sul grafo orientato la condizione di comunicazione equivale all’esistenza di almeno

4t2 e in generale diverso da t1

13.4. CLASSIFICAZIONE DEGLI STATI E CLASSI DI COMUNICAZIONE 467

un cammino orientato che porti da Si a Sk e di un altro che porti da Sk a Si o, equivalen-temente, di un ciclo orientato passante per entrambi i vertici.La relazione di comunicazione e riflessiva, simmetrica e transitiva, quindi e una equiva-lenza. In quanto tale, induce una partizione degli stati in classi di equivalenza (“classi dicomunicazione”) disgiunte, la cui unione coincide con l’intero spazio degli stati.Due stati distinti Si e Sk• appartengono alla medesima classe di comunicazione se e solo se Sk e accessibile daSi e Si e accessibile da Sk;• appartengono a classi di comunicazione diverse se almeno uno dei due non e accessible

dall’altro.

A seconda della struttura della catena, dagli stati di una classe di comunicazione puo essereo non essere possibile visitare stati di altre classi di comunicazione come, d’altra parte,una classe di comunicazione puo essere visitata, oppure non puo, da stati appartenenti aclassi diverse. Le situazioni possibili sono schematizzate in figura 13.4.1.

'

&

$

%u��7u��:

u�uJJJ] ��

uBBBBN

��

-

'

&

$

%u��7u��:

u�uJJJ] ��

uBBBBN

-

6

'

&

$

%u��7u��:

u�uJJJ] ��

uBBBBN

--

��

��

K1 K2K3

figura 13.4.1

K4

K5

Nel primo caso, dalla classe di comunicazione K1 si possono visitare stati di altre classi,nel secondo da altre classi di comunicazione e possibile accedere alla classe K2, nel terzocaso e possibile sia transitare dalla classe K3 ad altre classi, sia accedere a K3 da altreclassi. Va tuttavia osservato che nel terzo caso, in cui esistono sia stati di K3 accessibili daqualche altra classe K4, sia stati di qualche classe K5 accessibili da K3, non puo esistere uncammino chiuso che esce dalla classe K3 e poi vi ritorna: in tal caso esisterebbe infatti unacomunicazione fra stati di K3 e stati di altre classi, classi che dovrebbero quindi coinciderecon K3.

13.4.2 Classi di comunicazione ergodiche

Definizione 13.4.3 [Classi ergodiche e classi transitorie] Una classe di comuni-cazione K si dice

• ergodica5 (o chiusa) se hanno probabilita nulla le transizioni da stati di K verso statidi altre classi, i.e. se nessuno stato fuori di K e accessibile da (uno stato di) K (se Kconsta di un solo stato, questo viene detto stato “assorbente”);

• transitoria se sono possibili transizioni da stati di K verso stati di altre classi, i.e. seesistono stati esterni a K accessibili da (qualche stato di) K.

5si faccia attenzione a non confondere una classe ergodica, che e una particolare classe di comunicazione,con le classi cicliche che la compongono, che non sono classi di comunicazione e che della singola classe dicomunicazione ergodica rappresentano una particolare partizione in sottoinsiemi


Nella precedente figura 13.4.1, la classe K2 e ergodica, mentre sono transitorie sia la classeK1 che la classe K3.

• Esercizio 13.4.2 Possono esistere classi transitorie con un solo elemento? Quale ne puo essere lastruttura?

E chiaro che se ad un certo istante una catena entra in una classe ergodica Ke, non potrapiu uscirne e da quell’istante la catena si muovera soltanto entro Ke. In particolare, se lacatena raggiunge uno stato assorbente, vi rimarra indefinitamente.D’altra parte, se ad un certo istante la catena entra, o si trova, in una classe transitoria Kt,essa potra uscirne, ma - una volta uscita - non potra piu rientrarvi: ove cio si verificasse,esisterebbe un cammino c che parte da uno stato Si ∈ Kt, passa per almeno uno statoSk 6∈ Kt e termina in uno stato Sj ∈ Kt.Se Si = Sj , e immediato che Sk e Sicomunicano e quindi dovrebbero ap-partenere alla stessa classe di comuni-cazione, se Si 6= Sj , essi comunicano inquanto elementi della stessa classe Kt,quindi esisterebbe un cammino entro laclasse che connette Sj a Si e, combinan-dolo con c, una comunicazione fra Sk eSi.

'

&

$

%u��7u��:

u�uJJJ] ��

uBBBBN

6

-

u

�

� !

u

?�

Kt

Si

Sj

Sk

c

figura 13.4.2

Proposizione 13.4.4 [Esistenza e accessibilita delle classi ergodiche] Ognicatena C possiede almeno una classe ergodica. Se uno stato Si di C non appartiene ad unaclasse ergodica, esiste almeno un cammino orientato con inizio in Si e che termina in unaclasse ergodica.

Prova Se C ha una sola classe di comunicazione, questa e necessariamente ergodica. Seha piu classi di comunicazione e una di esse, Ki1 , e transitoria, esiste un cammino orientatocon origine in Ki1 che entra in una diversa classe Ki2 . Se questa non e ergodica, da Ki2il cammino puo proseguire in una classe Ki3 diversa Ki2 . Se anche questa non e ergodica,si prosegue il cammino attraverso una classe Ki4 diversa da Ki3 e cosı via. Poiche leclassi di comunicazione sono in numero finito, il cammino dovra entrare finalmente in unaclasse ergodica oppure in qualche momento visitera nuovamente una delle classi transitoriegia incontrate. Questa seconda alternativa implica che esista una comunicazione fra statiappartenenti a classi di comunicazione distinte (fra i quali per definizione non puo esisterecomunicazione): una contraddizione. Quindi C ha almeno una classe ergodica.La prova della seconda affermazione dell’enunciato e basata sul medesimo ragionamentosvolto per la prima. Dalla classe transitoria contenente Si esiste un cammino che porta daSi in una classe diversa da quella di Si, e se questa non e ergodica, si puo proseguirlo inun’altra classe diversa dalla seconda etc. La mancata visitazione di almeno uno stato inuna classe ergodica porterebbe ancora una volta a ritornare su una delle classi transitoriegia incontrate, e quindi alla comunicazione fra due stati appartenenti a classi distinte.

Proposizione 13.4.5 [Appartenenza asintotica alle classi ergodiche] Per t→+∞ e unitaria la probabilita che lo stato di una catena di Markov C appartenga a unaclasse ergodica.

13.4. CLASSIFICAZIONE DEGLI STATI E CLASSI DI COMUNICAZIONE 469

Prova Se lo stato iniziale appartiene a una classe ergodica, non c’e nulla da provare,dato che con probabilita 1 la catena visitera solo gli stati della classe.

Si e dimostrato nella proposizione precedente che se lo stato iniziale Si appartiene a unaclasse transitoria, esiste almeno un cammino che porta da Si in una classe ergodica. Seindichiamo con µi il numero minimo di passi richiesto per entrare da Si in una classeergodica e con pi la probabilita che la catena non raggiunga nessuna classe ergodica in µipassi, si ha pi < 1.

Sia

µ := maxi:Si in classi transitorie

{µi}, p := maxi:Si in classi transitorie

{pi} < 1

Partendo da qualsiasi stato in una classe transitoria, dopo µ passi la probabilita che lacatena non sia entrata in una classe ergodica e minore o eguale a p. Se lo stato della catenaal µ-esimo passo e ancora in una classe transitoria, la probabilita di non raggiungere classiergodiche nei successivi µ passi e ancora non superiore a p: quindi la probabilita di nonentrare in classi ergodiche nei primi 2µ passi e non superiore a p2. Induttivamente si haallora che la probabilita di non entrare in una classe ergodica nei primi kµ passi e nonsuperiore a pk, ovvero la probabilita di entrare in una classe ergodica nei primi kµ passi ealmeno 1− pk. Tale probabilita tende a 1 quando k →∞.

Ordiniamo ora gli stati di una catena di Markov C secondo il seguente criterio:

a) gli elementi di una classe di comunicazione ricevono indici consecutivi;

b) [livello zero] le classi ergodiche precedono tutte le classi transitorie;

c) fra le classi transitorie, vengono elencate

[primo livello] per prime quelle per cui ogni transizione verso le classi ergodichesi realizza direttamente (i.e. senza passare attraverso altre classi transitorie)

[secondo livello] poi le classi transitorie per cui il numero massimo di classitransitorie (inclusa la classe di partenza) incontrate per raggiungere le classiergodiche e 2;

[terzo livello] poi le classi transitorie per cui il numero massimo di classitransitorie (inclusa la classe di partenza) incontrate per raggiungere le classiergodiche e 3; etc.

Si noti che da nessuna classe del livello i-esimo si puo accedere ad altre classi delmedesimo livello o dei livelli superiori: altrimenti esisterebbe un percorso dal livelloi-esimo che raggiunge le classi ergodiche incontrando un numero di classi transitoriesuperiore a i.

La figura seguente illustra il criterio di precedenza fra le classi.


figura 13.4.3

� �K1

� �K2

� �K3

� �K4

� �K5

� �K6

� �K7

� �K8- - -

-

-

��

��

��1

PPPPPPPPPPPq

QQQQQQs

��

��

��1

PPPPPPPPPPq

@@@ �

��

La matrice di transizione P , una volta ordinati gli stati e le classi di comunicazione secondola procedura indicata, assume forma triangolare a blocchi. Nel caso specifico dell’esempiodi figura 13.4.3, indicando con il nome delle classi i blocchi diagonali (i cui elementi sonole probabilita di transizione entro le classi) e con il simbolo “+” i blocchi fuori diagonalein cui figurano alcuni elementi positivi, si perviene ad una matrice di transizione con laseguente struttura a blocchi (i primi due blocchi diagonali si riferiscono alle transizionientro le due classi ergodiche):

P =

K1 | O0 K2 |− − − − − − − − −+ 0 | K3

0 + | 0 K4 O+ + | 0 + K5

0 0 | + + + K6

0 0 | 0 0 0 + K7

0 0 | 0 0 0 + + K8

Si noti che i blocchi diagonali

- se di dimensione 1×1 si riferiscono ad una classe di comunicazione ergodica con un solostato (assorbente), e in tal caso sono unitari, oppure a una classe di comunicazionetransitoria con un solo stato, e in tal caso possono assumere qualsiasi valore nonnegativo e minore di 1;

- se si riferiscono a classi di comunicazione con almeno due stati, sono irriducibili estocastici o substocastici6 a seconda che la classe sia ergodica o transitoria. L’irriduci-bilita segue dal fatto che entro una classe di comunicazione e positiva la probabilitadi transitare da qualsiasi suo stato Si a qualsiasi suo stato Sj in un congruo numerodi passi; quindi, scelta una posizione (i, j) nel blocco diagonale, esiste una opportunapotenza del blocco in cui l’elemento in posizione (i, j) e positivo.

Lo studio di una catena C priva di classi transitorie, e quindi costituita soltanto da classiergodiche, e gia stato affrontato quando si sono discusse le catene irriducibili e in parti-colare quelle regolari. Infatti, se tutte le classi sono ergodiche, la matrice di transizione,

6una matrice quadrata nonnegativa e (propriamente) substocastica se la somma degli elementi di cia-scuna delle sue righe e inferiore a 1

13.5. CATENE CON CLASSI TRANSITORIE 471

a meno di una rinumerazione degli stati (i.e. di una trasformazione di cogredienza) hastruttura diagonale a blocchi

P =

P1

P2. . .

Ph

Siamo sostanzialmente in presenza di h catene irriducibili (o ergodiche) giustapposte e noninteragenti, con matrici di transizione P1, P2, . . . , Ph irriducibili.Se, ad esempio, lo stato iniziale appartiene alla prima classe (o se la distribuzione diprobabilita iniziale e concentrata solo sulla prima classe), le altre classi non saranno maivisitate e lo studio di C si riduce a quello della catena piu piccola, caratterizzata da P1.

• Esercizio 13.4.3 Si discuta il comportamento della catena C costituita da h > 1 classi ergodichee nessuna transitoria, quando la distribuzione di probabilita iniziale interessa stati appartenenti aclassi diverse e quindi assume la forma xT (0) = [ xT1 xT2 · · · xTh ], con xTi =

[π

(i)1 . . . π

(i)νi

]e∑

i,jπ

(i)j = 1.

13.5 Catene con classi transitorie

Quando siano presenti in una catena C una o piu classi transitorie, la sua matrice di tran-sizione, rispetto all’ordinamento degli stati discusso nel precedente paragrafo, ha strutturaa blocchi

P =[E 0R Q

](13.18)

Il blocco E, di dimensione r × r, si riferisce alla dinamica nelle classi ergodiche, checomprendono complessivamente r stati, ed e una matrice stocastica. Il blocco Q, didimensione (n− r)× (n− r) e una matrice substocastica7, poiche alcune sue righe (quellein corrispondenza alle quali non sono nulle le righe di R) hanno somma minore di 1.Piu precisamente, ogni blocco diagonale irriducibile della forma normale di Q ha sommedi riga non superiori ad 1 e almeno una riga a somma minore di 1, altrimenti il bloccoirriducibile farebbe riferimento ad una classe ergodica. Percio gli autovalori di ciascunblocco diagonale nella forma normale di Q hanno modulo minore di 1 e Qt converge a zeroal crescere di t.Nella potenza t-esima di P

P t =[Et 0? Qt

]l’elemento q(t)i,j di Qt da la probabilita che la catena, partendo dallo stato iniziale Si in unadelle classi transitorie, si trovi dopo t passi nello stato Sj delle classi transitorie. Il fattoche q(t)i,j converga a zero al crescere di t corrisponde alla proprieta , gia evidenziata, chequalunque sia lo stato iniziale Si di una classe transitoria, la probabilita che la catena C sitrovi all’istante t in qualche classe ergodica tende a 1 al divergere di t e quindi tende a zero

7gli elementi della matrice Q e delle sue potenze prendono gli indici nell’insieme {r + 1, r + 2, . . . , n} ,

i.e. fra gli indici degli stati delle classi transitorie. Quindi, se i > r e j > r, per ogni k ≥ 0 si ha p(k)ij = q

(k)ij .


la probabilita che la catena si trovi in una classe transitoria. Applicando il lemma 10.5.6sulla serie di C.Neumann, si conclude che la serie I +Q+Q2 + . . . converge all’inversa diI −Q, e tale inversa e una matrice positiva.

Definizione 13.5.1 [Matrice fondamentale delle classi transitorie] Se la catenaC ha classi transitorie e (13.18) ne e la matrice di transizione, la matrice fondamentaledegli stati transitori e la matrice positiva

L := (In−r −Q)−1 = In−r +Q+Q2 + . . . (13.19)

Introduciamo, per ogni coppia di stati Si e Sj nelle classi transitorie, la variabile casualevij che fornisce il numero di volte che la catena visita lo stato Sj partendo dallo stato Si.Se s(t)ij , t = 0, 1, 2, . . . denota la variabile casuale

s(t)ij =

{1 se, assumendo S(0) = Si, la catena all’istante t visita Sj0 se, assumendo S(0) = Si, la catena all’istante t non visita Sj ,

si ha vij =∑∞t=0 s

(t)ij , e la media della variabile vij e data da

E(vij) := E

( ∞∑t=0

s(t)ij

)=∞∑t=0

E(s(t)ij )

=∞∑t=0

[1 · p(t)ij + 0 · (1− p(t)

ij )] =∞∑t=0

p(t)ij =

∞∑t=0

q(t)ij (13.20)

dove si sono mantenti per gli elementi del blocco Q gli indici di righe e colonne ereditatida P , ovvero indici che variano sull’insieme {r + 1, r + 2, . . . n}. Abbiamo cosı provato laprima parte della seguente

Proposizione 13.5.2 L’elemento (i, j) della matrice fondamentale L = (I−Q)−1 fornisceil numero medio delle volte che la catena C visita lo stato transitorio Sj , a partire dallostato transitorio S(0) = Si.La componente i-esima del vettore colonna L1 rappresenta il numero medio complessivodi passi che la catena compie, a partire dallo stato transitorio i-esimo e rimanendo nelleclassi transitorie, prima di entrare in una delle classi ergodiche.

Prova (completamento) Per la seconda parte basta osservare che la prima componentedel vettore L1 e somma delle componenti della prima riga di L, quindi somma

- del numero medio di volte che la catena visita il primo stato transitorio- piu il numero medio di volte che visita il secondo- . . . . . . . . .- piu il numero medio di volte che visita l’(n− r)-esimo,

quando lo stato iniziale e il primo degli stati transitori. Analogo discorso vale per le altrecomponenti di L1.

Mentre la matrice fondamentale L da informazioni sul comportamento della catena finchelo stato rimane nelle classi transitorie, la matrice LR fornisce informazione circa le modalitadi passaggio della catena da classi transitorie a classi ergodiche. Si ha infatti


Proposizione 13.5.3 Indichiamo con bik la probabilita che la catena, partendo dallostato transitorio Si, entri in una delle classi ergodiche visitando per primo lo stato Sk. Siha allora

bik = [LR]ik (13.21)

Prova Se l’entrata della catena in una classe ergodica avviene visitando come primo statoergodico lo stato Sk, il passaggio da Si a Sk puo richiedere un passo, con probabilita pik,oppure piu passi, con la preliminare visitazione di alcuni stati transitori. Questa secondaeventualita comporta il passaggio al primo passo da Si verso uno qualsiasi degli statitransitori Sj , con probabilita pij , e il successivo cammino da Sj verso Sk, in un congruonumero di passi e con probabilita bjk. Quindi le probabilita bik sono date in forma implicitadalle relazioni

bik = pik +∑

j:Sj nelle classi transitorie

pijbjk (13.22)

con pik elemento di R e pij elemento di Q. In termini matriciali, posto B = [bik], da(13.22) si ricava B = R+QB e quindi

B = (I −Q)−1R = LR

• Esercizio 13.5.1 Si verifichi che nella matrice B e unitaria la somma degli elementi di ciascuna suariga.

] Suggerimento: si utilizzi l’identita R1r +Q1n−r = 1n−r.

Esempio 10.5.4 [Linea di produzione] Il processo di manifattura di un prodotto consiste di trestadi successivi, che chiameremo S5, S4, S3.

Una unita di prodotto entra inizialmente nello stadio di lavorazione S5 , alla fine della lavorazioneviene ispezionata e

– con probabilita p passa allo stadio di lavorazione successivo S4,

– con probabilita s viene scartata e non piu recuperata,

– con probabilita r viene riciclata nello stadio S5.

Analoga procedura, e con le stesse probabilita, vale per le unita di prodotto che sono entrate nellostadio S4. Per quelle entrate nello stadio S3, conclusa la lavorazione

– con probabilita p escono dalla linea di produzione e passano alla commercializzazione S2,

– con probabilita s vengono scartate e non piu recuperate,

– con probabilita r vengono riciclata nello stadio S3.

Se denotiamo con S1 lo stadio (unico) in cui entra l’unita di prodotto scartata, il processo puo essereschematizzato dalla seguente catena di Markov


u -��

p

s

��?

r

S5

u -

6

p

s

��?

r

S4

u -@@@

@@@

@@@I

p

s

��?

r

S3

u��?

1

S2

u��6

1

S1

figura 13.5.1

e ha matrice di transizione

P =

1 0 | 0 00 1 | 0 0 0− − | − − −s p | r 0 0s 0 | p r 0s 0 | 0 p r

=

[E 0R Q

]

La catena ha due stati assorbenti, S1 e S2, e tre classi transitorie, ciascuna comprendente un solostato: {S3}, {S4}, {S5}.La matrice fondamentale e data da L = (I3 − Q)−1 = (I3 − rI3 − pN)−1, dove con N si e indicatala matrice nilpotente

N =

[0 0 01 0 00 1 0

].

Si ha cosı

L = ((1− r)I3 − pN)−1 =1

1− r

(I3 −

p

1− rN)−1

=1

1− r

(I3 +

p

1− rN + (p

1− r )2N2)

=

1

1− r 0 0

p

(1− r)21

1− r 0

p2

(1− r)3p

(1− r)21

1− r

L13 =

1

1− r 0 0

p

(1− r)21

1− r 0

p2

(1− r)3p

(1− r)21

1− r

1

1

1

=

1

1− rp+ (1− r)

(1− r)2p2 + p(1− r) + (1− r)2

(1− r)3

B = LR =

s

1− rp

1− rsp+ s(1− r)

(1− r)2p2

(1− r)2sp2 + sp(1− r) + s(1− r)2

(1− r)3p3

(1− r)3

=

1− p

1− rp

1− r1− p2

(1− r)2p2

(1− r)2

1− p3

(1− r)3p3

(1− r)3


L’ultima riga della matrice fondamentale L fornisce i valori medi del numero di volte che una unitadi prodotto rimane nei tre stadi di lavorazione: 1/1−r nello stadio iniziale S5, p/(1−r)2 nello stadioS4, p2/(1− r)3 nell’ultimo stadio di lavorazione S3.

E possibile, in questo caso piuttosto semplice, reinterpretare il risultato: rk e la probabilita che unaunita di prodotto che entra in lavorazione nello stadio S5 vi venga riciclata per (almeno!) k volte;rk − rk+1 e la probabilita che vi venga riciclata per esattamente k volte, per cui il numero medio divisite nello stadio S5 e dato da

1(1− r) + 2(r − r2) + 3(r2 − r3) + . . . = 1 + (2r − r) + (3r2 − 2r2) + . . . = 1 + r + r2 + . . . =1

1− r

Per ottenere il numero medio di visite compiute nello stadio S4 da una unita che entra nello stadioiniziale S5, dobbiamo anzitutto considerare la probabilita che in qualche momento l’unita passi daS5 a S4; questa e data dalla somma delle probabilita che il passaggio avvenga in un passo, in duepassi (al primo passo un riciclo e al secondo il passaggio), in tre passi (nei primi due passi un riciclo,al terzo il passaggio) etc., ovvero da

p+ rp+ r2p+ r3p+ . . . = p/(1− r).

Si noti che tale quantita rappresenta anche, nella matrice B, la probabilita che, quando il processosi trova nello stadio finale di lavorazione S3, lo stato assorbente in cui esso finalmente entra sia lostato S2, i.e. quello di commercializzazione.

A questo punto, la probabilita che un’unita di prodotto che entra in lavorazione nello stadio S5 vengariciclata nello stadio S4 per esattamente k volte e data dal prodotto della probabilita di passaggioda S5 in S4 per la probabilita che, una volta giunta in S4, l’unita vi venga riciclata esattamente k

volte, ovvero dap

1− r (rk − rk+1). Ragionando come in precedenza, si ottiene il penultimo elemento

dell’ultima riga di L.

Infine, e facile convincersi che la probabilita che in qualche momento la catena passi in S3, partendoinizialmente da S5 e il quadrato di p/(1−r), da cui si ottiene facilmente il primo elemento dell’ultimariga di L.

• Esempio 13.5.2 [Si gioca] Vogliamo modellare una situazione in cui due giocatori A e B hannoinizialmente a disposizione a e b unita di conto (monete, fiches, etc.), rispettivamente. Duranteciascuna “mano” di gioco, il giocatore A ha probabilita p di vincere, p ∈ (0, 1), il giocatore B haprobabilita q = 1 − p. Il giocatore che vince la mano guadagna da quello che perde una unita diconto. Il gioco ha termine quando uno giocatore ha vinto tutte le a+ b = c unita di conto disponibili(e quindi l’altro rimane senza piu nulla da giocare).

Il gioco puo essere visto come una catena di Markov, in cui gli stati corrispondono al numero di unitadi conto disponibili al giocatore A. Il grafo che rappresenta la dinamica del processo in un passo eil seguente (il pedice dello stato rappresenta qui la somma disponibile al giocatore A):

u��?1S0

q� u� �-p

q�

S1

u� �-p

q�

S2 S3

u -�� uSc−1

� ��

-

. . .

. . . -p uSc

��1 ?

figura 13.5.2

La catena ha due stati assorbenti S0 e Sc e un’unica classe transitoria {S1, S2, . . . , Sc−1}. Conviene,prima di scrivere la matrice di transizione, rinumerare gli stati, riservando gli indici piu bassi aglistati assorbenti. Si ha allora


u��?1S1

q� u� �-p

q�

S3

u� �-p

q�

S4 S5

u -�� uSc+1

� ��

-

. . .

. . . -p uS2

��1 ?

figura 13.5.3

e la corrispondente matrice di transizione e

P =

1 0 | O0 1 |− − − − − − − −q 0 | 0 p 00 0 | q 0 p 00 0 | 0 q 0 p

.... . .

. . .. . .

0 0 | 0 0 0 . . . 0 p0 p | 0 0 0 . . . q 0

=

[E 0R Q

]

Come sappiamo, la matrice B = (I − Q)−1R fornisce le probabilita di entrare nelle due classiergodiche partendo da uno qualsiasi dei c − 1 stati della classe transitoria: la prima colonna di Bcontiene le probabilita che il giocatore A perda (i.e. entri nella prima classe ergodica) quando parteda una disponibilita iniziale di 1, 2, . . . , c − 1 unita di conto, la seconda colonna di B le probabilitache il giocatore A vinca. Possiamo valutare direttamente le probabilita di vittoria di A (i.e. laseconda colonna di B) con una procedura ricorsiva che sfrutta la struttura particolare di Q. Seξ1, ξ2, . . . , ξc−1 sono le componenti incognite della seconda colonna di B, per determinarle dobbiamorisolvere l’equazione

(I −Q)

ξ1ξ2...

ξc−1

=

00...p

(13.23)

ovvero il sistema lineare non omogeneo di c− 1 equazioni in c− 1 incogniteξ1 − pξ2 = 0

−qξ1 + ξ2 − pξ3 = 0−qξ2 + ξ3 − pξ4 = 0. . .−qξc−3 + ξc−2 − pξc−1 = 0−qξc−2 + ξc−1 = p

(13.24)

Se introduciamo le grandezze ausilarie ξ0 e ξc e le vincoliamo a valere rispettivamente 0 e 1, (13.24)assume struttura omogenea e uniforme in tutte le equazioni

−qξ0 + ξ1 − pξ2 = 0−qξ1 + ξ2 − pξ3 = 0−qξ2 + ξ3 − pξ4 = 0. . .−qξc−3 + ξc−2 − pξc−1 = 0−qξc−2 + ξc−1 − pξc = 0

e le componenti ξi sono legate dalla formula ricorsiva

pξi+1 = ξi − qξi−1 (13.25)

Posto x(i) =

[ξiξi−1

], da (13.25) si ricavano le equazioni di un sistema lineare osservabile e in


evoluzione libera

x(i+ 1) =

[1/p −q/p1 0

]x(i) = Fx(i)

ξi = [ 1 0 ] x(i) = Hx(i)

con autovalori 1 e q/p, del quale si hanno informazioni parziali sullo stato iniziale e sullo stato finale

x(1) =

[ξ10

], x(c) =

[1

ξc−1

].

L’uscita e combinazione lineare dei modi:

– se q 6= p, i modi sono {1i : i ∈ N} e {(q/p)i : i ∈ N} e abbiamo

ξi = k1(q/p)i + k2.

Imponendo le condizioni 0 = ξ0 = k1 + k2 e 1 = ξc = k1(q/p)c + k2, si determinano le costanti

k1 =1

(q/p)c − 1, k2 = −k1

Quindi la probabilita che il giocatore A vinca, partendo da una situazione iniziale in cui A e Bpossiedono rispettivamente i e c− i fiches, e data da

ξi =1

(q/p)c − 1(q/p)i − 1

(q/p)c − 1=

(q/p)i − 1

(q/p)c − 1(13.26)

– se q = p = 1/2 (quindi se il gioco e equo), l’autovalore 1 ha molteplicita 2 e i modi del sistemasono le successioni {1i : i ∈ N} e {

(i1

): i ∈ N}. In questo caso abbiamo

ξi = k1

(i

1

)+ k2

e imponendo le condizioni 0 = ξ0 = k10 + k2 e 1 = ξc = k1

(c1

)+ k2, si determinano le costanti

k1 =1

c, k2 = 0.

In questo caso, la probabilita che il giocatore A vinca e data da

ξi =1

c

(i

1

)=i

c,

come si ottiene anche da (13.26) passando al limite quando q/c tende a 1.

CATENE DI MARKOV - dei.unipd.itfornasini/10Ter_Catene di Markov.pdf · In alternativa a descrivere...

Documents

Transcript of CATENE DI MARKOV - dei.unipd.itfornasini/10Ter_Catene di Markov.pdf · In alternativa a descrivere...