Una catena di Markov descrive un sistema che evolve tra stati con probabilità che dipendono solo dallo stato attuale (proprietà di Markov, “assenza di memoria”). È il modello stocastico più usato: code, affidabilità, motori di ricerca, genetica. Questa scheda allena l’evoluzione della catena e il calcolo della distribuzione stazionaria.
Proprietà di Markov: \;P(X_{n+1}=j\mid X_n=i,\dots)=P(X_{n+1}=j\mid X_n=i)=p_{ij}.
1. Matrice di transizione
Esercizio. Un sistema meteo ha due stati: Sole (S) e Pioggia (P). Da S resta S con prob. 0{,}8; da P resta P con prob. 0{,}6. Scrivere la matrice di transizione.
Ogni riga somma a 1 (le probabilità di uscita da uno stato):
P=\begin{pmatrix}p_{SS}&p_{SP}\\p_{PS}&p_{PP}\end{pmatrix}=\begin{pmatrix}0{,}8&0{,}2\\0{,}4&0{,}6\end{pmatrix}.
La matrice di transizione è stocastica: elementi non negativi, righe a somma 1. Riga i = probabilità di andare ovunque partendo da i.
2. Evoluzione della distribuzione
Esercizio. Oggi è Sole con certezza: \pi_0=(1,\ 0). Calcolare la distribuzione domani.
Si moltiplica il vettore di stato per la matrice di transizione:
\pi_1=\pi_0 P=(1,\ 0)\begin{pmatrix}0{,}8&0{,}2\\0{,}4&0{,}6\end{pmatrix}=(0{,}8,\ 0{,}2).
Domani: 80\% Sole, 20\% Pioggia. L’evoluzione di un passo è una moltiplicazione vettore-matrice.
3. Distribuzione a due passi
Esercizio. Per lo stesso sistema, calcolare la distribuzione dopodomani partendo da \pi_1=(0{,}8,\ 0{,}2).
\pi_2=(0{,}64+0{,}08,\ 0{,}16+0{,}12)=(0{,}72,\ 0{,}28).
A ogni passo la distribuzione si avvicina a un equilibrio: la probabilità di Sole scende da 1 → 0,8 → 0,72…
4. Probabilità di transizione in n passi
Esercizio. Cosa rappresenta l’elemento (i,j) della matrice P^n?
Per le equazioni di Chapman-Kolmogorov, la matrice elevata alla n dà le transizioni in n passi:
P^{(n)}_{ij}=[P^n]_{ij}=P(X_n=j\mid X_0=i).
P^n fornisce la probabilità di passare da i a j in esattamente n passi, sommando su tutti i cammini intermedi. Elevare la matrice = comporre le transizioni.
5. Distribuzione stazionaria
Esercizio. Trovare la distribuzione stazionaria \pi=(\pi_S,\pi_P) del sistema meteo.
La distribuzione stazionaria soddisfa \pi P=\pi con \pi_S+\pi_P=1:
\pi_S=0{,}8\pi_S+0{,}4\pi_P\ \Rightarrow\ 0{,}2\pi_S=0{,}4\pi_P\ \Rightarrow\ \pi_S=2\pi_P.
Con \pi_S+\pi_P=1: 2\pi_P+\pi_P=1\Rightarrow\pi_P=1/3, \pi_S=2/3:
\pi=\left(\dfrac{2}{3},\ \dfrac{1}{3}\right).
A lungo termine il sistema sta nel Sole 2/3 del tempo, indipendentemente dallo stato iniziale. È l’equilibrio verso cui converge la catena.
6. Classificazione degli stati
Esercizio. Definire stati ricorrenti, transitori e assorbenti.
- Ricorrente: uno stato in cui, partendo da esso, si ritorna con probabilità 1;
- Transitorio: uno stato che, una volta lasciato, può non essere più visitato (prob. di ritorno <1);
- Assorbente: uno stato da cui non si esce più (p_{ii}=1).
Una catena irriducibile (ogni stato raggiungibile da ogni altro) e aperiodica ammette una distribuzione stazionaria unica verso cui converge. Gli stati assorbenti (es. “guasto” in affidabilità) catturano definitivamente il sistema.
7. Probabilità a due passi da matrice
Esercizio. Per la catena meteo, calcolare direttamente la probabilità di essere in Pioggia fra due giorni partendo da Sole.
Dobbiamo calcolare l’elemento (S,P) di P^2. I cammini possibili sono:
Quindi:
È lo stesso valore ottenuto nella distribuzione \pi_2=(0{,}72,0{,}28). La potenza della matrice somma tutti i cammini intermedi.
8. Stato assorbente e probabilità di assorbimento
Esercizio. Una macchina può essere Funzionante (F), Degradata (D), Guasta (G). La matrice è
Quale stato è assorbente e qual è la probabilità finale di arrivarci partendo da F?
Lo stato G è assorbente perché:
Da F si può restare in F, passare a D o andare a G; da D si può restare in D o andare a G; da G non si esce. Non esistono classi chiuse alternative a G. Quindi la probabilità finale di assorbimento in G, partendo da F, è:
La catena descrive un sistema che prima o poi si guasta con probabilità 1, anche se il tempo al guasto è aleatorio.
9. Periodicità
Esercizio. La catena con matrice
è periodica?
Da uno stato si torna allo stesso stato solo in un numero pari di passi:
I tempi di ritorno possibili sono 2,4,6,\dots, il cui massimo comun divisore è 2. La catena ha quindi periodo 2.
Anche se la distribuzione stazionaria esiste, la distribuzione al tempo n può oscillare e non convergere se si parte da uno stato deterministico. L’aperiodicità è l’ipotesi che elimina questa oscillazione.
10. Tempo medio di assorbimento semplice
Esercizio. Nella catena del punto 8, partendo da D, qual è il numero medio di passi prima del guasto?
Da D si resta in D con probabilità 0{,}6 e si va a G con probabilità 0{,}4. Il tempo di assorbimento è geometrico con probabilità di successo 0{,}4:
La media non dice che il guasto avverrà esattamente dopo 2 o 3 passi: è il valore atteso su molte repliche del processo.
Errori comuni
- Righe della matrice che non sommano a 1. Ogni riga è una distribuzione di probabilità: deve sommare a 1.
- Moltiplicare matrice × vettore nell’ordine sbagliato. Con il vettore riga si usa \pi P (vettore a sinistra); con il vettore colonna P\pi.
- Confondere P^n con nP. Le transizioni in n passi sono la potenza P^n, non il prodotto per n.
- Cercare la stazionaria senza il vincolo di normalizzazione. \pi P=\pi da sola ha infinite soluzioni: serve \displaystyle \sum\pi_i=1.
- Confondere stazionarietà e convergenza. Una distribuzione stazionaria può esistere anche se la catena periodica non converge da ogni stato iniziale.
- Dimenticare le classi chiuse. In catene con stati assorbenti, la stazionaria non descrive il comportamento transitorio prima dell’assorbimento.