Indice
1 Cenni introduttivi 1
1.1 Binomio matematica-sociologia . . . 2
1.2 Definizioni e teoremi preliminari . . . 4
2 Catene di Markov 9 2.1 Catene di Markov . . . 9
2.1.1 Esempi . . . 12
2.2 Equazioni di Chapman-Kolmogorov . . . 14
2.2.1 Probabilit`a di transizione in n passi . . . 15
2.2.2 Equazioni di Chapman-Kolmogorov . . . 17
2.3 Classificazione di stati e catene . . . 21
2.3.1 Stati accessibili e stati comunicanti . . . 21
2.3.2 Stati ricorrenti e stati transitori . . . 24
2.3.3 Connessioni con rappresentazione tramite grafo . . . . 28
2.4 Propriet`a asintotiche . . . 36
2.4.1 Catene di Markov e matrici assorbenti . . . 39
2.4.2 Catene di Markov e matrici regolari . . . 43
2.4.3 Catene di Markov ergodiche . . . 54
2.5 Costi medi al tempo t . . . 56
3 Mobilit`a sociale e modello markoviano 59 3.1 Mobilit`a sociale . . . 59
3.1.1 Le ricerche sulla mobilit`a sociale . . . 61
3.1.2 La mobilit`a sociale in Italia . . . 63
3.2 La scelta del modello . . . 64
3.2.1 Considerazioni sulla scelta del modello . . . 67
3.2.2 Definizione ed analisi del modello . . . 69
3.2.3 Connessione e comunicazione . . . 75
3.2.4 Classi di comunicazione . . . 76
3.2.5 Mobilit`a occupazionale per una prefissata categoria . . 79
4 Applicazioni del modello 81 4.1 Mobilit`a intragenerazionale: modello di Blumen, Kogan e Mc-Carthy . . . 81
4.1.1 Dati . . . 82
4.1.2 Risultati . . . 84
4.2 Mobilit`a intergenerazionale: modello di S.J. Prais . . . 87
4.2.1 Dati . . . 87
4.2.2 Risultati . . . 89
4.3 Modello per la carriera lavorativa . . . 90
4.3.1 Dati . . . 90
4.3.2 Risultati . . . 94
Conclusioni 99
A Prima Appendice 101
Capitolo 1
Cenni introduttivi
Scopo di questo lavoro `e il tentativo di compiere un piccolo passo in avanti nell’incontro tra le scienze definite esatte (matematica, fisica, etc.) e le scien-ze definite inesatte (scienscien-ze sociali ed economiche). Esso si inserisce, infatti, nella ricerca della formalizzazione e dell’utilizzo di modelli Markoviani per la rappresentazione e l’analisi dei problemi di mobilit`a sociale.
La mobilit`a sociale `e oggetto di studio di grande rilievo ormai da oltre mez-zo secolo, sia negli Stati Uniti che in gran parte dei Paesi europei ed `e in aumento l’impiego di processi stocastici nell’analisi di essa. In letteratura esistono vari tentativi di approccio in questo senso e la tesi vuole fornire uno strumento per un’analisi probabilistica della mobilit`a sociale.
Le catene di Markov sono sistemi dinamici (nel nostro caso verranno conside-rati quelli a stati finiti) nei quali la transizione da uno stato all’altro avviene su base probabilistica, invece che deterministica. Esse forniscono un modello matematico per descrivere sistemi soggetti a cambiamenti casuali di stato, la cui evoluzione temporale dipende solo dallo stato attuale e non dalla storia passata. A livello intuitivo, quindi, una catena di Markov (a stati finiti) pu`o essere interpretata come la descrizione di un sistema (a tempo discreto) che pu`o trovarsi ad ogni istante in un qualunque stato appartenente ad un as-segnato insieme (finito) di stati e muoversi con una probabilit`a stazionaria, condizionata solo dallo stato in cui si trova e non dalle transizioni precedenti.
L’esposizione del lavoro `e articolata come segue:
In questo capitolo, il primo introdurremo alcune definizioni utili e risultati noti di calcolo delle probabilit`a, preliminari per i capitoli successivi nei quali esse verranno utilizzate;
nel secondo capitolo riassumeremo gli aspetti generali della teoria delle catene di Markov;esporremmo le equazioni di Chapman-Kolmogorov, clas-sificheremo gli stati di una catena ed analizzeremo le propriet`a asintotiche delle catene finite;
nel terzo capitolo introdurremo la mobilit`a sociale come oggetto di studio ed esporremo il nostro modello, analizzando le assunzioni basilari che con-sentiranno la formalizzazione di esso tramite una catena di Markov;
nel quarto capitolo mostreremo alcune applicazioni del modello generale ad esempi di mobilit`a occupazionale gi`a presenti in letteratura ed esporremo una nostra applicazione per un modello di carriera lavorativa.
I nostri risultati si basano sull’ipotesi che la matrice di transizione rimanga costante nel tempo e questo potrebbe sembrare lontano dalla realt`a in cui condizioni sociali ed economiche subiscono cambiamenti. In realt`a, occorre osservare che le ambizioni degli individui rimangono focalizzate sui propri obiettivi, anche se cambiano le condizioni esterne, quindi, sotto specifiche ipotesi che esporremo dettagliatamente, i risultati possono essere considerati una buona approssimazione della realt`a.
1.1
Binomio matematica-sociologia
Il concetto di probabilit`a `e basilare in matematica come in sociologia e in tutte le discipline empiriche contemporanee. Esiste un vasto dibattito sul-l’adeguatezza del concetto di probabilit`a nel descrivere la realt`a, ma, forse proprio nell’area della probabilit`a, lo scienziato sociale ha la possibilit`a di vedere la stretta interrelazione tra il concetto esatto (assiomatico), le
cono-scenze informali, la deduzione (ovvero il procedimento che dal generale va al singolare), il calcolo e la corrispondenza.
L’incertezza esiste non perch´e commettiamo degli errori, ma piuttosto perch´e l’indeterminatezza `e un elemento della vita che dobbiamo accettare a qual-siasi livello di analisi.
Nel campo delle scienze umane esistono molti argomenti certamente razio-nali, pur senza essere certi, che ambiscono ad essere trattati con una logica appropriata. Quella che meglio si presta ad essere impiegata per questi scopi sembra essere quella probabilistica. La probabilit`a non si riferisce a giudizi, ma a risultati possibili di un esperimento concettuale o reale. La teoria della probabilit`a `e quindi uno dei pi`u importanti strumenti matematici usati nelle scienze sociali, in quanto fornisce modelli per i fenomeni sperimentali che presentano una certa misura di non prevedibilit`a.
Una profonda influenza, in questo senso, `e stata data alla teoria della proba-bilit`a dalla teoria degli insiemi e dalla teoria della misura.
I sociologi utilizzano metodi quantitativi nella ricerca sociale per descrivere le relazioni mediante modelli e sviluppare schemi interpretativi che possono aiutare a prevedere i cambiamenti sociali e a dare risposte ad essi.
La sociologia, definita come lo studio della vita sociale di uomini, gruppi e so-ciet`a, si occupa del nostro comportamento come esseri sociali. Vista quindi come una scienza applicata, `e possibile suddividerla in due parti, natural-mente, fortemente interconnesse. Una prima parte rappresentata da grandi teorie con lo scopo di creare modelli macro di spiegazione della societ`a; una seconda parte fatta di studi focalizzati soprattutto su fenomeni sociali circo-scritti per tempo e luogo.
Questa seconda parte rappresenta il lato applicativo della sociologia avvi-cinandola alle scienze naturali ed `e quella che ha bisogno di strumenti per l’osservazione del reale e di modelli che riproducano tali osservazioni.
1.2
Definizioni e teoremi preliminari
Definizione 1.1. Sia E un insieme non vuoto e sia E una determinata classe di parti di E.
Allora, la classe E si dice trib`u su E se verifica le seguenti propriet`a:
1. il complementare di un qualsiasi elemento di E `e ancora un elemento di E ;
2. l’unione di una qualsiasi famiglia numerabile di elementi di E `e ancora un elemento di E .
La coppia (E,E ) si dice spazio misurabile.
Definizione 1.2. Sia (E,E ) uno spazio misurabile.
Allora una funzione positiva µ definita su E si dice misura se verifica la condizione di additivit`a numerabile, ovvero vale la relazione:
µ([ i∈I Ai) = X i∈I µ(Ai)
dove (Ai)i∈I `e un’arbitraria famiglia numerabile di eventi di E a due a due
incompatibili; ossia per ogni coppia Ai, Aj con i 6= j si ha Ai∩ Aj = ∅.
La terna (E, E , µ) si dice spazio misurato.
Definizione 1.3. Siano (E1, E1), (E2, E2) due spazi misurabili.
Allora un’applicazione f : E1 → E2 si dice misurabile se, per ogni elemento
A ∈ E2, l’insieme
f−1(A) = {x ∈ E1 : f (x) ∈ A}
appartiene a E1. (f−1(A) `e detta immagine inversa di A mediante f ).
Nel linguaggio della probabilit`a introduciamo il concetto di spazio pro-babilizzato come un caso particolare di spazio misurato, dove la diversit`a dei nomi corrisponde alla diversit`a delle interpretazioni, ovvero:
Definizione 1.4. La coppia (Ω,A) si dice spazio probabilizzabile (o spazio delle probabilit`a, dove Ω `e un insieme i cui elementi rappresentano ipotetici risultati di un esperimento ed A `e una determinata classe di parti di Ω. Inoltre l’insieme Ω si dice Insieme delle Eventualit`a ed A si dice Trib`u degli eventi.
Definizione 1.5. Sia (Ω,A) uno spazio probabilizzabile.
Allora una funzione misura P : A → [0, 1] si dice Misura di probabilit`a se:
P(Ω) = 1
La terna (Ω, A, P) si dice Spazio Probabilizzato e, per ogni elemen-to A di A, il numero P(A) `e detto Probabilit`a dell’evento A secondo P.
Definizione 1.6. Uno spazio probabilizzabile (Ω,A) si dice discreto se Ω `e numerabile ed A `e l’insieme di tutte le parti di Ω, ovvero A = P(Ω).
Dato uno spazio cos´ı fatto, ogni applicazione
f : A → [0, 1] tale che X
ω∈Ω
f (ω) = 1
si dice densit`a discreta (di probabilit`a) su Ω.
Definizione 1.7. Sia (Ω, A, P) uno spazio probabilizzato. Fissato un ele-mento H di A, con P(H) 6= 0, si dice Misura di Probabilit`a dedotta da P sotto la condizione H la misura PH ottenuta normalizzando la misura
µ cos´ı definita su A
µ(A) = P(A ∩ H).
Per ogni evento A, la probabilit`a di A secondo PH, ossia il numero
PH(A) = P(H)−1P(A ∩ H),
si dice Probabilit`a Condizionale di A, secondo P, sotto la condizione H. Tale probabilit`a si denota anche con P(A|H).
Tale probabilit`a indica la probabilit`a che si verifichi A sapendo che “l’evento H si `e realizzato”; esprime quindi una “correzione” delle aspettative per A, dettata dall’osservazione dell’evento H.
Teorema 1.2.1. (Teorema dell’addizione delle probabilit`a)
Siano A e B due eventi non incompatibili. Allora la probabilit`a che accada A non precludendo la probabilit`a che si presenti anche B, cio`e che si verifichi (A ∪ B) risulta:
P(A ∪ B) = P(A) + P(B) − P(A ∩ B)
Teorema 1.2.2. (Teorema della moltiplicazione delle probabilit`a)
Siano A e B due eventi non incompatibili. Allora la probabilit`a del prodotto C = A × B, cio`e che i due eventi si verifichino entrambe simultaneamente (A ∩ B), risulta:
P(A ∩ B) = P(A) + P(B) − P(A ∪ B) Teorema 1.2.3. (Teorema delle Probabilit`a Totali)
Sia A ∈ Ω un evento e siano Bi per i = 1, .., n n eventi disgiunti tali che
Ω =Sn
i=1Bi. Allora risulta:
P(A) = n X i=1 P(A|Bi)P(Bi) Dimostrazione. Essendo A =Sn
i=1(A∩Bi) si ha che P(A) =
Pn
i=1P(A ∩ Bi).
Applicando i teoremi precedenti si ha la tesi.
Definizione 1.8. Si dice variabile aleatoria (v.a.) sullo spazio probabi-lizzabile (Ω,A) a valori nello spazio misurabile (E,E ), una qualunque appli-cazione misurabile da (Ω,A) in (E,E ) .
Definizione 1.9. Sia (Ω,A,P) uno spazio probabilizzato e su di esso sia definita un’applicazione
X : Ω × T → R, con T ⊂ R
tale che, per ogni t ∈ T , la funzione ω 7−→ X( ω, t) risulti una variabile aleatoria, si dice Processo Stocastico o aleatorio.
Un processo stocastico `e detto:
• a tempo continuo se T =R, • a tempo discreto se T =N .
Un processo stocastico `e, quindi, essenzialmente definito come una fami-glia di v.a. Xn ed `e classificato a seconda della natura di tali v.a.
In particolare un processo aleatorio a tempo discreto `e una successione di v.a. definite sullo spazio di probabilit`a (Ω, A, P) mediante Xn(ω) := X(ω, n).
Un tale processo si dice indipendente se, e solo se, tali sono le v.a. della successione.
I valori che possono essere assunti dalle v.a. (ovvero il codominio di queste variabili) sono detti stati e si denota con S.
Il numero degli stati di S pu`o essere finito, infinito e numerabile, infinito e non numerabile. Nel caso in cui gli stati del processo siano in numero finito si denota con N il loro numero.
L’interesse per i processi discreti ha molte provenienze, ad esempio:
1. essi possono rappresentare la discretizzazione, per scopi numerici o di trasmissione dei segnali, di processi continui;
2. sono adatti a descrivere problemi di conteggio; ad esempio, se si consi-dera un sistema a coda, Xn potrebbe rappresentare il numero di utenti
presenti nel sistema al tempo n.
3. si presentano come il modello pi`u appropriato alla descrizione della realt`a negli studi della mobilit`a sociale.
In seguito si assume che:
• T `e l’insieme degli interi non negativi T =N , ossia il processo stocastico Xt `e a tempo discreto;
• l’insieme S degli stati del processo `e numerabile.
Se Xn=sj, si dir`a che al tempo t=n, il processo si trova nello stato sj. Ad
ogni istante di tempo t ∈ T il sistema si trover`a quindi in un determinato stato appartenente ad un insieme numerabile di stati tra loro mutuamente esclusivi.
Il processo stocastico {Xn} parte da uno di questi stati e si muove in un altro
stato; ogni mossa si chiama passo.
La v.a. Xn sar`a, quindi, descritta da una densit`a (discreta) di probabilit`a
{p(n)i ; i ∈ S}, dove p(n)i = P(Xn = i).
Per ogni istante di tempo n vale che P
i∈Sp (n) i = 1.
Capitolo 2
Catene di Markov
2.1
Catene di Markov
Lo studio delle catene di Markov, senza dubbio la classe pi`u nota di sistemi dinamici di tipo stocastico, prende il nome dal matematico e statista russo A.A. Markov (1856-1922) che le introdusse intorno ai primi anni del 1900 e conduce a risultati di utilit`a pratica mettendo in relazione diverse strutture matematiche:
• i processi stocastici, • le matrici,
• i grafi.
Esso si `e diffuso a partire dalla prima met`a del XX secolo, grazie alle ap-plicazioni di successioni di eventi collegati tra loro nello studio dei fenomeni fisici, biologici e sociali, in cui le probabilit`a di un evento sono condizionate soltanto dal risultato immediatamente precedente, ovvero in cui basta co-noscere lo stato attuale del sistema per predire lo stato futuro, tralasciando ogni informazione sul passato.
Sotto le ipotesi di tali processi, la distribuzione di probabilit`a evolve nel tem-po secondo regole che rendono l’analisi elegante ed efficace.
Definizione 2.1. (Propriet`a di Markov)
Si dice che un processo stocastico verifica la propriet`a di Markov se per ogni istante di tempo t ∈ T , per ogni coppia di stati i, j ∈ S e per ogni sequenza k0, ..., kt−1 ∈ S, risulta:
P{Xt+1 = j|X0 = k0, ..., Xt−1 = kt−1, Xt= i} = P{Xt+1= j|Xt= i} (2.1)
La probabilit`a condizionata P{Xt+1 = j|Xt = i} `e detta probabilit`a di
transizione al tempo t dallo stato i allo stato j.
La propriet`a (2.1) `e interpretabile come una “perdita di memoria” del suo passato da parte del processo; cio`e, la previsione statistica dell’evento futuro che il processo sia nello stato Xt+1= j, `e identica sia se effettuata conoscendo
la storia passata e presente {X0 = k0, X1 = k1,..,Xt−1 = kt−1,Xt= i}, sia se
effettuata conoscendo solo il presente Xt = i.
Ovvero, noto il presente, il futuro non dipende dal passato; per questo moti-vo si dice che il sistema `e senza memoria.
Definizione 2.2. (Probabilit`a di transizione stazionarie)
Le probabilit`a di transizione sono dette stazionarie se, per ogni coppia di stati i, j ∈ S e per ogni t ∈ T , si ha:
P{Xt+1= j|Xt= i} = P{X1 = j|X0 = i} (2.2)
Tali probabilit`a condizionali si indicano con pij = P{X1 = j|X0 = i}.
La stazionariet`a delle probabilit`a di transizione indica una omogeneit`a tem-porale; la dinamica stocastica, che determina i passi del processo, non dipen-de quindi dal tempo, ma agisce sempre con le stesse modalit`a. Un sistema che gode di questa propriet`a si dice omogeneo.
Definizione 2.3. Un processo stocastico discreto {Xt}, t ∈ T = {1, 2, ...},
avente un insieme S numerabile di stati, `e detto Catena di Markov se verifica le seguenti propriet`a:
i. propriet`a di Markov;
ii. probabilit`a di transizione stazionarie.
Tale processo stocastico viene inoltre detto Catena di Markov a stati finiti nel caso in cui abbia un numero finito N di stati.
Nel caso di sistemi omogenei, le probabilit`a congiunte possono essere cal-colate nel seguente modo:
poniamo pij = P{Xt+1 = j|Xt = i} allora vale P{X0 = k0, X1 = k1, .., Xt+1= j} = = P{X0 = k0, X1 = k1, .., Xt= i} · pij = = ... = = P{X0 = k0} · pk0k1 · .. · pij (2.3)
Lo studio delle catene di Markov a stati finiti diventa particolarmente semplice ed efficace utilizzando un approccio basato sulle matrici; le pro-babilit`a di transizione stazionarie pij = P{X1 = j|X0 = i} possono essere
infatti rappresentate nella seguente forma matriciale.
Definizione 2.4. Si consideri una catena di Markov a stati finiti. Si definisce matrice di transizione la seguente matrice P :
P = (pij) ∈ [0, 1]N ×N con i, j ∈ N
Essa ha elementi non negativi, con somma 1 su ciascuna riga e soddisfa la seguente propriet`a fondamentale:
Osservazione 1. Le matrici non negative che soddisfano la relazione (2.4) sono dette matrici stocastiche, quindi, per definizione, la matrice di transizione P di una catena di Markov a stati finiti `e una matrice stocastica.
Per esse il vettore u `e un autovettore destro corrispondente all’autovalore λ = 1; ogni matrice stocastica ha 1 come autovalore ed `e l’autovalore di modulo massimo (nessun altro autovalore, cio`e, supera 1 in modulo).
2.1.1
Esempi
In questa sezione vogliamo fornire alcuni semplici esempi di catene di Markov a scopo illustrativo. Gli esempi proposti riguardano ci`o che normal-mente viene chiamato “Random Walk” o “Passeggiata aleatoria”, cio`e una formalizzazione matematica di un percorso costituito da una successione ca-suale di passi.
Immaginiamo che un punto si muova di un passo alla volta lungo una linea retta formata da 5 possibili stati, {s1, s2, s3, s4, s5}; ad ogni passo il punto ha
probabilit`a p di spostarsi verso destra e probabilit`a q di spostarsi verso sini-stra. Le possibilit`a di comportamento (movimento) del punto determinano diversi tipi di catene di Markov.
Esempio 1. Poniamo la condizione che il punto non si sposti pi`u quando raggiunge uno stato di confine s1 o s5; la matrice di transizione risulta essere la
seguente: P = 1 0 0 0 0 q 0 p 0 0 0 q 0 p 0 0 0 q 0 p 0 0 0 0 1
Esempio 2. Assumiamo ora che il punto venga “riflesso” quando raggiunge uno stato di confine, cio`e ogni volta che il punto raggiunge s1 venga
re-spinto allo stato precedente s2 ed, analogamente, ogni volta che il
transizione risulta essere la seguente: P = 0 1 0 0 0 q 0 p 0 0 0 q 0 p 0 0 0 q 0 p 0 0 0 1 0
Esempio 3. Assumiamo ora che il punto venga “spostato al centro” della linea quan-do raggiunge uno stato di confine, cio`e ogni volta che il punto raggiunge gli stati s1 o s5 venga mandato nello stato s3; la matrice di transizione
risulta essere la seguente:
P = 0 0 1 0 0 q 0 p 0 0 0 q 0 p 0 0 0 q 0 p 0 0 1 0 0
Esempio 4. Consideriamo un nuovo comportamento del punto quando si trova in uno stato di confine; esso avr`a probabilit`a 1/2 di rimanere nello stesso stato di confine e probabilit`a 1/2 di andare nell’altro stato di confine; la matrice di transizione risulta essere la seguente:
P = 1/2 0 0 0 1/2 q 0 p 0 0 0 q 0 p 0 0 0 q 0 p 1/2 0 0 0 1/2
Esempio 5. Vediamo ora una versione modificata del “random walk”: se il punto si trova in uno stato intermedio, ha la stessa probabilit`a di muoversi verso destra, verso sinistra o di rimanere fermo, mentre, se si trova in uno stato di confine ha la stessa probabilit`a di spostarsi in uno degli
altri 4 stati. La matrice di transizione risulta essere la seguente: P = 0 1/4 1/4 1/4 1/4 1/3 1/3 1/3 0 0 0 1/3 1/3 1/3 0 0 0 1/3 1/3 1/3 1/4 1/4 1/4 1/4 0
Esempio 6. Consideriamo ora uno studente che si iscrive alle scuole medie superiori. Definiamo gli stati nel modo seguente:
– s1 = anno di iscrizione (primo anno),
– s2 = secondo anno,
– s3 = terzo anno,
– s4 = quarto anno,
– s5 = quinto anno,
– s6 = diplomato
Supponiamo che lo studente abbia probabilit`a p di essere promosso e probabilit`a q di ripetere l’anno, sotto la condizione di poter ripetere la stessa classe infinite volte. La matrice di transizione risulta essere la seguente: P = q p 0 0 0 0 0 q p 0 0 0 0 0 q p 0 0 0 0 0 q p 0 0 0 0 0 q p 0 0 0 0 0 1
2.2
Equazioni di Chapman-Kolmogorov
Nelle catene di Markov il concetto di probabilit`a di transizione stazionaria pu`o essere ulteriormente esteso al caso in cui si vuole la probabilit`a che il
sistema passi dallo stato i allo stato j in n passi; ovviamente ben diversa dalla probabilit`a che all’istante n avvenga la transizione da i a j.
2.2.1
Probabilit`
a di transizione in n passi
Teorema 2.2.1. Si consideri una catena di Markov. Per ogni coppia di stati i, j ∈ S e per ogni intero n ≥ 0 risulta:
P{Xt+n= j|Xt= i} = P{Xn= j|X0 = i} (2.5)
Dimostrazione. La dimostrazione procede per casi. Per n = 0 : ovvio.
Per n = 1 : coincide con la stazionariet`a delle probabilit`a di transizione delle catene di Markov.
Per n > 1 : per il Teorema delle Probabilit`a Totali e per la definizione di probabilit`a condizionata si ha:
P{Xt+n = j|Xt= i} = X k∈S P{Xt+n= j, Xt+n−1 = k|Xt= i} = X k∈S P{Xt+n= j|Xt+n−1 = k, Xt= i}P{Xt+n−1 = k|Xt = i}
Inoltre, per la propriet`a di Markov e la stazionariet`a delle probabilit`a di transizione si ha: P{Xt+n = j|Xt+n−1 = k, Xt= i} = P{Xt+n = j|Xt+n−1 = k} = P{Xn = j|Xn−1 = k} = P{Xn = j|Xn−1 = k, X0 = i} da cui si ottiene: P{Xt+n = j|Xt= i} = X k∈S P{Xn= j|Xn−1 = k, X0 = i}P{Xn−1 = k|X0 = i} = X k∈S P{Xn= j, Xn−1 = k|X0 = i} = P{Xn= j|X0 = i}
Definizione 2.5. Le probabilit`a condizionate
p(n)ij = P{Xn = j|X0 = i} con n ∈ {0, 1, 2, ..} (2.6)
sono dette probabilit`a di transizione stazionarie in n passi.
Le probabilit`a (2.6) rappresentano la probabilit`a condizionata di passare in n passi dallo stato i allo stato j. Ovviamente risulta:
p(0)ij = P{X0 = j|X0 = i} = 1 se i = j 0 se i 6= j e p(1)ij = P{X1 = j|X0 = i} = pij
Inoltre, per definizione di probabilit`a, si ha:
0 ≤ p(n)ij ≤ 1 ∀i, j ∈ N e ∀n ≥ 0 X j∈N p(n)ij =X j∈N P{Xn = j|X0 = i} = 1 ∀i ∈ N e ∀n ≥ 0
Nelle catene di Markov a stati finiti esiste una rappresentazione in forma matriciale anche per le probabilit`a di transizione stazionarie in n passi; infatti:
Definizione 2.6. Si consideri una catena di Markov a stati finiti. Allora la matrice P(n), definita come:
P(n)= (p(n)ij ) ∈ [0, 1]N ×N con i, j ∈ N
si dice matrice di transizione in n passi. Si pone P(0) = I e P(1) = P .
2.2.2
Equazioni di Chapman-Kolmogorov
Lo strumento pi`u importante nello studio delle catene di Markov `e rap-presentato dalle equazioni di Chapman-Kolmogorov, che legano tra loro pro-babilit`a di transizione in tempi diversi. La mancanza di memoria delle catene di Markov permette di dimostrare che la probabilit`a di transizione in n+m passi dipende dalla probabilit`a condizionata di arrivare dallo stato di parten-za ad un certo stato k in n passi e dalla probabilit`a di passare dallo stato k allo stato finale negli ultimi m passi.
Teorema 2.2.2 (Equazioni di Chapman-Kolmogorov).
Si consideri una catena di Markov. ∀i, j ∈ S e ∀n, m ≥ 1 risulta:
p(n+m)ij =X
k∈S
p(n)ik p(m)kj
Dimostrazione. Per il Teorema delle Probabilit`a Totali si ha:
p(n+m)ij = P{Xn+m= j|X0 = i} = X k∈S P{Xn+m= j, Xn= k|X0 = i} = X k∈S P{Xn+m= j|Xn= k, X0 = i}P{Xn= k|X0 = i}
Inoltre per la propriet`a di Markov e per la stazionariet`a delle probabilit`a di transizione si ha: P{Xn+m = j|Xn = k, X0 = i} = P{Xn+m = j|Xn = k} = P{Xm = j|X0 = k} Quindi risulta: p(n+m)ij =X k∈S P{Xm= j|X0 = k}P{Xn= k|X0 = i} = X k∈S p(n)ik p(m)kj
Da ora in poi ci occuperemo delle catene di Markov a stati finiti.
I seguenti corollari permettono di dimostrare come le equazioni di Chapman-Kolmogorov possono essere rappresentate in forma matriciale e come la ma-trice di transizione in n passi non sia altro che l’n-esima potenza della mama-trice di transizione.
Corollario 2.2.3. Si consideri una catena di Markov a stati finiti. Allora, ∀n, m ≥ 1, si ha:
P(n+m)= P(n)P(m)
Corollario 2.2.4. Si consideri una catena di Markov a stati finiti. Allora si ha:
P(n)= Pn
Dimostrazione. Posto m = 1 e n = k − 1, `e sufficiente osservare che, ∀k ≥ 1, si ha:
P(k) = P(k−1)P(1) = P(k−1)P da cui segue che
P(n) = P(n−1)P = P(n−2)P2 = ... = P1Pn−1= Pn
Osservazione 2. Se A e B sono matrici stocastiche, allora il prodotto AB `e una matrice stocastica. Infatti si ha:
(AB)u = A(Bu) = Au = u
dove u = (1, 1, .., 1)T.
In particolare, il corollario 2.2.4 ci permette di dimostrare che tutte le potenze Pn sono matrici stocastiche, cio`e che lo sono tutte le matrici di transizione
in n passi con n ≥ 0. Infatti:
Dal teorema 2.2.2, usando la relazione (2.3) per le probabilit`a congiunte, mostriamo che le probabilit`a di transizione in n passi sono date dalla seguente sommatoria:
p(n)ij = X
k1,..,kn−1∈S
pik1 · pk1k2 · pk2k3 · .. · pkn−2kn−1· pkn−1j (2.7)
Questa somma di prodotti ha una struttura algebrica molto semplice e la sua dimostrazione `e conseguenza dell’applicazione dei corollari precedenti.
Supponiamo ora che la densit`a discreta xi sia la probabilit`a che il sistema
ha di trovarsi nello stato i ad un certo istante arbitrario; indichiamo tali probabilit`a con il vettore x = (x1, x2, .., xn)T che `e detto distribuzione di
probabilit`a del sistema in quell’istante. In particolare indichiamo con
x(0) = (x(0)1 , x(0)2 , .., x(0)n )T
il vettore di distribuzione di probabilit`a iniziale, cio`e la distribuzione di pro-babilit`a all’inizio del processo e con
x(n) = (x(n)1 , x(n)2 , .., x(n)n )T
il vettore di distribuzione di probabilit`a all’ n-esimo passo, cio`e la distribu-zione di probabilit`a dopo le prime n transizioni.
Sotto queste condizioni vale il seguente teorema:
Teorema 2.2.5. Sia P la matrice di transizione di un processo markoviano. Se x = (xi)T per i = 1, .., n `e la distribuzione di probabilit`a del sistema ad
un certo istante arbitrario, allora xTP `e la distribuzione di probabilit`a del sistema dopo una transizione e xTPn `e la distribuzione di probabilit`a del sistema dopo n transizioni. In particolare,
[x(n)]T = [x(n−1)]TP e x(n) `e correlato a x(0) dall’equazione
Dimostrazione. Segue direttamente dal Corollario 2.2.4. Infatti, per ogni stato i ∈ S risulta: x(n)i = P{Xn = i} = X k∈S P{X0 = k}P{Xn = i|X0 = k} = X k∈S x(0)k p(n)ki
ovvero, scritto in forma matriciale
[x(n)]T = [x(0)]TP(n)= [x(0)]TPn
Osservazione 3. I vettori x(n) sono dei vettori di distribuzione delle probabi-lit`a corretti. Infatti risulta:
[x(n)]Tu =X
k∈S
x(n)i =X
k∈S
P{Xn= i} = 1
Dalle equazioni di Chapman-Kolmogorov derivano, inoltre, le seguenti utili propriet`a:
Proposizione 2.2.6. Si consideri una catena di Markov. Allora ∀n, m ≥ 1, ∀i, j, k ∈ S, valgono le seguenti propriet`a:
i. p(n+m)ij ≥ p(n)ik p(m)kj ;
ii. p(n·m)ii ≥ (p(n)ii )m.
I risultati dimostrati mostrano che la chiave per lo studio delle catene finite di Markov `e lo studio della matrice di transizione e delle sue potenze. Gli elementi di queste potenze hanno di per s`e una interpretazione probabi-listica interessante; se prendiamo, per esempio, come vettore iniziale [x(0)]T
il vettore riga con 1 nella i-esima componente e 0 altrove, dal teorema 2.2.5, otteniamo che [x(n)]T=[x(0)]TPn. Ma [x(0)]TPn `e la i-esima riga della matri-ce Pn, cos´ı, la i-esima riga dell’n-esima potenza della matrice di transizione fornisce la probabilit`a di essere in ciascuno dei vari stati dopo n passi, sotto
la condizione che il processo, inizialmente, si trovasse nello stato si.
Consideriamo l’esempio 2 ed assumiamo la condizione che il processo ini-zialmente si trovi nello stato s3. Allora, come vettore iniziale, abbiamo
x(0) = (0, 0, 1, 0, 0) e all’ n-nesimo passo possiamo ottenere la distribuzio-ne di probabilit`a calcolando la potenza n-esima della matrice P e prendendo la terza riga. Ovvero:
P = 0 1 0 0 0 1/2 0 1/2 0 0 0 1/2 0 1/2 0 0 0 1/2 0 1/2 0 0 0 1 0 quindi x(1) = (0, 1/2, 0, 1/2, 0) P2 = 1/2 1 1/2 0 0 0 3/4 0 1/4 0 1/4 0 1/2 0 1/4 0 1/4 0 3/4 0 0 0 1/2 0 1/2 quindi x(2) = (1/4, 0, 1/2, 0, 1/4).
Da ora in poi, identificheremo con la matrice P tutto il processo una volta data la distribuzione iniziale delle probabilit`a x(0).
2.3
Classificazione di stati e catene
2.3.1
Stati accessibili e stati comunicanti
Le prime propriet`a fondamentali che legano gli stati di una catena di Markov sono date dalla loro possibilit`a di “comunicare”.
Definizione 2.7. Si consideri una catena di Markov. Siano si, sj ∈ S due
dei suoi stati. Allora:
i) lo stato sj si dice accessibile dallo stato si se ∃n ≥ 0 tale che p(n)ij > 0,
ossia se il processo ha la possibilit`a di passare dallo stato si allo stato
sj (non necessariamente in un solo passo).
In questo caso useremo la notazione:
i → j
ii) gli stati si e sj si dicono comunicanti se lo stato sj `e accessibile dallo
stato si ed a sua volta lo stato si `e accessibile dallo stato sj:
i → j e j → i
ovvero sie sj sono comunicanti se ∃n, m ≥ 0 tali che p (n)
ij > 0 e p (m) ji > 0.
Definizione 2.8. Una catena di Markov si dice irriducibile se tutti gli stati del processo comunicano tra di loro, altrimenti si dice riducibile.
Teorema 2.3.1. Si consideri una catena di Markov e due suoi stati si, sj ∈
S.
Le seguenti condizioni sono equvalenti:
i) i → j;
ii) P{∃n ≥ 0 tale che Xn = j|X0 = i} > 0;
iii) esistono n − 1 stati k1, .., kn−1 ∈ S, tali che:
pik1 · pk1k2 · pk2k3 · ... · ·pkn−2kn−1 · ·pkn−1j > 0
Dimostrazione. Basta osservare che:
p(n)ij ≤ P{∃n ≥ 0 tale che Xn = j|X0 = i} ≤ +∞ X n=0 p(n)ij Quindi si ha: i) ⇒ ii) Ovvio.
i) ⇐ ii) Se vale ii) allora P+∞
n=0p (n)
ij > 0 e quindi esiste necessariamente un
n ≥ 0 tale che p(n)ij > 0.
i) ⇔ iii) Basta ricordare le probabilit`a di transizione in n passi date dalla (2.7).
Teorema 2.3.2. Si consideri una catena di Markov e sia S l’insieme dei suoi stati.
Allora la relazione
i ∼ j ⇐⇒ i → j e j → i
`e una relazione di equivalenza.
Dimostrazione. Basta verificare le propriet`a della relazione di equivalenza:
i) Riflessiva: ogni stato comunica con se stesso (i ∼ i). Deriva dal fatto che p(0)ii = P{X0 = i|X0 = i} = 1
ii) Simmetrica: se lo stato i comunica con lo stato j allora anche lo stato j comunica con lo stato i (i ∼ j =⇒ j ∼ i).
Segue direttamente dalla definizione di stati comunicanti.
iii) Transitiva: se lo stato si comunica con lo stato sj e lo stato sj comunica
con lo stato sk allora anche lo stato si comunica con lo stato sk (si ∼
sj, sj ∼ sk =⇒ si ∼ sk)
Siano a, b, c, d ≥= 0 tali che p(a)ij > 0, p(b)ji > 0, p(c)jh > 0 e p(d)hj > 0; dalle equazioni di Chapman-Kolmogorov segue che:
p(a+c)ih =X k∈S p(a)ik p(c)kh ≥ p(a)ij p(c)jh > 0 p(d+b)hi =X k∈S p(d)hkp(b)ki ≥ p(d)hjp(b)ji > 0
Gli stati di una catena possono quindi essere partizionati in classi di equivalenza tali che tutti gli stati di una certa classe comunichino tra loro e
l’insieme S risulta completamente decomposto in classi di equivalenza modu-lo la relazione ↔; per decomporre modu-lo spazio degli stati, possiamo procedere nel seguente modo:
1) consideriamo i0 ∈ S e costruiamo C0 = {i ∈ S|i0 ↔ i};
2) consideriamo i1 ∈ S \ C0 e costruiamo C1 = {i ∈ S|i1 ↔ i};
3) iteriamo il processo fino a considerare tutti gli stati.
Allora otteniamo:
• Ci∩ Cj = ∅∀i, j ∈ S, cio`e tutte le classi sono disgiunte;
• S
iCi = S, cio`e l’unione di tutte le classi forma lo spazio degli stati.
2.3.2
Stati ricorrenti e stati transitori
Vediamo ora come `e possibile differenziare tra loro gli stati di una catena.
Definizione 2.9. Si consideri una catena di Markov ed un suo stato i ∈ S. Allora lo stato i si dice:
(i) transitorio se esiste uno stato j ∈ S con j 6= i tale che j `e accessibile da i, ma i non `e accessibile da j, ovvero se:
∃j ∈ S, j 6= i, tale che i → j e j 6→ i
In altre parole, uno stato i `e transitorio se il processo pu`o non ritor-narvi mai pi`u, ovvero se vi torner`a solamente un numero finito di volte (P
n≥1p (n)
ii < +∞).
(ii) ricorrente se non `e transitorio, ovvero se:
∀j ∈ S risulta : {i → j ⇒ j → i}
In altre parole, uno stato i `e ricorrente se il processo torner`a sicu-ramente prima o poi nello stato i, ovvero se vi torner`a infinite volte (P
n≥1p (n)
(iii) assorbente se pii= 1.
Definizione 2.10. Si definisce periodo di uno stato ricorrente, il massimo comun divisore d ≥ 1 dell’insieme {k > 0 | p(k)ii > 0}; in particolare, lo stato ricorrente si dice:
• con periodo d se d > 1, ovvero se il processo pu`o tornare nello stato i solamente dopo un numero k di transizioni con k = d, 2d, 3d..;
• aperiodico se d = 1, ovvero se il processo pu`o tornare nello stato i in due istanti successivi t e t + 1.
Osservazione 4. Uno stato assorbente i (pii = 1) `e un particolare stato
ricorrente aperiodico.
Definizione 2.11. Una catena di Markov si dice assorbente se ogni stato ricorrente `e assorbente.
Definizione 2.12. Sia i, j ∈ S due stati della catena. Allora si dice:
• numero di passaggi in i, la variabile aleatoria Ni =
P+∞
n=0Id{Xn=i}, dove Id{Xn=i} `e la funzione indicatrice che vale 1
se Xn= i, 0 altrimenti;
• tempo di primo passaggio in i, la variabile aleatoria Ti = inf {n ≥ 1 : Xn = i};
• probabilit`a del tempo di primo passaggio da i a j, fij(n) = P{Tj = n|X0 = i};
• probabilit`a di arrivo da i in j,
fij = P{Tj < +∞|X0 = i} = P{∃n ≥ 1 t.c. Xn= j|X0 = i}.
Nel caso in cui i = j, fii si dice probabilit`a di ritorno.
Da sottolineare che, per gli stati appartenenti ad una stessa classe di equivalenza, vale la seguente importante propriet`a.
Teorema 2.3.3. In una stessa classe di stati comunicanti, gli stati sono tutti transitori oppure sono tutti ricorrenti con egual periodo.
Dimostrazione. Siano i e j due qualsiasi stati comunicanti della classe con-siderata. Per definizione, quindi, ∃n, m ≥ 0 tali che p(n)ij > 0 e p(m)ji > 0. Per ogni r > 0 risulta:
p(n+r+m)ii ≥ p(n)ij · p(r)jj · p(m)ji e p(n+r+m)jj ≥ p(m)ji · p(r)ii · p(n)ij Quindi, rispettivamente dalle due disequazioni, si ottiene:
+∞ X r=0 p(r)jj ≤ 1 p(n)ij · p(m)ji · +∞ X r=0 p(n+r+m)ii ≤ 1 p(n)ij · p(m)ji · +∞ X r=0 p(r)ii (2.8) +∞ X r=0 p(r)jj ≥ +∞ X r=0 p(n+r+m)jj ≥ p(n)ij · p(m)ji · +∞ X r=0 p(r)ii (2.9) Se lo stato i `e transitorio si ha P+∞ r=0p (r) ii < +∞, dalla disequazione (2.8), segue che P+∞ r=0p (r)
jj < +∞ e quindi anche j `e transitorio.
Se lo stato i `e ricorrente si ha P+∞ r=0p (r) ii = +∞, dalla disequazione (2.9), segue che P+∞ r=0p (r)
jj = +∞ e quindi anche j `e ricorrente.
Supponiamo ora che i sia di periodo di e che j sia di periodo dj; dimostriamo
che di = dj facendo vedere che valgono le due disuguaglianze di ≤ dj e
di ≥ dj.
Poich´e i e j stati comunicanti della stessa classe di equivalenza, si ha che: ∃r, s ∈ N tali che p(r)ij > 0 e p(s)ji > 0.
Sia m ∈ N un intero tale che p(m)ii > 0, allora p(s+m+r)jj ≥ p(s)ji p(m)ii p(r)ij > 0 ma anche
p(s+2m+r)jj ≥ p(s)ji p(2m)ii p(r)ij > 0
Allora dj divide (s + m + r) ma dj divide anche (s + 2m + r) =⇒ dj divide
m, cio`e m divide tutti gli interi positivi n tali che p(n)ii > 0.
Ma, per definizione di periodo di uno stato, di `e il massimo comun divisore
di tutti questi numeri n, quindi si ha dj ≤ di.
Definizione 2.13. Una classe di equivalenza si dice:
(i) transiente se gli stati che la compongono sono transitori;
(ii) ergodica se gli stati che la compongono sono ricorrenti;
(iii) ciclica se d > 1, aciclica se d = 1.
Osservazione 5. Vediamo qualche altra propriet`a interessante:
(i) in una catena di Markov a stati finiti non tutti gli stati possono essere transitori (se ci`o accadesse, il sistema potrebbe abbandonare tutti i suoi stati dopo un numero finito di transizioni, il che `e assurdo);
(ii) una catena di Markov irriducibile `e composta da un’unica classe di equivalenza di stati comunicanti;
(iii) tutti gli stati di una catena di Markov a stati finiti irriducibile sono ricorrenti (per le due osservazioni precedenti);
(iv) se il sistema transisce al di fuori di una classe di equivalenza, allora tale classe `e composta esclusivamente da stati transitori ai quali il sistema non acceder`a mai pi`u (il sistema lascia una classe di equivalenza se transisce in uno stato che non comunica con i precedenti e quindi non pu`o pi`u tornare in seguito in tale classe, quindi, per definizione, segue che tutti gli stati della classe sono transitori);
(v) se il sistema transisce in uno stato appartenente ad una classe di equi-valenza composta soltanto da stati ricorrenti da quel momento in poi non lascer`a pi`u tale classe (se il sistema potesse lasciare tale classe essa sarebbe composta da stati transitori negando le ipotesi);
(vi) se una classe di equivalenza `e ciclica con periodo d, si suddivide in d sottoclassi e la catena di Markov si pu`o muovere solo in modo ciclico attraverso le d sottoclassi, con cicli di periodo d;
(vii) se una classe di equivalenza `e aciclica, il processo, indipendentemente dallo stato iniziale, dopo un tempo sufficientemente lungo, pu`o trovarsi in ogni stato della classe.
Dai risultati ottenuti in questa sezione, possiamo concludere che, ogni catena di Markov finita ha almeno una classe ergodica, ma vi possono non essere classi transienti e questo accade se la catena `e formata da un’unica classe ergodica o da pi`u classi ergodiche, da ognuna delle quali `e impossibile raggiungerne un’altra. In quest’ultimo caso si hanno, in realt`a pi`u catene di Markov, ognuna per ogni classe ergodica, non interagenti. Inoltre, data una catena di Markov, il processo si muove verso stati ricorrenti e quindi la probabilit`a che il processo, dopo un numero finito n di passi, si trovi in uno stato ricorrente tende a 1 per n che tende a ∞. `E quindi vantaggioso classificare una catena di Markov a seconda dei suoi stati ricorrenti.
2.3.3
Connessioni con rappresentazione tramite grafo
Un metodo pratico per studiare le propriet`a degli stati di una catena di Markov `e quello di analizzare il grafo ad essa associato.
Un grafo G `e costituito da una coppia di insiemi (N, A) dove N `e detto insieme dei nodi ed A `e detto insieme degli archi.
I nodi sono rappresentati graficamente con dei punti nel piano e gli archi con delle linee che congiungono tali punti. Se le coppie di nodi sono ordinate, il grafo `e detto orientato e queste linee sono delle frecce che si dicono uscenti dal nodo da cui partono ed entranti in quello in cui terminano.
Il grafo associato ad una catena di Markov si determina facendo in modo che ad ogni stato si corrisponda un nodo i ed ad ogni valore pij > 0 corrisponda
un arco orientato dal nodo i al nodo j. Ovvero, rappresentiamo gli stati si, sj, .., sn della catena con dei punti nel piano e tracciamo una freccia che
connette due di questi punti quando `e positiva la probabilit`a di eseguire la transizione dall’uno all’altro stato in un passo. Il grafo stocastico visualizza cos´ı in modo pratico tutte le transizioni elementari possibili, cio`e tutte le
transizioni di stato che si possono verificare in un intervallo di tempo unitario. Introduciamo a tale scopo alcune utili definizioni.
Definizione 2.14. Un grafo orientato G si dice fortemente connesso se ∀i, j ∈ N , insieme dei nodi, esiste un cammino orientato da i a j e da j a i. Definizione 2.15. Dato un grafo orientato G si dice componente forte-mente connessa di G ciascun sottografo di G che sia forteforte-mente connesso e massimale (cio`e non contenuto strettamente in un altro sottografo fortemente connesso).
Definizione 2.16. Dato un grafo orientato G si dice componente tran-siente (o transitoria) di G un insieme di archi e nodi che possiede almeno un arco uscente dalla componente stessa.
Definizione 2.17. Dato un grafo orientato G si dice componente ergodica (assorbente) di G un insieme di archi e nodi che non ha archi uscenti verso nodi al di fuori della componente stessa.
Osservazione 6. Gli stati di una componente ergodica possono essere:
. o tutti periodici;
. o tutti aperiodici.
Definizione 2.18. Una componente ergodica si dice periodica se e soltanto se tutti i suoi stati sono periodici.
Una componente ergodica si dice aperiodica se e soltanto se tutti i suoi stati sono aperiodici.
Osservazione 7. Siano si, sj ∈ S due stati di una catena di Markov finita.
si, sj appartengono alla stessa classe di equivalenza ⇔ si, sj appartengono
alla stessa componente del grafo orientato G.
Osservazione 8. Nel caso in cui tutti gli stati di una componente ergodica di una catena di Markov omogenea finita siano periodici, questi hanno tutti lo stesso periodo ed in particolare, tale periodo coincide con il periodo D della classe di equivalenza a cui essi appartengono.
Vediamo qualche esempio: Esempio (a): S1 S2 S3 S4 E
Figura 2.1: Esempio A di grafo con una componente fortemente connessa ergodica
Il grafo ha una sola componente fortemente connessa ed `e ovviamente ergo-dica o assorbente (=E).
Esempio (b): S1 S2 S3 S4 E
Figura 2.2: Esempio B di grafo con una componente fortemente connessa ergodica
Anche questo grafo ha una sola componente fortemente connessa ed `e ov-viamente ergodica o assorbente (=E).
Esempio (c): S1 S2 S3 S4 S5 S6 T T E
Figura 2.3: Esempio di grafo con tre componenti fortemente connesse: due transitorie e una ergodica
Il grafo ha tre componenti fortemente connesse di cui due sono transitorie (=T) ed una ergodica o assorbente (=E).
Esempio (d): S1 S2 S3 S4 T E E
Figura 2.4: Esempio di grafo con tre componenti fortemente connesse: una transitoria e due ergodiche
Il grafo ha tre componenti fortemente connesse di cui una `e transitoria (=T) e le altre due sono ergodiche o assorbenti (=E).
Le propriet`a degli stati possono quindi essere verificate anche a partire dal grafo associato alla catena markoviana, come evidenziato dalle seguenti proposizioni:
Proposizione 2.3.4. Dato il grafo associato ad una catena di Markov, val-gono le seguenti propriet`a:
(i) lo stato j risulta accessibile dallo stato i se e solo se esiste un cammino orientato dal nodo i al nodo j;
(ii) due stati risultano comunicanti (e quindi appartenenti alla stessa classe di equivalenza) se e solo se esiste un ciclo orientato che li contenga, in particolare diremo che appartengono alla stessa componente fortemente connessa;
(iii) gli stati assorbenti hanno un solo arco uscente, entrante verso il nodo stesso;
(iv) la catena di Markov `e irriducibile se e solo se il grafo ad essa associato `e fortemente connesso.
Proposizione 2.3.5. Data una catena di Markov, un suo stato `e:
(a) transitorio se e soltanto se appartiene ad una componente transiente;
(b) ricorrente se e soltanto se appartiene ad una componente ergodica.
Riprendiamo alcuni degli esempi di random walk proposti nella sezione 2.1.1 “Esempi” e vediamo la classificazione degli stati delle catene e i grafi associati: Esempio 1. S1 S2 S3 S4 S5 E T E
Figura 2.5: Esempio 1 di grafo associato alla matrice di transizione del Random Walk
Il grafo ha tre componenti fortemente connesse di cui due ergodiche e l’altra transiente. Infatti, gli stati s1 e s5 sono stati assorbenti e
ciascuno costituisce una classe di equivalenza a s´e. Gli stati s2, s3 e s4
sono stati comunicanti, in quanto `e possibile spostarsi tra due qualsiasi di questi stati e sono tutti transitori; essi appartengono alla stessa classe di equivalenza. In questo esempio la catena di Markov ´e riducibile ed assorbente; il processo sar`a definitivamente bloccato in uno dei due singoli stati assorbenti.
Esempio 2.
S1 S2 S3 S4 S5 E
Figura 2.6: Esempio 2 di grafo associato alla matrice di transizione del Random Walk
In questo caso il grafo ha un’unica componente fortemente connessa, ovviamente ergodica e quindi la catena `e irriducibile. `E infatti possibile andare da un qualunque stato in un qualunque altro stato. Non ci sono stati transitori, gli stati sono tutti ricorrenti di periodo 2. `E infatti possibile tornare in uno stato solo in un numero pari di passi, quindi il periodo di ogni stato `e d = 2. Sono tutti comunicanti, quindi esiste un’unica classe di equivalenza ciclica di periodo 2. In questo esempio la catena di Markov `e ciclica.
Esempio 3. S1 S2 S3 S4 S5 E
Figura 2.7: Esempio 3 di grafo associato alla matrice di transizione del Random Walk
Anche in questo caso, come nel precedente, il grafo ha un’unica com-ponente fortemente connessa, ovviamente ergodica e quindi la catena `e irriducibile. Infatti `e possibile andare da un qualunque stato in un qualunque altro stato. Non ci sono stati transitori, gli stati sono tutti comunicanti, quindi formano un’unica classe di equivalenza e sono ri-correnti, stavolta, di periodo 1. Infatti `e possibile tornare nello stato s3 da s3 in 2 o 3 passi, quindi il periodo `e d = 1. In questo caso
tut-te le potut-tenze sufficientut-tementut-te altut-te della matrice di transizione P sono positive. Non importa quindi da dove il processo sia partito, dopo un intervallo di tempo sufficiente pu`o trovarsi in un qualsiasi stato. In questo esempio la catena di Markov `e aciclica.
Esempio 4. S1 S2 S3 S5 S4 E T
Figura 2.8: Esempio 4 di grafo associato alla matrice di transizione del Random Walk
In questo caso il grafo ha due componenti fortemente connesse, di cui una transiente ed una ergodica. La catena `e riducibile. Infatti, gli stati s2, s3, s4 sono comunicanti, tutti transitori e formano un’unica classe
transiente, mentre gli stati s1, s5 sono ricorrenti di periodo d = 1 e
formano la classe di equivalenza ergodica.
Possiamo dimostrare la relazione (2.7) anche con l’aiuto dei grafi associa-ti; infatti `e possibile determinare sul grafo orientato di una catena di Markov le probabilit`a di transizione in 2 passi da uno stato i ad uno stato j e poi procedere per induzione e calcolare le probabilit`a di transizione in n passi. Il passaggio da i al tempo t = 0 a j al tempo t = 2 pu`o avvenire secondo n modalit`a mutuamente esclusive ed esaustive, passando prima da i a k con k = 1, 2, ..., n e poi da k a j. La j-esima di queste modalit`a ha probabilit`a pikpkj ed `e positiva se e solo se entrambe i fattori sono positivi, cio`e se nel
grafo esiste un cammino di due archi che connette il nodo i al nodo j passan-do per il nopassan-do k. La probabilit`a complessiva di passare da i a j in due passi
`e P
k∈Spikpkj, elemento di posizione (i, j) nella matrice P
2 corrispondente
alla somma di tutte le probabilit`a associate ai cammini di lunghezza 2 che nel grafo connettono i a j.
Estendendo il ragionamento alla transizione da i a j in n passi con n ≥ 3 si prenderanno in considerazione sul grafo tutti i cammini possibili di lun-ghezza n che connettono i a j, cammini corrispondenti agli addendi della sommatoria.
2.4
Propriet`
a asintotiche
In questa sezione la matrice di transizione della catena di Markov sar`a fissata, mentre la distribuzione iniziale potr`a variare. In particolare, per una distribuzione concentrata in un certo stato si, ovvero dove il vettore di
di-stribuzione iniziale avr`a un’unica componente diversa da 0 in corrispondenza della componente i-esima, si dir`a che la corrispondente catena di Markov (o processo) “`e iniziata nello stato i.”
Data una catena di Markov, `e interessante studiarne il comportamento:
i) prima che entri in una classe ergodica, analizzando la media del numero di volte in cui la catena si trova in uno stato transitorio e come questo numero dipenda dallo stato iniziale;
ii) dopo l’ ingresso in una classe ergodica, perch`e essa non pu`o essere pi`u lasciata.
Ad ogni catena di Markov `e associata una matrice stocastica e viceversa, quindi `e possibile utilizzare la teoria delle matrici per lo studio delle catene. Cambiando in maniera opportuna il nome degli stati e raggruppando tutte le classi ergodiche e tutte quelle transitorie (senza perdere di generalit`a pos-siamo supporre che ci siano t stati transitori e r stati ricorrenti), `e possibile scrivere la matrice di transizione di una catena di Markov nella seguente
forma, detta forma canonica, utile per la classificazione:
P = E O
R Q !
La sottomatrice O `e la matrice nulla di ordine r × t; Q `e la sottomatrice di dimensione t × t e tiene conto del processo fintanto che esso rimane in uno stato transitorio; la sottomatrice R di ordine t × r fa riferimento alle transizioni da stati transitori a stati ricorrenti e la sottomatrice E di ordine r × r tiene conto del processo dopo che esso `e entrato in una classe ergodica.
Teorema 2.4.1. In una catena di Markov finita, la probabilit`a che dopo n passi il processo sia in uno stato ricorrente tende a 1 quando n tende all’infinito, indipendentemente dallo stato iniziale.
Dimostrazione. Se la catena `e inizialmente in uno stato ricorrente, vi rimarr`a per sempre, quindi non c’`e niente da dimostrare.
Supponiamo, quindi, che la catena parta da uno stato transitorio e indichiamo con T l’insieme degli stati transitori e con E quello degli stati ricorrenti della catena. Dunque si ha:
X
i∈T
p(0)i = 1
per il teorema delle Probabilit`a Totali, si ha:
p(n)=X j∈E P{Xn = j} = X i∈T X j∈E P{Xn= j, X0 = i} = X i∈T p(0)i X j∈E p(n)ij
dove la doppia sommatoria nell’ultima espressione rappresenta la probabilit`a che la catena, trovandosi all’istante iniziale in un qualsiai stato transitorio, si trovi dopo n passi in uno stato ricorrente. Per ogni stato i ∈ T esiste un ni tale che 1 −X j∈T p(ni) ij = X j∈E p(ni) ij > 0
da cui si ricava che
X
j∈T
p(ni)
La successione P
j∈T p (k)
ij `e decrescente, infatti si ha che
X j∈T p(k+1)ij =X j∈T X h∈T p(k)ihphj = X h∈T p(k)ih X j∈T phj ≤ X h∈T p(k)ih
Dunque, esiste ci ∈ (0, 1) tale che, per ogni k ≥ ni, si ha:
X
j∈T
p(k)ij < ci < 1
Dato che gli stati sono in numero finito, poniamo:
c := max{ci : i ∈ T } e n0 := max{ni : i ∈ T }
allora otteniamo che c ∈ (0, 1) e, per ogni stato transiente i ∈ T e per ogni k ≥ n0,
X
j∈T
p(k)ij < c < 1.
Quindi, per ogni i ∈ T , k ≥ n0 e m numero naturale, si ha:
X j∈T p(mk+k)ij =X h∈T p(mk)ih X j∈T p(k)hj ≤ cX h∈T p(mk)ih
e per induzione, quando m → +∞, si ottiene
X
j∈T
p((m+1)k)ij ≤ cX
j∈T
p(mk)ij ≤ cm+1 −→ 0
Una successione estratta da {P
j∈Tp (k)
ij : k ∈ N } converge e, poich´e la
successione `e decrescente, l’intera successione converge allo stesso limite.
Corollario 2.4.2. Esistono due numeri b > 0 e 0 < c < 1 tali che p(n)ij ≤ bcn,
per ogni coppia di stati si, sj.
Dimostrazione. Diretta conseguenza del teorema precedente, esso mostra la velocit`a con cui p(n)ij tende a 0.
Dimostrazione. Nella potenza n-esima di P
Pn= E
n O
Rn Qn
!
l’elemento q(n)ij di Qn esprime la probabilit`a che la catena, partendo da uno stato transitorio si, si trovi, dopo n passi, nello stato transitorio sj. Per il
teorema (2.4.1) si ha
lim
n→+∞q (n) ij = 0
per ogni coppia di stati transitori si, sj. Da cui la tesi.
I risultati appena dimostrati, implicano che Qn `e infinitesima al diver-gere di n e quindi, se consideriamo potenze di P molto elevate, tali matrici approssimano una matrice con tutti gli elementi nulli nelle ultime t colonne. Nel caso delle catene di Markov a stati finiti `e possibile studiarne in modo molto semplice le propiet`a asintotiche, in quanto, il comportamento di una catena a stati finiti si stabilizza nel lungo periodo qualora soddisfi determinate caratteristiche.
2.4.1
Catene di Markov e matrici assorbenti
Definizione 2.19. Data una catena di Markov si dice assorbente se ogni suo stato ricorrente `e assorbente.
Per una catena di Markov assorbente con t stati transitori e r stati assorbenti, la forma canonica della matrice di transizione `e la seguente:
P = I O
R Q !
dove I `e la matrice identit`a r × r, Q `e una matrice quadrata t × t e fornisce informazioni sul processo fintanto che rimane in uno stato transitorio, R `e una matrice di ordine t × r non nulla ed O `e la matrice nulla di ordine r × t. Le potenze della matrice di transizione sono:
Pn= I O
Rn Qn
dove Rn=Pn−1m=0RQn−m−1.
Teorema 2.4.4. Per ogni catena di Markov assorbente, la matrice (I − Q) ammette inversa N e risulta
N = (I − Q)−1 = X
n∈Z+
Qn (2.10)
Dimostrazione. Vale l’identit`a
(I − Q)(I + Q + Q2+ .. + Qn−1) = I − Qn
Per il teorema 2.5.1 e per il suo corollario, si ha Qn → O, quindi per n sufficientemente grande, det(I − Qn) 6= 0. Questo implica det(I − Q) 6= 0, quindi esiste la matrice inversa det(I − Q)−1 e vale la (2.10).
Definizione 2.20. Data una catena di Markov assorbente, la matrice N = (I − Q)−1 si dice matrice fondamentale.
Definiamo inoltre, nj la funzione che restituisce il numero totale delle volte
che il processo si `e trovato nello stato transiente sj.
Abbiamo la seguente interpretazione probabilistica della matrice fonda-mentale N :
Proposizione 2.4.5. La matrice fondamentale N = (nij) esprime
esat-tamente il numero atteso di volte in cui il processo si trover`a nello stato transitorio sj essendo partito dallo stato si.
Dimostrazione. Fissiamo due stati transitori si e sj e consideriamo la
varia-bile aleatoria Yk che vale 1 se il processo `e nello stato s
j dopo k passi, 0 altrimenti. Si ha quindi: P{Yk= 1} = q(k) ij e P{Y k= 0} = 1 − q(k) ij ,
dove qij(k)`e l’elemento di posizione (i, j) della matrice Qk. Se il processo inizia
dallo stato si, il numero atteso di volte in cui esso si trova in sj, dopo n passi,
Teorema 2.4.6. Sia data una c.d.M. assorbente il cui processo parte dallo stato iniziale si e sia Ti il numero atteso di passi prima che la catena sia
assorbita, cio`e che entri in uno stato assorbente. Allora si ha
− → T = N 1 1 .. . 1 , dove −→T = T1 T2 .. . Tn .
Dimostrazione. Se, per ipotesi, il processo parte dallo stato iniziale si, il
numero atteso di passi prima che la catena sia assorbita `e la somma dei valori attesi di volte in cui la catena si trova in ogni stato prima dell’assorbimento, cio`e P
j∈Inij. Da questo segue la tesi.
Teorema 2.4.7. Sia data una catena di Markov assorbente e sia aij la
pro-babilit`a che la catena sia assorbita dallo stato sj se essa `e partita dallo stato
si. Posto A = (aij) la matrice t × r, si ha
A = N R
Dimostrazione. Per ipotesi, lo stato iniziale del processo `e si, quindi il
pro-cesso pu`o andare subito nello stato assorbente sj e terminare oppure pu`o
andare in un qualunque altro stato transitorio sk. Quindi si ha:
aij = pij +
X
k
pikakj
In termini matriciali si ha A = R + QA ovvero A = (I − Q)−1R. Da qui segue la tesi.
Applichiamo questi risultati all’esempio 1 della “passeggiata aleatoria” proposto nella sezione 2.1.1:
(I − Q) = 1 −p 0 −q 1 −p 0 −q 1
Quindi, poich´e p + q = 1, ma anche (p + q)2 = 1 e cio`e 1 − 2pq = p2+ q2,
la matrice fondamentale risulta essere:
N = (I − Q)−1 = s2 s3 s4 s2 p+q 2 p2+q2 p p2+q2 p2 p2+q2 s3 p2+qq 2 1 p2+q2 p p2+q2 s4 q 2 p2+q2 q p2+q2 q+p2 p2+q2
Osserviamo che, se, per esempio, il processo parte dallo stato s3, allora
ritorner`a in media in s3 p2+q1 2 volte.
Se assumiamo p = 13 e q = 23, cio`e che sia doppia la probabilit`a di muoversi verso sinistra, rispetto a quella di muoversi verso destra, si avr`a la seguente matrice fondamentale: N = (I − Q)−1 = s2 s3 s4 s2 7/5 3/5 1/5 s3 6/5 9/5 3/5 s4 4/5 6/5 7/5
Applichiamo ora questi risultati all’esempio 6 “carriera di uno studente” proposto nella sezione 2.1.1:
(I − Q) = 1 − q −p 0 0 0 0 1 − q −p 0 0 0 0 1 − q −p 0 0 0 0 1 − q −p 0 0 0 0 1 − q quindi si ha N = (I − Q)−1 = 1 1−q p (1−q)2 p2 (1−q)3 p3 (1−q)4 p4 (1−q)5 0 1−q1 (1−q)p 2 p2 (1−q)3 p3 (1−q)4 0 0 1−q1 (1−q)p 2 p2 (1−q)3 0 0 0 1−q1 (1−q)p 2 0 0 0 0 1 1−q
Ogni elemnto nij della matrice esprime il numero atteso di volte che uno
studente si trover`a nella classe j-esima, essendo partito dalla classe i-esima. In particolare, gli zeri della matrice N indicano che uno studente delle scuole medie superiori non pu`o essere retrocesso in una classe inferiore rispetto a quella che ha frequentato l’ultima volta.
2.4.2
Catene di Markov e matrici regolari
Definizione 2.21. Una matrice stocastica A si dice regolare se ∃k ∈ N tale che tutti gli elementi di Ak sono strettamente positivi.
Una catena di Markov finita si dice regolare se lo `e la sua matrice di transizione.
Questo significa che per qualche n `e possibile andare da ogni stato ad ogni altro in esattamente n passi.
Proposizione 2.4.8. Una catena di Markov `e regolare se e solo se non ha stati transitori ed `e formata da un’unica classe di stati ricorrenti aciclica.
Dimostrazione. Sia A la matrice di transizione associata alla catena di Mar-kov. Dimostriamo prima questa implicazione (=⇒).
Supponiamo che A sia regolare, cio`e che ∃k ∈ N tali che tutti gli elementi di Ak siano strettamente positivi. Allora, anche tutte le potenze Am con
m ∈ N e m > k hanno elementi strettamente positivi e quindi, l’insieme dei numeri naturali n per i quali ∃i, j coppia di indici tali che p(n)ij = 0, `e finito. La catena non ha quindi stati transitori, ma `e formata da un’unica classe ergodica. Inoltre, poich´e tra i numeri n ∈ N per i quali p(n)ii > 0 ce ne sono sicuramente due primi tra loro, si ha che il periodo della classe ergodica `e d = 1, cio`e la classe `e aciclica.
Dimostriamo ora l’altra implicazione (⇐=).
Supponiamo che la catena sia formata da un’unica classe di stati ricorrenti e sia aciclica e siano si, sj due stati qualunque. Allora ∃k ∈ N tale che p
(k) ij > 0.
grande, si ha
p(k+hij ≥ p(k)ij p(h)jj > 0.
Dunque, per ogni coppia di stati si, sj esiste un n(i,j) tale che
An(i,j) > 0.
Basta quindi prendere il minimo comune multiplo n dei numeri n(i,j) ed
ot-teniamo An > 0.
Supponiamo ora che i sia uno stato assorbente di una catena markoviana con matrice di transizione A. Allora, per j 6= i, la probabilit`a di transizione relativa all’n-esima transizione `e a(n)ij = 0 per ogni valore di n.
Di conseguenza, ogni potenza di A ha una componente nulla e quindi A non `e regolare. Vale quindi il seguente risultato:
Proposizione 2.4.9. Se una matrice stocastica A ha una componente uguale a 1 sulla diagonale principale, allora A non `e regolare (a meno che A sia una matrice 1 × 1).
Dimostrazione. Supponiamo, senza perdere di generalit`a, che sia a11 = 1,
ovvero che lo stato s1 della catena markoviana con matrice di transizione A
sia assorbente. Allora ∀i 6= 1 la probabilit`a relativa all’ n-esima transizione `e a(n)1j = 0 ∀n. Di conseguenza, ogni potenza di A ha un elemento nullo e quindi A non `e regolare.
Introduciamo il noto teorema di Perron-Frobenius che vale per matrici non-negative regolari e quindi, in particolare, per matrici stocastiche regolari. La conoscenza del massimo autovalore e del relativo autovettore sinistro ha grande importanza nel determinare il comportamento nel lungo periodo del processo modellato dalla matrice in questione; questo teorema ci garantisce che per una matrice ad elementi positivi, l’autovalore che ha massimo valore assoluto `e reale ed ha uno spazio di autovettori di dimensione 1:
Teorema 2.4.10. (Perron-Frobenius)
Sia A una matrice n × n non-negativa e regolare. Allora esiste un autovalore r tale che:
(a) r `e reale, > 0;
(b) ad r possono essere associati autovettori destri e sinistri strettamente positivi;
(c) r > |λ| per ogni autovalore λ 6= r;
(d) gli autovettori associati ad r sono unici a meno di costante moltiplica-tive;
(e) se 0 ≤ B ≤ A e β `e un autovalore di B, allora |β| ≤ r. Inoltre, |β| = r implica che B = A;
(f ) r `e radice semplice dell’equazione caratteristica di A.
Proposizione 2.4.11. Se una matrice stocastica A `e regolare, allora 1 `e autovettore di molteplicit`a 1 e tutti gli altri autovalori λi soddisfano la
dise-guaglianza |λi| < 1.
Dimostrazione. Discende dal teorema di Perron-Frobenius.
Teorema 2.4.12. (Markov)
Sia A una matrice stocastica regolare. Allora esistono quantit`a πj con j ∈ I
tali che
lim
n→+∞a (n)
ij = πj ∀i ∈ I.
Dimostrazione. Procederemo con la dimostrazione del teorema di Markov in due tappe:
1. Supponiamo A priva di elementi nulli e sia ε il minimo elemento di A, cio`e 0 < ε ≤ aij. Poniamo inoltre m(n)j =minia(n)ij e M
(n) j =maxia(n)ij . Poich´e si ha a(n)ij =X k∈I aika (n−1) kj ≥ X k∈I aikm (n−1) j = m (n−1) j ∀j ∈ I
la successione m(n)j `e non decrescente in n. Analogamente si ha che la successione Mj(n)`e non crescente in n e ovviamente
m(n)j ≤ a(n)jk ≤ Mj(n).
Supponiamo, s.l.g., che sia a(n)i0j = m(n)j e a(n−1)i1j = Mj(n−1). Allora: m(n)j = a(n)i0j =X k∈I ai0ka (n−1) kj = = εa(n−1)i1j + (ai0i1 − ε)a (n−1) i1j + X k6=i1 ai0ka (n−1) kj ≥ ≥ εMj(n−1)+ (ai0i1 − ε + X k6=i1 ai0k)m (n−1) j = = εMj(n−1)+ (1 − ε)m(n−1)j (2.11) Analogamente si ottiene: Mj(n)≤ εm(n−1)j + (1 − ε)Mj(n−1) (2.12)
Eseguendo la differenza tra le due disequazioni (2.12) e (2.11) si ottiene:
Mj(n)− m(n)j ≤ (1 − 2ε)(Mj(n−1)− m(n−1)j )
quindi:
Mj(n)− m(n)j ≤ (1 − 2ε)n che tende a 0 per n che tende a +∞.
Quindi m(n)j e Mj(n) tendono allo stesso limite πj
|a(n)ij − πj| ≤ M (n) j − m (n) j ≤ (1 − 2ε) n
e la convergenza `e maggiorata da una convergenza geometrica di ragione (1 − 2ε). Il teorema `e dimostrato se A non ha elementi nulli.
2. Caso generale: Am matrice stocastica regolare. Per il caso 1 abbiamo che:
∀k ∈ N , risulta, scrivendo la generica potenza della matrice A nella forma Anm+k, lim n→+∞A nm+k = lim n→+∞A kAnm = AkL = L e poich´e (AL)ij = X k∈I aikπkj = ( X k∈I aik)πj = πj
L `e una matrice con tutte le righe uguali.
Sia q := nm + kq con 0 ≤ kq < m. Dato che Anm → L, per n > n
risulta: kAnm− Lk < [max0≤kq<mkA kqk]−1 Quindi si ha: kAq− Lk = kAnm+kq − Lk = kAnmAkq − AkqLk ≤ ≤ kAkqk · kAnm− Lk ≤ (max 0≤kq<mkA kqk)(kAnm− Lk) ≤
Questo implica che kAq− Lk < , ∀q > q = nm.
Questo mostra che il teorema di Markov vale anche per il caso generale e quindi `e completamente dimostrato.
Definizione 2.22. Sia x(0) un vettore iniziale di distribuzione e sia L la
matrice limite che, in quanto tale, `e necessariamente stocastica. Allora le componenti di x(∞), definite dall’equazione
[x(∞)]T = [x(0)]TL
si dicono distribuzioni limite degli stati e rappresentano le proporzioni approssimate di oggetti nei vari stati di una catena markoviana dopo un gran numero di periodi.
Con il teorema di Markov abbiamo dimostrato che, in una catena di Mar-kov regolare, la probabilit`a di trovare la catena in un dato stato si stabilizza
nel lungo periodo attorno ad un valore legato alla matrice di transizione A, indipendente dallo stato di partenza e dalla storia passata. Ovvero, l’effetto della distribuzione iniziale di probabilit`a del processo si attenua al crescere del numero delle transizioni e si ha:
[x∞]T = π
dove π `e detto distribuzione stazionaria della catena di Markov.
In termini matriciali, le potenze n-esime di A convergono, elemento per ele-mento, ad una matrice L avente tutte la righe identiche, in quanto ciascuna riga `e l’unico autovettore di A associato all’autovalore λ = 1 e avente 1 come somma dei propri elementi. Ovvero:
Corollario 2.4.13. Per ogni x0 vettore delle distribuzioni iniziali risulta
[x(n)]T −→ π
dove π `e l’unico autovettore sinistro associato ad A soluzione del sistema {π(AT − 1) = 0, πu = 1}.
Il vettore π `e detto vettore fisso delle probabilit`a.
Richiamiamo un noto risultato di algebra lineare.
Teorema 2.4.14. Sia A una matrice quadrata tale che An → 0 (cio`e tende
alla matrice nulla) , allora esiste la matrice inversa (I − A)−1 ed `e uguale a (I − A)−1 =X
n≥0
An.
Per le catene di Markov assorbenti abbiamo definito la matrice fonda-mentale, introduciamo qualcosa di corrispondente per le catene di Markov regolari.
Teorema 2.4.15. Sia A la matrice di transizione per una catena di Markov regolare e sia L la sua matrice limite. Allora esiste Z = (I − (A − L))−1 ed `e uguale a Z = I + +∞ X n=1 (An− L)
Dimostrazione. Applicando il teorema (2.4.14), abbiamo: (I − (A − L))−1 =P n≥0(A − L) n = I +P n≥1(A − L) n
Quindi, se mostriamo che (A − L)n = An− L, possiamo concludere la dimo-strazione, in quanto diviene:
Z = (I − (A − L))−1 = I +P
n≥1(An− L), cio`e la tesi.
Poich´e L `e la matrice stocastica limite, risulta Lk = L e quindi:
(A − L)n= n X i=0 n i ! (−1)n−iAiLn−i = = An+ n−1 X i=0 n i ! (−1)n−iL = = An− L.
Definizione 2.23. Sia A una matrice di transizione regolare. Allora la ma-trice Z = (I − A + L)−1 si dice matrice fondamentale per la catena di Markov regolare associata ad A.
Teorema 2.4.16. Sia Z la matrice fondamentale per una catena di Markov regolare con A matrice di transizione, π vettore di distribuzione limite e L matrice limite. Allora:
1) AZ = ZA;
2) Zu = u;
3) πZ = π;
4) I − Z = L − AZ;
Dimostrazione. Per il teorema precedente abbiamo Z = I +P+∞
n=1(An− L),
quindi:
1) segue direttamente dal fatto che la matrice A commuta con ogni ele-mento della serie;
