Introduzione alle Catene di Markov - Tommaso...

Introduzione alle Catene di Markov

Tommaso R. Cesari

APPUNTI NON UFFICIALI1

(Calcolo delle Probabilità - corso di Giacomo Aletti)

1Nota del redattore

Questi appunti sono stati scritti da me durante il Corso (A.A. 2011-2012). Sono asso-lutamente indipendenti dall'iniziativa del Docente. Di queste carte non è fornita alcunagaranzia esplicita o implicita di correttezza o di completezza. In particolare, è assai pro-babile che risultino presenti numerosi errori delle tipologie più svariate, in primo luogoconcettuali, dovuti all'imperizia del curatore. Si sottolinea inoltre che non vi è stato daparte mia alcuno sforzo per rendere gli argomenti formalmente corretti, né tanto meno perdare loro una veste chiara e lineare. Usate dunque le informazioni qui contenute a vostrorischio e pericolo.Tommaso R. Cesari

Indice

1 Catene di Markov 3

1.1 Denizioni e prime proprietà . . . . . . . . . . . . . . . . . . . 31.2 Struttura delle distribuzioni congiunte nito dimensionali . . . 71.3 Probabilità di transizione in n passi . . . . . . . . . . . . . . . 91.4 Istante d'arresto e proprietà di Markov forte . . . . . . . . . . 141.5 Classicazione degli stati di una catena . . . . . . . . . . . . . 211.6 Alcuni esempi di catene di Markov . . . . . . . . . . . . . . . 30

1.6.1 Catena a due stati . . . . . . . . . . . . . . . . . . . . 301.6.2 Passeggiata aleatoria semplice su Z . . . . . . . . . . . 301.6.3 Passeggiata aleatoria semplice su Z2 . . . . . . . . . . 311.6.4 Passeggiata aleatoria semplice su Z3 . . . . . . . . . . 31

1.7 Assorbimento e tempi di assorbimento . . . . . . . . . . . . . 311.7.1 Catene di Nascita e Morte . . . . . . . . . . . . . . . . 341.7.2 Rovina del giocatore . . . . . . . . . . . . . . . . . . . 35

1.8 Proprietà asintotiche delle catene di Markov . . . . . . . . . . 361.8.1 Distribuzione invariante e distribuzione limite . . . . . 361.8.2 Convergenza all'equilibrio . . . . . . . . . . . . . . . . 381.8.3 Time reversal e catene reversibili . . . . . . . . . . . . 461.8.4 Teorema ergodico per le Catene di Markov . . . . . . . 49

Capitolo 1

Catene di Markov

1.1 Denizioni e prime proprietà

Notazione 1 (Leggere attentamente). Al ne di alleggerire la notazione,verranno ora ed in seguito enunciate alcune denizioni che non verranno piùrichiamate durante il testo. Per non rendere la lettura incomprensibile, ver-ranno utilizzati sistematicamente gli stessi simboli, ad esempio P per denotareuna misura di probabilità su qualche insieme e BE per una σ-algebra di sot-toinsiemi di qualche insieme E. Tali notazioni non verranno mai ripetute ameno che non lo si ritenga strettamente necessario. Si consiglia dunque dileggere queste dispense dall'inizio alla ne, senza omettere alcuna parte.

Notazione 2. Nel corso di tutte le dispense si utilizzeranno le notazioni :=e =: per indicare una denizione e la notazione

.= per indicare un teorema.

Entrambi i simboli possono essere letti come uguale per denizione ma,mentre nel primo caso si pone un'uguaglianza per denizione, nel secondo siintende che l'uguaglianza discende direttamente dalla denizione.

Ad esempio: siano a := 2 e 3 =: b, allora a+ b.= 5.

Notazione 3. Si utilizzerà la seguente convenzione per l'insieme dei numerinaturali:

N := 0, 1, 2, . . ..

Denizione 1 (Denizioni preliminari). Siano (Ω,F ,P) uno spazio diprobabilità, (S,BS) uno spazio probabilizzabile e I un insieme di indiciarbitrario.

• Una famiglia di v.a. (Xt)t∈I , tali che per ogni t ∈ I si abbia

Xt : (Ω,F)→ (S,BS)

si dice processo stocastico.

4 Catene di Markov

• L'insieme di indici I prende il nome di insieme dei tempi.

• Se I ⊂ N si dice che (Xt)t∈I è un processo a tempo discreto.

• Lo spazio (S,BS) si dice spazio degli stati.

• Se l'insieme S è al più numerabile, il processo (Xt)t∈I prende il nomedi catena.

Osservazione 1.1.1 (Interpretazione di (Xt)t∈I). I processi stocasticirappresentano l'evoluzione temporale di una famiglia di variabili aleatorie.

Osservazione 1.1.2. Nel corso di queste dispense, l'attenzione verràfocalizzata principalmente su catene a tempo discreto.

Notazione 4. Per semplicare la notazione si scriverà che

(Xt)t∈I : (Ω,F ,P)→ (S,BS)

è un processo stocastico. Con questa notazione si intende che, ssati unospazio di probabilità (Ω,F ,P) e uno spazio probabilizzabile (S,BS), per ognit ∈ I si ha Xt : (Ω,F)→ (S,BS).

Denizione 2 (Nucleo di transizione). Sia S un insieme al più numerabile.Si dice che

P : S × S → [0, 1],

(i, j) 7→ P (i, j) := pij

è un nucleo di transizione (o una matrice stocastica) se per ogni i ∈ S si ha∑j∈S

pij = 1. (1.1)

Osservazione 1.1.3. Per i nuclei di transizione si utilizzerà spesso lanotazione

P := (pij, i, j ∈ S).

Questa notazione permette l'interpretazione intuitiva di P come una matricein cui la somma dei valori su ogni riga è uguale ad 1.

Osservazione 1.1.4 (Interpretazione). Nel seguito si vedrà come i nucleidi transizione associati ai processi stocastici possano essere pensati come laprobabilità di andare da uno stato i ad uno stato j in un passo. In questospirito la proprietà (1.1) sottolinea questo aspetto probabilistico, aermandoche la probabilità di andare da uno stato i ad un qualunque altro stato èuguale ad 1.

1.1 Denizioni e prime proprietà 5

Denizione 3 (Filtrazione). Sia (Ω,F ,P) uno spazio di probabilità. Unasuccessione di σ-algebre Fnn∈N si dice ltrazione di F se

F0 ⊂ F1 ⊂ . . . ⊂ Fk ⊂ . . . ⊂ F .

Si dice in questo caso che (Ω,F , Fnn∈N,P) è uno spazio ltrato.Sia inoltre (Xn)n∈N : (Ω,F ,P) → (S,BS) un processo stocastico. Si dice cheFnn∈N è la ltrazione naturale generata dal processo (Xn)n∈N se, per ognin ∈ N si ha Fn := σ(X0, . . . Xn).

Osservazione 1.1.5 (Intuitivamente). L'introduzione delle ltrazioni è difondamentale importanza nella applicazioni. Si ricordi come nelle σ-algebresiano contenute tutte le informazioni conosciute dall'esecutore di un esperi-mento aleatorio. In genere non si hanno a disposizione tutte le informazionicontenute in F . Tuttavia, se si pensa ad un processo stocastico come un'e-voluzione temporale di v.a., certamente ad ogni istante n sono note tutte leinformazioni derivanti dalla conoscenza delle prime n v.a. del processo, ov-vero precisamente tutte le informazioni contenute nella ltrazione naturaleal tempo n. Proprio per questo motivo d'ora in poi il nostro dato fondamen-tale non sarà più uno spazio di probabilità (Ω,F ,P), ma uno spazio ltrato(Ω,F , Fnn∈N,P).

Denizione 4 (Processo adattato). Sia (Xn)n∈N : (Ω,F , Fnn∈N,P) →(S,BS) un processo stocastico. Si dice che (Xn)n∈N è Fn-adattato se per ognin ∈ N si ha che Xn è Fn-misurabile.

Notazione 5 (Importante). Per rendere più chiara la notazione, d'ora inpoi si indicherà sempre con S un sottoinsieme (eventualmente innito) di N.Inoltre con la notazione

(Xn)n∈N : (Ω,F , Fnn∈N,P)→ (S,BS)

si supporrà sempre implicitamente che per ogni n ∈ N e per ogni i ∈ S siabbia

P(Xn = i) > 0,

ovvero che S sia l'insieme degli stati in cui il processo può eettivamentecadere (con probabilità positiva!)1.

Denizione 5 (Catena di Markov). Sia (Xn)n∈N : (Ω,F , Fnn∈N,P) →(S,BS) una catena. Si dice che (Xn)n∈N è una catena di Markov con matricedi transizione P := (pij, i, j ∈ S) :=

(P(Xn+1 = j|Xn = i), i, j ∈ S

)e

distribuzione di probabilità iniziale π (più brevemente C.M. (P, π)) se

1Questa, come sarà chiaro già dalla prossima denizione, è un'ipotesi necessaria perrendere rigorosa la trattazione.

6 Catene di Markov

1. (Xn)n∈N è Fn-adattata;

2. X0 ∼ π, ovvero, per ogni i ∈ S si ha P(X0 = i) = π(i);

3. per ogni n ∈ N e per ogni i0, i1, . . . , in−1, i, j ∈ S si ha

P(Xn+1 = j|X0 = i0, X1 = i1, . . . Xn = i) = P(Xn+1 = j|Xn = i).= pij.(1.2)

La (1.2) viene detta proprietà di Markov.

Osservazione 1.1.6. In modo analogo si denisce una C.M. costituita dauna famiglia nita di variabili aleatorie (Xn)Nn=0.

Osservazione 1.1.7. Si noti quanto segue:

1. è una proprietà analitica, necessaria per rendere rigoroso il formalismo;

2. la conoscenza della distribuzione iniziale dà delle informazioniprobabilistiche sull'istante iniziale del processo;

3. la proprietà di Markov si può formulare a parole dicendo che condiziona-tamente al presente, il futuro è indipendente dal passato. La memoriadel processo si limita quindi all'ultimo istante prima del presente.

Esercizio 1. Si dimostri che la matrice di transizione P di una catena diMarkov è una matrice stocastica.

Teorema 1.1.1 (di esistenza). Siano S un insieme al più numerabile, P :=(pij, i, j ∈ S) una matrice stocastica e π = (πi, i ∈ S) una distribuzione(i.e.

∑i∈S πi = 1). Allora esiste uno spazio ltrato (Ω,F , Fnn∈N,P) e una

catena di Markov (Xn)n∈N denita su (Ω,F , Fnn∈N,P), a valori in (S,BS),con matrice di transizione P e distribuzione iniziale π.

Dimostrazione. Per una dimostrazione di questo teorema si veda ad esempioProbability and Measure - P. Billingsley.

Esempio 1.1.1 (Diusione di Bernoulli-Laplace). Si mostrerà ora un primo,semplice esempio di catena di Markov. Sono lasciati al lettore alcuni dettaglisulla discussione.Si considerino due urne ciascuna contenente r palline. In totale ci sono quindi2r palline, di cui r bianche ed r nere. Si consideri come insieme degli statiS := 0, 1, . . . , r, che rappresenta il numero di palline bianche nella primaurna. Il meccanismo di transizione è il seguente: si estrae una pallina da ogniurna e le si scambia.

1.2 Struttura delle distribuzioni congiunte nito dimensionali 7

Si vuole descrivere la matrice di transizione P = (pij, i, j ∈ 0, 1, . . . , r).Per ogni i, j ∈ 0, 1, . . . , r si pensino i pedici di pij nel seguente modo: iè il numero di palline bianche nella prima urna prima dell'estrazione; j è ilnumero di palline bianche nella prima urna dopo l'estrazione. Sia i ∈ S ssatoarbitrariamente. Allora

• la probabilità di estrarre una pallina bianca dalla prima urna ed unanera dalla seconda è data da

pi,i−1 =i

r

i

r;

• la probabilità di estrarre una pallina nera dalla prima urna ed unabianca dalla seconda è data da

pi,i+1 =r − ir

r − ir

;

• la probabilità di estrarre due palline dello stesso colore è data da

pi,i =i

r

r − ir

+r − ir

i

r=

2i(r − i)r2

.

Questi casi esauriscono tutti i casi possibili, dunque per ogni altro j ∈ S siha pi,j = 0.

1.2 Struttura delle distribuzioni congiunte

nito dimensionali

Osservazione 1.2.1. Si consideri un processo stocastico (Xn)n∈N. In que-sta sezione si vuole studiare, per ogni n ∈ N, la probabilità congiunta delvettore aleatorio (X0, X1, . . . , Xn), ossia la probabilità P(X0 = i0, X1 =i1, . . . , Xn = in) al variare degli ik in S. Si dimostrerà come la struttura delledistribuzioni congiunte nito dimensionali caratterizzi le catene di Markov.Prima di procedere si ricorda un semplice lemma, che verrà utilizzato nelladimostrazione.

Lemma 1.2.1 (Proprietà moltiplicativa della probabilità). Sia (Ω,F ,P) unospazio di probabilità e siano A1, . . . , An ∈ F eventi di probabilità positiva.Allora

P(A1 ∩ A2 ∩ . . . ∩ An) = P(A1)P(A2|A1) . . .P(An|A1 ∩ . . . ∩ An−1). (1.3)

8 Catene di Markov

Dimostrazione. Ovvia.

Teorema 1.2.1. Sia (Xn)n∈N : (Ω,F , Fnn∈N,P)→ (S,BS) una catena taleche per ogni i, j ∈ S e per ogni m,n ∈ N si abbia P(Xn+1 = j|Xn = i) =P(Xm+1 = j|Xm = i), e dove Fnn∈N è la ltrazione naturale generata da(Xn)n∈N. Siano inoltre ssate una distribuzione π : S → [0, 1] e una matricestocastica P := (pij, i, j ∈ S) :=

(P(X1 = j|X0 = i), i, j ∈ S

). Allora

(Xn)n∈N è una C.M.(P, π) ⇔ per ogni i0, . . . , iN ∈ S si ha

P(X0 = i0, . . . , XN = iN) = π(i0)pi0i1 . . . piN−1iN . (1.4)

Dimostrazione. Si dimostrano separatamente le due implicazioni.

⇒) Sia (Xn)n∈N una C.M.(P, π). Allora, per ogni i0, . . . , iN ∈ S si ha

P(X0 = i0, . . . , XN = iN)

(1.3)= P(X0 = i0)P(X1 = i1|X0 = i0) . . .P(XN = iN |X0 = i0, . . . , XN−1 = iN−1)

(1.2)= π(i0)pi0i1 . . . piN−1iN .

⇐) Si supponga la (1.4). Essendo P stocastica2, se si sommano entrambi imembri della (1.4) su iN ∈ S si ha (per ogni i0, . . . , iN−1 ∈ S)

P(X0 = i0, . . . , XN−1 = iN−1) = π(i0)pi0i1 . . . piN−2iN−1.

Iterando questo ragionamento è quindi immediato convincersi che la(1.4) vale per ogni n ∈ 0, . . . , N, dunque in particolare per n = 0.Per ogni i0 ∈ S si può pertanto scrivere

P(X0 = i0) = π(i0),

ovvero che X0 ∼ π. Rimane soltanto da dimostrare la validità dellaproprietà di Markov. Per ogni i0, . . . , iN−1, i, j ∈ S, si ha

P(XN+1 = j|X0 = i0, . . . , XN−1 = iN−1, XN = i)

.=

P(X0 = i0, . . . , XN−1 = iN−1, XN = i,XN+1 = j)

P(X0 = i0, . . . , XN−1 = iN−1, XN = i)

(1.4)=

π(i0)pi0i1 . . . piN−1ipij

π(i0)pi0i1 . . . piN−1i

= pij.= P(XN+1 = j|XN = i).

2Dunque∑iN∈S

piN−1iN = 1.

1.3 Probabilità di transizione in n passi 9

Notazione 6. Con la notazione (Xn)n∈N : (Ω,F , Fnn∈N,P) → (S,BS) sisottintenderà sempre (a meno che diversamente specicato) che la ltrazioneFtt∈N sia quella naturale generata dal processo.

1.3 Probabilità di transizione in n passi

Osservazione 1.3.1. Il problema discusso in questa sezione è il seguente.Si parta da un certo stato i ∈ S. Qual'è la probabilità che dopo n passi unacatena di Markov cada proprio in un ssato stato j ∈ S3? Per risponderea questa domanda, dimostriamo prima un teorema che mostra un aspettointeressante della proprietà di Markov.

Notazione 7. Sia i ∈ S ssato. Si indica con δi la distribuzione δ diKronecker. Si ha cioè

δi : S → [0, 1],

j 7→ δi(j) := δij :=

1, se j = i,

0, altrimenti.

Teorema 1.3.1 (Proprietà di Markov). Sia (Xn)n∈N : (Ω,F , Fnn∈N,P)→(S,BS) una C.M.(P, π). Siano inoltre i ∈ S e m ∈ N ssati arbitrariamente.Allora, condizionatamente a Xm = i, (Xm+n)n∈N è una C.M.(P, δi) ed èindipendente dalle v.a. X0, . . . , Xm, cioè

1. (Xm+n)n∈N :(Ω,F , Fm+nn∈N,P( · |Xm = i)

)→ (S,BS) è una

C.M.(P, δi);

2. per ogni A ∈ σ(X0, . . . , Xm) e per ogni B ∈ σ((Xm+n)n∈N

)si ha

P(A ∩B|Xm = i) = P(A|Xm = i) · P(B|Xm = i).

Dimostrazione. Si dimostrano separatamente i due punti.

1. Chiaramente il processo (Xm+n)n∈N è Fm+n-adattato. Inoltre, per ogniim, . . . , im+N ∈ S si ha

3Si sottolinea che questo non vieta che in qualche istante intermedio il processo possapassare da j.

10 Catene di Markov

P(Xm = im, . . . , Xm+N = im+N |Xm = i)

.=

P(Xm = im, . . . , Xm+N = im+N , Xm = i)

P(Xm = i)

=δiim · P(Xm = im, . . . , Xm+N = im+N)

P(Xm = i)

=∑

i0,...,im−1∈S

δiim · P(X0 = i0, . . . , Xm−1 = im−1, Xm = im, . . . , Xm+N = im+N)

P(Xm = i)

(1.4)=

∑i0,...,im−1∈S

δiim · π(i0)pi0i1 . . . pim−1impimim+1 . . . pim+N−1im+N

P(Xm = i)

=∑

i0,...,im−1∈S

(π(i0)pi0i1 . . . pim−1im

)· δiim ·

(pimim+1 . . . pim+N−1im+N

)P(Xm = i)

(1.4)=

∑i0,...,im−1∈S

P(X0 = i0, . . . , Xm = im)

P(Xm = i)· δiim · pimim+1 . . . pim+N−1im+N

(δiim )=

∑i0,...,im−1∈S

P(X0 = i0, . . . , Xm = im|Xm = i)︸︷︷︸=δiim

·δiimpimim+1 . . . pim+N−1im+N

= δiimpimim+1 . . . pim+N−1im+N,

quindi per il Teorema 1.2.1 si ha la tesi.

2. Siano m,n ∈ N e i, i0, . . . , im−1, imA, imB

, im+1, . . . , im+n ∈ S arbitrari.Si consideri inizialmente il caso in cui A e B sono eventi elementari deltipo

A := X0 = i0, . . . , Xm = imA, Bn := Xm = imB

, . . . , Xm+n = im+n.

Allora

P(A ∩Bn|Xm = i)

.= P(X0 = i0, . . . , Xm = imA

, Xm = imB, . . . , Xm+n = im+n|Xm = i)

.=

P(X0 = i0, . . . , Xm = imA, Xm = imB

, . . . , Xm+n = im+n, Xm = i)

P(Xm = i)

=δiimA

δiimBP(X0 = i0, . . . , Xm = i, . . . , Xm+n = im+n)

P(Xm = i)

(1.4)=

δiimA

(π(i0)pi0i1 . . . pim−1i

)δiimB

(piim+1 . . . pim+n−1im+n

)P(Xm = i)


(1.4)= δiimA

P(X0 = i0, . . . , Xm = i)

P(Xm = i)δiimB

piim+1 . . . pim+n−1im+n

(δiimA)

=P(X0 = i0, . . . , Xm = imA

, Xm = i)

P(Xm = i)δiimB

piim+1 . . . pim+n−1im+n

.= P(X0 = i0, . . . , Xm = imA

|Xm = i) δiimBpiim+1 . . . pim+n−1im+n

(δiimB)

= P(X0 = i0, . . . , Xm = imA|Xm = i) δiimB

pimBim+1 . . . pim+n−1im+n

(∗)= P(X0 = i0, . . . , Xm = imA

|Xm = i) ··P(Xm = imB

, . . . , Xm+n = im+n|Xm = i).= P(A|Xm = i) · P(Bn|Xm = i)

dove (∗) vale per il punto precedente e per la solita (1.4). Si noti orache l'unione al varare di tutti i possibili i0, . . . , im−1, imA

∈ S deglieventi elementari A visti sopra costituisce un π-sistema che generaσ(X0, . . . , Xm−1). Analogamente, l'unione al variare di n ∈ N e diimB

, im+1, . . . , im+n ∈ S degli eventi elementari Bn visti sopra costi-tuisce un π-sistema che genera σ

((Xm+n)n∈N

). Per il lemma di unicità

dell'estensione la tesi vale dunque su tutte e due le σ-algebre.

Notazione 8. Siano P := (pij, i, j ∈ S) una matrice stocastica e π : S →[0, 1] una distribuzione. Pensando π come un vettore riga π = (π(i), i ∈ S)si può introdurre in modo molto naturale la notazione

πP :=

(∑i∈S

π(i)pij

)j∈S

.

Posta P 0 := I (matrice identica), per ogni n ∈ N\0 si introducono lepotenze n-esime

P n .=

∑j1,...,jn−1

pij1 . . . pjn−1j

i,j∈S

:= (p(n)ij , i, j ∈ S).

Fatto 1.3.1. Sia P una matrice stocastica. Allora per ogni n ∈ N, P n è unamatrice stocastica.

Teorema 1.3.2. Sia (Xn)n∈N : (Ω,F , Fnn∈N,P) → (S,BS) unaC.M.(P, π). Allora

12 Catene di Markov

1. Per ogni n ∈ N e per ogni j ∈ S si ha

P(Xn = j) = (πP n)j;

2. per ogni n,m ∈ N e per ogni i, j ∈ S si ha

P(Xn = j|X0 = i) = P(Xm+n = j|Xm = i) = p(n)ij . (1.5)

Dimostrazione. Si dimostrano separatamente i due casi.


P(Xn = j) =∑

i0,...,in−1∈S

P(X0 = i0, . . . , Xn−1 = in−1, Xn = j)

(1.4)=

∑i0,...,in−1∈S

π(i0)pi0i1 . . . pin−1j

.= (πP n)j.

2. Si ssi i ∈ S arbitrariamente. Per la proprietà di Markov si ha cheper ogni m ∈ N (si noti che quanto segue vale anche per m = 0),(Xm+n)n∈N :

(Ω,F , Fm+nn∈N,P( · |Xm = i)

)→ (S,BS) è una

C.M.(P, δi). Applicando dunque il punto precedente con l'accuratez-za di sostituire (Xm+n)n∈N a (Xn)n∈N, P( · |Xm = i) a P e δi a π si haimmediatamente la tesi.

Denizione 6. Sia (Xn)n∈N : (Ω,F , Fnn∈N,P)→ (S,BS) una C.M.(P, π).Si ssino n ∈ N e i, j ∈ S. Si dice che p(n)

ij è la probabilità di andare da i a jin n passi.

Lemma 1.3.1 (Proprietà di Markov generalizzata). Sia (Xn)n∈N :(Ω,F , Fnn∈N,P) → (S,BS) una C.M.(P, π). Per ogni m,n ∈ N, per ognik1 < k2 < . . . < kn ∈ N e per ogni ik1 , . . . , ikn , ikn+m ∈ S, si ha

P(Xkn+m = ikn+m|Xk1 = ik1 , . . . , Xkn = ikn) = P(Xkn+m = ikn+m|Xkn = ikn).

Dimostrazione. Per ogni m,n ∈ N, per ogni k1 < k2 < . . . < kn ∈ N e perogni ik1 , . . . , ikn , ikn+m ∈ S, posti jk1 := ik1 , . . . , jkn := ikn , jkn+m := ikn+m, siha


P(Xkn+m = ikn+m|Xk1 = ik1 , . . . , Xkn = ikn)

.=

P(Xk1 = ik1 , Xk2 = ik2 , . . . , Xkn = ikn , Xkn+m = ikn+m)

P(Xk1 = ik1 , . . . , Xkn = ikn)

=

∑i0,...,ik1−1,

ik1+1,...,ik2−1,...

ikn−1+1,...,ikn−1,

ikn+1,...,ikn+m−1∈S

P(X0 = i0, X1 = i1, . . . , Xkn+m = ikn+m)

∑j0,...,jk1−1,

jk1+1,...,jk2−1,...

jkn−1+1,...,jkn−1∈S

P(X0 = j0, X1 = j1, . . . , Xkn = jkn)

(1.4)=

∑i0,...,ik1−1,

ik1+1,...,ik2−1,...

ikn−1+1,...,ikn−1,


πi0pi0i1 . . . pikn−1iknpikn ikn+1

. . . pikn+m−1ikn+m

∑j0,...,jk1−1,

jk1+1,...,jk2−1,...

jkn−1+1,...,jkn−1∈S

πj0pj0j1 . . . pjkn−1jkn

=

∑ikn+1,...,ikn+m−1∈S

pikn ikn+1, . . . pikn+m−1ikn+m

∑i0,...,ik1−1,

ik1+1,...,ik2−1,...

ikn−1+1,...,ikn−1∈S

πi0pi0i1 . . . pikn−1ikn

∑j0,...,jk1−1,

jk1+1,...,jk2−1,...

jkn−1+1,...,jkn−1∈S

πj0pj0j1 . . . pjkn−1jkn

=∑


pikn ikn+1, . . . pikn+m−1ikn+m

.= p

(m)ikn ikn+m

(1.5)= P(Xkn+m = ikn+m|Xkn = ikn).

14 Catene di Markov

Teorema 1.3.3 (Equazioni di Chapman-Kolmogorov). Sia (Xn)n∈N :(Ω,F , Fnn∈N,P) → (S,BS) una C.M.(P, π). Per ogni m,n ∈ N e per ognii, j ∈ S, si ha

p(m+n)ij =

∑k∈S

p(m)ik p

(n)kj .

Dimostrazione. Per ogni m,n ∈ N e per ogni i, j ∈ S, per la proprietà diMarkov generalizzata (M), si ha

p(m+n)ij

.= P(Xn+m = j|X0 = i)

.=

P(Xn+m = j,X0 = i)

P(X0 = i)

=∑k∈S

P(Xn+m = j,Xm = k,X0 = i)

P(X0 = i)

=∑k∈S

P(Xm = k,X0 = i)P(Xn+m = j|Xm = k,X0 = i)

P(X0 = i)

(M)=

∑k∈S

P(Xm = k,X0 = i)P(Xn+m = j|Xm = k)

P(X0 = i)

.=

∑k∈S

P(Xm = k|X0 = i)P(Xn+m = j|Xm = k)

(1.5)=

∑k∈S

p(m)ik p

(n)kj .

Osservazione 1.3.2 (Equazioni di Chapman-Kolmogorov). Intuitivamente,le equazioni di Chapman-Kolmogorov dicono una cosa molto semplice. Laprobabilità di andare da i a j in m+ n passi è uguale a quella di andare dai ad un qualunque altro stato intermedio k in m passi e poi da quello statoarrivare a j dopo altri n passi.

1.4 Istante d'arresto e proprietà di Markov

forte

Osservazione 1.4.1. Lo scopo di questa sezione è enunciare una forma piùforte del Teorema sulla proprietà di Markov, estendendo questa proprietàanche a catene di Markov arrestate in istanti di tempo aleatori.

1.4 Istante d'arresto e proprietà di Markov forte 15

Notazione 9 (F∞). Sia (Ω,F , Fnn∈N) uno spazio probabilizzabile ltrato.Si indica con F∞ la sotto σ-algebra di F data da

F∞ := σ

(⋃n∈N

Fn

)

Denizione 7 (Tempo d'arresto). Sia (Ω,F , Fnn∈N) uno spazio probabi-lizzabile ltrato. Si dice che una funzione T : Ω → N ∪ +∞ è un tempod'arresto (o istante d'arresto) se per ogni n ∈ N ∪ +∞ si ha

T = n ∈ Fn. (1.6)

Lemma 1.4.1. Sia T un tempo d'arresto (denito su qualche(Ω,F , Fnn∈N)). Allora T : (Ω,F) → (N ∪ +∞,P(N ∪ +∞) èuna variabile aleatoria.


Denizione 8. Sia (Xn)n∈N : (Ω,F , Fnn∈N,P) → (S,BS) un processostocastico Fnn∈N-adattato. Si dice in questo caso che T è un tempo d'arrestoper il processo (Xn)n∈N.

Esempio 1.4.1.

1. Primo istante di arrivo in j.

Siano (Xn)n∈N : (Ω,F , Fnn∈N,P) → (S,BS) e j ∈ S ssato. Sidenisce primo istante di arrivo in j, la funzione

Tj : Ω → N ∪ +∞,ω 7→ Tj(ω) := inf n ∈ N ∪ +∞ : Xn(ω) = j .

È chiaro che Tj è un tempo d'arresto per (Xn)n∈N, infatti per ognin ∈ N si ha

Tj = n = X0 6= j, . . . , Xn−1 6= j,Xn = j ∈ Fn

e per n = +∞ si ha

Tj = +∞ =

(⋂k∈N

Xk 6= j

)∈ F∞.

16 Catene di Markov

2. Primo istante di arrivo in A.

Siano (Xn)n∈N : (Ω,F , Fnn∈N,P) → (S,BS) e A ∈ BS ssato. Sidenisce primo istante di arrivo in A, la funzione

TA : Ω → N ∪ +∞,ω 7→ TA(ω) := inf n ∈ N ∪ +∞ : Xn(ω) ∈ A .

È chiaro che TA è un tempo d'arresto per (Xn)n∈N.

3. Ultimo istante di uscita da A.

Siano (Xn)n∈N : (Ω,F , Fnn∈N,P) → (S,BS) e A ∈ BS ssato. Sidenisce ultimo istante di uscita da A, la funzione

LA : Ω → N ∪ +∞,ω 7→ LA(ω) := sup n ∈ N ∪ +∞ : Xn(ω) ∈ A .

È chiaro che (in generale) LA non è un tempo d'arresto per (Xn)n∈N.Infatti, per ogni n ∈ N, LA dipende anche dagli instanti futuri m ≥ n,dunque in generale LA = n /∈ Fn.

Notazione 10 (XT ). Sia (Xn)n∈N : (Ω,F , Fnn∈N,P)→ (S,BS) un proces-so stocastico Fnn∈N-adattato e sia T un tempo d'arresto per (Xn)n∈N. Siindica con XT la funzione

XT : Ω → S,

ω 7→ XT (ω)(ω).

Lemma 1.4.2. Sia (Xn)n∈N : (Ω,F , Fnn∈N,P)→ (S,BS) un processo sto-castico Fnn∈N-adattato e sia T un tempo d'arresto per (Xn)n∈N. Allora, perogni k ∈ N, si ha

X∞ = k :=

ω ∈ Ω : ∃ lim

n→+∞Xn(ω) = k

∈ F∞.

Dimostrazione. Si noti che l'evento

A :=

ω ∈ Ω : ∃ lim

n→+∞Xn(ω)

appartiene alla σ-algebra coda del processo, a sua volta inclusa in F∞.Dunque per ogni ω ∈ A è ben denito il limite puntuale

X∞(ω) := limn→+∞

(Xn

∣∣A

)(ω).


Essendo per ogni n ∈ N le Xn variabili aleatorie F∞-misurabili e A ∈ F∞,allora anche le restrizioni

(Xn

∣∣A

)sono F∞-misurabili e di conseguenza il loro

limite puntuale. Si è quindi concluso che X∞ : (A,F∞) → (S,BS) è unavariabile aleatoria, da cui la tesi.

Denizione 9 (FT ). Sia (Ω,F , Fnn∈N) uno spazio probabilizzabile ltratoe sia T un tempo d'arresto. Si denisce σ-algebra generata dal tempo d'arrestoT , e si indica con FT (o con σ(T )), la σ-algebra4

FT :=F ∈ F : F ∩ T = n ∈ Fn,∀n ∈ N ∪ +∞

.

Lemma 1.4.3. Sia (Xn)n∈N : (Ω,F , Fnn∈N,P) → (S,BS) una catenaa tempo discreto e sia T un tempo d'arresto per (Xn)n∈N. Allora XT :(Ω,FT )→ (S,BS) è una variabile aleatoria.

Dimostrazione. Per ogni k ∈ N si ha

XT = k .=

(⋃n∈N

(Xn = k ∩ T = n

))∪(X∞ = k ∩ T = +∞

).

Notazione 11 (XT+k). Siano (Xn)n∈N : (Ω,F , Fnn∈N,P) → (S,BS) unprocesso stocastico Fnn∈N-adattato, T un tempo d'arresto per (Xn)n∈N ek ∈ N. Si indica con XT+k la funzione

XT+k : Ω → S,

ω 7→ XT (ω)+k(ω).

Denizione 10 (FT+k). Siano (Ω,F , Fnn∈N) uno spazio probabilizzabileltrato, T un tempo d'arresto e k ∈ N. Si denisce σ-algebra generata dopok istanti dal tempo d'arresto T , e si indica con FT+k, la σ-algebra

FT+k :=F ∈ F : F ∩ T = n ∈ Fn+k,∀n ∈ N ∪ +∞

.

Osservazione 1.4.2. È chiaro che, considerando il caso particolare k = 0,si ha XT+0 = XT e FT+0 = FT .

Lemma 1.4.4. Sia (Xn)n∈N : (Ω,F , Fnn∈N,P) → (S,BS) una catena atempo discreto e sia T un tempo d'arresto per (Xn)n∈N. Allora, per ognik ∈ N, si ha che XT+k : (Ω,FT+k)→ (S,BS) è una variabile aleatoria.

4Si verichi che lo è!

18 Catene di Markov


Lemma 1.4.5. Sia (Xn)n∈N : (Ω,F , Fnn∈N,P) → (S,BS) una catena atempo discreto e sia T un tempo d'arresto per (Xn)n∈N. Allora FT+kk∈N èuna ltrazione di F .


Lemma 1.4.6. Sia (Xn)n∈N : (Ω,F , Fnn∈N,P) → (S,BS) una catena atempo discreto e sia T un tempo d'arresto per (Xn)n∈N. Allora, per ognii ∈ S e per ogni m ∈ N, si ha l'uguaglianza insiemistica

T = m,XT = i = T = m,Xm = i, (1.7)

mentre, in generale,

T = m,XT = i ⊂ Xm = i. (1.8)

Dimostrazione. Siano i ∈ S e m ∈ N arbitrari. Si dimostrano inizialmente ledue inclusioni per la (1.7).

⊂ ) Sia ω ∈ T = m,XT = i, ovvero, per denizione, sia ω ∈ Ω tale che

T (ω) = m e XT (ω)(ω)︸︷︷︸=Xm(ω)

= i.

Allora, ovviamente ω ∈ T = m,Xm = i.

⊃ ) Sia ω ∈ T = m,Xm = i, ovvero, per denizione, sia ω ∈ Ω tale che

T (ω) = m e Xm(ω)︸︷︷︸=XT (ω)(ω)

= i.

Allora, ovviamente ω ∈ T = m,XT = i.

La (1.7) è quindi provata. Per dimostrare la (1.8) basta osservare che

T = m,XT = i (1.7)= T = m,Xm = i .= T = m∩Xm = i ⊂ Xm = i.

Osservazione 1.4.3. (Importante!) Si sottolinea il fatto che la (1.8) è un'in-clusione ma non è in generale un'uguaglianza. Si faccia molta attenzione anon incappare in questo tipo di errori grossolani dovuti agli abusi di nota-zione. Quando si trovano intersezioni con un insieme del tipo T = m nonbasta sostituire m a tutte le occorrenze di T . Si raccomanda di tenere semprepresente la semantica di ciò che si sta trattando, perché con le uguaglianzeformali si prendono parecchie cantonate.


Teorema 1.4.1 (Proprietà di Markov forte). Siano (Xn)n∈N :(Ω,F , Fnn∈N,P)→ (S,BS) una C.M.(P, π), T un tempo d'arresto per la ca-tena tale che P(T < +∞) > 0, i ∈ S ssato e PTi := P( · |T < +∞, XT = i).Allora

• (XT+n)n∈N :(Ω, F , FT+nn∈N, PTi

)→ (S,BS) è una C.M.(P, δi);

• per ogni A ∈ FT e per ogni B ∈ σ((XT+n)n∈N

), si ha che

PTi (A ∩B) = PTi (A) · PTi (B), (1.9)

ovvero (XT+n)n∈N è PTi -indipendente dal passato costituito da FT .

Dimostrazione. Chiaramente (XT+n)n∈N è una catena FT+nn∈N-adattata.Si ssino arbitrariamente n ∈ N, j0, . . . , jn ∈ S e A ∈ FT . È sucientedimostrare che

P(XT = j0, . . . , XT+n = jn ∩ A|T < +∞, XT = i)

= Pi(X0 = j0, . . . , Xn = jn)P(A|T < +∞, XT = i)(1.10)

Infatti, se la (1.10) è vericata, ponendo A = Ω, si ottiene

P(XT = j0, . . . , XT+n = jn ∩ Ω|T < +∞, XT = i)

= P(XT = j0, . . . , XT+n = jn|T < +∞, XT = i) (1.11)(1.10)= Pi(X0 = j0, . . . , Xn = jn), (1.12)

cioè che il processo

(XT+n)n∈N :(Ω, F , FT+nn∈N, PTi

)→ (S,BS)

ha le stesse distribuzioni congiunte nito dimensionali di

(Xn)n∈N :(Ω, F , Fnn∈N, Pi

)→ (S,BS).

Ma per il Teorema 1.3.1 sulla proprietà di Markov, quest'ultimo èuna C.M.(P, δi). Per il Teorema 1.2.1 sulle distribuzioni congiunte nitodimensionali segue quindi che anche (XT+n)n∈N è una C.M.(P, δi).

Sfruttando inne l'identità (1.11) = (1.12), dalla (1.10) segue l'indipen-denza richiesta in (1.9) per gli eventi elementari di σ

((XT+n)n∈N

). Con la

σ-additività si conclude la dimostrazione.Si vuole quindi dimostrare la (1.10).

Se P(A) = 0 la tesi è banalmente vericata. Si supponga pertanto P(A) > 0.Posto N = n ∈ N : P(A ∩ T = m,XT = i) > 0, si ha

20 Catene di Markov

P(XT = j0, . . . , XT+n = jn ∩ A|T < +∞, XT = i)

.=

P(XT = j0, . . . , XT+n = jn ∩ A ∩ T < +∞, XT = i)P(T < +∞, XT = i)

.=

∑m∈N

P( =:C︷︸︸︷XT = j0, . . . , XT+n = jn∩

=:Dm︷︸︸︷A ∩ T = m,XT = i

)P(T < +∞, XT = i)

=∑m∈N

P(C ∩Dm)

P(T < +∞, XT = i)

=∑m∈N

P(Dm)P(C|Dm)

P(T < +∞, XT = i)

.=

∑m∈N

P(A ∩ T = m,XT = i)P(T < +∞, XT = i)

· P(C|Dm).

Si vuole ora dimostrare che P(C|Dm) è indipendente da m, ovvero che perogni m,n ∈ N si ha P(C|Dm) = P(C|Dn). Sia dunque m ∈ N arbitrario.Poiché A ∈ FT , si ha che A ∩ T = m ∈ Fm. Si supponga senza perderein generalità che A ∩ T = m sia un evento elementare5 di Fm, ovvero cheesistano i0, . . . , im−1 ∈ S tali che6

A ∩ T = m = X0 = i0, . . . Xm−1 = im−1, Xm = i. (1.13)

Allora, per la proprietà di Markov (M) e per il Teorema sulla proprietà diMarkov (T), si ha

P(C|Dm).= P(XT = j0, . . . , XT+n = jn|A ∩ T = m,XT = i)

(1.7)= P(XT = j0, . . . , XT+n = jn|A ∩ T = m,Xm = i).=

P(XT = j0, . . . , XT+n = jn ∩ A ∩ T = m,Xm = i)P(A ∩ T = m,Xm = i)

(1.7)=

P(Xm = j0, . . . , Xm+n = jn ∩ A ∩ T = m,Xm = i)P(A ∩ T = m,Xm = i)

.= P(Xm = j0, . . . , Xm+n = jn|A ∩ T = m,Xm = i)

(1.13)= P(Xm = j0, . . . , Xm+n = jn|X0 = i0, . . . , Xm = i)

(M)= P(Xm = j0, . . . , Xm+n = jn|Xm = i)(T )= Pi(X0 = j0, . . . , Xn = jn).

5Se così non fosse, A si potrebbe comunque scrivere come unione al più numerabile dieventi elementari e quanto segue si potrebbe estendere in modo immediato al caso generalesfruttando la σ-additività di P.

6Si noti che avendo imposto che m ∈ N , deve valere necessariamente Xm = i.

1.5 Classicazione degli stati di una catena 21

Sfruttando quindi il fatto che P(C|Dm) è indipendente da m e che sommaresu N equivale a sommare su N , si ha

∑m∈N

P(A ∩ T = m,XT = i)P(T < +∞, XT = i)

· P(C|Dm)

= Pi(X0 = j0, . . . , Xn = jn)∑m∈N

P(A ∩ T = m,XT = i)P(T < +∞, XT = i)

= Pi(X0 = j0, . . . , Xn = jn)∑m∈N

P(A ∩ T = m,XT = i)P(T < +∞, XT = i)

= Pi(X0 = j0, . . . , Xn = jn)P(A ∩ T < +∞, XT = i),

che è precisamente la (1.10).

Osservazione 1.4.4. Concludiamo questa sezione con una denizione utilenelle applicazioni.

Denizione 11. Siano (Xn)n∈N : (Ω,F , Fnn∈N,P) → (S,BS) e j ∈ Sssato. Si ponga T 0

j ≡ 0. Per ogni n ∈ N\0 si denisce n-esimo istante divisita dello stato j (dopo l'istante iniziale), la funzione

T nj : Ω → N ∪ +∞,ω 7→ T nj (ω) := inf

m > T n−1

j (ω) : Xm(ω) = j.

1.5 Classicazione degli stati di una catena

Osservazione 1.5.1. Lo scopo di questa sezione è quello di classicare glistati di una C.M. in due classi distinte. Quelli transitori (in cui la catenacadrà soltanto un numero nito di volte) e quelli ricorrenti (in cui la catenacadrà un numero innito di volte), enunciando dei criteri che permettano didedurre la transitorietà o la ricorrenza degli stati.

Notazione 12. Sia (Xn)n∈N : (Ω,F , Fnn∈N,P) → (S,BS) e sia i ∈ Sssato. Si indica col simbolo Pi la probabilità condizionata

Pi = P( · |X0 = i).

Denizione 12. Sia (Xn)n∈N : (Ω,F , Fnn∈N,P)→ (S,BS) e siano i, j ∈ Sssati. Si dice che i conduce a j, e si scrive i→ j, se esiste un n ∈ N tale che

Pi(Xn = j) > 0.

Si dice che i comunica con j, e si scrive i↔ j, se i→ j e j → i.

22 Catene di Markov

Denizione 13 (Classe chiusa). Sia (Xn)n∈N : (Ω,F , Fnn∈N,P)→ (S,BS)e sia C ⊂ S. Si dice che C è una classe chiusa se per ogni i ∈ C e j ∈ S taliche i→ j, si ha j ∈ C.

Osservazione 1.5.2 (Intuitivamente). In sostanza da una classe chiusa nonc'è possibilità di fuga.

Denizione 14 (Classe irriducibile). Sia (Xn)n∈N : (Ω,F , Fnn∈N,P) →(S,BS) e sia C ⊂ S. Si dice che C è una classe irriducibile se C è chiusa etutti i suoi stati sono comunicanti tra loro.

Denizione 15 (C.M. irriducibile). Sia (Xn)n∈N : (Ω,F , Fnn∈N,P) →(S,BS) una C.M.(P, π). Si dice che la catena è irriducibile se S è costituitoda un'unica classe irriducibile.

Osservazione 1.5.3. Si noti che ↔ costituisce una relazione d'equivalenzatra gli stati di una catena di Markov. È pertanto sempre possibile partizionaregli stati di una catena in classi comunicanti. Qualora qualcuna di queste classifosse anche chiusa, sarebbe quindi possibile studiare il comportamento dellaC.M. restringendosi a quella singola classe irriducibile. Per questo motivo èutile focalizzarsi in modo particolare sullo studio delle catene irriducibili.

Notazione 13. Sia (Xn)n∈N : (Ω,F , Fnn∈N,P)→ (S,BS) una C.M.(P, π).Per ogni i, j ∈ S e per ogni n ∈ N, si denota con

f(n)ij := Pi(X1 6= j, . . . , Xn−1 6= j,Xn = j)

la probabilità che, partendo da i, la C.M. arrivi in j in esattamente n passi.Si denota inoltre con

fij := Pi

(+∞⊔n=1

Xn = j

)=

+∞∑n=1

Pi(Xn = j) =∞∑n=1

f(n)ij (1.14)

la probabilità che, partendo da i, la C.M. arrivi prima o poi in j, ovvero laprobabilità che, partendo da i, la C.M. passi per j almeno una volta.

Osservazione 1.5.4 (Importante). Si noti che, detto T 1j il primo istante di

visita dello stato j (dopo l'istante iniziale)7, si ha

f(n)ij = Pi(T 1

j = n), (1.15)

fij = Pi(T 1j < +∞). (1.16)

7Vedi Denizione 11, pag. 21.


Denizione 16 (Stati ricorrenti e transitori). Sia (Xn)n∈N :(Ω,F , Fnn∈N,P) → (S,BS) una C.M.(P, π) e sia i ∈ S uno statossato. Si dice che

• i è ricorrente se fii = 1;

• i è transitorio se fii < 1.

Osservazione 1.5.5 (Stati ricorrenti e transitori). Si noti che le denizionidi ricorrenza e transitorietà sono disgiuntive ed esaustive. Dunque ogni statoè ricorrente se e solo se non è transitorio.

Teorema 1.5.1. Sia (Xn)n∈N : (Ω,F , Fnn∈N,P)→ (S,BS) una C.M.(P, π)e sia i ∈ S. Si ha

1. Pi(Xn = i, i.o.) = 0 ⇔ i è transitorio,

2. Pi(Xn = i, i.o.) = 1 ⇔ i è ricorrente.

Dimostrazione. Si dimostrano contemporaneamente entrambi i casi.

Siano i ∈ S, k ∈ N e 1 ≤ n1 ≤ . . . ≤ nk ∈ N ssati. Si consideri l'evento

An1,...,nk:= X1 6= i, . . . , Xn1−1 6= i, Xn1 = i,

Xn1+1 6= i, . . . , Xn2−1 6= i, Xn2 = i,...

Xnh−1+1 6= i, . . . , Xnh−1 6= i, Xnh= i

...Xnk−1+1 6= i, . . . , Xnk−1 6= i, Xnk

= i

Informalmente, An1,...,nkè l'evento dopo l'istante iniziale la C.M. visita i8

esattamente agli istanti n1, . . . , nk. Per la proprietà di Markov (M) e per il

8Cioè capita che Xn = i.

24 Catene di Markov

Teorema sulla proprietà di Markov (T ), si ha

Pi(An1,...,nk)

(M)= Pi(X1 6= i, . . . , Xn1−1 6= i,Xn1 = i) ·

·P(Xn1+1 6= i, . . . , Xn2−1 6= i,Xn2 = i|Xn1 = i) ·...

·P(Xnh−1+1 6= i, . . . , Xnh−1 6= i,Xnh= i|Xnh−1

= i) ·...

·P(Xnk−1+1 6= i, . . . , Xnk−1 6= i,Xnk= i|Xnk−1

= i)

(T )= Pi(X1 6= i, . . . , Xn1−1 6= i,Xn1 = i) ·

·Pi(X1 6= i, . . . , Xn2−n1−1 6= i,Xn2−n1 = i) ·...

·Pi(X1 6= i, . . . , Xnh−nh−1−1 6= i,Xnh−nh−1= i) ·

...

·Pi(X1 6= i, . . . , Xnk−nk−1−1 6= i,Xnk−nk−1= i)

.= f

(n1)ii · f (n2−n1)

ii · . . . · f (nk−1−nk−2)ii · f (nk−nk−1)

ii .

Si denisca ora l'evento

Bk :=⊔

n1,...,nk∈N,1≤n1≤...≤nk

An1,...,nk.

Informalmente, Bk è l'evento dopo l'istante iniziale la C.M. visita i almenok volte. Si ha pertanto

Pi(Bk) =∑

n1,...,nk∈N,1≤n1≤...≤nk

Pi(An1,...,nk)

=∑

n1,...,nk∈N,1≤n1≤...≤nk

f(n1)ii · f (n2−n1)

ii · . . . · f (nk−1−nk−2)ii · f (nk−nk−1)

ii

(1.14)= (fii)

k .

Si noti che, per ogni n ∈ N, si ha Bn ⊃ Bn+1 e che Bn ↓ Xn = i, i.o.. Perla continuià della misura di probabilità si ha allora

P(Xn = i, i.o.) = limn→+∞

Pi(Bn) = limn→+∞

(fii)n =

0 ⇔ fii < 0,1 ⇔ fii = 1.


Osservazione 1.5.6. Si sottolinea che il teorema precedente non deriva dallaLegge 0-1 di Kolmogorov. Infatti al variare di n ∈ N gli Xn = i non sonoin generale indipendenti.

Notazione 14 (Numero di visite ad uno stato). Sia (Xn)n∈N :(Ω,F , Fnn∈N,P) → (S,BS) una catena e sia i ∈ S ssato. Si deniscenumero di visite allo stato i (dopo l'istante iniziale) la variabile aleatoria

Vi :=+∞∑n=1

IXn=i.

Denizione 17 (Numero medio di visite ad uno stato). Sia (Xn)n∈N :(Ω,F , Fnn∈N,P) → (S,BS) una C.M.(P, π) e sia i ∈ S ssato. Si deniscenumero medio di visite allo stato i (partendo da i) il numero reale esteso

EPi[Vi]

.=

+∞∑n=1

Pi(Xn = i).=

+∞∑n=1

p(n)ii .

Osservazione 1.5.7 (First passage decomposition). Sia (Xn)n∈N :(Ω,F , Fnn∈N,P) → (S,BS) una catena, siano i, j ∈ S e sia n ∈ N\0.Si noti che si può sempre scrivere la seguente decomposizione, detta rstpassage decomposition:

Xn = j =n−1⊔s=0

X1 6= j,X2 6= j, . . . , Xn−s−1 6= j,Xn−s = j,Xn = j

=n⊔s=1

X1 6= j,X2 6= j, . . . , Xs−1 6= j,Xs = j,Xn = j

In questo modo si mettono in evidenza gli insiemi in cui la prima visita dellacatena allo stato j (dopo l'istante iniziale) avviene esattamente all'istanten− s (o s, a seconda di come si conta).

Lemma 1.5.1 (First passage decomposition). Sia (Xn)n∈N :(Ω,F , Fnn∈N,P) → (S,BS) una C.M.(P, π). Per ogni i, j ∈ S e perogni n ∈ N\0 si ha9

p(n)ij =

n−1∑s=0

f(n−s)ij p

(s)jj =

n∑s=1

f(s)ij p

(n−s)jj .

9Si ricordi che dalla Notazione 8 di pag. 11 segue che per ogni i, j ∈ S, si ha p(0)ij.= δij .

26 Catene di Markov

Dimostrazione. Chiaramente basta dimostrare l'uguaglianza dei primi duemembri. Sfruttando l'osservazione precedente (D) e il Teorema sulla proprietàdi Markov (M), per ogni i, j ∈ S e per ogni n ∈ N si ha

p(n)ij

.= Pi(Xn = j)

(D)=

n−1∑s=0

Pi(X1 6= j, . . . , Xn−s−1 6= j,Xn−s = j,Xn = j)

(M)=

n−1∑s=0

Pi(X1 6= j, . . . , Xn−s−1 6= j,Xn−s = j)Pi(Xn = j|Xn−s = j)

=n−1∑s=0

f(n−s)ij p

(s)jj .

Teorema 1.5.2 (Criterio per transitorietà e ricorrenza). Sia (Xn)n∈N :(Ω,F , Fnn∈N,P)→ (S,BS) una C.M.(P, π) e sia i ∈ S ssato. Allora

1. i è transitorio ⇔ EPi[Vi] < +∞;

2. i è ricorrente ⇔ EPi[Vi] = +∞.

Dimostrazione. Chiaramente basta dimostrare il primo punto.

1. Si dimostrano separatamente le due implicazioni.

⇐) Essendo EPi[Vi]

.=∑+∞

n=1 Pi(Xn = i), si ha

+∞∑n=1

Pi(Xn = i) < +∞.

Per il primo lemma di Borel-Cantelli è quindi possibile concludereche Pi(Xn = i, i.o.) = 0. Dal Teorema 1.5.1 segue inne che i èricorrente.

⇒) Per ipotesi fii < 1. Si vuole determinare una maggiorazione con-vergente per EPi

[Vi].=∑+∞

n=1 p(n)ii . Si consideri il termine generale di

questa serie. Per la rst passage decomposition (F ) e scambiando


l'ordine delle sommatorie (S), per ogni N ∈ N\0, si ha

N∑n=1

p(n)ii

(F )=

N∑n=1

n−1∑s=0

f(n−s)ii p

(s)ii

(S)=

N−1∑s=0

N∑n=s+1

p(s)ii f

(n−s)ii =

N−1∑s=0

p(s)ii

N∑n=s+1

f(n−s)ii

≤N∑s=0

p(s)ii fii = fii + fii

N∑s=1

p(s)ii .

Confrontando inne primo ed ultimo membro (e ricordando cheper ipotesi fii < 1, si ottiene

N∑n=1

p(n)ii (1− fii) ≤ fii ⇐⇒

N∑n=1

p(n)ii ≤

fii1− fii

.

Avendo maggiorato in modo uniforme il termine generale di questaserie, segue la tesi.

Teorema 1.5.3 (Classicazione degli stati di una C.M. irriducibile). Sia(Xn)n∈N : (Ω,F , Fnn∈N,P) → (S,BS) una C.M.(P, π) irriducibile. Alloraavviene una e una sola delle seguenti:

1. tutti gli stati sono transitori;

2. tutti gli stati sono ricorrenti.

Inoltre

• la 1. è equivalente alle seguenti aermazioni:

1.a) per ogni i ∈ S si ha

Pi

(⋃j∈S

Xn = j, i.o.

)= 0;

1.b) per ogni i, j ∈ S, si ha

+∞∑n=1

p(n)ij < +∞.

28 Catene di Markov

• la 2. è equivalente alle seguenti aermazioni:

2.a) per ogni i ∈ S si ha

Pi

(⋂j∈S

Xn = j, i.o.

)= 1;

2.b) per ogni i, j ∈ S, si ha+∞∑n=1

p(n)ij = +∞.

Dimostrazione. Chiaramente è suciente dimostrare che se la 2 non siverica, allora la 1 è soddisfatta, e che la 1 implica la 1.b)10.

Si supponga quindi l'esistenza di un i ∈ S transitorio. Sia j ∈ S ssato inmodo arbitrario. Per il criterio di transitorietà enunciato precedentemente siha∑+∞

i=1 p(n)ii < +∞. Essendo inoltre S irriducibile esistono r, s ∈ N tale che

p(r)ij > 0 e p(s)

ji > 0. Per le equazioni di Chapman-Kolmogorov è inoltre chiaroche, per ogni n ∈ N si ha

p(r+n+s)ii ≥ p

(r)ij p

(n)jj p

(s)ji .

Sommando ambo i membri su n ≥ 1 e sfruttando la transitorietà di i si haquindi che j è transitorio.

Essendo i, j ∈ S arbitrari, per concludere la dimostrazione è sucienteprovare che

∑+∞n=1 p

(n)ij < +∞, ma questa stima segue immediatamente dalla

rst passage decomposition.L'equivalenza tra 2, 2.a) e 2.b) viene lasciata come esercizio al lettore

interessato11

Corollario 1.5.1. Sia (Xn)n∈N : (Ω,F , Fnn∈N,P) → (S,BS) unaC.M.(P, π) irriducibile e sia S nito. Allora tutti gli stati sono ricorrenti.

Dimostrazione. Segue direttamente dal teorema precedente.

Esercizio 2. Sia (Xn)n∈N : (Ω,F , Fnn∈N,P) → (S,BS) una C.M. (P, π)con S := 0, 1, . . . , 6 e matrice di transizione

P :=

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

1/3 0 0 1/3 1/3 00 0 0 1/2 1/2 00 0 0 0 0 10 0 0 0 1 0

.

10Infatti è chiaro che 1.b) ⇔ 1.a) e che 1.a) ⇒ 1.11Vedi Billingsley - Probability and measure, Theorem 8.3.


Si classichino i sei stati di S.

Teorema 1.5.4 (Criterio di transitorietà). Siano (Xn)n∈N :(Ω,F , Fnn∈N,P) → (S,BS) una C.M.(P, π) e j ∈ S arbitrario. Seesiste uno stato i tale che j → i ma i 6→ j, allora j è transitorio.

Dimostrazione. Per ipotesi e poiché N è un insieme discreto e limitato dalbasso, esiste il minimo m ∈ N tale che p(m)

ji > 0. Si ssi questo m. Allora,per le equazioni di Chapman-Kolmogorov e poichè m è il minimo numero dipassi per andare da j ad i, esistono m− 1 stati h1, . . . , hm−1 ∈ S\i, j taliche pjh1ph1h2 . . . phm−1i > 0. Si sottolinea che h1, . . . , hm−1 ∈ S\i, j, infattise un h` fosse uguale ad i o a j, la condizione di minimalità di m sarebbechiaramente contraddetta. Sia

A := X1 = h1, . . . , Xm−1 = hm−1, Xm = i.

Per quanto appena detto, è chiaro che Pj(A) > 0. Sia T 1j il primo istante di

visita dello stato j (dopo l'istante iniziale)12. Si noti che dimostrando

Pj(A ∩ T 1j < +∞) = 0 (1.17)

segue la tesi. Infatti se valesse la (1.17), si avrebbe

fjj(1.16)= Pj(T 1

j < +∞)

= Pj(T 1j < +∞ ∩ A) + Pj(T 1

j < +∞ ∩ Ac)(1.17)= Pj(T 1

j < +∞ ∩ Ac)≤ Pj(Ac) = 1− Pj(A)︸︷︷︸

>0

< 1,

dunque j sarebbe transitorio. Si dimostra allora la (1.17). Si noti innanzituttoche

Pj(A ∩ T 1j < +∞) .

=+∞∑k=1

Pj(A ∩ T 1j = k) (∗)

=+∞∑

k=m+1

Pj(A ∩ T 1j = k),

dove (∗) vale per denizione di A, in quanto, come sottolineato sopra, siha h1, . . . , hm−1 6= j. Si mostra ora che il termine generale della serie appenascritta è identicamente nullo. Per ogni k ∈ m+1,m+2, . . ., per la proprietà

12Vedi Denizione 11, pag. 21.

30 Catene di Markov

di Markov (M) si può scrivere

Pj(A ∩ T 1j = k) = Pj(T 1

j = k |A)Pj(A).= Pj(T 1

j = k|X1 = h1, . . . , Xm−1 = hm−1, Xm = i)Pj(A)

≤ Pj(Xk = j|X1 = h1, . . . , Xm−1 = hm−1, Xm = i)Pj(A)(M)= Pj(Xk = j|Xm = i)Pj(A).= P(Xk = j|Xm = i,X0 = j)Pj(A)

(M)= P(Xk = j|Xm = i)Pj(A).= p

(k−m)ij︸︷︷︸=0

Pj(A)

= 0,

dove p(k−m)ij = 0 in quanto per ipotesi i 6→ j.

Proposizione 1.5.1. Sia (Xn)n∈N : (Ω,F , Fnn∈N,P) → (S,BS) unaC.M.(P, π), con S nito. Allora esiste almeno una classe irriducibile e nonvuota C ⊂ S costituita da soli stati ricorrenti.

Dimostrazione. La dimostrazione di questo risultato si lascia come esercizioal lettore interessato.

Teorema 1.5.5 (Criterio di transitorietà per S nito). Sia (Xn)n∈N :(Ω,F , Fnn∈N,P) → (S,BS) una C.M.(P, π), con S nito e sia j ∈ S.Allora j è transitorio se e solo se esiste un i ∈ S tale che i→ j, ma j 6→ i.

Dimostrazione. Un'implicazione segue direttamente dal Teorema 1.5.4. Sidimostra il viceversa. Per la proposizione precedente esistono in S stati ri-correnti. Essendo S nito si può aermare che esiste un i ricorrente tale chej conduca ad i. Chiaramente i non può condurre a j, altrimenti j sarebbericorrente.

1.6 Alcuni esempi di catene di Markov

1.6.1 Catena a due stati

[Aggiungere]

1.6.2 Passeggiata aleatoria semplice su Z[Aggiungere]

1.7 Assorbimento e tempi di assorbimento 31

1.6.3 Passeggiata aleatoria semplice su Z2

[Aggiungere]

1.6.4 Passeggiata aleatoria semplice su Z3

[Aggiungere]

1.7 Assorbimento e tempi di assorbimento

Notazione 15. Per tutta la sezione, si indicherà con (Xn)n∈N :(Ω,F , Fnn∈N,P)→ (S,BS) una C.M.(P, π) e con A ⊂ S una classe chiusa.

Denizione 18 (Probabilità di assorbimento). Sia i ∈ S e sia TA il primoistante d'arrivo in A13. Si denisce probabilità di assorbimento in A (partendoda i), il numero

hAi := Pi(TA < +∞).

Osservazione 1.7.1 (Informalmente). A volte, in modo più informale, sipuò dire che hAi è la probabilità che, partendo da i, la C.M. entri in A. Sipuò anche trovare la notazione intuitiva hAi = Pi(colpire A).

Denizione 19 (Tempo medio di assorbimento in A). Sia i ∈ S e sia TA ilprimo istante d'arrivo in A. Si denisce tempo medio di assorbimento in A(partendo da i) il numero reale esteso

kAi := Ei(TA).=

+∞, se Pi(TA = +∞) 6= 0,∑n∈N

nPi(TA = n), se Pi(TA = +∞) = 0.

Talvolta, per indicare la formula precedente, si utilizzerà la notazionecompatta

kAi =:∑n∈N

nPi(TA = n).

Osservazione 1.7.2. Come si dimostra nei due successivi teoremi, sia laprobabilità che il tempo medio di assorbimento possono essere determinatisfruttando la matrice stocastica P della catena di Markov.

13Vedi Esempio 1.4.1, pag. 15.

32 Catene di Markov

Teorema 1.7.1. Con le notazioni appena introdotte, il vettore delle proba-bilità di assorbimento hA := (hAi , i ∈ S) è la minima soluzione non negativadel sistema

hAi = 1, i ∈ A,

hAi =∑j∈S

pijhAj , i /∈ A. (1.18)

(La minimalità signica che se x := (xi, i ∈ S) è un'altra soluzione di (1.18)tale che per ogni i ∈ S si abbia xi ≥ 0, allora per ogni i ∈ S si ha xi ≥ hAi .)

Dimostrazione. Si divide la dimostrazione in due parti.

• Si verica per prima cosa che hA soddisfa la (1.18).

È chiaro che se i ∈ A, allora hAi.= Pi(TA < +∞) = 1.

Sia invece i ∈ S\A. Allora Pi(TA ≥ 1) = 1, da cui

Pi(TA = 0) = 0. (1.19)

Dunque, per la proprietà di Markov (M), per ogni j ∈ S si ha

Pi(TA < +∞|X1 = j).= P(TA < +∞|X1 = j,X0 = i)

(1.19)= P

(infn ≥ 1 : Xn ∈ A < +∞

∣∣X1 = j,X0 = i)

(M)= P

(infn ≥ 1 : Xn ∈ A < +∞

∣∣ X1 = j)

= P(infn ≥ 0 : Xn ∈ A < +∞

∣∣X0 = j)

.= Pj(TA < +∞).= hAj .

In conclusione, quindi:

hAi.= Pi(TA < +∞)

=∑j∈S

Pi(TA < +∞, X1 = j)

=∑j∈S

Pi(TA < +∞|X1 = j)Pi(X1 = j)

=∑j∈S

pijhAj .

• Si verica ora la minimalità. Sia x := (xi, i ∈ S) una soluzione di (1.18)tale che, per ogni i ∈ S, si abbia xi ≥ 0.


È chiaro che se i ∈ A, allora hAi = xi = 1.

Sia invece i ∈ S\A. Allora x soddisfa

xi =∑j∈S

pijxj =∑j∈A

pij +∑j∈S\A

pijxj.

Sostituendo, per ogni j ∈ S\A, la relativa espressione per gli xj, siottiene

xi =∑j∈A

pij +∑j∈S\A

pij

∑k∈A

pjk +∑k∈S\A

pjkxk

.= Pi(X1 ∈ A) + Pi(X1 /∈ A,X2 ∈ A) +

∑j /∈A

∑k/∈A

pijpjkxk.

Procedendo iterativamente, per ogni n ≥ 1 si può scrivere

xi = Pi(X1 ∈ A) + . . .+ Pi(X1 /∈ A, . . . , Xn−1 /∈ A,Xn ∈ A)

+∑j1 /∈A

. . .∑jn /∈A

pij1pj1j2 . . . pjn−1jnxjn︸︷︷︸≥0

.

Si noti ora che

Pi(X1 ∈ A) + . . .+ Pi(X1 /∈ A, . . . , Xn−1 /∈ A,Xn ∈ A).= Pi(TA ≤ n).

Dunque per ogni n ≥ 1 si ha xi ≥ Pi(TA ≤ n). Osservando inne cheper ogni n ≥ 1 si ha TA ≤ n ⊂ TA ≤ n + 1, per la continuità dalbasso della misura di probabilità si può concludere che

xi ≥ limn→+∞

Pi(TA ≤ n) = Pi(TA < +∞) = hAi .

Osservazione 1.7.3. Presentiamo ora un paio di esempi di applicazione delteorema precedente.

Esempio 1.7.1. Sia

P :=

1 0 0 0

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

.

[Aggiungere]

34 Catene di Markov

1.7.1 Catene di Nascita e Morte

[Aggiungere]

Teorema 1.7.2. Con le notazioni precedentemente introdotte, il vettore deitempi medi di assorbimento kA := (kAi , i ∈ S) è la minima soluzione nonnegativa del sistema

kAi = 0, i ∈ A,

kAi = 1 +∑j∈S\A

pijkAj , i /∈ A. (1.20)

(La minimalità signica che se x := (xi, i ∈ S) è un'altra soluzione di (1.20)tale che per ogni i ∈ S si abbia xi ≥ 0, allora per ogni i ∈ S si ha xi ≥ kAi .)

Dimostrazione. Si dimostra soltanto che kA è soluzione di (1.20). Laminimalità si prova in modo analogo a quanto visto nel Teorema 1.7.1.

Sia i ∈ A. Allora Pi(TA = 0) = 1 e dunque, dalla Denizione 19, si puòconcludere immediatamente che kAi = 0.

Sia i /∈ A. Allora Pi(TA ≥ 1) = 1, da cui

Pi(TA = 0) = 0. (1.21)

Per ogni j ∈ S, dalla proprietà di Markov (M) si ha dunque

Ei[TA|X1 = j].=

∑n∈N

nPi(TA = n|X1 = j)

.=

∑n∈N

nP(TA = n|X1 = j,X0 = i)

(1.21)=

∑1≤n≤+∞

nP(TA = n|X1 = j,X0 = i)

(M)=

∑1≤n≤+∞

nP(TA = n|X1 = j)

=∑n∈N

(n+ 1)P(TA = n+ 1|X1 = j)

(M)=

∑n∈N

(n+ 1)P(TA = n|X0 = j)

=∑n∈N

nP(TA = n|X0 = j)︸︷︷︸.=Ej [TA]

+∑n∈N

P(TA = n|X0 = j)︸︷︷︸=1

= 1 + Ej[TA].


Segue pertanto che

kAi.= Ei[TA]

=∑j∈S

Ei[TAIX1=j

]=

∑j∈S

∑n∈N

nPi(TA = n ∩ X1 = j

)=

∑j∈S

∑n∈N

nPi(TA = n|X1 = j

)Pi(X1 = j

)=

∑j∈S

Pi(X1 = j

)∑n∈N

nPi(TA = n|X1 = j

).=

∑j∈S

Pi(X1 = j

)E[TA|X1 = j]

=∑j∈S

Pi(X1 = j

)(1 + Ej[TA]

)=

∑j∈S

Pi(X1 = j

)︸︷︷︸

=1

+∑j∈S

Pi(X1 = j

)︸︷︷︸.=pij

Ej[TA]︸︷︷︸.=kAj

= 1 +∑j∈S

pijkAj

= 1 +∑j∈S\A

pijkAj ,

dove l'ultima identità segue dal fatto che per ogni j ∈ A si ha kAj = 0.

Osservazione 1.7.4 (Intuitivamente). Il teorema precedente dice che se siparte già da dentro la classe (chiusa!) A, allora non bisogna aspettare nean-che un istante, mentre se si parte al di fuori di A, sarà certamente necessa-rio aspettare almeno un istante e in più bisognerà tenere sotto controllo lepossibili transizioni al di fuori di A.

Esempio 1.7.2. Si riprenda l'Esempio 1.7.1.[Aggiungere]

1.7.2 Rovina del giocatore

[Aggiungere]

36 Catene di Markov

1.8 Proprietà asintotiche delle catene di Mar-

kov

Notazione 16. Per tutta la sezione, si indicherà con (Xn)n∈N :(Ω,F , Fnn∈N,P)→ (S,BS) una C.M.(P, π).

1.8.1 Distribuzione invariante e distribuzione limite

Denizione 20 (Distribuzione invariante). Una distribuzione di probabilitàλ := (λi, i ∈ S) si dice invariante (o stazionaria) per la matrice stocasticaP := (pij, i, j ∈ S), se λP = λ, ossia se per ogni j ∈ S si ha

λj =∑i∈S

λipij.

Osservazione 1.8.1 (Informale). In modo informale si dice che una distri-buzione invariante rende stazionaria la propensione al moto del nucleo ditransizione P , come si capisce dal lemma seguente.

Lemma 1.8.1.

1. Sia λ := (λi, i ∈ S) una qualunque una distribuzione invariante per P .Allora per ogni n ∈ N si ha

λ = λP n.

2. Si supponga che la distribuzione iniziale π.= (πj, j ∈ S) sia invariante

per P . Allora per ogni n ∈ N e per ogni j ∈ S si ha

P(Xn = j) = P(X0 = j) = πj. (1.22)

Dimostrazione. Si dimostrano separatamente i due semplici casi.

1. Per ogni n ∈ N si ha

λP (n) = λP︸︷︷︸=λ

P (n−1) = λP (n−1) = . . . = λP = λ.


P(Xn = j) =∑i∈S

P(Xn = j,X0 = i)

=∑i∈S

P(X0 = i)P(Xn = j|X0 = i)

.=

∑i∈S

πip(n)ij

= πj.

1.8 Proprietà asintotiche delle catene di Markov 37

Osservazione 1.8.2 (Informale). Come anticipato prima, il lemma appenaenunciato aerma quanto segue. Se π è stazionaria allora dopo un qualunquenumero di passi la catena continua a muoversi in accordo con la distribuzioneiniziale.

Denizione 21. Si dice che una distribuzione π := (πi, i ∈ S) è ladistribuzione limite della C.M. (Xn)n∈N se per ogni i, j ∈ S si ha

limn→+∞

p(n)ij = πj.

Osservazione 1.8.3. Si noti che la denizione di distribuzione limite richiededue cose. Innanzitutto l'esistenza del limite (che non è aatto garantita ingenerale). Secondariamente la convergenza delle probabilità di transizione inn passi alla distribuzione limite. Tuttavia (per l'unicità del limite) è chiaroche se esiste una distribuzione limite, questa è unica.

Teorema 1.8.1. Sia S nito. Si supponga che esista distribuzione limiteπ := (πi, i ∈ S) di (Xn)n∈N. Allora π è invariante per P .

Dimostrazione. Siano j, k ∈ S arbitrari. Allora per le equazioni di Chapman-Kolmogorov (CK), si ha

πj = limn→+∞

p(n)kj

(CK)= lim

n→+∞

(∑i∈S

p(n−1)ki pij

)

=∑i∈S

limn→+∞

p(n−1)ki︸︷︷︸

=πi

pij

=

∑i∈S

πipij.

Osservazione 1.8.4. Si noti che nel penultimo passaggio della dimostrazioneprecedente si è potuto portare il limite all'interno della sommatoria, poiché Sè nito. Chiaramente questo passaggio non si sarebbe potuto fare se S fossestato numerabile. Lo studio dei legami tra distribuzione limite e distribuzioneinvariante presenta in eetti delle dicoltà aggiuntive nel caso S numerabile.A questo proposito si veda l'Osservazione 1.8.7 di pagina 45.

38 Catene di Markov

Esempio 1.8.1 (Importante). Come sottolineato nell'Osservazione 1.8.3,non è aatto detto che una distribuzione limite esista. Con il seguente sempli-ce esempio si mostra come il limite delle probabilità di transizione potrebbenon esistere per alcun i, j ∈ S.

Si consideri una qualunque C.M. a valori in S, con Card(S) = 2, aventematrice di transizione

P :=

(0 11 0

).

È chiaro che per ogni n ∈ N si ha P 2n = I e P 2n+1 = P , dunque per ognii, j ∈ S la successione p(n)

ij n∈N non converge.

1.8.2 Convergenza all'equilibrio

Denizione 22 (Aperiodicità di uno stato). Si dice che uno stato i ∈ S èaperiodico se esiste m ∈ N tale che, per ogni n ≥ m si ha p(n)

ii > 0.

Lemma 1.8.2 (Aperiodicità come proprietà di classe). Si supponga che laC.M. (Xn)n∈N sia irriducibile e che esista uno stato i ∈ S aperiodico. Alloraper ogni j, k ∈ S esiste un m(j, k) ∈ N tale che, per ogni n ≥ m(j, k) si ha

p(n)jk > 0. (In particolare tutti gli stati sono aperiodici.)

Dimostrazione. Siano j, k ∈ S arbitrari. Essendo (Xn)n∈N irriducibile esi-stono r, s ∈ N tali che p

(r)ji > 0 e p

(s)ik > 0. Per le equazioni di

Chapman-Kolmogorov si può quindi scrivere, per ogni n ∈ N,

p(r+n+s)jk ≥ p

(r)ji p

(n)ii p

(s)ik .

Essendo i periodico si ha quindi la tesi.

Osservazione 1.8.5. A seguito del Teorema 1.5.3 e del Lemma 1.8.2 èpossibile dare le denizioni che seguono.

Denizione 23 (Proprietà di classe). Sia (Xn)n∈N irriducibile. Si dice che

• (Xn)n∈N è transitoria, se tutti i suoi stati sono transitori,

• (Xn)n∈N è ricorrente, se tutti i suoi stati sono ricorrenti,

• (Xn)n∈N è aperiodica, se tutti i suoi stati sono aperiodici.

Teorema 1.8.2 (di convergenza all'equilibrio). Sia (Xn)n∈N :(Ω,F , Fnn∈N,P) → (S,BS) una C.M.(P, π) irriducibile e aperiodica.Si supponga inoltre l'esistenza di una distribuzione λ := (λi, i ∈ S)invariante per P . Allora


1. (Xn)n∈N è ricorrente;

2. λ è la distribuzione limite di (Xn)n∈N;

3. per ogni i ∈ S si ha λi > 0.

Dimostrazione. Si dimostrano separatamente i vari casi.

1. Si supponga per assurdo che (Xn)n∈N sia transitoria. Allora, ssati inmodo arbitrario i, j ∈ S, si ha14

∑n∈N p

(n)ij < +∞. In particolare,

dunque,lim

n→+∞p

(n)ij = 0.

Ma, ricordando che λ è invariante, per ogni n ∈ N si ha

λj =∑k∈S

λkp(n)kj . (1.23)

Si divide ora l'analisi in due casi, al variare della cardinalità di S.

• Se S è nito, allora per la linearità del limite, dalla (1.23) si ottiene

λj = limn→+∞

∑k∈S

λkp(n)kj =

∑k∈S

λk limn→+∞

p(n)kj︸︷︷︸

=0

= 0.

Essendo j arbitrario questo implica che λ = 0 e ciò è assurdo inquanto

∑k∈S λk = 1.

• Se S è innito, si osservi preliminarmente che per ogni n ∈ N siha

λip(n)ij ≤ λi

e che per ipotesi∑

k∈S λi = 1 < +∞. Allora passando al limitenella (1.23), per il Teorema di Convergenza Dominata15 (D) siconclude nuovamente che

λj = limn→+∞

∑k∈S

λkp(n)kj

(D)=

∑k∈S

λk limn→+∞

p(n)kj︸︷︷︸

=0

= 0.

Dall'arbitrarietà di j segue l'assurdo.

14Per il Teorema 1.5.3 di pag. 27.15Nel caso discreto.

40 Catene di Markov

2. Si dimostra questo punto con la tecnica dell'accoppiamento di duecatene di Markov.

Ricordando che P.= (pij, i, j ∈ S) è la matrice di transizione di

(Xn)n∈N, si consideri su S × S la matrice stocastica

P :=(pikpj`, (i, j), (k, `) ∈ S × S

).

Ricordando che π.= (πi, i ∈ S) è la distribuzione iniziale di (Xn)n∈N,

si consideri su S × S la distribuzione

µ :=(πiλj, (i, j) ∈ S × S

).

Per il Teorema di Esistenza 1.1.1 di pag. 6 esiste una catena di Mar-kov (Yn, Zn)n∈N, denita su qualche spazio ltrato e a valori in S × S,avente matrice di transizione P e distribuzione iniziale µ. Si dice che(Yn, Zn)n∈N è la catena accoppiata16 (alla C.M. (Xn)n∈N). Si vericafacilmente che per ogni n ∈ N e per ogni (i, j), (k, `) ∈ S × S si ha

P(n)(i,j)(k,`) = p

(n)ik p

(n)j` .

Essendo (Xn)n∈N irriducibile e aperiodica è immediato concludere cheanche la catena accoppiata è aperiodica. Per il lemma precedente, lacatena accoppiata è anche irriducibile.

Inoltre è chiaro che la catena accoppiata ammette la distribuzioneinvariante

λ := (λiλj, (i, j) ∈ S × S),

infatti, essendo λ invariante per (Xn)n∈N, per ogni (k, `) ∈ S × S si ha∑(i,j)∈S×S

λ(i,j)P(i,j)(k,`).=

∑i,j∈S

λiλj pikpj,`

=∑i∈S

λipik︸︷︷︸=λk

∑j∈S

λjpj`︸︷︷︸=λ`

= λ(k,`).

Per il punto 1, la catena accoppiata è pertanto ricorrente.

16Per come è stata costruita, la catena accoppiata descrive il comportamento congiuntodi una coppia di C.M. indipendenti, con distribuzioni iniziali π e λ e con comune matrice ditransizione P . Informalmente, è come se avessimo accostato a (Xn)n∈N una C.M. (Zn)n∈Nche evolve secondo la sua stessa legge, ma da essa indipendente e con distribuzione inizialeinvariante.


Siano allora i, j, i0 ∈ S ssati in modo arbitrario. Per il Teorema 1.5.3di pag. 27, dalla ricorrenza della catena accoppiata segue che

P(i,j)

((Yn, Zn) = (i0, i0), i.o.

)= 1 (1.24)

(ovvero, detto informalmente, che indipendentemente da dove partono,le due catene (Yn)n∈N e (Zn)n∈N si incontrano quasi certamente in i0innite volte). Denito allora il tempo d'arresto

T : Ω→ N, ω 7→ T (ω) := infn ∈ N\0 : (Xn, Yn) = (i0, i0)

(ovvero il primo istante in cui le catene si incontrano in i0), dalla (1.24)segue immediatamente (ragionando per assurdo) che

P(i,j)(T < +∞) = 1.

(L'idea informale ora è la seguente. Sfruttando la proprietà di Markovforte, si vuole dimostrare che pur partendo da stati diversi i e j, dalmomento in cui le due catene (Yn)n∈N e (Zn)n∈N si incontrano, ripartonoseguendo le stesse legge di probabilità, diventando a tutti gli eettiindistinguibili. Da quel punto in poi quindi gli eetti della distribuzioneiniziale sono completamente annullati. Con questo fatto sarà possibileprovare facilmente la tesi.)

Si ssino arbitrariamente k, ` ∈ S e m,n ∈ N, con m ≤ n. Dallaproprietà di Markov forte (M), segue che

P(i,j)

((Yn, Zn) = (k, `), T = m

)(M)= P(i,j)

((Y0, Z0) 6= (i0, i0), . . . , (Ym−1, Zm−1) 6= (i0, i0), (Ym, Zm) = (i0, i0)

)·

·P(i0,i0)

((Yn−m, Zn−m) = (k, `)

).= P(i,j)(T = m)p

(n−m)i0k

p(n−m)i0,`

.

Sommando primo ed ultimo membro su ` ∈ S, si ottiene la (1.25);sommando primo ed ultimo membro su k ∈ S, si ottiene la (1.26):

P(i,j)(Yn = k, T = m) = P(i,j)(T = m)p(n−m)i0k

; (1.25)

P(i,j)(Zn = `, T = m) = P(i,j)(T = m)p(n−m)i0`

. (1.26)

Essendo m, k ed ` arbitrari, le uguaglianze appena scritte rimangonovalide nel caso particolare k = ` e se si somma su m ∈ 0, . . . , n.

42 Catene di Markov

Procedendo in questo modo, il confronto delle equazioni (1.25) e (1.26)porta a concludere che

P(i,j)(Yn = k, T ≤ n) = P(i,j)(Zn = k, T ≤ n)

(ovvero che, indipendentemente da dove si è partiti, le probabilità dicadere in uno stato k dopo l'istante di incontro T , sono le stesse).

Dall'identità appena scritta segue che

P(i,j)(Yn = k) = P(i,j)(Yn = k, T ≤ n) + P(i,j)(Yn = k, T > n)

= P(i,j)(Zn = k, T ≤ n) + P(i,j)(Yn = k, T > n)

≤ P(i,j)(Zn = k) + P(i,j)(T > n)

e analogamente che

P(i,j)(Zn = k) ≤ P(i,j)(Yn = k) + P(i,j)(T > n).

La tesi segue quindi osservando che

|p(n)ik − λk| = |P(i,j)(Yn = k)− P(i,j)(Zn = k)|

≤ P(i,j)(T > n)

e che passando al limite per n→ +∞ l'ultimo membro è nullo in quantoil tempo d'arresto T è quasi certamente nito. Si ha cioè

limn→+∞

|p(n)ik − λk| = 0. (1.27)

3. Sia i ∈ S arbitrario. Si vuole mostrare che λi > 0. Sia j ∈ S ssatoarbitrariamente. Essendo (Xn)n∈N irriducibile, esistono r, s ∈ N tali chep

(r)ij > 0 e p(s)

ji > 0. Sfruttando le equazioni di Chapman-Kolmogorov,per ogni n ∈ N si ha

p(r+s+n)ii ≥ p

(r)ij p

(n)jj p

(s)ji .

Inoltre, grazie al punto precedente, si possono passare ambo i membridella disuguaglianza precedente al limite (per n→ +∞) , ottenendo

λi ≥ p(r)ij p

(s)ji︸︷︷︸

>0

λj.

Essendo j arbitrario la disuguaglianza precedente vale per tutti i j ∈ S,ma essendo λ una distribuzione17, esiste certamente un j ∈ S tale cheλj > 0. Si ha quindi

λi ≥ p(r)ij p

(s)ji λj > 0.

Dall'arbitrarietà di i segue quindi la tesi.17Quindi tale che

∑j∈S λj = 1.


Osservazione 1.8.6 (Intuitivamente). Si faccia attenzione all'interpretazio-ne probabilistica di questo teorema. La convergenza all'equilibrio

limn→+∞

p(n)ij = πj, ∀i, j ∈ S,

aerma che, partendo da un qualunque stato i, la probabilità di raggiungereuno stato j in un numero innito di passi è data dalla distribuzione invariante,e dipende quindi soltanto dallo stato di arrivo j. Dunque, indipendentementedal particolare stato in cui la catena parta, allo scorrere del tempo questatenderà a sparpagliarsi toccando tutti gli stati secondo la legge imposta dalladistribuzione invariante. Proprio questa considerazione ha portato allo studiodel cosiddetto time reversal, di cui si parlerà nel prossimo paragrafo.

Teorema 1.8.3 (Non esistenza della distribuzione invariante). Sia (Xn)n∈Nuna C.M. irriducibile e aperiodica. Se non esiste una distribuzione invariante,allora per ogni i, j ∈ S si ha

limn→+∞

p(n)ij = 0.

Dimostrazione. Essendo (Xn)n∈N irriducibile, (Xn)n∈N è o ricorrente o transi-toria. Senza perdere in generalità si può supporre (Xn)n∈N ricorrente, infattise fosse transitoria si avrebbe

∀i, j ∈ S∑n∈N

p(n)ij < +∞ =⇒ ∀i, j ∈ S lim

n→+∞p

(n)ij = 0.

Sia allora (Xn)n∈N ricorrente.Analogamente a quanto visto nella dimostrazione del Teorema di Convergen-za all'equilibrio (TCE), si consideri la catena accoppiata (Yn, Zn)n∈N, aventematrice di transizione

P :=(pikpj`, (i, j), (k, `) ∈ S × S

)e distribuzione iniziale18

µ := (πiπj, (i, j) ∈ S × S).

18Si noti che la scelta della distribuzione iniziale è diversa da quella fatta nel teoremadi convergenza all'equilibrio.

44 Catene di Markov

Come mostrato nel (TCE), anche (Yn, Zn)n∈N è irriducibile. Di nuovo, se(Yn, Zn)n∈N fosse transitoria, si avrebbe

∀(i, j), (k, `) ∈ S × S,∑n∈N

P(n)(i,k)(j,`) < +∞,

=⇒ ∀(i, j), (k, `) ∈ S × S, limn→+∞

P(n)(i,k)(j,`) = 0,

=⇒ ∀(i, i), (k, k) ∈ S × S, limn→+∞

P(n)(i,i)(k,k) = lim

n→+∞

(p

(n)ik

)2

= 0,

=⇒ ∀i, k ∈ S, limn→+∞

p(n)ik = 0.

Sia allora (Yn, Zn)n∈N ricorrente.Ripetendo lo stesso ragionamento fatto nel (TCE) si ottiene che19, per ognii, j, k ∈ S,

limn→+∞

|p(n)ik − p

(n)jk | = 0. (1.28)

Ragionando per assurdo, si suppone l'esistenza di h, ` ∈ S tali che

p(n)h`

n→+∞6−→ 0. (1.29)

Si vuole dimostrare che in questa ipotesi è possibile costruire unadistribuzione stazionaria, contraddicendo così le premesse del teorema.

Si osservi innanzitutto, che essendo(p

(n)h`

)n∈N

una successione limitata di

numeri reali, esiste certamente una sua sottosuccessione convergente ad unnumero strettamente positivo (per la (1.29)) e indipendente da h (per la(1.28)). Procedendo in modo diagonale si può trovare una successione cre-scente di interi naturali nuu∈N tale che, per ogni i, j ∈ S si abbia l'esistenzadel limite

αj := limu→+∞

p(nu)ij

con (per quanto appena detto) almeno α` > 0. Per il Lemma di Fatou, si hadunque

0 < α :=∑j∈M

αj.=∑j∈M

lim infu→+∞

p(nu)ij ≤ lim inf

u→+∞

∑j∈M

p(nu)ij︸︷︷︸

=1

= 1.

Ora, per le equazioni di Kolmogorov-Chapman, per ogni i, j ∈ S e per ogniu ∈ N si ha ∑

k∈S

p(nu)ik pkj =

∑k∈S

pikp(nu)kj .

19La formula che segue è infatti l'analoga della (1.27), ma scritta nel caso più generalein cui la (Zn)n∈N possa non avere una distribuzione invariante.


Per le equazioni di Kolmogorov-Chapman (KC), il Lemma di Fatou (F ) edil Teorema di convergenza dominata (D), per ogni j ∈ S,∑

k∈S

αkpkj =∑k∈S

lim infu→+∞

p(nu)ik pkj

(F )

≤ lim infu→+∞

∑k∈S

p(nu)ik pkj

(KC)= lim inf

u→+∞

∑k∈S

pikp(nu)kj

(D)=

∑k∈S

pik lim infu→+∞

p(nu)kj

= αj.

Se (per assurdo) per qualche j ∈ S la disuguaglianza (F ) fosse stretta,sommando su S si otterrebbe∑

j∈S

(∑k∈S

αkpkj

)<∑m∈S

αm,

ma ciò è assurdo in quanto, per il Teorema di Fubini,

∑j∈S

(∑k∈S

αkpkj

)=

∑k∈S

(∑j∈S

αkpkj

)

=∑k∈S

αk

(∑j∈S

pkj

)︸︷︷︸

=1

.

Dunque, per ogni j ∈ S ∑k∈S

αkpkj = αj,

ovvero la distribuzioneλ :=

(αjα, j ∈ S

)è stazionaria per P .

Osservazione 1.8.7. La contronominale del teorema precedente aermache, per una catena irriducibile e aperiodica, l'esistenza di una distribu-zione limite implica l'esistenza di una distribuzione stazionaria. Il teoremaprecedente è quindi il viceversa del teorema di convergenza all'equilibrio.

46 Catene di Markov

1.8.3 Time reversal e catene reversibili

Osservazione 1.8.8 (Introduzione informale). Nelle catene di Markov il fu-turo ed il passato sono indipendenti dato il presente. Questa proprietà, percosì dire, di simmetria, ha suggerito lo studio di catene di Markov in cuiil tempo scorre all'indietro. Il Teorema di convergenza all'equilibrio, tutta-via, mostra un comportamento asimmetrico nel tempo. Pur partendo da unacongurazione iniziale molto organizzata (X0 = i, per qualche i ∈ S, ovverotutta la massa è concentrata in un solo punto), la catena tende ad evolve-re verso una congurazione più disorganizzata, descritta precisamente dalladistribuzione invariante. Questo aspetto viene spesso interpretato come unaumento di entropia del sistema stesso. Volendo quindi ottenere una simme-tria temporale della catena, risulta necessario partire nell'equilibrio, ovveroda una distribuzione iniziale che sia uguale a quella limite. Il risultato chesegue mostra come una C.M. nell'equilibrio, quando percorsa all'indietro,rimanga una C.M. (con matrice di transizione che potrebbe però cambiare).

Denizione 24 (Time reversal). Fissato N ∈ N, sia (Xn)Nn=0 :(Ω,F , FnNn=0,P) → (S,BS) una C.M.(P, π). Si dice che (Yn)Nn=0 è la timereversal di (Xn)Nn=0 se, per ogni n ∈ 0, . . . , N si ha

Yn = XN−n.

Teorema 1.8.4 (Time reversal nito). Fissato N ∈ N, sia (Xn)Nn=0 :(Ω,F , FnNn=0,P) → (S,BS) una C.M.(P, π) irriducibile avente distribu-zione iniziale π stazionaria. Siano (Yn)Nn=0 la time reversal di (Xn)Nn=0,P := (pij, i, j ∈ S) e π := (πi, i ∈ S). Allora

1. la matrice P := (pij, i, j ∈ S), denita per ogni i, j ∈ S da

πj pji = πipij,

detta matrice duale di P , ammette π come distribuzione invariante;

2. la time reversal (Yn)Nn=0 : (Ω,F , GnNn=0,P) → (S,BS), dove GnNn=0

è la ltrazione naturale di (Yn)Nn=0, è una C.M.(P , π) irriducibile.

Dimostrazione. Si dimostrano separatamente i due punti.

1. Chiaramente P è una matrice stocastica, infatti, essendo π invarianteper P , per ogni i ∈ S si ha∑

j∈S

pij.=

1

πi

∑j∈S

πjpiji =πiπi

= 1.


Inoltre, essendo P stocastica, per ogni j ∈ S si ha∑i∈S

πipij.=∑i∈S

πiπjπipji = πj

∑i∈S

pji = πj,

dunque π è invariante per P .

2. È chiaro che (Yn)Nn=0 sia GnNn=0-adattata. Avendosi poi, per ognii0, . . . , iN ∈ S

P(Y0 = i0, . . . , YN = iN).= P(X0 = iN , . . . , XN = i0)

(1.4)= πiNpiN iN−1

. . . pi2i1pi1i0.= πiN

πiN−1

πiNpiN−1iN . . .

πi1πi2

pi1i2πi0πi1

pi0i1

= πi0 pi0i1 pi1i2 . . . piN−1iN

e per ogni n ∈ 0, . . . , N − 1, i, j ∈ SP(Yn+1 = j|Yn = i)

.= P(XN−n−1 = j|XN−n = i)

.=

P(XN−n−1 = j,XN−n = i)

P(XN−n = i)︸︷︷︸(1.22)

= πi

=

.=pji︷︸︸︷

P(XN−n = i|XN−n−1 = j)

(1.22)= πj︷︸︸︷

P(XN−n−1 = j)

πi

=πjπipji

.= pij

sono soddisfatte le ipotesi del Teorema 1.2.1 e si può quindi concludereche (Yn)Nn=0 : (Ω,F , GnNn=0,P)→ (S,BS) è una C.M.(P , π).

Rimane soltanto da vericare l'irriducibilità. Siano i, j ∈ S arbitrari.Per le equazioni di Chapman-Kolmogorov è suciente dimostrare cheesistono i1, . . . , in ∈ S tali che pii1 pi1i2 . . . pin−1in pinj > 0. Questo implicaimmediatamente che i → j (rispetto a (Yn)Nn=0). Si ricordi però che(Xn)Nn=0 è irriducibile. Allora j → i (rispetto a (Xn)Nn=0). Esistonodunque i1, . . . , in ∈ S tali che pjinpinin−1 . . . pi2i1pi1i > 0. Ma essendoper ogni k ∈ S, πk > 0, si ha anche

0 <πjπin

pjin︸︷︷︸.=pinj

πinπin−1

pinin−1︸︷︷︸.=pin−1in

. . .πi2πi1

pi2i1︸︷︷︸.=pi1i2

πi1πipi1i︸︷︷︸

.=pii1

.= pii1 pi1i2 . . . pin−1in pinj.

48 Catene di Markov

Denizione 25 (Bilancio dettagliato). Siano P := (Pij, i, j ∈ S) una ma-trice stocastica e λ := (λi, i ∈ S) una distribuzione. Si dice che P e λ sonoin bilancio dettagliato se per ogni i, j ∈ S si ha

λiPij = λjPji. (1.30)

Lemma 1.8.3. Siano P := (Pij, i, j ∈ S) una matrice stocastica e λ :=(λi, i ∈ S) una distribuzione. Se P e λ sono in bilancio dettagliato, allora λè stazionaria per P.

Dimostrazione. Per ogni j ∈ S si ha∑i∈S

λiPij(1.30)=∑i∈S

λjPji = λj∑i∈S

Pji = λj.

Osservazione 1.8.9. Per quanto ovvio, il risultato precedente è utile a livellocomputazionale. Infatti se esiste una soluzione λ alle equazioni di bilanciodettagliato, è più facile determinare una distribuzione stazionaria risolvendole (1.30), piuttosto che risolvendo λ = λP .

Denizione 26 (C.M. reversibile). Sia (Xn)n∈N una C.M.(P, π). Si dice che(Xn)n∈N è reversibile se

• (Xn)n∈N è irriducibile,

• (Xn)n∈N ha distribuzione inziale π stazionaria per P ,

• per ogni N ∈ N\0 la time reversal (XN−n)Nn=0 : (Ω,F , GnNn=0,P)→(S,BS) è una C.M.(P, π).

Osservazione 1.8.10. Si noti bene che nella denizione di reversibilitàsi richiede che tutte le time reversal di (Xn)n∈N siano C.M. con comunedistribuzione iniziale stazionaria e stessa matrice di transizione P .

Teorema 1.8.5 (Reversibilità). Sia (Xn)n∈N una C.M.(P, π) irriducibile.Allora sono equivalenti

1. (Xn)n∈N è reversibile;

2. P e π sono in bilancio dettagliato.

Dimostrazione. Si dimostrano separatamente le due implicazioni.


1.⇒ 2.) Sia N ∈ N\0 arbitrario. Detta P := (pij, i, j ∈ S) la matrice duale diP relativamente alla time reversal (XN−n)Nn=0, si ha per ipotesi P = P .Ma dal Teorema sul time reversal nito si ha, per ogni i, j ∈ S

πipij = πj pji = πjpji,

ovvero, per denizione, P e π sono in bilancio dettagliato.

2.⇒ 1.) Per il Lemma 1.8.3 si ha che π è stazionaria per P . Sia N ∈N\0 arbitrario. Per il Teorema sul time reversal nito, (XN−n)Nn=0 :

(Ω,F , GnNn=0,P) → (S,BS) è una C.M.(P , π), dove P := (pij, i, j ∈S è denita, per ogni i, j ∈ S, da

πj pji = πipij.

Poichè P e π sono in bilancio dettagliato, si ha anche che per ognii, j ∈ S

πipij = πjpji.

Confrontando le identità appena ricavate si conclude quindi che P = P .

Esempio 1.8.2 (C.M. non reversibile).[Aggiungere]

Esempio 1.8.3 (C.M. reversibile: Rovina del giocatore).[Aggiungere]

1.8.4 Teorema ergodico per le Catene di Markov

Denizione 27 (Tempo medio di ritorno). Sia j ∈ S. Detto T 1j il primo

istante di arrivo in j (dopo l'istante iniziale), si dice tempo medio di ritornoin j, e si indica con µj, il numero reale esteso

µj := Ej[T 1j

] .=∑n∈N

nf(n)jj .

Osservazione 1.8.11. Come sarà chiaro in seguito, i limiti del Teorema diconvergenza all'equilibrio (limn p

(n)ij = πj) e del Teorema di non esistenza della

distribuzione stazionaria (limn p(n)ij = 0) possono essere descritti in termini

di tempo medio di ritorno. A questo scopo si enuncia il seguente lemma delquale non si riporta la dimostrazione. A seguito di questo si ottiene il Teorema1.8.6 sulla classicazione delle C.M. irriducibili ed aperiodiche e l'importanteTeorema ergodico per le catene di Markov.

50 Catene di Markov

Lemma 1.8.4. Sia j ∈ S ricorrente e si supponga l'esistenza del limite

limn→+∞

p(n)jj := uj.

Allora uj > 0⇔ µj < +∞, e in tale caso uj = 1/µj.

Teorema 1.8.6. Sia (Xn)n∈N una C.M. irriducibile e aperiodica. Allora letre seguenti aermazioni sono disgiuntive ed esaustive20:

1. (Xn)n∈N è transitoria21;

2. non esiste una distribuzione stazionaria, ma (Xn)n∈N è ricorrente22

(ricorrenza nulla);

3. esiste una distribuzione stazionaria, dunque (Xn)n∈N è ricorrente23

(ricorrenza positiva).

Osservazione 1.8.12 (Teorema ergodico). I teoremi ergodici riguardano ilcomportamento limite delle medie temporali. La legge dei grandi numeri è unimportante esempio di questa famiglia di teoremi. Si dimostra ora un risul-tato che identica la proporzione asintotica (i.e. a lungo termine) di tempotrascorsa da una catena di Markov in ciascuno stato. Prima di procedere siintroduce una notazione che si utilizzerà nel teorema.

Notazione 17. Siano i ∈ S e n ∈ N . Si dice numero di visite ad i prima din, e si indica con Vi(n), la variabile aleatoria

Vi(n) :=n−1∑k=0

IXk=i.

20Ovvero una ed una sola delle tre aermazioni è vericata.21In particolare, per ogni i, j ∈ S si ha∑

n∈Np(n)ij < +∞, e di conseguenza lim

n→+∞p(n)ij = 0, da cui µj = +∞.

22In particolare, per ogni i, j ∈ S si ha∑n∈N

p(n)ij = +∞, ma lim

n→+∞p(n)ij = 0, da cui µj = +∞.

Capita quindi che i p(n)ij vanno sì a zero, ma non abbastanza velocemente.23In particolare, per ogni i, j ∈ S si ha∑

n∈Np(n)ij = +∞, con lim

n→+∞p(n)ij = πj > 0, da cui µj = 1/πj < +∞.


Osservazione 1.8.13 (Informalmente). Nello spirito della notazione prece-dente, la v.a. Vi(n)/n rappresenta la proporzione di tempo passato in i primadi n.

Notazione 18. Sia (Xn)n∈N una C.M. irriducibile e sia i ∈ S ssato. Perogni r ∈ N\0, 1 si denisce lunghezza dell'r-esima escursione e si indicacon S(r)

i , la variabile aleatoria

S(r)i :=

T

(r)i − T

(r−1)i , se T (r−1)

i < +∞,0, altrimenti.

Lemma 1.8.5. Siano (Xn)n∈N una C.M. irriducibile, i ∈ S e r ∈ N\0, 1.Allora, condizionatamente a T

(r−1)i < +∞, S

(r)i è indipendente da F

T(r−1)i

e

per ogni n ∈ N si ha

P(S(r)i = n|T (r−1)

i < +∞) = Pi(T (1)i = n).

Dimostrazione. È suciente applicare la proprietà di Markov forte al tem-po d'arresto T := T

(r−1)i . La catena al tempo T assume il valore i, cioè

XT = i, dunque condizionatamente a T < +∞, (XT+n)n∈N è una C.M.(P, δi)indipendente da FT . Inne è chiaro che S(r)

i = infn ∈ N : XT+n = i,quindi P(S

(r)i = n|T (r−1)

i < +∞) è il rst hitting time di (XT+n)n∈N, ossiaPi(T (1)

i = n).

Teorema 1.8.7 (Ergodico). Sia (Xn)n∈N una C.M. irriducibile e sia i ∈ Sssato.

1. Detto µi := Ei[T 1i ] il tempo medio di ritorno in i, si ha

P(Vi(n)

n

n→+∞−→ 1

µi

)= 1,

con la solita convenzione per cui se µi = +∞, allora 1/µi := 0.

2. Se la (Xn)n∈N è positivamente ricorrente e λ := (λj, j ∈ S) è la suadistribuzione invariante, per ogni v.a. f : (S,BS) → (R,BR) limitata,si ha

P

(1

n

n−1∑k=0

f(Xk)n→+∞−→ f :=

∑j∈S

λjf(j)

)= 1.

Si dice in questo caso che la media temporale converge quasi certamentealla media spaziale.

52 Catene di Markov

Dimostrazione. Si dimostrano separatamente i due risultati.

1. Essendo (Xn)n∈N irriducibile, senza perdere in generalità si può suppor-re (Xn)n∈N ricorrente, infatti se la catena fosse transitoria, per quasiogni ω ∈ Ω il numero totale Vi(ω) di visite ad i sarebbe nito, dunqueper quasi ogni ω ∈ Ω

limn→+∞

Vi(n)(ω)

n≤ lim

n→+∞

Vi(ω)

n= 0 =

1

µi.

Sia allora (Xn)n∈N ricorrente.

Si ha dunque P(Ti < +∞) = 1. Inoltre, per la proprietà di Markov for-te, (XTi+n)n∈N è una C.M.(P, δi) ed è indipendente da FTi . Si noti cheessendo Ti quasi certamente nita, la proporzione di tempo trascorsain i è la stessa per (Xn)n∈N e per (XTi+n)n∈N. È quindi suciente con-siderare il caso π = δi. Per il lemma precedente, le variabili aleatorieS

(1)i , S

(2)i , . . . sono iid con media Ei(S(r)

i ) ≡ µi. Sia n ∈ N sucientegrande da garantire Vi(n) > 024. Si ha

S(1)i + . . .+ S

(Vi(n)−1)i ≤ n− 1,

dove il membro di sinistra è il tempo di ultima visita ad i prima di n.Si ha inoltre

S(1)i + . . .+ S

(Vi(n)+1)i ≥ n,

dove il membro di sinistra è il tempo di prima visita ad i dopo n. Seguepertanto che

S(1)i + . . .+ S

(Vi(n)−1)i

Vi(n)≤ n

Vi(n)≤ S

(1)i + . . .+ S

(Vi(n)+1)i

Vi(n). (1.31)

Applicando la legge forte dei grandi numeri25 membri esterni della(1.31), per confronto semplice segue che quasi certamente n/Vi(n) →µi, da cui la tesi.

24È chiaro che un tale n esiste un quanto (Xn)n∈N è ricorrente dunque Vi(n)→ +∞.25Pare che esista una versione della legge dei grandi numeri che fa questa cosa.


2. Sia f : (S,BS)→ (R,BR) limitata, con |f | ≤M ∈ R+. Per ogni J ⊂ Se per ogni n ∈ N, si ha∣∣∣∣∣ 1n

n−1∑k=0

f (Xk)− f

∣∣∣∣∣ =

∣∣∣∣∣∑i∈S

(Vi(n)

n− λi

)f(i)

∣∣∣∣∣≤ M

∑j∈J

∣∣∣∣Vj(n)

n− λj

∣∣∣∣+M∑i/∈J

∣∣∣∣Vi(n)

n− λi

∣∣∣∣≤ M

∑j∈J

∣∣∣∣Vj(n)

n− λj

∣∣∣∣+M∑i/∈J

(Vi(n)

n+ λi

)≤ 2M

∑j∈J

∣∣∣∣Vj(n)

n− λj

∣∣∣∣+ 2M∑i/∈J

λi.

Sia ε > 0 arbitrario. Certamente esiste J ⊂ S nito tale che∑i/∈J

λi < ε.

Si ssi tale J . Poiché per il punto precedente e per il Lemma 1.8.4, perogni j ∈ S si ha quasi certamente

limn→+∞

Vj(n)

n= λj,

per quasi ogni ω ∈ Ω esiste N = N(ε, ω) tale che, per ogni n ≥ N∑j∈J

∣∣∣∣Vj(n)

n− λj

∣∣∣∣ < ε.

Dunque per quasi ogni ω ∈ Ω esiste N = N(ε, ω) tale che, per ognin ≥ N ∣∣∣∣∣ 1n

n−1∑k=0

f (Xk)− f

∣∣∣∣∣ < 4Mε.

Dall'arbitrarietà di ε segue la tesi.

Introduzione alle Catene di Markov - Tommaso...

Documents

Transcript of Introduzione alle Catene di Markov - Tommaso...