Immagina di trovarti in un labirinto. In alcuni corridoi, non importa quanto giri a vuoto: sai che prima o poi tornerai al punto di partenza. In altri, basta varcare una soglia per rendersi conto che non c’è più modo di tornare indietro. Quella porta si è chiusa per sempre.

Questo è, in essenza, il cuore pulsante delle Catene di Markov. Non sono solo matrici di numeri o grafi astratti disegnati su una lavagna; sono il modello matematico che descrive l’evoluzione dei sistemi. Che si tratti di prevedere se un cliente rimarrà fedele al tuo brand o di calcolare se una particella di gas scapperà da una scatola aperta, la domanda è sempre la stessa: questo stato è una trappola (ricorrente) o solo un passaggio momentaneo (transitorio)?

Mettiamo da parte le definizioni polverose per un attimo e sporchiamoci le mani con i numeri. Ecco 6 esercizi progressivi per imparare a leggere il futuro di un sistema, un passo alla volta.

Esercizio 1 (Livello facile) – Analisi di una piccola catena

Testo:

Una centrale meteorologica semplifica le condizioni del tempo in una cittadina in due stati: Sole (S) e Pioggia (P). Le probabilità di transizione giornaliere sono:

• Se oggi c’è il sole, domani piove con probabilità [math]0.2[/math].
• Se oggi piove, domani c’è il sole con probabilità [math]0.5[/math].

Rappresenta la catena con il grafo e la matrice di transizione. Classifica gli stati come ricorrenti o transitori motivando la risposta.

Risoluzione:

Definizione degli stati e matrice:

Stati: [math]S_1 = \text{Sole}, S_2 = \text{Pioggia}[/math]

Matrice [math]P[/math]:

[math]P = \begin{pmatrix} 0.8 & 0.2 \ 0.5 & 0.5 \end{pmatrix}[/math]

• La prima riga: da Sole a Sole ([math]0.8[/math]), Sole a Pioggia ([math]0.2[/math]).
• La seconda riga: da Pioggia a Sole ([math]0.5[/math]), Pioggia a Pioggia ([math]0.5[/math]).

Grafo:

Sole (0.8) → Sole ↓ 0.2 Pioggia (0.5) → Pioggia ↑ 0.5

Due stati, comunicanti entrambi (si può passare dall’uno all’altro in un passo o due).

Classificazione:

1. Due stati che comunicano tra loro: da S a P ([math]0.2 > 0[/math]) e da P a S ([math]0.5 > 0[/math]).
2. Quindi formano un’unica classe chiusa (non si esce).
3. Una catena irriducibile (un’unica classe).
4. Definizione: Uno stato è ricorrente se partendo da esso la probabilità di ritornarvi è [math]1[/math].

In una catena finita e irriducibile, tutti gli stati sono ricorrenti.

Conclusione:

S e P sono entrambi stati ricorrenti.

Osservazione 💡
In una catena finita (numero finito di stati), se uno stato è in una classe chiusa (non si può uscire), allora è ricorrente. Qui gli stati comunicano e non c’è modo di uscire dall’insieme {[math]\text{Sole, Pioggia}[/math]}, quindi ricorrenti.

Domanda di riflessione:
Quale proprietà hai usato per concludere che sono ricorrenti?
(Risposta in fondo)

---

---

Esercizio 3 (Livello medio) – Ricorrenza e periodo

Testo:

Considera la catena con stati {[math]1, 2, 3[/math]} e matrice:

[math]P = \begin{pmatrix} 0 & 1 & 0 \ 0.5 & 0 & 0.5 \ 0 & 1 & 0 \end{pmatrix}[/math]

Disegna il grafo, determina le classi di stati e se sono ricorrenti/transitori. Calcola il periodo degli stati.

Risoluzione:

Grafo:

 

In dettaglio:
[math]1 \to 2[/math] ([math]1[/math]),
[math]2 \to 1[/math] ([math]0.5[/math]) e [math]2 \to 3[/math] ([math]0.5[/math]),
[math]3 \to 2[/math] ([math]1[/math]).

Comunicazione:
[math]1 \leftrightarrow 2[/math] ([math]1 \to 2[/math] e [math]2 \to 1[/math])
[math]2 \leftrightarrow 3[/math] ([math]2 \to 3[/math] e [math]3 \to 2[/math])
Quindi [math]1 \leftrightarrow 2 \leftrightarrow 3 \leftrightarrow 1[/math]? [math]1 \to 2 \to 3 \to 2 \to 1[/math], sì [math]1[/math] comunica con [math]3[/math] attraverso [math]2[/math]. Quindi un’unica classe {[math]1, 2, 3[/math]}.
La classe è chiusa? Sì, non ci sono archi in uscita verso altri stati.
Quindi irriducibile, tutti ricorrenti.

Periodo:
Periodo di uno stato = MCD delle lunghezze dei cammini che partono e tornano allo stato.

Stato 1: cammini che tornano in 1:

• [math]1 \to 2 \to 1[/math] (lunghezza [math]2[/math])
• [math]1 \to 2 \to 3 \to 2 \to 1[/math] (lunghezza [math]4[/math])
• MCD([math]2, 4, \dots[/math]) = [math]2[/math].

Stato 2: cammini:

• [math]2 \to 1 \to 2[/math] ([math]2[/math] passi)
• [math]2 \to 3 \to 2[/math] ([math]2[/math] passi)
• [math]2 \to 1 \to 2 \to 3 \to 2[/math] = [math]4[/math] passi.
• MCD([math]2, 4[/math]) = [math]2[/math].

Stato 3: simmetrico a 1, periodo [math]2[/math].
Tutti periodo [math]2[/math].

Osservazione 💡
Il periodo è una proprietà di classe: tutti gli stati in una classe hanno lo stesso periodo. Qui MCD=[math]2[/math], quindi la catena è periodica di periodo [math]2[/math].

Domanda di riflessione:
Come si trova il periodo di uno stato dalla matrice P?
(Risposta in fondo)

---

Esercizio 4 (Livello medio) – Probabilità di ritorno e natura ricorrente

Testo:

Data la catena con stati {[math]0, 1, 2[/math]} e matrice:

[math]P = \begin{pmatrix} 0.5 & 0.5 & 0 \ 0.5 & 0.5 & 0 \ 0 & 0 & 1 \end{pmatrix}[/math]

Trova le classi. Per la classe {[math]0, 1[/math]}, calcola [math]f_{00}[/math] (prob. di ritorno in 0 partendo da 0) e determina se 0 è ricorrente usando la definizione.

Risoluzione:

Classi:
[math]0 \leftrightarrow 1[/math] (comunicano), classe chiusa? Da 0 e 1 non si va a 2, quindi {[math]0, 1[/math]} chiusa.
{[math]2[/math]} è assorbente (classe chiusa).
Quindi due classi chiuse.

Ricorrenza di stato 0:
Siccome {[math]0, 1[/math]} è chiusa e finita, 0 è ricorrente (in catene finite, stati in classi chiuse sono ricorrenti).

Per esercizio: calcoliamo [math]f_{00}[/math].
[math]f_{00}[/math] = prob. di tornare in 0 partendo da 0 prima o poi.

Passi:

[math]f_{00}^{(1)} = P_{00} = 0.5[/math]
[math]f_{00}^{(2)} = P_{01}P_{10} = 0.5 \cdot 0.5 = 0.25[/math]
[math]f_{00}^{(3)} = P_{01}P_{11}P_{10} = 0.5 \cdot 0.5 \cdot 0.5 = 0.125[/math]

In generale, per [math]n \ge 2[/math]: cammini [math]0 \to 1 \to (\text{eventuali giri in 1}) \to 1 \to 0[/math].
Ma più semplice: somma delle prob di ritorno in un tempo finito:
Prob di ritorno in 0 in al più 2 passi: [math]0.5 + 0.25 = 0.75[/math].
Iterando, [math]f_{00} = \sum_{n=1}^{\infty} f_{00}^{(n)} = 0.5 + 0.25 + 0.125 + \dots = 1[/math].
Quindi ricorrente.

Osservazione 💡
In una classe chiusa finita, la probabilità di ritornare è 1 perché non c’è modo di uscire e gli stati sono finiti, quindi prima o poi si torna.

Domanda di riflessione:
Se la classe fosse infinita, questo ragionamento varrebbe?
(Risposta in fondo)

---

Esercizio 5 (Livello difficile) – Catena infinita e transitorietà

Testo:

Una particella si muove sui numeri interi non negativi {[math]0, 1, 2, \dots[/math]}.
Dallo stato [math]n \ge 1[/math]: prob [math]\frac{1}{2}[/math] va a [math]n+1[/math], prob [math]\frac{1}{2}[/math] va a [math]n-1[/math].
Dallo stato 0: prob 1 va a 1 (quindi 0 è riflettente).
Dimostra che tutti gli stati sono ricorrenti o transitori? (Suggerimento: considera il problema della rovina del giocatore).

Risoluzione:

È una catena di nascita e morte con [math]p_n = \frac{1}{2}, q_n = \frac{1}{2}[/math] per [math]n \ge 1[/math], e da 0: [math]p_0 = 1, q_0 = 0[/math].

Criterio per ricorrenza/transitorietà in catene di nascita-morte:
Uno stato 0 è ricorrente se e solo se:

[math]\displaystyle \sum_{n=1}^{\infty} \frac{q_1 q_2 \dots q_n}{p_1 p_2 \dots p_n} = \infty[/math]

Qui [math]p_n = \frac{1}{2}, q_n = \frac{1}{2}[/math] per [math]n \ge 1[/math].
Quindi:

[math]\displaystyle \frac{q_1 \dots q_n}{p_1 \dots p_n} = \frac{(1/2)^n}{(1/2)^n} = 1[/math]

Somma [math]\sum_{n=1}^{\infty} 1 = \infty[/math]. Quindi ricorrente.
Essendo irriducibile, se 0 è ricorrente, tutti gli stati sono ricorrenti.

Osservazione 💡
Per catene di nascita-morte infinite, il comportamento (transitorio/ricorrente) dipende dalla convergenza di una serie. Se la serie diverge, ricorrente; se converge, transitorio.

Domanda di riflessione:
Se da ogni stato n, la prob di andare a n+1 fosse 2/3 e di andare a n-1 1/3, cosa cambierebbe?
(Risposta in fondo)

---

Esercizio 6 (Livello difficile) – Tempo medio di ritorno

Testo:

Considera la catena con stati {[math]1, 2, 3, 4[/math]} e matrice:

[math]P = \begin{pmatrix} 0 & 1 & 0 & 0 \ 0 & 0 & 1 & 0 \ 0 & 0 & 0 & 1 \ 1 & 0 & 0 & 0 \end{pmatrix}[/math]

Determina se gli stati sono ricorrenti e il periodo. Calcola il tempo medio di ritorno [math]m_i = E[T_i \mid X_0 = i][/math] per lo stato 1, dove [math]T_i[/math] è il primo tempo di ritorno.

Risoluzione:

Grafo: [math]1 \to 2 \to 3 \to 4 \to 1[/math] (ciclo deterministico).
Un’unica classe, irriducibile, finita → tutti ricorrenti.

Periodo: i cammini che tornano in 1: solo [math]1 \to 2 \to 3 \to 4 \to 1[/math] ([math]4[/math] passi), quindi periodo 4.

Tempo medio di ritorno in 1:
Partendo da 1, il primo ritorno avviene esattamente dopo 4 passi (percorso obbligato).
Quindi [math]T_1 = 4[/math] con prob 1.
[math]m_1 = E[T_1] = 4[/math].

In generale per catena finita irriducibile, la distribuzione stazionaria [math]\pi[/math] soddisfa [math]\pi_i = 1/m_i[/math].
Qui [math]\pi = (1/4, 1/4, 1/4, 1/4)[/math], quindi [math]m_i = 4[/math] per ogni i.

Osservazione 💡
In una catena finita irriducibile, il tempo medio di ritorno [math]m_i[/math] è l’inverso della massa stazionaria [math]\pi_i[/math].

Domanda di riflessione:
Se la catena fosse stata aperiodica e con una matrice diversa, come si poteva calcolare [math]m_i[/math] senza simulazione?
(Risposta in fondo)

---

Risposte alle Domande di Riflessione

• Esercizio 1: Proprietà usata: In una catena di Markov finita, uno stato in una classe chiusa è ricorrente. Qui la classe è chiusa e finita.
• Esercizio 3: Il periodo di uno stato i si trova come MCD di tutti gli n tali che [math]P_{ii}^{(n)} > 0[/math]. Si può calcolare dalle potenze di P guardando gli elementi diagonali.
• Esercizio 4: Se la classe fosse infinita, non è detto che uno stato in una classe chiusa sia ricorrente. Esempio: passeggiata casuale semplice su interi (infinita) con p > 1/2: stati transitori anche se la classe è chiusa (tutti comunicano).
• Esercizio 5: Se [math]p=2/3, q=1/3[/math], allora [math]\frac{q_1 \dots q_n}{p_1 \dots p_n} = (1/3 / 2/3)^n = (1/2)^n[/math]. La serie converge, quindi lo stato 0 sarebbe transitorio, e tutti gli stati transitori.
• Esercizio 6: Si può calcolare [math]m_i[/math] risolvendo il sistema lineare [math]m_i = 1 + \sum_{j \neq i} P_{ij} m_j[/math] per i fissato, con condizioni di primo ritorno. Oppure trovare la distribuzione stazionaria [math]\pi[/math] e usare [math]m_i = 1/\pi_i[/math].

Perché questi esercizi sono interessanti?

1. L’importanza del Meteo (Es 1 – Matrici dense): Anche se semplice, questo modello è la base degli algoritmi di smoothing. Nelle telecomunicazioni, il canale “Good/Bad” (modello di Gilbert-Elliot) è esattamente questo esercizio: serve a prevedere la perdita di pacchetti dati.

2. Il Robot e il Funnel (Es 2 – Stati Assorbenti): Nelle analisi di marketing (Customer Journey), lo stato “Acquisto” e lo stato “Disiscrizione” sono assorbenti. Capire quali stati sono transitori (es. pagina carrello) permette di calcolare la probabilità di assorbimento (conversion rate) prima che l’utente abbandoni.

3. Periodicità (Es 3): Negli algoritmi di ranking (come PageRank), la periodicità è un problema. Se il web fosse periodico, l’algoritmo non convergerebbe a una soluzione stabile. Google ha dovuto introdurre il “damping factor” proprio per rompere queste strutture periodiche e rendere la catena ergodica.

4. La Trappola Infinita (Es 5): Questo è il modello della “Rovina del Giocatore”. Se giochi contro un banco con risorse infinite (o molto grandi), anche se il gioco è equo, la barriera assorbente (o riflettente in certi casi) determina il tuo destino. In finanza, questo aiuta a capire la probabilità di default di un asset che fluttua casualmente.