Esercizio - Classificazione degli stati e probabilità di assorbimento in una catena a sei stati

Teoria: Catene di Markov - matrice di transizione, classificazione degli stati e distribuzione stazionariaUna catena di Markov a tempo discreto e stati finiti è descritta da una matrice stocastica P: P(X_{n+1}=j | X_n=i)=P_ij, la legge al tempo n è π_0 P^n. Gli stati si classificano in classi comunicanti (irriducibilità), periodo (aperiodicità) e ricorrenza/transitorietà. Una distribuzione stazionaria soddisfa πP=π; per catene finite irriducibili esiste ed è unica, vale π_i=1/h_ii (h_ii = tempo medio di primo ritorno), e se la catena è anche aperiodica P^n converge a una matrice con tutte le righe uguali a π. Le catene reversibili (π_i P_ij = π_j P_ji) hanno stazionaria immediata.Catene di Markov - matrice di transizione, classificazione degli stati e distribuzione stazionaria →.

Testo. Una catena sugli stati $1,\dots,6$ ha matrice $$P=\begin{pmatrix}0&\tfrac12&\tfrac12&0&0&0\\\tfrac14&0&0&\tfrac14&\tfrac12&0\\0&0&0&1&0&0\\0&0&1&0&0&0\\0&0&0&0&\tfrac12&\tfrac12\\0&0&0&0&1&0\end{pmatrix}.$$

1. Disegnare il grafo, trovare le classi comunicanti, dire quali sono ricorrenti o transitorie e il periodo di ciascuna.
2. Partendo da $1$ e da $2$, probabilità di finire assorbiti nella classe $\{3,4\}$ e in $\{5,6\}$.
3. Numero medio di passi spesi negli stati transitori (tempo di assorbimento).
4. Tutte le distribuzioni stazionarie.
5. Calcolare $\lim P^{2n}$ e $\lim P^{2n+1}$ (o dire che non esiste).

Soluzione

1. Archi: $1\to2,3$; $2\to1,4,5$; $3\to4$; $4\to3$; $5\to5,6$; $6\to5$.

Si ragiona sui sottoinsiemi:

• $1\leftrightarrow2$ comunicano ($1\to2\to1$). Da $\{1,2\}$ si esce (verso $3$, $4$, $5$) senza possibilità di tornare: classe aperta, transitoria. Periodo: $1\to2\to1$ ha lunghezza $2$; non ci sono cappi e non ci sono cicli di lunghezza dispari, quindi periodo $2$ (irrilevante per la convergenza, perché la classe è transitoria).
• $\{3,4\}$: $3\to4\to3$, nessuna uscita: chiusa, ricorrente, periodo $\gcd\{2,4,6,\dots\}=2$.
• $\{5,6\}$: $5\to6\to5$, nessuna uscita: chiusa, ricorrente; $P_{55}=\tfrac12>0$ dà cicli di lunghezza $1$ e $2$, quindi periodo $1$ (aperiodica).

2. Sia $a_i$ la probabilità di assorbimento in $C_1=\{3,4\}$ partendo da $i$ (con $a=1$ per $i\in C_1$, $a=0$ per $i\in C_2=\{5,6\}$). Condizionando al primo passo: $$a_1=\tfrac12a_2+\tfrac12\cdot1,\qquad a_2=\tfrac14a_1+\tfrac14\cdot1+\tfrac12\cdot0.$$ Sostituendo: $a_1=\tfrac12(\tfrac14a_1+\tfrac14)+\tfrac12=\tfrac18a_1+\tfrac58$, quindi $\tfrac78a_1=\tfrac58$, $a_1=\tfrac57$ e $a_2=\tfrac5{28}+\tfrac14=\tfrac{12}{28}=\tfrac37$. In $C_2$: $1-a_i$, cioè $\boxed{\tfrac27\ \text{da }1,\ \tfrac47\ \text{da }2}$.

3. Sia $Q$ il blocco transitorio, $Q=\begin{pmatrix}0&\tfrac12\\\tfrac14&0\end{pmatrix}$. La matrice fondamentale $N=(I-Q)^{-1}$ ha entrata $N_{ij}$ = numero medio di visite a $j$ partendo da $i$. Si ha $I-Q=\begin{pmatrix}1&-\tfrac12\\-\tfrac14&1\end{pmatrix}$, $\det=1-\tfrac18=\tfrac78$, quindi $N=\tfrac87\begin{pmatrix}1&\tfrac12\\\tfrac14&1\end{pmatrix}=\begin{pmatrix}\tfrac87&\tfrac47\\\tfrac27&\tfrac87\end{pmatrix}$. Il tempo medio di assorbimento è la somma delle righe: $\boxed{t_1=\tfrac{12}7\approx1{,}71,\ t_2=\tfrac{10}7\approx1{,}43}$. Controllo diretto: $t_1=1+\tfrac12t_2$, $t_2=1+\tfrac14t_1\Rightarrow t_1=1+\tfrac12+\tfrac18t_1\Rightarrow t_1=\tfrac{12}7$. Le probabilità di assorbimento nei singoli stati sono le entrate di $NR$, con $R$ il blocco da transitori a ricorrenti: da $1$ in $(3,4,5,6)$: $(\tfrac47,\tfrac17,\tfrac27,0)$; da $2$: $(\tfrac17,\tfrac27,\tfrac47,0)$.

4. In ogni classe chiusa c'è una stazionaria. Su $C_1$: $\pi_3=\pi_4$, quindi $(\tfrac12,\tfrac12)$. Su $C_2$: $\pi_5=\tfrac12\pi_5+\pi_6$, cioè $\pi_6=\tfrac12\pi_5$, con somma $1$: $(\tfrac23,\tfrac13)$. Gli stati transitori hanno $\pi=0$. Le stazionarie di $P$ sono le combinazioni convesse, infinite: $$\pi=\bigl(0,0,\tfrac\lambda2,\tfrac\lambda2,\tfrac{2(1-\lambda)}3,\tfrac{1-\lambda}3\bigr),\qquad\lambda\in[0,1].$$ Non c'è unicità perché la catena non è irriducibile.

5. Dopo l'assorbimento, in $C_1$ la catena alterna $3,4,3,4,\dots$, quindi la posizione dipende dalla parità del tempo; in $C_2$ converge a $(\tfrac23,\tfrac13)$. Partendo da $1$ (tempo $0$) si entra in $C_1$ in $3$ a un istante dispari ($1\to3$ al tempo $1$, oppure dopo $k$ giri $1\to2\to1$ di lunghezza $2$) oppure in $4$ a un istante pari ($1\to2\to4$ al tempo $2$, più giri): in entrambi i casi, per $n$ pari si è in $4$ e per $n$ dispari in $3$. Partendo da $2$ è il contrario: si entra in $4$ a tempo dispari ($2\to4$) o in $3$ a tempo pari ($2\to1\to3$), quindi per $n$ pari si è in $3$. Perciò, per $n$ pari e grande:

• riga $1$: $(0,0,0,\tfrac57,\tfrac27\cdot\tfrac23,\tfrac27\cdot\tfrac13)=(0,0,0,0{,}7143;\,0{,}1905;\,0{,}0952)$;
• riga $2$: $(0,0,\tfrac37,0,\tfrac47\cdot\tfrac23,\tfrac47\cdot\tfrac13)=(0,0,0{,}4286;\,0;\,0{,}3810;\,0{,}1905)$.

Per $n$ dispari le colonne $3$ e $4$ si scambiano, le colonne $5,6$ restano uguali. Le due sottosuccessioni hanno limiti diversi: $\lim P^n$ non esiste, esistono $\lim P^{2n}$ e $\lim P^{2n+1}$.

Codice di verifica

import numpy as np
P = np.array([[0, .5, .5, 0, 0, 0], [.25, 0, 0, .25, .5, 0], [0, 0, 0, 1, 0, 0],
              [0, 0, 1, 0, 0, 0], [0, 0, 0, 0, .5, .5], [0, 0, 0, 0, 1, 0]])
Q, R = P[:2, :2], P[:2, 2:]
N = np.linalg.inv(np.eye(2) - Q)
print("N =", N, " t =", N.sum(axis=1))
B = N @ R
print("assorbimento C1:", B[:, :2].sum(axis=1), " C2:", B[:, 2:].sum(axis=1))
print(np.round(np.linalg.matrix_power(P, 50)[:2], 4))
print(np.round(np.linalg.matrix_power(P, 51)[:2], 4))

Output (le ultime due matrici sono le righe $1$ e $2$ di $P^{50}$ e di $P^{51}$):

N = [[1.14285714 0.57142857]
 [0.28571429 1.14285714]]  t = [1.71428571 1.42857143]
assorbimento C1: [0.71428571 0.42857143]  C2: [0.28571429 0.57142857]
[[0.     0.     0.     0.7143 0.1905 0.0952]
 [0.     0.     0.4286 0.     0.381  0.1905]]
[[0.     0.     0.7143 0.     0.1905 0.0952]
 [0.     0.     0.     0.4286 0.381  0.1905]]