61
CATENE DI MARKOV F. Fagnola, E. Sasso February 17, 2006 Contents 1 Definizione e prime propriet` a 2 2 Classificazione degli stati 9 3 Leggi invarianti e teoremi limite. 21 4 Assorbimento in classi ricorrenti 31 5 Criteri di transienza o ricorrenza 41 6 Convergenza verso la legge invariante 46 7 Algoritmo di Metropolis 48 8 Catene di Markov a tempo continuo 51 9 Applicazioni: le catene di Markov in genetica 57 10 Applicazioni: lotto economico d’acquisto 59 1

catene di markov

Embed Size (px)

Citation preview

Page 1: catene di markov

CATENE DI MARKOV

F. Fagnola, E. Sasso

February 17, 2006

Contents

1 Definizione e prime proprieta 2

2 Classificazione degli stati 9

3 Leggi invarianti e teoremi limite. 21

4 Assorbimento in classi ricorrenti 31

5 Criteri di transienza o ricorrenza 41

6 Convergenza verso la legge invariante 46

7 Algoritmo di Metropolis 48

8 Catene di Markov a tempo continuo 51

9 Applicazioni: le catene di Markov in genetica 57

10 Applicazioni: lotto economico d’acquisto 59

1

Page 2: catene di markov

1 Definizione e prime proprieta

Sia (Ω,F , P) uno spazio probabilizzato e I un insieme finito o numerabile chesara sempre considerato. Si consideri una successione di variabili aleatorie X =(Xn)n≥0 su (Ω,F , P) a valori in I.

Definizione 1.1 La successione X di variabili aleatorie (Xn)n≥0 su (Ω,F , P)a valori in I e una catena di Markov con insieme degli stati I se, per ogniintero n, per ogni i0, . . . , in, j ∈ I, con PXn = in, . . . , X0 = i0 > 0 si ha

P Xn+1 = j |Xn = in, . . . , X0 = i0 = P Xn+1 = j |Xn = i (1)

La catena di Markov si dice omogenea se i due membri di (1) sono indipendentida n.

I numeri reali positivi pij dati da

pij =

PXn+1 = j |Xn = i se PXn = i 6= 0,1 se PXn = i = 0 e i = j,0 se PXn = i = 0 e i 6= j,

si chiamano probabilita di transizione della catena di Markov omogenea X.La catena di Markov X si chiama omogenea poiche le probabilita di transizione(1) sono indipendenti da n. Nel seguito considereremo sempre catene di Markovomogenee percio ometteremo spesso l’aggettivo. Inoltre, quando scriveremouna probabilita condizionata, supporremo sempre, implicitamente, che l’eventocondizionante sia non trascurabile.

La famiglia di numeri reali positivi (pij)i,j∈I si chiama matrice di tran-sizione della catena di Markov X ed ha le proprieta seguenti:

(1) pij ≥ 0 per ogni i, j ∈ I,

(2)∑

j∈I pij = 1 per ogni i ∈ I.

Definizione 1.2 Una matrice p = (pij)i,j∈I con le proprieta (1) e (2) si dicestocastica. Se la matrice trasposta e anch’essa una matrice stocastica allora sidice che p e bistocastica.

La matrice di transizione p = (pij)i,j∈I e la legge µ di X0, detta anche leggeiniziale, determinano la legge congiunta delle variabili aleatorie (Xn)n≥0 cioepermettono, come vedremo, di calcolare tutte le probabilita di eventi determi-nati dalle variabili aleatorie (Xn)n≥0.

ESEMPIO 1.1 La rovina del giocatore. Sia N ≥ 2 un numero naturale fissatoe p, q ∈]0, 1[ due numeri reali tali che p + q = 1. Due giocatori A e B concapitali iniziali rispettivi di a monete e b, con N = a + b, monete giocano uncerto numero di partite in ciascuna delle quali A vince una moneta (che gli vienepagata da B) con probabilita p e la perde (cioe la paga a B) con probabilitaq. Il gioco si puo modellizzare con una catena di Markov (Xn)n≥0 nella quale

2

Page 3: catene di markov

la variabile aleatoria Xn rappresenta il capitale del giocatore A al tempo n. Lacatena di Markov ha insieme degli stati 0, 1, . . . , N e matrice di transizione

1 0 0 0 . . . 0 0 0q 0 p 0 . . . 0 0 00 q 0 p . . . 0 0 00 . . . . . . . . . . . . . . . . . . 00 0 0 0 . . . 0 p 00 0 0 0 . . . q 0 p0 0 0 0 . . . 0 0 1

.

Il gioco termina non appena uno dei due giocatori resta senza monete. Unproblema naturale e il calcolo della probabilita che vinca A oppure B.

ESEMPIO 1.2 Estrazioni da un mazzo di carte. Si consideri l’esperimentoaleatorio consistente nelle estrazioni (senza rimpiazzo) di carte da un mazzo.Le carte vengono estratte ad una ad una e, quando sono state tutte estratte, sirimettono insieme e si ricomincia. Indicando con Xn la carta ottenuta nell’n-esima estrazione si trova una successione X = (Xn)n≥0 di variabili aleatorie.E facile verificare che X non e una catena di Markov poiche la probabilta diottenere come risultato dell’(n+1)-esima estrazione una certa carta dipende dairisultati di tutte le precedenti estrazioni e non solamente dall’(n− 1)-esima.

PX5 = A♠ |X4 = A♦, X3 = A♠ = 0 6= PX5 = A♠ |X4 = A♦ =151

.

ESEMPIO 1.3 Successione di variabili indipendenti. Sia (Xn)n≥0 una succes-sione di variabili aleatorie su uno spazio probabilizzato (Ω,F , P) a valori interiindipendenti ed equidistribuite e sia (an)n≥0 la successione di numeri reali pos-itivi data da

an = PXk = n, k ∈ N.

La successione (Xn)n≥0 e una catena di Markov con insieme degli stati N ematrice di transizione (pij)i,j∈I data da a0 a1 a2 . . .

a0 a1 a2 . . .. . . . . . . . . . . .

.

ESEMPIO 1.4 Passeggiata casuale. Con le notazioni dell’esempio precedente,si consideri la successione di variabili aleatorie (Yn)n≥0 definita da

Yn =n∑

k=0

Xk.

3

Page 4: catene di markov

La successione (Yn)n≥0 e una catena di Markov con insieme degli stati N ematrice di transizione (pij)i,j∈I data da

a0 a1 a2 a3 . . .0 a0 a1 a2 . . .0 0 a0 a1 . . .

. . . . . . . . . . . . . . .

.

ESEMPIO 1.5 Sia (Yk)k≥1 una successione di variabili aleatorie indipendentie equidistribuite a valori in N∗ e sia Sk =

∑kj=0 Yj . Poniamo

N0 := 0, Nn =∑k≥1

1Sk≤n,∀n ≥ 1.

Le condizioni seguenti sono equivalenti

i) (Nn)n≥1 e una catena di Markov omogenea;

ii) le variabili aleatorie Yk hanno legge geometrica.

Infatti, se assumiamo vera i), per ogni n ≥ 1 si ha che

PY1 = n + 1PY1 = n

=PNn+1 = 1, Nn = 0PNn = 1, Nn−1 = 0

=PNn+1 = 1|Nn = 0PNn = 1|Nn−1 = 0

PNn = 0PNn−1 = 0

=PY1 > n

PY1 > n− 1.

Poniamo p = PY1 = 1, allora

PY1 = 2 = PY1 = 1PY1 > 1= PY1 = 1(1− PY1 = 1) = p(1− p).

A questo punto si puo concludere per induzione che PY1 = n + 1 = p(1− p)n.Infatti, se assumiamo per ipotesi che PY1 = k = p(1− p)k−1, abbiamo che

PY1 = k + 1 = PY1 = k PY1 > kPY1 > k − 1

= p(1− p)k−1 (1− PY1 ≤ k)1− PY1 ≤ k − 1)

= p(1− p)k−11−

∑kj=1 p(1− p)j−1

1−∑k−1

j=1 p(1− p)j−1

= p(1− p)k−1

∑k≥k+1 p(1− p)j−1∑

j≥k p(1− p)j−1

= p(1− p)k.

4

Page 5: catene di markov

Questo dimostra che i) implica ii). L’implicazione opposta segue direttamentese si interpretano le Yk come il tempo del k−esimo successo in uno schema diBernoulli. Allora Nn conta il numero di successi in n prove e quindi (Nn)n≥1

soddisfa la propriata markoviana.

ESEMPIO 1.6 Coda casuale. Con le notazioni degli Esempi 1.3 e 1.4 si con-sideri la successione di variabili aleatorie (Yn)n≥0 definita da

Y0 = X0

Yn+1 = (Yn − 1)+ + Xn+1

dove, per ogni numero reale x,

x+ = maxx, 0.

La successione (Yn)n≥0 e una catena di Markov con insieme degli stati N ematrice di transizione (pij)i,j∈I data da

a0 a1 a2 a3 a4 . . .a0 a1 a2 a3 a4 . . .0 a0 a1 a2 a3 . . .0 0 a0 a1 a2 . . .

. . . . . . . . . . . . . . . . . .

.

Questa catena di Markov descrive la lunghezza di una coda ad uno sportellodove, in ogni unita di tempo, viene servito un cliente e ne arriva un numeroaleatorio Y , inoltre i numeri di clienti che arrivano in unita di tempo distintesono indipendenti.

Mostreremo ora come si possono esprimere le probabilita di eventi relativiad una catena di markov (Xn)n≥0 attraverso la matrice di transizione. Iniziamocol dimostrare il seguente

Lemma 1.3 Per ogni coppia di numeri naturali n, m con m ≥ 1, e ogni coppiai, j di elementi di I si ha

P(Xn+m = j | Xn = i

)= p

(m)ij (2)

dove p(m) denota la potenza m–esima della matrice p.

Dimostrazione. Grazie alla definizione di probabilita condizionata e allaformula della probabilita totale il membro sinistro di (2) si puo scrivere nellaforma ∑

k∈I

P Xn+m = j, Xn+m−1 = k, Xn = i /P Xn = i

5

Page 6: catene di markov

Per ogni k ∈ I si ha quindi, grazie alla proprieta di Markov (1),

PXn+m = j, Xn+m−1 = k, , Xn = i= PXn+m = j | Xn+m−1 = k, Xn = i · P(Xn+m−1 = k, Xn = i= pkj · P(Xn+m−1 = k, Xn = i

e percio

PXn+m = j |Xn = i =∑k∈I

pkj · PXn+m−1 = k | Xn = i

Ragionando per induzione si vede quindi che il membro sinistro della (2) si puoesprimere nel modo seguente∑

k∈I

pkjPXn+m−1 = k | Xn = i

=∑

k1,k2∈I

pk1jpk2k1PXn+m−2 = k2 | Xn = i

=∑k2∈I

(∑k1∈I

pk2k1pk1j

)PXn+m−2 = k2 | Xn = i

=∑k2∈I

p(2)k2jPXn+m−2 = k2 | Xn = i

= . . . =∑k∈I

p(m−1)kj PXn+1 = k | Xn = i.

La conclusione segue quindi dalla proprieta di Markov (1).

Sia µ la legge della variabile aleatoria X0.

Proposizione 1.4 Per ogni n-pla (jk)0≤k≤n di stati ed ogni n-pla (mk)0≤k≤n

(m0 < m1 < . . . < mn) di tempi si ha

P (∩0≤k≤nXmk= jk) = p

(mn−mn−1)jn−1jn

p(mn−1−mn−2)jn−2jn−1

. . . p(m1)j0j1

µj0.

Dunque la legge iniziale µ e la matrice di transizione (pij)i,j∈I determinano lalegge congiunta delle variabili aleatorie (Xn)n≥0.

Dimostrazione. Applicando piu volte la proprieta di Markov (1) ed ilLemma 1.3 si ha

P(∩0≤k≤n Xmk

= jk)

= P(Xmn = jn | ∩0≤k≤n−1 Xmk

= jk)

·P(∩0≤k≤n−1 Xmk

= jk)

= p(mn−mn−1)jn−1jn

P(∩0≤k≤n−1 Xmk

= jk)

= . . . = p(mn−mn−1)jn−1jn

p(mn−1−mn−2)jn−2jn−1

. . . p(m1)j0j1

PX0 = j0

= p(mn−mn−1)jn−1jn

p(mn−1−mn−2)jn−2jn−1

. . . p(m1)j0j1

µj0.

6

Page 7: catene di markov

La proposizione e cosı dimostrata.

Osservazione. Si puo verificare facilmente che dalla proprieta di Markov (1)segue che, per ogni evento A, dipendente dalle variabili aleatorie X0, . . . , Xn−1

si haP Xn+1 = j | Xn = in ∩A = P Xn+1 = j |Xn = i . (3)

Per esempio, se In−1, . . . I0 sono sottoinsiemi di I potremmo prendere

A = Xn−1 ∈ In−1 ∩ · · · X0 ∈ I0.

Si potrebbe dimostrare pure che, per ogni legge µ su I e ogni matrice sto-castica P = (pij)i,j∈I esiste una catena di Markov con matrice stocastica P evariabile aleatoria X0 con legge µ.

A volte puo essere utile rappresentare le catene di Markov (a stati finiti) conun grafo. I nodi rappresentano gli stati della catena di Markov, le frecce tra inodi rappresentano le probabilita di transizione. In particolare, se si etichettanole frecce fra i nodi con le probabilita di transizione da uno stato ad un altro, siavra che la somma delle ”frecce uscenti” da un nodo deve essere uguale a 1. Inquesto modo ad ogni matrice stocastica n × n corrisponde in maniera univocaun grafo a n nodi. Ad esempio, data la matrice P

P =

1/2 1/2 01/3 1/3 1/31/4 3/4 0

,

associata a una catena di Markov con spazio degli stati 0, 1, 2, si puo associareil corrispondente grafo orientato

?>=<89:;012

12

?>=<89:;1

13

JJ

13

OO

13 //?>=<89:;234

oo

14

^^=====

ESERCIZI

Es 1.1 Sia (Xn)n≥1 una successione di variabili aleatorie indipendenti a valoriin N∗ con legge geometrica di parametro p. Stabilire se la successione (Zn)n≥1

di variabili aleatorie a valori in N∗ cosı definita

Z0 = 1, Zn+1 = ZnXn+1

e una catena di Markov e calcolare la matrice di transizione.

7

Page 8: catene di markov

Es 1.2 Un punto si muove a caso sui vertici di un esagono regolare saltandoad ogni istante dal vertice in cui si trova in uno dei due adiacenti scelto a caso.Modellizzare il moto del punto con una catena di Markov e scriverne la matricedi transizione. Calcolare la probabilita che dopo due salti si trovi nello stessovertice.

Es 1.3 Uno sportello serve al massimo 1 cliente per unita di tempo. Il numerodi clienti che arrivano nell’n−esima unita di tempo e una variabile aleatoriaVn di legge B(2, 1/2). Supponendo che le Vn siano indipendenti e inoltre che iclienti che arrivando vedono gia 5 persone in coda se ne vadano immediatamente,modellizzare la situazione con una catena di Markov e scriverne la matrice ditransizione.

Es 1.4 Un modello preliminare sulle previsioni meteorologiche si basa sull’ipotesiche il tempo di domani sia influenzato dalla situazione odierna. Basandosi suquesta ipotesi e naturale utilizzare le catene di Markov. Per semplicita assum-iamo che ci siano solo due tipi di tempo ”sole” (stato 0) e ”pioggia” (stato 1).Una realistica matrice di transizione per il tempo di Roma potrebbe essere

P =(

0.5 0.50.1 0.9

).

Calcolare la probabilita che se oggi piove, domani e dopo ci sia il sole. Calcolarela probabilita che se oggi piove, dopo tre giorni ci sia una nuova giornata dipioggia.

Es 1.5 Una pedina si muove su un circuito ”circolare” a 4 vertici, numerati da1 a 4. La pedina si trova inizialmente nel vertice 1. Ad ogni passo un giocatorelancia un dado equilibrato a quattro facce: se la pedina si trova negli stati 1, 2o 3 avanza di una posizione in caso di risultato dispari e di due posizioni in casodi risultato pari; se la pedina si trova nel vertice 4, essa passa nel vertice 1, seil risultato del dado e 4, altrimenti resta in 4. Sia Xn la variabile aleatoria cheindica la posizione della pedina al tempo n−esimo, ossia dopo l’n−esimo lanciodel dado. Si individui la legge µ0 di X0. Qual e la probabilita che partendo da4 la catena si trovi in 1 dopo due passi? Qual e la probabilita che al terzo passosi trovi in 1? Qual e la posizione attesa dopo il secondo lancio del dado?

8

Page 9: catene di markov

2 Classificazione degli stati

Sia (Xn)n≥0 una catena di Markov su uno spazio probabilizzato (Ω,F , P) coninsieme degli stati I e matrice di transizione (pij)i,j∈I .

Definizione 2.1 Uno stato j e accessibile da uno stato i se esiste un interopositivo n tale che

p(n)ij > 0.

Due stati i, j comunicano, o sono comunicanti, se ciascuno dei due e acces-sibile dall’altro.

Osserviamo che, essendo

p(0)ij =

1 se i = j,0 se i 6= j,

secondo la definizione precedente, ogni stato comunica con se stesso.

Proposizione 2.2 Siano i, j, k tre elementi di I. Se k e accessibile da j e j, asua volta, e accessibile da i allora k e accessibile da i.

Dimostrazione. Dall’ipotesi segue che esistono due interi positivi m,ntali che

p(n)ij > 0, p

(m)jk > 0.

Si ha quindip(n+m)ik =

∑l∈I

p(n)il p

(m)lk ≥ p

(n)ij p

(m)jk > 0.

Cio dimostra che k e accessibile da i.

Grazie alla proposizione precedente e facile dimostrare che la proprieta “co-municare” induce una relazione di equivalenza tra stati; le corrispondenti classidi equivalenza sono dette classi di stati.

Definizione 2.3 Una classe di stati e un sottoinsieme J dello spazio deglistati I tale che, per ogni coppia i, j di elementi di J , gli stati i e j comunicanoe, per ogni coppia di stati i, j con i ∈ I − J , j ∈ J , i e j non comunicano.

Definizione 2.4 Una catena di Markov si dice irriducibile se la sola classedi stati non vuota e l’insieme I.

Definizione 2.5 Dato uno stato i tale che l’insiemen ≥ 1 | p(n)

ii > 0

sia non vuoto, si chiama periodo di i il massimo comune divisore dei numeriinteri n ≥ 1 appartenenti a tale insieme. Uno stato avente periodo n > 1 si diceperiodico di periodo n, diversamente se n = 1, lo stato i si dice aperiodico.

9

Page 10: catene di markov

Dunque uno stato i e periodico di periodo n se, partendo dallo stato i altempo 0, la catena di Markov non puo ritornare nello stato i a tempi m che nonsiano un multiplo intero di n.

Proposizione 2.6 Siano i e j due stati comunicanti. Allora il periodo di i euguale al periodo di j.

Dimostrazione. Bastera ovviamente dimostrare la proposizione nel casoin cui i 6= j. Denotiamo con d(i) e d(j) i periodi di i e j. Siano a e b due numeriinteri strettamente positivi tali che

p(b)ij > 0, p

(a)ji > 0.

Per ogni intero n tale che il numero reale p(n)ii sia strettamente positivo si hanno

allora le diseguaglianze seguenti

p(a+n+b)jj

∑k1,k2

p(a)jk1

p(n)k1k2

p(b)k2j ≥ p

(a)ji p

(n)ii p

(b)ij > 0

e, analogamente, si trovano le diseguaglianze

p(a+2n+b)jj ≥ p

(a)ji p

(2n)ii p

(b)ij ≥ p

(a)ji (p(n)

ii )2p(b)ij > 0.

Ne segue che i due numeri naturali

a + b + n, a + b + 2n

sono multipli di d(j), dunque anche la loro differenza n e un multiplo di d(j).Quindi il numero naturale d(j) e un divisore di tutti i numeri naturali n per iquali p

(n)ii sia strettamente positivo ovvero d(j) e un multiplo di d(i). In modo

analogo si puo dimostrare che d(i) e un multiplo di d(j), pertanto d(i) e d(j)coincidono.

ESEMPIO 2.1 Consideriamo la catena di Markov Rovina del giocatore dell’Esem-pio 1.1. Ciascuno degli stati 0 ed N forma una classe con un solo elemento poichep(n)0j = p

(n)Ni = 0 per ogni n ≥ 1 ed ogni i ∈ 0, 1, . . . , N − 1, j ∈ 1, 2, . . . , N.

Infatti non e possibile lasciare gli stati 0 e N una volta raggiunti. Gli stati1, 2, . . . , N − 1 formano un’altra classe perche comunicano. Infatti, per ognii, j ∈ 1, 2, . . . , N − 1 con i < j (risp. i > j) si ha

p(j−i)ij = pj−i > 0 (risp. p

(i−j)ij = qi−j > 0).

ESEMPIO 2.2 Consideriamo la catena di Markov dell’esempio Successione divariabili aleatorie indipendenti dell’Esempio 1.3. Si puo vedere, con un facilecalcolo, che la matrice di transizione P relativa verifica la condizione

p(n)ij = pij per ogni n ≥ 1 (4)

10

Page 11: catene di markov

per ogni coppia di stati i, j. Quindi uno stato k e accessibile da un qualunquealtro stato se e solo se il numero ak e strettamente positivo. Pertanto la con-dizione

ak > 0 per ogni k ≥ 0

e necessaria e sufficiente affinche la catena di Markov sia irriducibile. Utilizzandola formula (4) si puo vedere inoltre che, sotto questa condizione, tutti gli statisono aperiodici.

ESEMPIO 2.3 Consideriamo la catena di Markov dell’Esempio 1.4 e supponi-amo che i numeri (ak)k≥0 siano tutti strettamente positivi. E chiaro allora che,dati due stati i e j, lo stato j e accessibile dallo stato i se e solo se j ≥ i. Dunquele sole classi di stati, oltre alla classe vuota, sono le classi costituite da un solostato. Tutti gli stati sono evidentemente aperiodici.

ESEMPIO 2.4 Consideriamo la catena di Markov dell’Esempio 1.6 e supponi-amo che siano soddisfatte le condizioni seguenti

0 < a0 < 1, 0 < a0 + a1 < 1. (5)

Si puo dimostrare allora che tutti gli stati comunicano. Infatti, per ogni coppiadi stati i, j con j < i, ragionando come nell’esempio precedente, si trova ladiseguaglianza

p(i−j)ij ≥ pii+1pi+1i+2 . . . pj−2j−1pj−1j = (a0)i−j > 0,

che mostra che j e accessibile da i. Osserviamo poi che, grazie alla secondadelle diseguaglianze (2.2), esiste un intero ν ≥ 2 tale che il numero reale aν siastrettamente positivo. Quindi, per ogni stato i ed ogni numero intero n ≥ 1, glistati (i + n(ν − 1))n≥1 sono accessibili dallo stato i perche, procedendo comesopra, si trova la diseguaglianza

p(n)ii+n(ν−1) ≥ (aν)n > 0.

Percio, per ogni coppia di stati i, j con i < j, esiste uno stato k accessibile da icon k > j. Per quanto gia dimostrato, lo stato j e, a sua volta, accessibile dak, quindi, per la Proposizione 2.2, j e accessibile da i.

Cio prova che, per ogni coppia di stati i, j lo stato j risulta accessibile dallostato i, dunque tutti gli stati comunicano ovvero la catena di Markov e ir-riducibile. Inoltre lo stato 0 e evidentemente aperiodico, dunque, poiche lacatena di Markov e irriducibile, grazie alla Proposizione 2.6, ogni stato e aperi-odico.

Definizione 2.7 Uno stato i si dice ricorrente se

P

( ∞⋃n=1

Xn = i | X0 = i

)= 1,

altrimenti si dice transiente.

11

Page 12: catene di markov

Quindi uno stato i e ricorrente se, partendo dallo stato i al tempo 0 lacatena di Markov ritorna nello stato i in un tempo finito quasi certamente. Inparticolare se pii = 1, allora i si dice stato assorbente o trappola, in quantouna volta raggiunto, non se ne puo piu uscire.

ESEMPIO 2.5 Per la catene di Markov con spazio degli stati E finito, la rapp-resentazione grafica puo semplificare la classificazione degli stati. In particolare,se uno stato appartiene a una classe I chiusa, ovvero per ogni i ∈ I non esistenessun stato j ∈ E \ I, tale che pij > 0, risultera ricorrente. Allora si vedefacilmente che nella catena di Markov associata al grafo

?>=<89:;0

//?>=<89:;1

?>=<89:;2

OO

?>=<89:;3oo

OO

gli stati 0, 1, 2 una classe di stati ricorrenti, mentre 3 e uno stato transiente.Si osservi che uno stato e ricorrente o transiente indipendentemente dall’esattovalore numerico delle probabilita di passaggio da uno stato all’altro.

ESEMPIO 2.6 Consideriamo nuovamente la catena di Markov Rovina giocatoredell’Esempio 1.1. Come abbiamo visto, partendo da 0 (o da N), con probabilita1 la catena di Markov rimane in 0 (o in N) ad ogni istante successivo. Questistati sono evidentemente ricorrenti. Ogni stato i ∈ 1, 2, . . . , N − 1 invece etransiente poiche, partendo da i, la catena di Markov arrivera in 0 (risp. N)con probabilita maggiore o uguale a qi (risp. pN−i). Una volta arrivata in 0 oin N non lascera piu lo stato raggiunto e quindi la probabilita di ritornare in iverifica la diseguaglianza

P

( ∞⋃n=1

Xn = i | X0 = i

)≤ 1− (qi + pN−i) < 1.

Nello studio della ricorrenza degli stati di una catena di Markov e di grandeutilita la variabile aleatoria seguente

Definizione 2.8 Sia j uno stato. Si chiama tempo della prima entratanello stato j la variabile aleatoria a valori N ∪ +∞

Tj(ω)

minn ≥ 1 |Xn(ω) = j se n ≥ 1 |Xn(ω) = j 6= ∅,+∞ altrimenti.

Osserviamo che, per ogni stato j ed ogni intero n > 1, valgono le seguentieguaglianze

Tj < +∞ =⋃

1≤n<+∞

Xn = j,

Tj = 1 = X1 = j,

Tj = n = Xn = j⋂

1≤m≤n−1

Xm 6= j.

12

Page 13: catene di markov

Notazione. Nel seguito, per semplicita, denoteremo con Pi la probabilita con-dizionata

Pi (·) = P (·| X0 = i) .

Per ogni numero intero n strettamente positivo ed ogni coppia i, j di elementidi I poniamo

f(n)ij = PiTj = n , f

(0)ij = 0.

Poniamo inoltref∗ij =

∑1≤n<+∞

f(n)ij = PiTj < +∞.

Poiche la catena di Markov (Xn)n≥0 e omogenea, per ogni coppia di statii, j ed ogni coppia di numeri interi n, m > 1 si ha inoltre

f(n)ij = P (Xm+n = j ∩1≤ν≤n−1 Xm+ν 6= j | Xm = i) .

Osserviamo inoltre che, con le notazioni ora introdotte, uno stato i e ricorrentese risulta f∗ii = 1, transiente se f∗ii < 1.

Possiamo dimostrare ora il seguente

Teorema 2.9 (Equazione dei rinnovi) Siano i, j elementi di I. Per ogni interon ≥ 1 si ha

p(n)ij =

n∑ν=1

f(ν)ij p

(n−ν)jj . (6)

Dimostrazione. Supponiamo, per semplificare le notazioni, che l’eventoX0 = i sia quasi certo. Utilizzando la decomposizione dell’evento Xn = jin eventi disgiunti della forma

Xn = j =n⋃

ν=1

(Xn = j ∩ Tj = ν)

e la proprieta di Markov (1.1) si ha allora

p(n)ij = PXn = j

=∑

1≤ν≤n

PXn = j, Tj = ν

= PXn = j, Xn−1 6= j, . . . , X2 6= j,X1 = j+

∑1≤ν≤n−1

P (Xn = j,Xν = j, Xν−1 6= j, . . . , X1 6= j)

= f(n)ij +

∑1≤ν≤n−1

PXn = j |Xν = j,Xν−1 6= j, . . . , X1 6= j

·PXν = j, Xν−1 6= j, . . . , X1 6= j= f

(n)ij +

∑1≤ν≤n−1

PXn = j |Xν = jPTj = ν

= f(n)ij +

∑1≤ν≤n−1

f(ν)ij p

(n−ν)jj .

13

Page 14: catene di markov

Cio dimostra la (6).

Nella dimostrazione del Teorema 2.11, un criterio fondamentale per stabilirese uno stato e transiente o ricorrente utilizzeremo il seguente risultato dettoLemma di Abel

Lemma 2.10 Sia (an)n≥0 una successione di numeri reali non negativi tale chela serie di potenze

A(s) =∞∑

n=0

ansn

abbia raggio di convergenza r ≥ 1. Si ha allora

lims→1−

A(s) =∞∑

n=0

an.

Teorema 2.11 Per ogni stato i le condizioni seguenti sono equivalenti

a) i e ricorrente,

b) la serie∑∞

n=0 p(n)ii e divergente.

Se i e transiente allora si ha∞∑

n=0

p(n)ii

11− f∗ii

.

Dimostrazione. Consideriamo le funzioni generatrici delle successioni dinumeri reali (p(n)

ii )n≥0, (f (n)ii )n≥0

Pii(s) =∞∑

n=0

p(n)ii sn, Fii(s) =

∞∑n=0

f(n)ii sn.

Osserviamo che queste serie di potenze hanno raggio di convergenza r ≥ 1 poichele successioni (p(n)

ii )n≥0 e (f (n)ii )n≥0 sono limitate. Grazie al Teorema 2.13, per

ogni intero n ≥ 1 si ha allora

p(n)ii sn = sn

n∑ν=1

f(ν)ii p

(n−ν)ii =

n∑ν=1

f(ν)ii sνp

(n−ν)ii sn−ν

da cui segue che

Pii(s)− 1 =∞∑

n=1

p(n)ii sn

=∞∑

n=1

n∑ν=1

f(ν)ii sνp

(n−ν)ii sn−ν

14

Page 15: catene di markov

=∞∑

ν=1

f(ν)ii sν

∞∑n=ν

p(n−ν)ii sn−ν

=∞∑

ν=1

f(ν)ii sν

∞∑n=0

p(n)ii sn

= Fii(s)Pii(s).

Si ha pertanto, per ogni s ∈ (−1, 1),

Pii(s) =1

1− Fii(s).

La conclusione segue allora osservando che

lims→1−

Fii(s) = f∗ii, lims→1−

Pii(s) =∞∑

n=0

p(n)ii

ed applicando il Lemma di Abel.

Corollario 2.12 Sia J una classe di stati e j un elemento di J . Se j e ricor-rente (o, rispettivamente, transiente) allora ogni elemento di J e ricorrente (o,rispettivamente, transiente).

Dimostrazione. Sia k elemento di J − j. Poiche k e j comunicano,esistono due interi l,m ≥ 1 tali che

p(l)jk > 0, p

(m)kj > 0.

Per ogni intero n ≥ 1 si ha allora

p(l+n+m)kk ≥ p

(m)kj p

(n)jj p

(l)jk

p(l+n+m)jj ≥ p

(l)jkp

(n)kk p

(m)kj .

Quindi le serie∞∑

n=0

p(n)kk ,

∞∑n=0

p(n)jj

sono entrambe convergenti oppure entrambe divergenti. La conclusione segueallora dal Teorema 2.11.

Osserviamo che, per ogni stato j, la somme della serie∑n≥0

p(n)ij

e il tempo medio di occupazione dello stato j partendo da i. Infatti la variabilealeatoria ∑

n≥0

1Xn=j

15

Page 16: catene di markov

rappresenta il tempo (aleatorio) trascorso nello stato j poiche conta per quantin si e veificato l’evento Xn = j e la sua speranza e

Ei

∑n≥0

1Xn=j

=∑n≥0

Ei

[1Xn=j

]=∑n≥0

PXn = j =∑n≥0

p(n)ij . (7)

Corollario 2.13 Se j e uno stato transiente, allora, per ogni stato i, la serie

∞∑n=0

p(n)ij (8)

e convergente. In particolare, partendo da qualunque stato i, la catena di Markovpassa per j quasi certamente solo un numero finito di volte.

Dimostrazione. Se i = j la convergenza della serie segue dal Teorema2.11. Se i 6= j allora, grazie all’equazione dei rinnovi (6), si ha

∞∑n=1

p(n)ij =

∞∑n=1

n∑ν=1

f(ν)ij p

(n−ν)jj

=∞∑

ν=1

f(ν)ij

∞∑n=ν

p(n−ν)jj

= f∗ij

∞∑n=0

p(n)jj < ∞.

In particolare, grazie alla (7), la variabile aleatoria∑n≥0

1Xn=j

ha speranza finita. Ne segue che e quasi certamente finita e quindi che si verificasolo un numero finito di eventi Xn = j.

Nel caso in cui l’insieme degli stati sia finito la catena di Markov non potraoccupare sempre stati transienti (che occupa per un tempo medio finito). Si haquindi il seguente

Corollario 2.14 Una catena di Markov con insieme degli stati I finito ha al-meno uno stato ricorrente.

Dimostrazione. Supponiamo, per assurdo, che tutti gli stati siano tran-sienti. Allora, per ogni i, j, la serie (8) e convergente e quindi, in particolare

limn→∞

p(n)ij = 0.

16

Page 17: catene di markov

La matrice p(n) e stocastica e quindi, per ogni n ≥ 1, si ha anche∑j∈I

p(n)ij = 1.

Facendo tendere n all’infinito e scambiando il limite con la sommatoria (cosapossibile perche I e finito) si trova la contraddizione 0 = 1.

Applicheremo ora il criterio di transienza o ricorrenza del Teorema 2.11 allostudio delle passeggiate casuali su Zd.

ESEMPIO 2.7 Passeggiata casuale su Z. Consideriamo una catena di Markov(Xn)n≥0 con insieme degli stati Z e matrice di transizione

P =

. . . . . . . . . . . . . . . . . . . . .. . . q 0 p 0 0 . . .. . . 0 q 0 p 0 . . .. . . . . . . . . . . . . . . . . . . . .

dove p, q sono due numeri reali tali che

p, q ∈]0, 1[, p + q = 1.

E chiaro che questa catena di Markov rappresenta il moto sull’insieme deinumeri naturali di un punto che, ad ogni istante, si sposta da i a i + 1 conprobabilita p e da i a i−1 con probabilita q. E facile vedere inoltre che si trattadi una catena di Markov irriducibile e che ogni stato ha periodo 2.

Vogliamo stabilire se gli stati sono transienti oppure ricorrenti. A questoscopo cominciamo con l’osservare che, per ogni n ≥ 0, si ha

P(n)00 =

(2n

n

)(pq)n.

Grazie alla formula di Stirling

limn→∞

nn exp(−n)√

2πn

n!= 1

si trova l’andamento asintotico

P(n)00 ≈ (4pq)n

√πn

.

Poiche il numero reale positivo 4pq = 4p(1 − p) e eguale a 1 se p = q = 1/2e strettamente minore di 1 se p 6= q, applicando il Teorema 2.11 possiamoconcludere che tutti gli stati sono ricorrenti nel primo caso e transienti nelsecondo.

Nel caso in cui p = q i tempi della prima entrata in ogni stato sono vari-abili aleatorie positive quasi certamente a valori finiti. Utilizzando le funzionigeneratrici F00 e P00 introdotte nella dimostrazione del Teorema 2.11 possiamo

17

Page 18: catene di markov

calcolare anche il tempo medio della prima entrata in 0 sotto la condizioneX0 = 0. Infatti, ricordando lo sviluppo in serie di Taylor notevole,

(1− 4x)−12 =

∑n≥0

(2n

n

)xn, |x| < 1

4,

otteniamo in forma esplicita la funzione generatrice P00

P00(s) =1√

1− 4pqs2, |s| < 1.

La funzione generatrice F00 e quindi

F00(s) = 1− (P00(s))−1 = 1−

√1− 4pqs2, |s| < 1.

Grazie al Lemma di Abel, poiche 4pq = 1, troviamo infine

E0[T0] =∑n≥1

nf(n)00 = lim

s→1−

∑n≥1

nf(n)00 sn−1

= lims→1−

dF00(s)ds

= lims→1−

4pqs√1− 4pqs2

= +∞.

Nel caso in cui p = q = 1/2 pertanto, anche se il ritorno in 0 e quasi certo, si faraattendere molto a lungo e comunque, in media, piu di quanto possa aspettareun individuo mortale.

ESEMPIO 2.8 Passeggiata casuale simmetrica su Z2. Consideriamo una catenadi Markov (Xn)n≥0 con insieme degli stati Z2 e probabilita di transizione

P Xn+1 = (i, j) | Xn = (h, k) =

1/4 se |i− h|+ |j − k| = 1,0 altrimenti.

(Xn)n≥0 e una catena di Markov irriducibile ed ogni stato ha periodo 2. DettaP la matrice di transizione si ha

P(2n)00 =

∑h+k=n

(2n)!(h!)2(k!)2

(14

)2n

(dove 0 denota l’origine di Z2). Con facili calcoli si trova quindi

P(2n)00 =

n∑k=0

(2n)!(k!)2((n− k)!)2

(14

)2n

=(

2n

n

)(14

)2n n∑k=0

(n

k

)(n

n− k

)Confrontando i termini anbn del binomio di Newton di (a + b)2n e del quadratodel binomio di Newton di (a + b)n si trova l’identita notevole(

2n

n

)=

n∑k=0

(n

k

)(n

n− k

).

18

Page 19: catene di markov

Otteniamo quindi la formula

P 2n00 =

((2n

n

)(14

)n)2

.

Utilizzando la formula di Stirling troviamo poi lo sviluppo asintotico

P 2n00 ≈ 1

πn

che ci permette di concludere, grazie al Teorema 2.11 e al Corollario 2.12 chetutti gli stati sono ricorrenti.

Tramite la definizione delle fii si puo dare una caratterizzazione ulteriore diperiodo di uno stato i, che verra utilizzata in seguito.

Proposizione 2.15 Il periodo d(i) di uno stato i coincide con il massimo co-mun divisore dell’insieme n ≥ 1|f (n)

ii > 0.

Dimostrazione. Assumiamo inizialmente che i sia uno stato aperiodico.In questo caso cio che vogliamo dimostrare e che il massimo comune divisoredell’insieme di numeri naturali

k ≥ 1 | f (k)ii > 0

sia eguale a 1. Se cosı non fosse, detto m > 1 tale numero avremmo ovviamentep(k)ii = 0 per 1 ≤ k < m e quindi

p(m+k)ii = f

(m)ii p

(k)ii = 0

per 1 ≤ k < m. Si potrebbe quindi dimostrare per induzione su n che p(mn+k)ii

e nullo per 1 ≤ k < m e n ≥ 0 ovvero che p(k)ii e nullo se k non e multiplo di

m. Cio contraddice l’ipotesi che i e aperiodico. Il caso in cui d(i) = n > 1 sidimostra nello stesso modo.

ESERCIZI

Es 2.1 Individuare le classi di stati in una catena di Markov con matrice ditransizione

0 1/2 0 0 1/21/2 0 0 1/2 01/3 1/3 1/3 0 00 1/4 1/4 1/4 1/4

1/2 1/2 0 0 0

.

Quali sono gli stati ricorrenti e transienti? Dire se vi sono stati periodici ecalcolarne eventualmente il periodo.

19

Page 20: catene di markov

Es 2.2 Una catena di Markov con insieme degli stati N ha matrice di transizione1− p p 0 0 0 0 · · ·1− p 0 p 0 0 0 · · ·1− p 0 0 p 0 0 · · ·1− p 0 0 0 p 0 · · ·1− p 0 0 0 0 p · · ·

dove p ∈ (0, 1). Mostrare che la catena di Markov e irriducibile e aperiodica.verificare che il tempo T0 del primo ritorno nello stato 0 rispetto ad ogni prob-abilita Pi ha legge geometrica. Questo fatto ha qualche relazione con la notaproprieta della legge geometrica?

Es 2.3 Data una catena di Markov con matrice di transizione

P =

1/3 1/3 0 0 1/31/4 0 1/4 1/2 00 0 1/2 1/2 00 0 0 1/2 1/20 0 0 1/2 1/2

individuare gli stati transienti e gli stati ricorrenti. Verificare che, per ognin ≥ 2, si ha che

Pn =

∗ ∗ ∗ ∗ ∗∗ ∗ ∗ ∗ ∗0 0 2−n ∗ ∗0 0 0 1/2 1/20 0 0 1/2 1/2

(al posto degli asterischi ci sono opportuni numeri reali strettamente positivi).Si puo spiegare questo fatto con qualche proprieta della catena di Markov?

Es 2.4 Sia (Xn)n≥1 una successione di variabili aleatorie indipendenti con leggedi Bernoulli B(1, p) e (Zn)n≥0 la successione di variabili aleatorie cosı definita

Z0 = 1, Zn+1 = Zn(2Xn+1 − 1).

Stabilire se (Zn)n≥0 e una catena di Markov e determinarne eventualmente lala matrice di transizione. Mostrare che tutti gli stati sono ricorrenti.

Es 2.5 Assegnati due stati i e j di una catena di Markov, provare che

i) se j e ricorrente e accessibile da i, allora∑

n≥1 p(n)ij = +∞,

ii) se j e ricorrente e non accessibile da i, allora∑

n≥1 p(n)ij = 0.

20

Page 21: catene di markov

3 Leggi invarianti e teoremi limite.

Sia (Xn)n≥0 una catena di Markov sullo spazio probabilizzato (Ω,F , P) coninsieme degli stati I e matrice di transizione P = (pij)i,j∈I .

Definizione 3.1 Una legge µ su I e invariante per la catena di Markov (Xn)n≥0

se la variabile aleatoria Xn ha legge µ per ogni n ≥ 0.

Identificheremo spesso le leggi su I con la loro densita (rispetto alla misurache conta i punti di ogni sottoinsieme di I) cioe con la famiglia di numeri realinon negativi (µi)i∈I ove µi = µ(i).

Proposizione 3.2 Una legge µ su I e invariante per la catena di Markov(Xn)n≥0 se e solo se, per ogni stato i, si ha

µi =∑j∈I

µjpji (9)

(ovvero la sua densita e un autovettore sinistro della matrice di transizione conautovalore relativo 1).

Dimostrazione. Detta µ la legge di X0, la legge ν di X1 ha densita

νi = PX1 = i =∑j∈I

PX0 = jpji =∑j∈I

µjpji,

Quindi, se µ e una legge invariante per la catena di Markov (Xn)n≥0, allora lavale la (9). Viceversa, se µ e una legge su I che soddisfa la (9), si puo dimostrarefacilmente per induzione che Xn ha legge µ per ogni n.

Dunque una legge µ su I, identificando la sua densita con il vettore (µi)i∈I ,e invariante se e solo se

µ = µP (P e la matrice di transizione).

Teorema 3.3 Se l’insieme degli stati I e finito allora esiste almeno una leggeinvariante.

Dimostrazione. L’insieme delle densita di probabilita su I

K =

(µi)i∈I

∣∣∣∣ 0 ≤ µi ≤ 1, per ogni i,∑i∈I

µi = 1

e compatto. Preso un elemento µ(0) di K e facile dimostrare che, per ogni interon ≥ 1, la famiglia di numeri reali non negativi (µ(n)

j )j∈I cosı definita

µ(n)j =

1n

n∑k=1

(∑i∈I

µ(0)i p

(k)ij

)

21

Page 22: catene di markov

e una densita di probabilita su I. Poiche l’insieme K e compatto, passando even-tualmente a sottosuccessioni, possiamo supporre che la successione (µ(n)

j )n≥0 siaconvergente per ogni j ∈ I. Posto quindi

πj = limn→∞

µ(n)j

la famiglia di numeri reali (πj)j∈I e una densita di probabilita su I e inoltre siha ∑

i∈I

πipij = limn→∞

1n

n∑k=1

(∑i∈I

πip(k+1)ij

)

= limn→∞

1n + 1

n+1∑k=1

(∑i∈I

πip(k)ij

)− lim

n→∞

1n + 1

∑i∈I

πipij

= πj

per ogni j ∈ I. Cio dimostra che la legge con densita (πi)i∈I e invariante per lacatena di Markov.

Nel teorema precedente la legge invariante e stata ottenuta come limite (disottosuccessioni estratte da) (µ(n))n≥1 dove µ(0) e una legge su I e

µ(n)j =

1n

n∑k=1

(µ(0)P k)j

per ogni n ≥ 1 ed ogni j ∈ I (qui (µ(0)P k)j =∑

i∈I µ(0)i p

(k)ij ). In particolare, se

µ(0) = δi (densita di Dirac nel punto i), si ha

µ(n)j

1n

n∑k=1

p(k)ij .

L’analisi di questa espressione fornisce anche l’interpretazione del significatodella legge invariante. Infatti, ricordando che la variabile aleatoria

n∑k=1

1Xk=j

rappresenta il numero di visite nello stato j fino al tempo n, e chiaro che lavariabile aleatoria

1n

n∑k=1

1Xk=j

rappresenta la frequenza delle visite nello stato j al tempo n. La sua media,rispetto alla probabilita Pi,

Ei

[1n

n∑k=1

1Xk=j

]=

1n

n∑k=1

PiXk = j =1n

n∑k=1

p(k)ij

22

Page 23: catene di markov

rappresenta quindi la frequenza media delle visite nello stato j al tempo n. Sipossono quindi interpretare i πj della legge invariante come frequenza mediaasintotica delle visite nello stato j.

Una catena di Markov (anche con I finito) puo avere piu di una legge in-variante come mostra l’esempio Rovina del giocatore. In questo caso infatti ledensita

(1, 0, . . . , 0), (0, . . . , 0, 1)

e le loro combinazioni convesse

λ(1, 0, . . . , 0) + (1− λ)(0, . . . , 0, 1)(λ, 0, . . . , 0, 1− λ) λ ∈ [0, 1]

sono tutte leggi invarianti.Nel caso in cui l’insieme I sia infinito, tuttavia, si possono fornire esempi

naturali di catene di Markov che non ammettono nessuna legge invariante.

ESEMPIO 3.1 La catena di Markov corrispondente alla Passeggiata casuale suZ dell’Esempio 2.7 non ha nessuna legge invariante infatti la densita (πi)i∈I ditale legge dovrebbe soddisfare la relazione

πi = qπi+1 + pπi−1

per ogni numero intero i, cioe

q (πi+1 − πi) = p (πi − πi−1) . (10)

Cominciamo con l’osservare che deve essere πi+1 6= πi per ogni intero i poiche,diversamente, dalla relazione precedente, otterremmo πi+1 = πi per ogni interoi e la (πi)i∈I trovata non e una densita di probabilita. Quindi distinguiamo i trecasi p > q, p = q = 1/2 e p < q. Nel primo caso dalla (10) si trova facilmenteper induzione la formula

πi+1 − πi = (p/q)i(π1 − π0)

dalla quale segue la relazione

limi→+∞

|πi+1 − πi| = +∞

che contraddice la limitatezza di (πi)i∈I . Nel secondo dalla (10) si trova laformula

πi+1 − πi = π1 − π0

dalla quale segue la relazione

πi = i(π1 − π0) + c

(con c costante) che contraddice ancora la limitatezza di (πi)i∈I . Il terzo casosi tratta come il primo. In conclusione la catena di Markov considerata nonpossiede nessuna legge invariante.

23

Page 24: catene di markov

Il calcolo esplicito o anche la sola dimostrazione dell’esistenza di una leggeinvariante in generale puo non essere semplice. L’esempio seguente, che mod-ellizza varie situazioni (rovina del giocatore contro un avversario con capitalepraticamente infinito, passeggiata casuale su N, ...) mostra un caso notevole incui l’insieme degli stati e infinito ma si riesce ugualmente a risolvere semplice-mente entrambi i problemi.

ESEMPIO 3.2 Consideriamo la catena di Markov con insieme degli stati N ematrice di transizione

r0 p0 0 0 0 . . .q1 r1 p1 0 0 . . .0 q2 r2 p2 0 . . .0 0 q3 r3 p3 . . .0 0 0 q4 r4 . . .

. . . . . . . . . . . . . . . . . .

dove (pm)m≥0, (rm)m≥0, (qm)m>0 sono tre successioni di numeri reali conpm, qm ∈]0, 1[ e rm ∈ [0, 1] tali che

r0 + p0 = 1, qm + rm + pm = 1

per ogni intero m ≥ 1. Ogni legge invariante (πn)n≥0 soddisfa le equazioni

π0 = r0π0 + q1π1

πn = pn−1πn−1 + rnπn + qn+1πn+1

per ogni n ≥ 1 oltre alla condizione di positivita πn ≥ 0 e di normalizzazione∑n≥0

πn = 1.

Dalla prima equazione si trova

π1 =1− r0

q1π0 =

p0

q1π0

e, per induzione,πn =

p0 . . . pn−1

q1 . . . qnπ0

per ogni n ≥ 1. La condizione di normalizzazione puo essere soddisfatta pren-dendo

π0

1 +∑n≥1

p0 . . . pn−1

q1 . . . qn

−1

se e solo se la serie ∑n≥1

p0 . . . pn−1

q1 . . . qn

e convergente. Questa condizione e quindi necessaria e sufficiente per l’esistenzadi una legge invariante che sara necessariamente unica.

24

Page 25: catene di markov

Enunciamo il seguente teorema (vedi [2] p. 335 oppure [3] p. 81 per la di-mostrazione), che ci servira per enunciare una condizione necessaria e sufficienteaffinche una catena di Markov con insieme degli stati infinito abbia una leggeinvariante.

Teorema 3.4 Sia (ak)k≥1 una successione di numeri reali non negativi tale che

∞∑k=1

ak = 1

e il massimo comune divisore dell’insieme dei numeri naturali k per i qualiak sia strettamente positivo sia 1. La successione di numeri reali non negatividefinita per ricorrenza dalle relazioni

u0 = 1, un =n∑

k=1

akun−k,

e limitata e soddisfa la relazione (con la convenzione abituale 1/∞ = 0)

limn→∞

un =

( ∞∑k=1

kak

)−1

.

Osserviamo che la successione (un)n≥0 qui definita e limitata poiche vale ladiseguaglianza

0 ≤ un ≤ max1≤k≤n−1

ukn∑

k=1

ak

per ogni intero n ≥ 1.Enunciamo ora il seguente risultato abbastanza naturale data l’interpretazione

della legge invariante.

Teorema 3.5 Se i e uno stato ricorrente aperiodico allora si ha

limn→∞

p(n)ii = (Ei[Ti])

−1.

Dimostrazione. Basta applicare il Teorema 3.4 Infatti, grazie alla Propo-sizione 2.15, si ha

p(n)ii =

n∑k=1

f(k)ii p

(n−k)ii

e, valgono le formule,∞∑

k=1

f(k)ii = 1,

∞∑k=1

kf(k)ii = Ei[Ti].

25

Page 26: catene di markov

essendo i ricorrente. Inoltre, per la Proposizione 2.15, il massimo comune divi-sore dell’insieme di numeri naturali

k ≥ 1 | f (k)ii > 0

e eguale a 1.

Ricordiamo che Ti e l’istante (aleatorio) del primo ritorno nello stato i chee quasi certamente finito per la probabilita Pi (cioe PiTi < ∞ = 1) ma puoavere speranza infinita (cioe Ei[Ti] = +∞). In tal caso, poniamo (Ei[Ti])

−1 = 0.

Definizione 3.6 Uno stato ricorrente i si chiama ricorrente positivo (o veloce)se Ei[Ti] < +∞ e ricorrente nullo (o lento) se Ei[Ti] = +∞.

Osserviamo che, se i e j sono due stati comunicanti, ricorrenti e aperiodiciallora sono entrambi ricorrenti positivi o entrambi ricorrenti nulli. Infatti bastaosservare, come abbiamo gia fatto molte volte, che vale una diseguaglianza deltipo

p(a+n+b)jj ≥ p

(a)ji p

(n)ii p

(b)ij

dove i numeri interi a, b ≥ 1 sono scelti in modo tale che i numeri reali p(a)ji e

p(b)ji siano strettamente positivi.

Si puo verificare che una catena di Markov con insieme degli stati I finito nonha stati ricorrenti nulli (o lenti). Infatti, detta C la classe a cui appartiene uneventuale stato ricorrente lento i, ragionando come nell’osservazione precedente,si vede subito che tutti gli stati della classe C sono tutti ricorrenti nulli ovverola successione (p(n)

jj )n≥1 converge a 0 per n tendente all’infinito per ogni j ∈ C.Inoltre, poiche la catena di Markov non puo uscire da C, si ha∑

j∈Cpkj = 1

per ogni stato k. Infine, procedendo come nella dimostrazione del Corollario2.14, si ottiene una contraddizione.

Osserviamo inoltre che il caso di uno stato ricorrente i di periodo d > 1 sipuo trattare in modo analogo considerando i come uno stato (aperiodico) dellacatena di Markov (Xnd)n≥0. In tal caso si ottiene

limn→∞

p(nd)ii = d (Ei[Ti])

−1.

Poiche si vede facilmente che p(m)ii e nullo per ogni intero m ≥ 1 che non sia

multiplo di d, si trova la relazione

limn→∞

1n

n∑k=1

p(k)ii = (Ei[Ti])

−1.

Teorema 3.7 Sia (Xn)n≥0 una catena di Markov irriducibile e aperiodica. Lecondizioni seguenti sono equivalenti:

26

Page 27: catene di markov

1. ogni stato e ricorrente positivo,

2. esiste una legge invariante (πi)i∈I tale che per ogni coppia di stati i, j siabbia

limn→∞

p(n)ij = lim

n→∞p(n)jj = πj .

Se valgono le condizioni precedenti allora (πi)i∈I e l’unica legge invariante perla catena di Markov (Xn)n≥0.

Dimostrazione. 1. ⇒ 2. Grazie al Teorema 2.9 si ha

p(n)ij =

n∑k=1

f(k)ij p

(n−k)jj

e quindi, per Corollario 3.5 (e il Teorema di Lebesgue), detto πj il limite dellasuccessione (p(n)

jj )n≥0, si trova

limn→∞

p(n)ij

∞∑k=1

f(k)ij πj = πj .

Inoltre, per ogni sottoinsieme finito F di I, abbiamo la diseguaglianza∑j∈F

πj = limn→∞

∑j∈F

p(n)ij ≤ lim

n→∞

∑j∈I

p(n)ij = 1

e quindi ∑j∈I

πj ≤= 1.

Dimostriamo ora che (πj)j∈I e la densita di una legge invariante per la catenadi Markov (Xn)n≥0. Sia F un sottoinsieme finito di I. Passando al limite nellarelazione ∑

k∈F

p(n)ik pkj ≤ p

(n+1)ij

per ogni i, j ∈ I, otteniamo le diseguaglianze∑k∈F

πkpkj ≤ πj

e quindi, data l’arbitrarieta di F ,∑k∈I

πkpkj ≤ πj . (11)

Sommando su j troviamo poi∑k∈I

πk =∑j∈I

∑k∈I

πkpkj =∑j∈I

πj .

27

Page 28: catene di markov

Le diseguaglianze (11) sono dunque eguaglianze.Iterando le eguaglianze (11) si trovano le identita

πj =∑k∈I

πkp(n)kj

per ogni intero n ≥ 1. Facendo tendere n all’infinito si trova

πj = πj

∑k∈I

πk

per ogni stato j da cui segue che ∑k∈I

πk = 1.

Dunque (πj)j∈I e la densita di una legge invariante per (Xn)n≥0.2. ⇒ 1. La conclusione segue immediatamente dal Teorema 3.5.Mostriamo infine che, se valgono 1. e 2., allora la legge invariante e unica.

Per dimostrare questo basta osservare che, se µ e un’altra legge invariante,allora, per ogni stato j si ha

µj =∑k∈I

µkpkj .

Iterando n-volte si trovano le identita

µj =∑k∈I

µkp(n)kj .

Facendo tendere n all’infinito si ottiene la relazione

µj =∑k∈I

µkπj = πj

per ogni j ∈ I. L’unicita e cosı dimostrata.

Come conseguenza di questo Teorema, data una catena di Markov a statifiniti irriducibile e aperiodica esiste un’unica legge invariante π, tale che Ei[Ti] =1πi

. Nelle stesse ipotesi, possiamo chiederci quando vale il tempo medio neces-sario per raggiungere uno stato j partendo da i, con 1 6= j,. Vogliamo quindicalcolare

Ei[Tj ] =∑k≥1

kPiTj = k

= pij +∑k>1

kPiTj = k.

28

Page 29: catene di markov

Siccome PiTj = k =∑

h6=j pihPhTj = k − 1 per ogni k > 1, abbiamo che

Ei[Tj ] = pij +∑k>1

∑h6=j

kpihPhTj = k − 1

= pij +∑h6=j

∑k>1

kpihPhTj = k − 1

= pij +∑h6=j

pihEh[Tj + 1]

= 1 +∑h6=j

pihEh[Tj ].

. In questo modo abbiamo ottenuto un sistema di equazioni lineari che ci per-mette di calcolare le speranza Ei[Tj ] quando i 6= j. Nella prossimo capitolo,cercheremo di rispondere a domande analoghe quando la catena di Markov none piu irriducibile.

ESERCIZI

Es 3.1 Individuare tutte le leggi invarianti della catena di Markov con matricedi transizione

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

.

Es 3.2 Una catena di Markov con insieme degli stati N ha matrice di transizionep 1− p 0 0 0 0 · · ·p 0 1− p 0 0 0 · · ·p 0 0 1− p 0 0 · · ·p 0 0 0 1− p 0 · · ·p 0 0 0 0 1− p · · ·

,

dove p ∈ (0, 1). Mostrare che la catena di Markov e irriducibile e aperiodica eche la sua legge invariante e la legge geometrica di parametro p.

Es 3.3 Provare che, per una catena di Markov con matrice di transizione bis-tocastica, la distribuzione uniforme e invariante. Quando questa puo essere unamisura di probabilita?

Es 3.4 Una legge (πi)i∈I si dice reversibile rispetto ad una matrice di tran-sizione P se, per ogni i, j ∈ I verifica

πipij = πjpji.

Mostrare che una legge reversibile e necessariamente invariante.

29

Page 30: catene di markov

Es 3.5 Classificare gli stati della catena di Markov (Xn)n≥0 con insieme deglistati S = 1, 2, 3, 4, 5 e matrice di transizione del tipo

P =

∗ ∗ 0 0 ∗0 ∗ ∗ 0 00 ∗ ∗ 0 00 0 ∗ ∗ 0∗ 0 0 ∗ 0

,

dove il simbolo ∗ individua gli elementi della matrice strettamente positivi.Una tale catena possiede leggi invarianti? Si puo dire qualcosa di piu nel casoin cui si supponga che tutte le transizioni in partenza dallo stesso vertice sianoequiprobabili?

Es 3.6 Sia (Xn)n≥0 una catena di Markov con legge invariante. π. Sia C unaclasse di stati e sia a ∈ C. Provare che a e ricorrente e πj > 0 per ogni j ∈ C.

Es 3.7 Data una catena di Markov (Xn)n≥0 con insieme degli stati Z e matricedi transizione

· · · · · · · · · · · · · · · · · ·· · · 2/5 1/5 2/5 · · · · · ·· · · · · · 2/5 1/5 2/5 · · ·· · · · · · · · · · · · · · · · · ·

.

Classificare gli stati e dire se esiste una legge invariante.

Es 3.8 Supponiamo che un’industria produca due tipi di Cola, Cola1 e Cola2.Sappiamo che una persona che all’acquisto abbia scelto Cola1, all’acquisto suc-cessivo scegliera Cola 2 con probabilita 0.9, mentre se ha scelto inizialmenteCola2 scegliera ancora Cola 2 con probabilita 0.8. Quante bottiglie in mediaberra il compratore di Cola1 prima di passare a Cola2?

30

Page 31: catene di markov

4 Assorbimento in classi ricorrenti

Abbiamo dimostrato che gli stati transienti sono visitati solo un numero finitodi volte e quindi, partendo da uno stato transiente, la catena di Markov ha duepossibilita

1) continua a muoversi tra stati transienti (sempre che ce ne siano infiniti),

2) entra in una classe C di stati ricorrenti da cui non uscira piu.

Nel caso in cui l’insieme degli stati I sia finito il primo caso (vedi Propo-sizione 4.1 qui sotto) non puo sussistere e quindi, quando vi sono piu classiricorrenti, sorge il problema di calcolare la probabilita di assorbimento in cia-scuna di esse. Questo problema e abbastanza naturale nelle applicazioni. Nellacatena di Markov che descrive la Rovina del giocatore (Esempio 1.1), per es-empio, le probabilita di assorbimento nelle classi 0 ed N rappresentano leprobabilita di rovina del giocatore e del banco.

In questo paragrafo, supponendo sempre che I sia finito, vedremo come sipossono calcolare semplicemente queste probabilita.

Denotiamo con T l’insieme degli stati transienti e, per ogni i ∈ T , denotiamocon u

(n)i la probabilita, partendo da i di continuare passare ad altri stati tran-

sienti almeno fino al tempo n e con ui la probabilita di fare questo per semprecioe

u(n)i = Pi Xn ∈ T , . . . , X1 ∈ T

ui = Pi

( ⋂n≥1

Xn ∈ T )

.

Proposizione 4.1 Per ogni stato transiente i la successione (u(n)i )n≥0 e decre-

scente elim

n→∞u

(n)i = ui.

La famiglia di numeri reali (ui)i∈T soddisfa le equazioni

ui =∑j∈T

pijuj . (12)

In particolare, se l’insieme T e finito, allora l’unica soluzione del sistema diequazioni (12) e ui = 0 per ogni i ∈ T .

Dimostrazione. La successione e ovviamente decrescente poiche le (u(n)i )n≥0

rappresentano le probabilita di una successione decrescente di eventi. Inoltre,per ogni n ≥ 1, si ha

u(n+1)i =

∑j∈T

piju(n)j .

La (12) segue passando al limite.

31

Page 32: catene di markov

Se l’insieme T e finito, allora, iterando la (12) abbiamo

ui =∑j∈T

pijuj

=∑

j,l∈T

pijpjlul

≤∑l∈T

(∑l∈I

pijpjl

)ul

=∑l∈T

p(2)il ul.

Pertanto, iterando la (12) n volte, troviamo le diseguaglianze

|ui| ≤∑j∈T

p(n)ij |uj | ≤ max

j∈I|uj |

∑j∈T

p(n)ij .

Grazie al Corollario 2.13, la conclusione segue facendo tendere n all’infinito.

Calcoliamo ora la probabilita vi che, partendo da uno stato transiente i, lacatena di Markov entri in una classe ricorrente C e quindi vi rimanga definitiva-mente. Questa probabilita e detta probabilita di assorbimento. Sia V il tempodella prima entrata (detto anche tempo di assorbimento) nella classe C cioe

V = infj∈C

Tj

(dove Tj denota il tempo della prima entrata nello stato j). Si vede facilmenteche V e un tempo d’arresto. Denotiamo con (v(n)

i )1≤n≤+∞ la legge di V per laprobabilita Pi

v(n)i = PiV = nPiXn ∈ C, Xn−1 /∈ C, . . . , X1 /∈ C,

v(∞)i = PiV = +∞ = Pi (∩1≤n<+∞Xn /∈ C) .

Si ha alloravi = Pi(∪1≤n<+∞Xn ∈ C) =

∑1≤n<+∞

v(n)i .

Possiamo dimostrare il seguente risultato

Teorema 4.2 Le probabilita (vi)i∈C sono una soluzione limitata delle equazioni

vi =∑j∈C

pij +∑j∈T

pijvj , i ∈ T . (13)

Se l’insieme degli stati I e finito, allora le probabilita (vi)i∈T sono l’unicasoluzione limitata delle equazioni (13).

32

Page 33: catene di markov

Dimostrazione. Si ha evidentemente

v(1)i = PiX1 ∈ C =

∑j∈C

pij

e, per ogni n ≥ 2,

v(n)i = PiXn ∈ C, Xn−1 ∈ T , . . . , X2 ∈ T , X1 ∈ T

=∑j∈T

PiXn ∈ C, Xn−1 ∈ T , . . . , X1 = j

=∑j∈T

pijPjXn ∈ C, Xn−1 ∈ T , . . . , X2 ∈ T

=∑j∈T

pijPjXn−1 ∈ C, . . . , X1 ∈ T

=∑j∈T

pijv(n−1)j .

Sommando le relazioni precedenti, si ottiene

vi = v(1) +∑

2≤n<+∞

v(n)

=∑j∈C

pij +∑

2≤n<+∞

∑j∈T

pijv(n−1)j

=∑j∈C

pij +∑j∈T

pijvj

Dunque (vi)i∈T soddisfa le equazioni (13).Se l’insieme degli stati I e finito e (vi)i∈I , (wi)i∈I sono due soluzioni di (13),

allora la differenza (ui)i∈I ui = vi − wi e una soluzione di (12) ed essendo Ifinito e nulla. La conclusione e ora evidente.

ESEMPIO 4.1 Riprendiamo l’Esempio 1.1. Sia N ≥ 2 un numero naturalefissato e p, q due numeri reali strettamente positivi tali che p + q = 1. Consid-eriamo una catena di Markov con insieme degli stati 0, 1, . . . , N con matricedi transizione

1 0 0 0 . . . 0 0 0q 0 p 0 . . . 0 0 00 q 0 p . . . 0 0 00 . . . . . . . . . . . . . . . . . . 00 0 0 0 . . . 0 p 00 0 0 0 . . . q 0 p0 0 0 0 . . . 0 0 1

.

La catena di Markov in questione ha evidentemente due classi ricorrenti 0e N e tutti gli stati 1, 2, . . . , N − 1 sono transienti. Il calcolo della probabilita

33

Page 34: catene di markov

suddetta equivale quindi al calcolo delle probabilita di assorbimento vi degli statitransienti i ∈ 1, 2, . . . , N − 1 nelle classi ricorrenti 0 e N. Calcoliamo,per esempio, le probabilita di assorbimento (vi)1≤i≤N−1in 0. Poiche l’insiemedegli stati e finito le equazioni (13), che in questo caso si scrivono

v1 = q + pv2

vi = qvi−1 + pvi+1 se 2 ≤ i ≤ N − 2vN−1 = qvN−2

Ponendo quindi, come e naturale v0 = 1 e vN = 0 si trova

vi = qvi−1 + pvi+1

per ogni i ∈ 1, . . . , N − 1. Risolvendo questo sistema di equazioni a differenzefinite, con v0 = 1 e vN = 0 come “condizioni al bordo”, si trova

vi =(q/p)i − (q/p)N

1− (q/p)N

se p 6= q e

vi = 1− i

N

se p = q = 1/2. Cio risolve il problema posto.Osserviamo che, per N → +∞, le vi convergono verso

1 se q ≥ p, (q/p)i se q < p.

Questo indica che, per N molto grande, il giocatore con capitale iniziale i haprobabilita vicina a (q/p)i di diventare ricchissimo (sbancando l’avversario).

Una procedura a quella indicata per il calcolo delle probabilita di assorbi-mento permette di dedurre un metodo per il calcolo dei tempi medi di assorbi-mento in una classe ricorrente in un caso particolare notevole.

Teorema 4.3 Supponiamo l’insieme degli stati I sia finito ed esista un’unicaclasse ricorrente C. I tempi medi di assorbimento wi = Ei[V ] di uno statotransiente i nella classe C sono finiti e coincidono con l’unica soluzione limitata(wi)i∈T delle equazioni

wi = 1 +∑j∈T

pijwj . (14)

Dimostrazione. Cominciamo con l’osservare che, con le notazioni utiliz-zate piu sopra, per ogni intero n ≥ 1, si ha

PiV > n = PiXn ∈ T , . . . , X1 ∈ T = u(n)i .

34

Page 35: catene di markov

Inoltre, dalla relazione trovata precedentemente,

u(n+1)i =

∑j∈T

piju(n)j

si ottengono facilmente per iterazione le diseguaglianze

u(n+m)i ≤

∑j∈T

p(m)ij u

(n)j

per ogni intero m ≥ 1. Si hanno inoltre le diseguaglianze

u(n+m)i ≤ max

j∈Tu(n)

j ∑j∈T

p(m)ij (15)

Grazie al Corollario 2.13, per ogni j ∈ T , la successione (p(m)ij )m≥1 converge

verso 0 per m tendente a +∞. Possiamo quindi scegliere un numero naturalem abbastanza grande in modo tale che, per ogni i ∈ T , valga la diseguaglianza∑

j∈Tp(m)ij < 1

ovvero, poiche l’insieme degli stati I e finito, in modo tale che il numero realeM

M = maxi∈T

∑j∈T

p(m)ij

risulti strettamente minore di 1. Dalla (15) si ha pertanto la diseguaglianza

u(n)i ≤ M [n/m]

dalla quale segue che

Ei[V ] =+∞∑n=0

PiV > n ≤+∞∑n=0

M [n/m] ≤ (M(1−M1/m))−1 < +∞.

Cio dimostra la prima affermazione. Per completare la dimostrazione basterafar vedere che i tempi medi di assorbimento (wi)i∈T soddisfano le equazioni (14)infatti la soluzione di tali equazioni e unica per il Corollario (4.1). Questo seguedalle identita seguenti

Ei[V ] =∞∑

n=1

nPiV = n

=∞∑

n=1

nPiV = n, X1 ∈ T +∞∑

n=1

nPiV = n, X1 ∈ C

=∞∑

n=2

n∑j∈T

pijPXn ∈ C, Xn−1 ∈ T , . . . |X1 = j+∑j∈C

pij

35

Page 36: catene di markov

=∞∑

n=2

n∑j∈T

pijPjXn−1 ∈ C, Xn−2 ∈ T , . . .+∑j∈C

pij

=∑j∈T

pij

∞∑n=2

nPjV = n− 1+∑j∈C

pij .

Con facili calcoli si ha infine

Ei[V ] =∑j∈T

pij

∞∑n=1

(n + 1)PjV = n+∑j∈C

pij

=∑j∈T

pij

∞∑n=1

nPjV = n+∑j∈T

pij +∞∑

n=1

PjV = n∑j∈C

pij

=∑j∈T

pijEj [V ] +∑j∈T

pij +∑j∈C

pij

= 1 +∑j∈T

pijEj [V ].

Cio conclude la dimostrazione.

ESEMPIO 4.2 Il collezionista di figurine. Un tale acquista ogni giorno unabustina contente una figurina con lo scopo di completare un album con N fig-urine distinte. Evidentemente, vedendo la figurina contenuta in ogni busta solodopo l’acquisto, puo accadere che trovi piu volte la stessa figurina. E spontaneochiedersi quanti giorni occorreranno, in media, perche il tale completi l’album.L’evoluzione della collezione si puo descrivere con una catena di Markov (Xn)n≥0

con insieme degli stati 0, 1, . . . , N convenendo che Xn rappresenti il numerodi figurine al giorno n e X0 = 0. La matrice di transizione e evidentemente lamatrice

0 1 0 0 0 . . . 0 0 00 1

NN−1

N 0 0 . . . 0 0 00 0 2

NN−2

N 0 . . . 0 0 0. . . . . . . . . . . . . . . . . . . . . . . . . . .0 0 0 0 0 . . . N−2

N2N 0

0 0 0 0 0 . . . 0 N−1N

1N

0 0 0 0 0 . . . 0 0 1

E chiaro che gli stati 0, . . . , N − 1 sono transienti e lo stato N e ricorrente. Iltempo medio per il completamento dell’album e rappresentato dal tempo mediodi assorbimento nella classe ricorrente N. Grazie ai risultati precedenti, sitrova

E0[TN ] =N∑

k=1

N

N − k + 1≈ N log(N + 1).

Nel caso in cui vi siano piu classi ricorrenti e chiaro che i tempi di assorbi-mento in una di esse potrebbero essere uguali a +∞ con probabilita strettamente

36

Page 37: catene di markov

positiva. Infatti, se la catena di Markov, partendo dallo stato transiente i, en-tra in una classe ricorrente C non potra piu uscire ed entrare in un’altra classericorrente C2. Nel caso in cui si verifichi questo evento, e che abbia probabilitastrettamente positiva, il tempo di assorbimento in C2 sara quindi uguale a +∞ed evidentemente anche la sua speranza. Il tempo medio di assorbimento saraquindi uguale a +∞. Il Teorema 4.3 non si puo applicare direttamente.

Una piccola variante permette pero di calcolare il tempo medio di assor-bimento per la probabilita condizionata all’evento costituito dall’entrata dellacatena di Markov nella classe ricorrente della quale si vuole calcolare il tempomedio (rispetto alla probabilita condizionata!) di assorbimento.

In questo caso bastera risolvere un sistema di equazioni simile a (14) comemostra la seguente applicazione alla rovina del giocatore in cui C = 0, T =1, . . . , N − 1 e C2 = N.

ESEMPIO 4.3 Riprendiamo l’Esempio 1.1 Rovina del giocatore. Vogliamo cal-colare il tempo medio della durata del gioco nel caso in cui il giocatore siarovinato ovvero

wi = Ei [T0 | T0 < ∞ ] .

Posto w0 = 0, le wi soddisfano le equazioni

wi = 1 + qwi−1 + pwi+1, per i = 1, . . . , N − 2,wN−1 = 1 + wN−2, per i = N − 1.

(16)

La seconda equazione e modificata, rispetto alla corrispondente di (14), pertenere conto del fatto che stiamo calcolando la speranza rispetto alla probabi-lita condizionata Pi · | T0 < ∞ per la quale si ha PXn = N = 0 e quindi,arrivando in N − 1 la catena di Markov deve ritornare in N − 2.

Consideriamo dapprima il caso p = q = 1/2. Le soluzioni delle equazioni

wi = 1 +12wi−1 +

12wi+1

hanno la forma (soluzioni dell’equazione omogenea associata piu una soluzioneparticolare (ui) dell’equazione non omogenea, linearmente indipendente dallesoluzioni precedenti dell’equazione omogenea)

wi = c1 + c2i + ui.

Si verifica facilmente che una soluzione particolare e data da ui = −i2. Conquesta scelta le wi qui sopra soddisfano (16) se e solo se w0 = 0 e wN−1 =1+wN−2 ovvero se e solo se c1 = 0 e c2 = 2(N−1). I tempi medi di assorbimentosono quindi dati da

wi = 2(N − 1)i− i2, i = 1, . . . , N − 1.

Consideriamo poi il caso p 6= q. Si vede subito che una soluzione particolaredella prima equazione (16) e data da ui = i/(q − p) e quindi tutte le soluzionisono date da

wi = c1 + c2

(q

p

)i

+i

q − p.

37

Page 38: catene di markov

Le wi qui sopra soddisfano (16) se e solo se w0 = 0 e wN−1 = 1 + wN−2 ovverose e solo se

c1 = −c2 c2 = − 2(1− p/q)2

(q

p

)−N

.

I tempi medi di assorbimento sono quindi dati da

wi =i

q − p+

2(1− p/q)2

((q

p

)−N

−(

q

p

)i−N)

, i = 1, . . . , N − 1.

ESEMPIO 4.4 I metodi studiati per determinare le probabilita di assorbimentonelle classi ricorrenti, possono essere utilizzati per studiare il comportamentolimite della catena di Markov, quando non sono soddisfatte le ipotesi del Teo-rema 3.7. Consideriamo la matrice di transizione

P =

1/2 1/2 0 01/4 3/4 0 01/4 1/4 1/4 1/40 0 0 1

,

sullo spazio degli stati 0, 1, 2, 3. Si puo verificare facilmente che 0, 1 e 3sono classi ricorrenti, mentre 2 e transiente. Partendo dallo stato 2, il processoverra assorbito in una delle due classi e le probabilita di assorbimento nellesingole classi si ottengono risolvendo un sistema. In particolare, avremo che laprobabilita di assorbimento nella classe 0, 1, si ottiene risolvendo

v =12

+14v,

cioe v = 23 , Quindi, la probabilita di assorbimento nella classe 3 sara pari

a 1 − v = 1/3. Se restringiamo l’attenzione alla classe ricorrente 0, 1 conmatrice di transizione ottenuta da P , cancellando le ultime due righe e colonne,otteniamo una nuova matrice di transizione(

1/2 1/21/4 3/4

)irriducibile e aperiodica, per cui e possibile calcolare la legge limite, che risulta(1/3, 2/3). Siccome possiamo scrivere

p(n)2,0 = PXn = 0, Xm ∈ 0, 1, per qualche m ≤ n|X0 = 2,

passando al limite si ha che

limn→∞

p(n)2,0 =

23

13

=29.

Quindi

limn→∞

P (n) =

1/3 2/3 0 01/3 2/3 0 02/9 4/9 0 1/30 0 0 1

.

38

Page 39: catene di markov

La stessa tecnica non puo essere applicata se le classi ricorrenti non sonoaperiodiche. Infatti, consideriamo il seguente esempio. Data la matrice di tran-sizione

P =

1/2 1/2 0 0 0 01/3 2/3 0 0 0 01/3 0 01/3 1/6 1/61/6 1/6 1/6 0 1/3 1/60 0 0 0 0 10 0 0 0 1 0

con spazio degli stati 0, 1, 2, 3, 4, 5.

Ci sono due classi ricorrenti C1 = 0, 1 e C2 = 4, 5. La legge limiteper la classe C1 e (2/5, 3/5). La classe C2 e periodica, quindi pij non convergeper i, j ∈ C2. Converge, comunque, il tempo medio ossia limn→∞

1n

∑n−1m=0 pm

ij =1/2. Allora, calcolate le probabilita di assorbimento nelle classi C1 e C2 partendodalla classe transiente 2, 3, si puo ottenere

limn→∞

1n

n−1∑m=0

Pm =

2/5 3/5 0 0 0 02/5 3/5 0 0 0 0

(8/17)(2/5) (8/17)(3/5) 0 0 (9/17)(1/2) (9/17)(1/2)(7/17)(2/5) (7/17)(3/5) 0 0 (10/17)(1/2) (10/17)(1/2)

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

.

ESERCIZI

Es 4.1 Data una catena di Markov con insieme degli stati 1, 2, 3, 4, 5 e matricedi transizione

P =

1/5 1/5 1/5 1/5 1/51/3 1/3 1/3 0 00 1/3 1/3 1/3 00 0 0 2/3 1/30 0 0 1/2 1/2

Determinare quali sono gli stati ricorrenti e gli stati transienti. Calcolare laprobabilita di assorbimento degli stati transienti negli stati ricorrenti. Calcolarela probabilita, partendo dallo stato 1, di arrivare nello stato 4 senza passaredallo stato 3.

Es 4.2 Un pezzo semilavorato entra in una linea produttiva da cui puo usciredifettoso con probabilita 0.2 oppure ricuperabile con probabilita 0.3 oppurebuono con probabilita 0.5. I pezzi difettosi sono scartati, i pezzi buoni vengonoportati in magazzino come pezzi finiti; i pezzi ricuperabili rientrano nella lineaproduttiva per essere nuovamente lavorati. Descrivere il processo di lavorazionemediante una catena di Markov. Sapendo che un pezzo e ricuperabile, calcolarela probabilita che dopo due processi di lavorazione sia classificabile come buono.

39

Page 40: catene di markov

Calcolare la probabilia che alla fine del ciclo produttivo un pezzo recuperabile siabuono. Calcolare il tempo medio di un ciclo produttivo di un pezzo recuperabile.

Es 4.3 un giocatore muove la pedina tra i vertici (numerati da 1 a 4) e il centro(0) di un quadrato con la seguente ”strategia”. Ad ogni passo lancia un dadoa 4 facce equilibrato: se la pedina si trova in 0, si muovera nel vertice connumero pari al risultato del dado. Se la pedina si trova in un diverso vertice,questa si spostera in 0 se il risultato del lancio e pari, altrimenti avanzera diuna posizione in senso antiorario sul perimetro esterno del circuito. Se la pedinaparte, al tempo iniziale, dal vertice 1, qual ‘’e il tempo medio necessario perchela pedina visiti il vertice 0 per la prima volta? Qual e la probabilita che lapedina visiti il vertice 0 per la prima volta senza passare mai dal vertice 4?

Es 4.4 Una moneta equilibrata e lanciata ripetutamente fino a che non si ot-tengono come risultati due ”teste” consecutive. Indicare con Xn il numero di”teste” consecutive ottenute dopo l’n−esimo lancio. Trovare il numero mediodi lanci richiesti.

40

Page 41: catene di markov

5 Criteri di transienza o ricorrenza

La caratterizzazione degli stati ricorrenti del Teorema 2.11 e spesso difficilmenteutilizzabile nelle applicazioni. In questo paragrafo dimostreremo due criteri perclassificare gli stati di una catena di Markov irriducibile.

Teorema 5.1 Sia (Xn)n≥0 una catena di Markov irriducibile con insieme deglistati I. Condizione necessaria e sufficiente affinche ogni stato sia transiente eche esista una famiglia (yj)j∈I limitata e non costante che soddisfi le equazioni∑

k∈I

pjkyk = yj , (17)

per tutti gli stati j ∈ I tranne al piu uno.

Dimostrazione. Denotiamo con z l’unico stato che eventualmente nonsoddisfa la (17). Consideriamo la catena di Markov (Xn)n≥0 con matrice ditransizione

pij =

pij se i 6= z,δij se i = z,

ottenuta dalla (Xn)n≥0 trasformando lo stato z in uno stato assorbente. Co-minciamo col far vedere che la condizione e necessaria. La catena di Markov(Xn)n≥0 e transiente; dunque esiste almeno uno stato i 6= z per il quale si abbia

f∗iz = PiTz < +∞ < 1.

Consiamo allora le probabilita di assorbimento in z (vj)j≥0 relative alla catenadi Markov (Xn)n≥0 e poniamo v0 = 1. Osserviamo che

vj = Pj

(∪∞n=1Xn = z

)= PjX1 = z+

∞∑n=2

PjXn = z, Xn−1 6= z, . . . , X1 6= z

= PjX1 = z+∞∑

n=2

PjXn = z,Xn−1 6= z, . . . ,X1 6= z

= Pj (∪∞n=1Xn = z) = f∗jz < 1

per qualche j 6= z. Percio, grazie al Teorema (4.2), e verificata l’equazione

∞∑k∈I

pjkvk = vj

per ogni j ∈ I ovvero la successione limitata e non costante (vk)k≥0 soddisfa leequazioni (17).

41

Page 42: catene di markov

Dimostriamo ora che la condizione e sufficiente. Una soluzione limitata(yk)k≥0 delle equazioni (17) soddisfa evidentemente le equazioni

∞∑k∈I

pjkyk = yj

per ogni stato j. Iterando n volte queste relazioni si trovano le identita

∞∑k∈I

p(n)jk yk = yj

per ogni stato j e n ≥ 1. Se la catena di Markov (Xn)n≥0 fosse ricorrente, siavrebbe

limn→∞

p(n)jz lim

n→∞PjXn = z = lim

n→∞PjTz ≤ n = 1

da cui, per ogni j 6= z,

|yj − yz| = limn→∞

|yj − p(n)jz yz|

= limn→∞

∣∣∣∣∣∣∑k 6=z

p(n)jk yk

∣∣∣∣∣∣≤ sup

k 6=z|yk| · lim

n→∞

∑k 6=z

p(n)jk

= supk 6=z

|yk| · limn→∞

(1− p(n)jz ) = 0.

Cio implica che la famiglia (yk)k∈I e costante.

Teorema 5.2 Sia (Xn)n≥0 una catena di Markov irriducibile con insieme deglistati N. Condizione sufficiente affinche ogni stato sia ricorrente e che esista unasuccessione (yj)j≥0 tale che

∞∑k=0

pjkyk ≤ yj , per ogni j > 0 e limk→∞

yk = +∞. (18)

Dimostrazione. Utilizzeremo le stesse notazioni della dimostrazione delTeorema 5.2. E chiaro che, la diseguaglianza

∞∑k=0

pjkyk ≤ yj (19)

vale per ogni j ≥ 0. Inoltre la successione (yj)j≥0 e limitata inferiormentee percio, considerando eventualmente una successione della forma (yj + c)j≥0

42

Page 43: catene di markov

con c > 0, possiamo supporre che la (yj)j≥0 sia a valori strettamente positivi.Iterando n volte l’equazione 19 otteniamo le diseguaglianze

∞∑k=0

p(n)jk yk ≤ yj

per ogni j ≥ 0 ed ogni n ≥ 1. Nella catena di Markov (Xn)n≥0, lo stato 0 ericorrente e tutti gli altri stati sono transienti poiche

Pj

(∩∞n=1Xn 6= j

)≥ Pj (∩∞n=1Xn = 0) > 0

per ogni j > 0 essendo la catena di Markov irriducibile.Fissato ε > 0 sia M(ε) un intero tale che yj > ε−1 per ogni j > M(ε). Per

ogni stato i ≥ 0 possiamo scrivere le diseguaglianze

∑j>0

p(n)ij =

M(ε)∑j=1

p(n)ij +

∑j>M(ε)

p(n)ij

≤M(ε)∑j=1

p(n)ij + ε

∑j>M(ε)

p(n)ij yj

≤M(ε)∑j=1

p(n)ij + εyi.

Quindi, passando al limite,

0 ≤ lim supn→∞

∑j>0

p(n)ij ≤ εyi

ovvero, data l’arbitrarieta di ε, la successione (∑

j>0 p(n)ij )n≥0 converge verso 0

per ogni (i, j) 6= (0, 0). Ne segue che

limn→∞

p(n)i0 = lim

n→∞

1−∑j>0

p(n)ij

= 1.

Osservando che

Pi (∪∞k=1Xk = 0) = limn→∞

Pi (∪nk=1Xk = 0)

= limn→∞

PiXn = 0

= limn→∞

p(n)i0 = 1

per ogni i > 0, troviamo l’eguaglianza

P0 (∪∞k=1Xk = 0) = p00 +∑j>0

p0jPj (∪∞k=1Xk = 0)

43

Page 44: catene di markov

= p00 +∑j>0

p0j = 1

che implica che 0 e ricorrente per la catena di Markov (Xn)n≥0. Cio concludela dimostrazione.

ESEMPIO 5.1 Consideriamo la catena di Markov dell’Esempio 1.6. Nell’Esempio2.4 abbiamo verificato che, sotto le condizioni

0 < a0 < 1, 0 < a0 + a1 < 1

la catena di Markov e irriducibile. Supponiamo quindi che queste condizionisiano verificate e denotiamo

λ =∞∑

k=1

kak

il numero medio di clienti che arrivano in una unita di tempo. Utilizzando iTeoremi 5.1 e 5.2 possiamo dimostrare che la catena di Markov e:

a) transiente se λ > 1,

b) ricorrente se 0 < λ ≤ 1.

Per verificare l’affermazione a) cerchiamo una soluzione limitata e non costantedelle equazioni (5.1) della forma yj = ξj con ξ ∈]0, 1[. La successione (ξj)j≥0

soddisfa le (5.1) se e solo se∞∑

k=j−1

ak−j+1ξk = ξj , per ogni j > 0

ovvero∞∑

k=0

akξk = ξ.

La funzione

f : [0, 1] → [0, 1], f(ξ) =∞∑

k=0

akξk.

ha soddisfa le condizioni f(0) = a0 > 0, f(1) = 1 e, grazie al Lemma di Abel,

limη→1−

f ′(η) = λ.

Pertanto, se λ > 1, esiste un numero reale ξ0 ∈]0, 1[ tale che f(ξ0) = ξ0. Lasuccessione (ξj

0)j≥0 e quindi una soluzione limitata non costante delle equazioni5.2.

Per verificare l’affermazione b) basta verificare che la successione (j)j≥0 sod-disfa le 18. Per ogni j > 0 si ha infatti

∞∑k=0

pjkyk =∞∑

k=j−1

ak−j+1k

44

Page 45: catene di markov

=∞∑

k=0

ak(k + j − 1)

=∞∑

k=0

kak + (j − 1)∞∑

k=0

ak

= j + λ− 1 ≤ j.

Si puo dimostrare inoltre (ma e piuttosto laborioso) che gli stati sono ricorrentipositivi se m < 1 e ricorrenti nulli se m = 1.

ESEMPIO 5.2 Passeggiata casuale su N (vedi Esempio 1.4).

45

Page 46: catene di markov

6 Convergenza verso la legge invariante

Mostreremo ora come si puo ottenere semplicemente una stima della velocita diconvergenza verso la legge invariante. Cominciamo introducendo una distanzatra le leggi di probabilita su I nel modo seguente

‖µ− ν‖ =∑k∈I

|µk − νk|.

Si dimostra facilmente che l’insieme delle leggi su I munito di questa distanza euno spazio metrico completo. Osserviamo inoltre che ogni matrice di transizioneP agisce come una contrazione sulle leggi su I. Si ha infatti

‖µP − νP‖ =∑j∈I

∣∣∣∣∣∑k∈I

(µk − νk)pkj

∣∣∣∣∣≤

∑k∈I

|µk − νk|∑j∈I

pkj

= ‖µ− ν‖ .

Teorema 6.1 Se esiste un intero k ≥ 1 per il quale il numero reale c ∈ [0, 1]

c =∑j∈I

(infi∈I

p(k)ij

)sia strettamente positivo allora la catena di Markov ha un’unica legge invarianteπ e, per ogni legge µ su I ed ogni intero n ≥ 1 vale la diseguaglianza

‖µPn − π‖ ≤ (1− c)[n/k] ‖µ− π‖ . (20)

Dimostrazione. Consideriamo la matrice di transizione Q = (qij)i,j∈I

cosı definitaqij = c−1 inf

l∈Ip(k)lj .

Si tratta evidentemente di una matrice stocastica per come e definito il numeroreale c. Inoltre si ha p

(k)ij ≥ cqij per ogni coppia di stati i, j e∑

j∈I

(p(k)ij − cqij) =

∑j∈I

p(k)ij − c

∑j∈I

qij = 1− c.

Dunque la matrice R = (1−c)−1(P k−cQ) e una matrice stocastica e la matriceP k si puo scrivere nella forma

P k = cQ + (1− c)R.

Per ogni coppia µ, ν di leggi su I le leggi µQ, νQ coincidono e si trova subitola diseguaglianza∥∥µP k − νP k

∥∥ = (1− c) ‖µR− νR‖ ≤ (1− c) ‖µ− ν‖ .

46

Page 47: catene di markov

Ne segue che l’applicazione µ → µP k e una contrazione stretta nello spaziometrico completo delle leggi su I e quindi possiede un unico punto fisso π.Dalla relazione π = πP k si ottiene subito πP = (πP )P k; dunque anche la leggeπP e un punto fisso per µ → µP k e, pertanto, coincide con π. Cio dimostrache π e l’unica legge invariante. Infine, dimostrare la diseguaglianza 20, bastaosservare che, per ogni intero n ≥ 1, si ha∥∥µPnk − π

∥∥ ≤ (1− c)n ‖µ− π‖

e, posto dn = ‖µPn − π‖, la successione (dn)n≥0 e non crescente. Quindi, sem = [n/k], si ha mk ≤ n e dn ≤ dmk ≤ (1− c)m ‖µ− π‖.

ESEMPIO 6.1 Applicazione al problema del collezionista di figurine dell’Esempio4.2. Osservare che, per k = N , si ha c = N !/NN .

47

Page 48: catene di markov

7 Algoritmo di Metropolis

In questo capitolo studieremo un algoritmo, noto come algoritmo di Metropo-lis, per la ricerca dei punti di minimo assoluto di una funzione

V : 1, 2, . . . , N →]0,+∞[,

utilizzando la modellizzazione fornita dalla teoria sulle catene di Markov. Talealgoritmo e particolarmente efficace quando N e molto grande, quindi, l’algoritmobanale consistente nel calcolo e confronto dei valori assunti dalla funzione V etroppo costoso in termini di tempo.

Questo problema ha una classica applicazione nella risoluzione del cosiddetto”problema del commesso viaggiatore”. Il commesso deve visitare N citta in Ngiorni, rimanendo un giorno in ognuna e si chiede in che ordine le deve visitarein modo da minimizzare il costo dei viaggi. Se le citta in questione sono adesempio i capoluoghi di provincia italiani, allora N = 102 e i possibili itinerarisono N !, che e un numero dell’ordine di 10162.

In particolare, l’algoritmo di Metropolis cerca i punti di minimo assolutoseguendo l’evoluzione di una opportuna catena di Markov, in generale non omo-genea, con insieme degli stati I = 1, 2, . . . , N che, ad ogni istante, ha proba-bilita maggiore di entrare negli stati nella quale V ha valore piu piccolo e, colpassare del tempo la probabilta di entrare negli stati in cui V ha valore grande esempre piu piccola. In questo modo la catena di Markov dovrebbe ”convergere”ai punti di minimo assoluto non arrestandosi nei punti di minimo relativo.

Lo stesso algoritmo si puo utilizzare per simulare la scelta di uno stato i ∈ I,con un’assegnata distribuzione π. Infatti i ”classici ”metodi di simulazione sonoinutilizzabili se la cardinalita di I e molto grande. Stesse tecniche, si stannoutilizzando nella teoria dei problemi inversi di ricostruzione di immagini percalcolare il valore medio di una variabile aleatoria e quindi per approssimare ilcalcolo di integrali.

L’idea e la seguente: supponiamo di poter costruire una catena di Markov(Xn)n∈N irriducibile e aperiodica, con un’unica legge limite π. Se noi simuliamol’evoluzione della catena, per il Teorema 3.3, la legge di Xn al tempo n, quandon → +∞, convergera a π, indipendentemente dalla legge iniziale scelta.

Prima di enunciare la proposizione principale di questo capitolo, conside-riamo una matrice stocastica simmetrica e irriducibile Q = (qij)i,j∈I e π unalegge di probabilita su I, tale che πj > 0, per ogni j ∈ I. Poniamo

pij =

qij se πj ≥ πi,qij

πj

πise πj < πi,

1−∑

j 6=i pij se i = j.(21)

Proposizione 7.1 Sia π una distribuzione di probabilita non uniforme. Lacatena di Markov associata alla matrice di transizione P , definita da (21), haπ come unica legge invariante.

48

Page 49: catene di markov

Dimostrazione. Si dimostra facilmente che P = (pij)i,j∈I e ancora unamatrice stocastica. Inoltre, si ha che

πipij = πjpji,

cioe π e reversibile per P (vedi Esercizio 3.4), quindi π e una legge invarianteper P . infatti

(πP )j =∑

i

πipij

=∑

i

πjpji = πj .

Si osserva anche che P e una matrice irriducibile. Infatti, se gli stati i, j ∈ I,i 6= j, sono tali che qij > 0, allora, per definizione pij > 0. Quindi l’irriducibilitadi P segue dalla scelta di Q. Inoltre, se i 7→ πi non e costante, allora P eaperiodica. Infatti, consideriamo l’insieme M = i ∈ I : πi = maxj∈I πj.Siccome Q e irriducibile esistono i0 ∈ M e j0 ∈ M c, tali che qi0j0 > 0. Inoltre siha che πi0 > πj0 per definizione di M . Quindi, sapendo che pij ≤ qij . se i 6= j,si ottiene che

pi0i0 = 1−∑j 6=i0

pi0j

= 1−∑

j 6=i0,j0

pi0j − pi0j0

≥ 1−∑

j 6=i0,j0

qi0j − qi0j0

πj0

πi0

≥ qi0i0 + qi0j0

(1− πj0

πi0

)≥ qi0j0

(1− πj0

πi0

)> 0.

Abbiamo quindi dimostrato che, se π non e uniforme, e possibile costruireuna catena di Markov, associata a una matrice di transizione P (costruita apartire da una qualunque matrice simmetrica e irriducibile Q) irriducibile eaperiodica, tale che ammetta π come legge limite.

Il metodo per simulare la catena di Markov associata alla matrice P si chiamaalgoritmo di Metropolis. Vediamo alcune applicazioni.

ESEMPIO 7.1 Supponiamo, ad esempio, di voler simulare la scelta di un nu-mero i ∈ E a caso con una legge assegnata π. Come abbiamo gia osservato,i metodi ”classici” di generazione di numeri casuali spesso sono inapplicabilise la cardinalita di E e molto elevata. Possiamo, pero costruire una variabilealeatoria con legge approssimativamente uguale a π. A partire da una matricesimmetrica e irriducibile Q, si costruisce P , data da (21) e si simula la catena di

49

Page 50: catene di markov

Markov (Xn)n associata. Questo significa che se Xn = i e sufficiente sceglierea caso j con legge qij dopo di che se πj ≥ πi si pone Xn+1 = j, altrimenti sipone Xn+1 = j con probabilita πj

πi, mentre con probabilita 1 − πj

πisi rifiuta la

transizione e si lascia Xn+1 = i.

Ritorniamo ora al problema del commesso viaggiatore e, in generale, allaricerca dei punti di minimo assoluto di una funzione V . Consideriamo, per ogniε > 0, la legge su 0, . . . , N non uniforme πε data da

πεi =

e−V (i)/ε

Zε,

con Zε costante di normalizzazione. Scelta una matrice simmetrica e irriducibileQ, si puo costruire a partire da (21) una matrice di transizione P (ε). E chiaroche per calcolare la matrice P (ε), in generale, dovremmo calcolare il valore dellafunzione V per tutti gli interi i ∈ 0, . . . , N e quindi non avremmo aggiratol’ostacolo iniziale se non scegliessimo una matrice Q con molti elementi nulli.Ad esempio possiamo scegliere

Q =

23

13 0 0 . . . 0 0 0

13

13

13 0 . . . 0 0 0

0 13

13

13 . . . 0 0 0

. . . . . . . . . . . . . . . . . . . . . . . .0 0 0 0 . . . 1

313

13

0 0 0 0 . . . 0 13

23

.

In questo caso per determinare la probabilita di transizione (P (ε))ij con i fissatooccorre calcolare i valori di V in al piu due punti. A questo punto si puoprocedere con la simulazione della catena di Markov associata alla matrice P (ε),come nell’esempio precedente.

Osserviamo che se ε e piccolo, la distribuzione πε si concentra su quegli statisu cui V e piccola, Si puo anzi dimostrare che se i1, . . . , ik sono punti di minimoassoluto per V , allora per ε → 0, πε converge alla distribuzione uniforme sui1, . . . , ik.

Si puo anche dimostrare che prendendo una successione (εn)n≥0 convergenteverso 0 abbastanza lentamente, la catena di Markov non omogenea (Xn)n≥0

che ha P (εn) come matrice di transizione al tempo n converge in legge verso lalegge uniforme sui punti di minimo assoluto di V . La dimostrazione e piuttostotecnica e sara omessa. Questa procedura, in cui si fa variare il valore di εviene chiamata simulated annealing ed e un’utile tecnica per certi problemidi ottimizzazione.

50

Page 51: catene di markov

8 Catene di Markov a tempo continuo

Una catena di Markov a tempo continuo (X(t))t∈I , dove I e un inter-vallo della retta reale, e un sistema a stati discreti E e tempo continuo in cuil’evoluzione della variabile di stato X(t) e caratterizzata dalla proprieta marko-viana

PX(tk+1) = xk+1|X(tk) = xk, . . . , X(t0) = x0 = PX(tk+1) = xk+1|X(tk) = xk,

per ogni scelta di t0, t1, . . . , tk+1 tale che t0 ≤ t1 ≤ · · · ≤< tk+1. Tale definizioneestende in maniera naturale la (1) nel caso continuo. In particolare, si ha cheX(t) condensa tutta l’informazione passata (per τ ≤ t) ai fini della valutazioneprobabilistica dell’evoluzione della catena di Markov a tempo continuo per τ > t.

Come nel caso discreto, l’evoluzione di una catena di Markov a tempo con-tinuo e governata dalle funzioni di transizione

pij(s, t) = PX(t) = j|X(s) = i,

per ogni i, j appartenente all’insieme degli stati E e s ≤ t. Una volta fissatis e t, pij(s, t) si puo ancora vedere come elemento di una matrice stocastica.Infatti, dal teorema della probabilita totale, si ha che, per s ≤ τ ≤ t

pij(s, t) =∑r∈E

pir(s, τ)prj(τ, t), (22)

che e l’equivalente dell’equazione di Chapman–Kolmogorov nella sua versione atempo continuo. Utilizzando la notazione matriciale P (s, t) = (pij(s, t))i,j∈E ,risultera P (s, s) = I e

∑j∈E pij(s, t) = 1. Inoltre l’identita (22) puo essere

scritta comeP (s, t) = P (s, τ)P (τ, t), (23)

per s ≤ τ ≤ t. Anche nel caso continuo, si definisce la classe delle catene diMarkov omogenee, ovvero catene di Markov a tempo continuo dipendenti das e t esclusivamente attraverso la differenza τ = t − s. In particolare si avrache P (s, s + τ) e indipendente da s. Con un abuso di linguaggio, indichiamoP (s, s + τ) = P (τ). In questo caso l’identita (23), diventa

P (t + h) = P (t)P (h). (24)

Nel seguito tratteremo solo catene di Markov a tempo continuo omogenee.

Se assumiamo in aggiunta che

limt→0+

P (t) = I,

dalla (24) e si ricava facilmente che P (t) e continua non solo in 0, ma per ognit > 0. Infatti, si ha che

limh→0+

P (t + h) = limh→0+

P (t)P (h) = P (t).

51

Page 52: catene di markov

Inoltre, per t > 0 e 0 < h < t, (24) diventa

P (t) = P (t− h)P (h).

Siccome P (h) → I, quando h → 0, P (h)−1 esiste per h sufficientemente piccoloe h → 0+P (h)−1 = I, allora

P (t) = P (t) limh→0+

P (h)−1 = limh→0+

P (t− h),

da cui segue la continuita di P (t).In realta, si puo dimostrare che P(t) non e solo continua, ma anche differen-

ziabile. InfattiP (t + h)− P (t) = P (t)(P (h)− I),

per t, h > 0. Dividendo per h e passando al limite per h → 0,si ha

limh→0

P (t + h)− P (t)h

= P (t) limh→0

P (h)− I

δt.

Indichiamo con Q la matrice

Q = limh→0

P (h)− I

δt,

detta matrice dei rate di transizione o generatore infinitesimale. Sidimostra che qij esistono (vedi [4]): in generale qii possono assumere valoreinfinito, mentre qij , con i 6= j sono sempre finiti. Nel caso di catene di Markova stati finiti, si ha che 0 ≥ −qii < +∞.

Si ottiene cosıd

dtP (t) = P (t)Q,

o analogamented

dtP (t) = QP (t). (25)

Imponendo le condizioni iniziali P (0) = I, si ottiene che P (t) = eQt, nel sensoche

P (t) = I + Qt +Q2

2!t2 + . . . ,

il che spiega in parte il nome della matrice Q.Per una Catena di Markov a tempo continuo non omogenea, il generatore

infinitesimale dipendera da t.

Un processo stocastico particolarmente importante, che rientra nella classedelle catene di Markov a tempo continuo e il processo di Poisson. Lo intro-duciamo mediante un esempio.

ESEMPIO 8.1 Indichiamo con Xn la durata di certi ”pezzi” di un sistema chevengono sostituiti non appena si guastano. Possiamo supporre che (Xn)n≥1

sia una successione di variabili aleatorie indipendenti con legge esponenziale di

52

Page 53: catene di markov

parametro λ, con λ > 0. Posto Tn = X1 + · · ·+ Xn il tempo di vita del sistemadopo il cambio di n pezzi. Per ogni numero reale t ≥ 0 definiamo Nt a valori inN ∪ +∞

Nt =∑n≥1

1Tn≤t

La variabile aleatoria Nt rappresenta quindi il numero di guasti nel tempo [0, t].E abbastanza semplice provare che Nt ha legge di Poisson di parametro λt perogni t > 0. In particolare PNt = +∞ = 0. Inoltre il processo (Nt)t≥0 haincrementi indipendenti, ovvero per ogni intero n ≥ 1 e per ogni 0 < t1 < . . . <tn le variabili aleatorie Nt1 , Nt2 − Nt1 , . . . , Ntn

− Ntn−1 sono indipendenti. Lafamiglia di variabili aleatorie (Nt)t≥0 cosı costruita e una versione del processodi Poisson.

In generale si ha che

Definizione 8.1 Si chiama processo di Poisson di parametro λ > 0 unafamiglia (Nt)t≥0 di variabili aleatorie su uno spazio probabilizzato (Ω,F , P) taliche

1. per ogni ω ∈ Ω la traiettoria ω → Nt(ω) e regolare;

2. per ogni intero n ≥ 1 e per ogni 0 < t1 < . . . < tn le variabili aleatorieNt1 , Nt2−Nt1 , . . . , Ntn

−Ntn−1 sono indipendenti e hanno legge di Poissoncon parametri rispettivamente λt1, λ(t2 − t1), . . . , λ(tn − tn−1).

A questo punto, e possibile fornire un’interpretazione fisica dei coeffici-enti della matrice Q = (qij)i,j∈E . Consideriamo l’equazione scalare relativaall’equazione differenziale (25) nel caso i = j, si ottiene

∂tpii(t)|t=0 = qii,

che puo essere riscritta come

−qii =∂

∂t(1− pii(t))|t=0.

Siccome 1 − pii(t) rappresenta la probabilita che la catena di Markov lasci lostato i in un intervallo di lunghezza t, si ottiene che −qii puo essere interpretatocome la frequenza con cui si verifica la transizione ”uscita dallo stato i”. Inmaniera analoga il parametro qij , con i 6= j, puo essere interpretato come lafrequenza con cui si verifica la transizione ”passaggio dallo stato i allo stato j”.Inoltre, siccome P e una matrice di transizione si ottiene la seguente relazionetra gli elementi della matrice Q

−qii =∑j 6=i

qij .

Questa relazione andrebbe giustificata con opportune ipotesi nel caso di catenedi Markov a stati infiniti.

53

Page 54: catene di markov

ESEMPIO 8.2 Nel caso particolare del processo di Poisson Nt descritto nell’esem-pio precedente, si vede facilmente che pii(t) = eλt, da cui segue che −qii = λ,che conferma l’interpretazione fisica data per qii. Infatti

PNt+h > i|Nt = i = 1− e−λh,

per ogni h > 0 e i ∈ E, da cui si ottiene che

d

dhPNt+h > i|Nt = i|h=0 = λ.

La matrice Q gioca un ruolo fondamentale nell’analisi di transitorio e aregime di una catena di Markov a tempo continuo omogenea. Infatti, in modoanalogo a quanto visto per le catene di Markov a tempo discreto, si possonodefinire le leggi delle singole variabili aleatorie X(t), come

πj(t) = PX(t) = j,

tali che, per il teorema della probabilita totale, devono soddisfare la relazionematriciale

π(t) = π(0)P (t) = π(0)eQt.

Differenziando rispetto a t, diventa

d

dtπ(t) = π(t)Q (26)

Nell’analisi a regime delle catene di Markov a tempo continuo omogenee, ci sichiede se i limiti limt→+∞ πj(t) esistono e se risultano indipendenti dalla leggeiniziale di X(0). Al tal scopo, esiste un risultato importante che estende al casocontinuo il Teorema 3.3.

Teorema 8.2 In una catena di Markov a tempo continuo (X(t))t≤0 irriducibilecon spazio degli stati finiti, esiste un’unica distribuzione limite π = limt→+∞ π(t),tale che πj > 0, per ogni j ∈ E. Tale legge risulta indipendente da π(0). Infine,il vettore π si determina in maniera univoca risolvendo il sistema di equazioni

πQ = 0,∑j∈E

πj = 1.

ESEMPIO 8.3 Si consideri un sistema produttivo costituito da un’unica ma-cchina che lavora un pezzo per volta e ha un tempo di lavorazione con leggeesponenziale di parametro λ1. E previsto un tempo di setup tra due lavorazionisuccessive con legge esponenziale di parametro λ2. La macchina non e soggettaa usura, quindi il tempo fra due guasti ha legge esponenziale di parametro λ3.Infine, supponiamo che la macchina guasta venga subito riparata e il tempo diriparazione ha ancora una densita esponenziale di parametro λ4.

54

Page 55: catene di markov

Possiamo schematizzare gli stati del sistema con l’insieme 0, 1, 2, dove 0:fase di setup, 1: in lavorazione, 2: in riparazione. Il sistema e gestito in modotale che la macchina riparata puo riprendere la lavorazione del pezzo che stavalavorando prima del guasto. In questo caso la matrice Q diventa −λ2 −λ2 0

λ1 −(λ1 + λ3) λ3

0 λ4 −λ4

E facile vedere che la catena di Markov e irriducibile con spazio degli stati finitie, quindi, tutti i suoi stati sono ricorrenti positivi. E possibile trovare la leggelimite π, risolvendo il sistema πQ = 0.

Contrariamente potremmo considerare il caso in cui la macchina riprenda lalavorazione sempre da un pezzo nuovo. In questo caso il generatore infinitesimaleQ′ diventa −λ2 −λ2 0

λ1 −(λ1 + λ3) λ3

λ4 0 −λ4

.

Risolvendo il sistema π′Q′ = 0 si ottiene che π′0 > π0, π′1 < π1 e π′2 < π2 equesto porta a concludere che la prima politica sembra essere migliore rispettoalla seconda.

Diamo ora un esempio significativo di catene di Markov a tempo continuocon spazio degli stati infinito.

ESEMPIO 8.4 Processi di nascita e morte. I processi di nascita e morte pos-sono essere considerati come l’estensione al caso continuo delle passeggiatealeatorie. Tali processi sono importanti perche modellizzano molti fenomeniin varie discipline. Consideriamo (X(t))t≥0 una catena di Markov omogenea atempo continuo con insieme degli stati N, tale che

(1) pi,i+1(h) = λih + o(h), i ≥ 0,

(2) pi,i−1(h) = µih + o(h), i ≥ 1,

(3) pi,i(h) = 1− (λi + µi)h + o(h), i ≥ 0,

(4) pi,j(0) = δij ,

(5) µ0 = 0, λ0 > 0, µi, λi > 0, i ≥ 1,

con o(h) un funzione infinitesima per h ↓ 0, eventualmente dipendente da i. Inquesto caso valgono le ipotesi per determinare il generatore infinitesimale Q,che risulta essere la matrice

−λ0 λ0 0 0 · · ·µ1 −(µ1 + λ1) λ1 0 · · ·0 µ2 −(µ2 + λ2) λ2 · · ·0 0 µ3 −(µ3 + λ3) · · ·· · · · · · · · · · · · · · ·

55

Page 56: catene di markov

ESERCIZI

Es 8.1 Lungo un cavo sottomarino compaiono dei difetti, modelizzabili tramiteun processo di Poisson di parametro 0.1. Indichiamo con Xn il numero di difettientro ennesimo miglio di cavo. Qual e la probabilita che nessun difetto compaianelle prime due miglia di cavo? Sapendo che non si sono riscontrati difetti nelleprime due miglia, qual e la probabilita di non aver difetti tra il secondo e il terzomiglio?

Es 8.2 Supponiamo che la posizione in un’azienda possa essere occupata daun lavoratore per ognuno dei tre livelli: principiante, junior, senior. Sia X(t)il livello della persona nella posizione al tempo t e assumiamo che X(t) evolvacome una catena di Markov con matrice infinitesimale

Q =

−10 10 02 −5 31 0 −1

.

Calcolare la probabilita che alla fine della carriera, un lavoratore raggiunga illivello senior.

56

Page 57: catene di markov

9 Applicazioni: le catene di Markov in genetica

La teoria delle catene di Markov puo essere utilizzata per simulare l’andamentodella frequenza genica sotto l’influenza delle mutazioni e della selezione. Il primoad utilizzare questo modello fu S. Wright negli anni Sessanta.

Inizialmente, descriviamo il modello di riproduzione casuale nel caso piusemplice in cui viene trascurato l’intervento delle mutazioni e delle selezioni.Supponiamo di lavorare con una popolazione fissa di 2N geni, suddivisa in genidi topo a e A. Assumiamo inoltre che la composizione di una nuova generazionesia determinata come da 2N estrazioni indipendenti e con reiserimento, ossiaogni nuovo individuo generato da una popolazione costituita da i a−geni e(2N − i) A−geni, avra probabilita di essere di tipo a (risp. A)

pi =i

2N,

(risp. qi = 2N−i2N ,) indipendentemente uno dall’altro. Inoltre selezioni ripetute

sono fatte con reinserimento. Con questa procedure si definisce una catena diMarkov (Xn)n≥0, dove indichiamo con Xn il numero di a−geni nell’ennesimagenerazione fra una popolazione costante di 2N elementi. Lo spazio degli staticontiene, quindi, 2N + 1 valori. La probabilita di transizione sara

PXn+1 = j|Xn = i =(

2N

j

)pj

i q2N−ji . (27)

Si puo osservare che gli stati 0 e 2N sono completamente assorbenti, cioeuna volta che Xn = 0 (risp. = 2N), allora Xn+h = 0 (risp. = 2N), per ognih ∈ N.

Un problema interessante e determinare la probabilita che, partendo da unapopolazione con i a−tipi, con i 6= 0, 2N , si arrivi a una popolazione pura, ovveroformata solo da a−tipi o A−tipi. In particolare, questo coincide con il calcolodella probabilita di assorbimento da un qualsiasi stato transiente i nella classedegli stati riccorrenti 0, 2N.

Un modello piu realistico tiene ovviamente conto anche dei fattori muto-geni. Assumiamo che, prima della formazione di una nuova generazione, ognigene possa cambiare nell’altro tipo. In particolare, assumiamo che a → A conprobabilita α e A → a con probabilita β. Ipotizziamo ancora che la nuovagenerazione sia formata da 2N individui, ottenuti da ”estrazioni” indipendentie con reinserimento. Definito pi come nel caso precedente, possiamo assumereche

pi =i

2N(1− α) +

2N − i

2Nβ,

qi = 1− pi. (28)

La motivazione di questa scelta dipende dal fatto che, una volta avvenuta lamutazione (prima della nuova generazione) il numero medio di a−tipi e i(1−α)+

57

Page 58: catene di markov

(2N−i)β. Siccome la probabilita (mediata rispetto a tutte le possibili variazioni)e 1

2N per il numero medio di a−tipi presenti, questo porta alla formula trovata.Le probabilita di transizione associate alla nuova catena di Markov, sono definitecome in (27), a partire dai valori pi e qi dati in (28).

Se α e β sono positivi, allora ogni stato risulta essere ricorrente e non si puoconcludere, come nel caso precedente, che una volta raggiunti gli stati 0 o2N, la popolazione continui a rimanere pura. Nonostante questo, e possibilecalcolare la legge limite, tale distribuzione e detta distribuzione stazionaria dellafrequenza genica.

Aggiungiamo ora, l’influenza delle forze selettive a favore, o contrarie, aun gene. Supponiamo che il gene di tipo a sia avantaggiato, in modo che ilnumero di discendenti attesi sia (1 + s)-volte quello previsto per il tipo A, cons piccolo e positivo. In questo caso si sostituiscono ai valori di pj e qj calcolatiprecedentemente con

pj =(1 + s)j2N + sj

,

qj = 1− pj

e si costruisce la nuova generazione utilizzando un campionamento binomialecome nel caso precedente. Infatti, se si considera inizialmente una popolazioneformata da j a − geni, allora nella generazione successiva il numero medio dia−geni e A−geni sara rispettivamente

2N(1 + s)j2N + sj

, 2N2N − j

2N + sj.

Confrontando i due valori ottenuti, si ottiene che il rapporto fra il numero mediodi a−geni e A−tipi nella (n + 1)−generazione e

(1 + s)j2N + sj

=(

1 + s

1

)numero di a− geni nell’n−esina generazionenumero di A− geni nell’n−esina generazione

,

e questo riassume il significato di selezione.

58

Page 59: catene di markov

10 Applicazioni: lotto economico d’acquisto

Mostreremo ora un’applicazione dei processi puntuali alla determinazione dellotto economico d’acquisto. Il problema consiste nell’ottimizzare la gestionedelle scorte di un’azienda acquista un certo prodotto in lotti di una certa quan-tita e lo rivende per unita.

Per descrivere il modello supponiamo che:

1. i tempi Xn trascorsi tra la (n− 1)-esima ed n-esima vendita sono variabilialeatorie con la stessa speranza m,

2. il costo di ordinazione K e indipendente dalla quantita di merce ordinata,

3. il costo di stoccaggio per unita di merce per unita di tempo e c.

Supporremo inoltre che l’azienda si rifornisca con S unita di prodotto non ap-pena il magazzino sia vuoto.

Nelle ipotesi fatte le variabili aleatorie

Tn = X1 + · · ·+ Xn e Nt =∑n≥1

1Tn≤t

sono rispettivamente il tempo necessario per vendere n unita e il numero dipezzi venduti fino al tempo t.

Il costo di stoccaggio di una quantita S e quindi

c

∫ ∞

0

(S −Nt)+dt.

Il costo medio di stoccaggio e percio

cE[∫ ∞

0

(S −Nt)+dt

]= c

∫ ∞

0

S∑k=1

PS −Nt ≥ k dt

= c

∫ ∞

0

S∑k=1

PNt ≤ S − k dt

= c

∫ ∞

0

S∑k=1

PNt < S + 1− k dt

= c

∫ ∞

0

S∑h=1

PNt < h dt

Osservando che Nt < h = Th > t troviamo la seguente formula per ilcosto medio di stoccaggio

cE[∫ ∞

0

(S −Nt)+dt

]= c

S∑h=1

∫ ∞

0

PTh > t dt

59

Page 60: catene di markov

= cS∑

h=1

E[Th]

= cS∑

h=1

mh

= cmS(S + 1)/2.

Il costo totale di un lotto, ovvero la somma del costo di ordinazione e di stoccag-gio, e quindi

K +cmS(S + 1)

2e il costo totale medio per unita di merce e

K

S+

cm(S + 1)2

.

Minimizzando (rispetto a S) questa funzione troviamo che la quantita di merceda acquistare per ottimizzare i costi di ordinazione e stoccaggio e

S =

√2K

cm.

60

Page 61: catene di markov

References

[1] P. Baldi Calcolo delle Probabilita e Statistica. McGraw–Hill, Milano 1992.

[2] W. Feller An Introduction to Probability Theory and its Applications.

[3] S. Karlin, H. Taylor A First Course in Stochastic Processes. AcademicPress, New-York 1972.

[4] S. Karlin, H. Taylor A Second Course in Stochastic Processes. AcademicPress, New-York 1975.

[5] N. Pintacuda, Catene di Markov, ETS Editrice, 2000.

[6] Norris

[7] Nummelin, E. (1984). General irreducible Markov chains and non-negativeoperators. Cambridge Tracts in Mathematics, 83. Cambridge UniversityPress, Cambridge.

[8] W. Woess Catene di Markov e teoria del potenziale nel discreto. Quadernidell’Unione Matematica Italiana n.41, Pitagora Editrice, Bologna, 1996.

61