Catene di Markov - matrice di transizione, classificazione degli stati e distribuzione stazionaria

In questa pagina 6

Una catena di Markov descrive un processo casuale che "dimentica il passato": dove va dipende solo da dove si trova. È il modello di fondo di passeggiate aleatorie, algoritmi randomizzati con memoria finita, PageRank e campionamento MCMC (altre note di questa materia: Passeggiate aleatorie - rovina del giocatore, 2-SAT e grafi, Metodi Monte Carlo - stima, generazione di variabili aleatorie e MCMC). Prerequisiti: Probabilità condizionata, Formula delle probabilità totali e formula di Bayes, Valore atteso. Le catene di Markov nei modelli probabilistici dell'IA (HMM, filtraggio) sono in Ragionamento probabilistico nel tempo - catene di Markov, HMM, filtraggio e smoothing.

Definizione e matrice di transizione

Definizione (catena di Markov). Una successione di variabili aleatorie $X_0, X_1, X_2, \dots$ a valori in un insieme finito di stati $S=\{1,\dots,k\}$ è una catena di Markov (omogenea) se per ogni $n$ e per ogni scelta di stati vale la proprietà di Markov $P(X_{n+1}=j\mid X_n=i,\,X_{n-1}=i_{n-1},\dots,X_0=i_0)=P(X_{n+1}=j\mid X_n=i)=P_{ij},$ con $P_{ij}$ che non dipende da $n$ . La matrice $P=(P_{ij})$ è la matrice di transizione: ha entrate $\ge0$ e ogni riga somma a 1 (matrice stocastica), perché dallo stato $i$ si va per forza da qualche parte.

Una catena si disegna come un grafo orientato pesato: un arco $i\to j$ con peso $P_{ij}$ per ogni $P_{ij}>0$ .

Esempio (meteo). Stati $1=$ sole, $2=$ pioggia. Se oggi c'è il sole, domani c'è sole con probabilità $0{,}9$ ; se oggi piove, domani piove con probabilità $0{,}5$ : $P=\begin{pmatrix}0{,}9&0{,}1\\0{,}5&0{,}5\end{pmatrix}.$ Ogni riga somma a 1. Un "giorno" è un passo; il meteo di domani non dipende dal meteo di ieri una volta noto quello di oggi.

Potenze di P e distribuzione al tempo n

Sia $\pi^{(n)}$ il vettore riga con $\pi^{(n)}_j=P(X_n=j)$ . Per la formula delle probabilità totali (Formula delle probabilità totali e formula di Bayes) sulle posizioni al tempo $n$ : $\pi^{(n+1)}_j=\sum_i P(X_n=i)\,P(X_{n+1}=j\mid X_n=i)=\sum_i\pi^{(n)}_iP_{ij}\quad\Longrightarrow\quad \pi^{(n+1)}=\pi^{(n)}P,\qquad \pi^{(n)}=\pi^{(0)}P^n.$ L'entrata $(P^n)_{ij}$ è la probabilità $P(X_n=j\mid X_0=i)$ di andare da $i$ a $j$ in esattamente $n$ passi. Vale l'equazione di Chapman-Kolmogorov $P^{m+n}=P^mP^n$ : per andare da $i$ a $j$ in $m+n$ passi si passa al tempo $m$ da qualche stato $k$ , e si somma su $k$ .

Esempio. Nel meteo, $P^2$ ha prima riga $(0{,}9\cdot0{,}9+0{,}1\cdot0{,}5,\ 0{,}9\cdot0{,}1+0{,}1\cdot0{,}5)=(0{,}86,\ 0{,}14)$ e seconda riga $(0{,}5\cdot0{,}9+0{,}5\cdot0{,}5,\ 0{,}5\cdot0{,}1+0{,}5\cdot0{,}5)=(0{,}70,\ 0{,}30)$ . Partendo dal sole, la probabilità di sole dopo $n=1,2,3,5,10$ giorni vale $0{,}9;\ 0{,}86;\ 0{,}844;\ 0{,}83504;\ 0{,}83335$ : si avvicina a $5/6\approx0{,}8333$ .

Per due stati con $P=\begin{pmatrix}1-a&a\\b&1-b\end{pmatrix}$ c'è la forma chiusa $P^n=\frac1{a+b}\begin{pmatrix}b&a\\b&a\end{pmatrix}+\frac{(1-a-b)^n}{a+b}\begin{pmatrix}a&-a\\-b&b\end{pmatrix}.$ Col meteo ( $a=0{,}1$ , $b=0{,}5$ , $1-a-b=0{,}4$ ) il primo addendo ha righe uguali $(5/6,\,1/6)$ e il secondo tende a zero come $0{,}4^n$ : è la convergenza all'equilibrio (verificata con frazioni esatte per $n\le5$ ).

Classificazione degli stati

Il grafo della catena dice quasi tutto. Si scrive $i\to j$ (" $j$ è raggiungibile da $i$ ") se $(P^n)_{ij}>0$ per qualche $n\ge0$ , cioè se nel grafo c'è un cammino da $i$ a $j$ ; e $i\leftrightarrow j$ ("comunicano") se $i\to j$ e $j\to i$ . La comunicazione è una relazione di equivalenza, quindi gli stati si dividono in classi comunicanti.

Definizione (irriducibilità). Una catena è irriducibile se ha una sola classe, cioè da ogni stato si può raggiungere ogni altro: il grafo è fortemente connesso.

Una classe è chiusa se da essa non si esce; altrimenti è aperta. Uno stato con $P_{ii}=1$ è assorbente (classe chiusa di un solo stato).

Definizione (periodo). Il periodo di $i$ è $d(i)=\gcd\{n\ge1:(P^n)_{ii}>0\}$ (massimo comun divisore delle lunghezze dei cammini chiusi per $i$ ). Se $d(i)=1$ lo stato è aperiodico. Il periodo è uguale per tutti gli stati di una classe. Una catena irriducibile è aperiodica se lo è un suo stato; in particolare basta un cappio $P_{ii}>0$ .

Definizione (ricorrenza). Sia $T_i=\min\{n\ge1: X_n=i\}$ il tempo di primo ritorno in $i$ partendo da $i$ . Lo stato è ricorrente se $P(T_i<\infty\mid X_0=i)=1$ , transitorio altrimenti. Il tempo medio di ritorno è $h_{ii}=E[T_i\mid X_0=i]$ ; se ricorrente e $h_{ii}<\infty$ è ricorrente positivo.

Intuizione: in uno stato transitorio c'è una probabilità positiva $q$ di non tornare mai più. Per la proprietà di Markov ogni visita "ricomincia da capo", quindi il numero di visite (contando la prima) è geometrico di parametro $q$ , con media finita $1/q$ (Distribuzione geometrica): prima o poi la catena esce per sempre. Ricorrenza e transitorietà sono proprietà di classe.

Fatti per catene finite.

Una classe è ricorrente se e solo se è chiusa. Una classe aperta è transitoria, perché con probabilità positiva ne esce senza tornare. Una classe chiusa finita è ricorrente, perché non può lasciare l'insieme finito e quindi ritorna.
Ogni catena finita ha almeno una classe chiusa (ricorrente).
In una catena finita irriducibile tutti gli stati sono ricorrenti positivi: $h_{ii}<\infty$ . Infatti da ogni stato si raggiunge $i$ in al più $k$ passi con probabilità almeno $\varepsilon>0$ (il minimo sulle coppie di stati delle probabilità di un cammino più breve); quindi $P(T_i>mk)\le(1-\varepsilon)^m$ e la coda geometrica dà una media finita.

Grafico interattivo: Catena a quattro stati: 1 transitorio (cappio 1/4), {2,3} classe chiusa aperiodica (cappio 1/2 in 3), 4 assorbente. Pesi: 1→2 1/2, 1→4 1/4, 2→3 1, 3→2 1/2

Esempio. Nella catena del disegno ( $P_{11}=\tfrac14$ , $P_{12}=\tfrac12$ , $P_{14}=\tfrac14$ ; $P_{23}=1$ ; $P_{32}=P_{33}=\tfrac12$ ; $P_{44}=1$ ) le classi sono $\{1\}$ , $\{2,3\}$ , $\{4\}$ . Lo stato $1$ è transitorio: da $1$ si va in $2$ o in $4$ e non si torna. $\{2,3\}$ è chiusa e ricorrente, aperiodica perché $P_{33}>0$ (lunghezze di ritorno in $3$ : $1,2,3,\dots$ ). $4$ è assorbente. La probabilità di assorbimento in $\{2,3\}$ partendo da $1$ è $a$ con $a=\tfrac14a+\tfrac12\cdot1+\tfrac14\cdot0$ (se si resta in $1$ si ricomincia; se si va in $2$ si è assorbiti in $\{2,3\}$ ; se si va in $4$ no): $\tfrac34a=\tfrac12$ , $a=\tfrac23$ ; in $4$ finisce con probabilità $\tfrac13$ .

Esempio (periodo). Il ciclo orientato $1\to2\to3\to1$ ( $P_{12}=P_{23}=P_{31}=1$ ) è irriducibile con periodo $3$ : si torna in $1$ solo ai tempi $3,6,9,\dots$ . $P^3=I$ : la distribuzione ruota per sempre e $P^n$ non converge. La distribuzione $(\tfrac13,\tfrac13,\tfrac13)$ è però invariante.

Distribuzione stazionaria

Definizione (distribuzione stazionaria). Un vettore riga $\pi$ con $\pi_i\ge0$ , $\sum_i\pi_i=1$ e $\pi P=\pi,\qquad\text{cioè}\qquad \pi_j=\sum_i\pi_iP_{ij}\ \ \text{per ogni }j$ è una distribuzione stazionaria (o invariante): se $X_0\sim\pi$ allora $X_n\sim\pi$ per ogni $n$ .

È un autovettore sinistro di $P$ con autovalore $1$ (l'autovalore $1$ c'è sempre: $P\mathbf1=\mathbf1$ perché le righe sommano a $1$ ). Si trova risolvendo $\pi(P-I)=0$ con $\sum_i\pi_i=1$ (un'equazione del sistema è ridondante).

Esempio (meteo). Con $\pi=(x,y)$ , $x+y=1$ : $\pi P=\pi$ dà $0{,}9x+0{,}5y=x$ , cioè $0{,}5y=0{,}1x$ , $x=5y$ ; con $x+y=1$ : $y=\tfrac16$ , $x=\tfrac56$ . A lungo termine il $83{,}3\%$ dei giorni è di sole, qualunque sia il tempo di oggi.

Teorema fondamentale delle catene di Markov. Sia $P$ una catena finita e irriducibile. Allora:

esiste un'unica distribuzione stazionaria $\pi$ , con $\pi_i>0$ per ogni $i$ ;

$\pi_i=\dfrac1{h_{ii}}$ (il tempo medio di ritorno è l'inverso della probabilità stazionaria);

la frazione di tempo passata in $j$ tende a $\pi_j$ con probabilità 1 (teorema ergodico), anche se la catena è periodica;

se inoltre è aperiodica, per ogni $i,j$ : $\lim_{n\to\infty}(P^n)_{ij}=\pi_j$ , cioè $P^n\to\mathbf1\pi$ (tutte le righe tendono a $\pi$ ) e la legge di $X_n$ tende a $\pi$ qualunque sia lo stato iniziale.

Dimostrazione di 1 (esistenza) e 2. Si fissa uno stato $i$ e si pone, per ogni $j$ , $\mu_j=\sum_{t\ge0}P(X_t=j,\ T_i>t\mid X_0=i),$ il numero medio di visite a $j$ in una "escursione" da $i$ che termina al primo ritorno in $i$ (si conta il tempo $0$ ma non il ritorno finale). Sommando su $j$ si ottiene $\sum_j\mu_j=\sum_tP(T_i>t)=E[T_i]=h_{ii}<\infty$ . Si verifica $\mu P=\mu$ : $\sum_j\mu_jP_{jk}=\sum_{t\ge0}\sum_jP(X_t=j,T_i>t)P_{jk}=\sum_{t\ge0}P(X_{t+1}=k,\ T_i>t),$ perché $\{T_i>t\}$ dipende solo da $X_1,\dots,X_t$ e vale la proprietà di Markov. Si divide l'evento $\{T_i>t\}$ in $\{T_i>t+1\}$ e $\{T_i=t+1\}$ : il primo dà $\sum_{t\ge0}P(X_{t+1}=k,T_i>t+1)=\mu_k-P(X_0=k)=\mu_k-\mathbf 1[k=i]$ (la somma su $t'=t+1\ge1$ è $\mu_k$ meno il termine $t'=0$ ); il secondo dà $\sum_{t}P(X_{t+1}=k,T_i=t+1)=P(X_{T_i}=k)=\mathbf1[k=i]$ (al primo ritorno si è in $i$ ). Totale: $\mu_k$ . Quindi $\pi=\mu/h_{ii}$ è stazionaria e $\pi_i=\mu_i/h_{ii}=1/h_{ii}$ perché $\mu_i=1$ (si visita $i$ solo al tempo $0$ ). $\blacksquare$

Unicità: lo spazio delle soluzioni di $xP=x$ ha dimensione $1$ per una matrice stocastica irriducibile (Perron-Frobenius, qui senza dimostrazione). Perciò $\pi_i=1/h_{ii}$ vale per ogni $i$ con la stessa $\pi$ .

Idea della dimostrazione di 4 (accoppiamento). Si lanciano due copie della catena, una da $i$ e una con $X_0'\sim\pi$ (quindi sempre $\sim\pi$ al tempo $n$ ). Le due evolvono indipendenti finché non si incontrano nello stesso stato, poi si muovono insieme. Per aperiodicità e irriducibilità la coppia (catena prodotto) è irriducibile: l'incontro avviene in tempo finito con coda geometrica, $P(\text{non ancora incontrate al tempo }n)\le C\rho^n$ con $\rho<1$ . Dopo l'incontro le due leggi coincidono, quindi la distanza tra la legge di $X_n$ e $\pi$ è $\le C\rho^n$ . Senza aperiodicità l'incontro può non avvenire mai (ciclo di periodo $3$ sopra).

Esempio. Catena "server": stati $1=$ libero, $2=$ occupato, $3=$ guasto, con $P=\begin{pmatrix}0{,}7&0{,}2&0{,}1\\0{,}4&0{,}5&0{,}1\\0{,}5&0&0{,}5\end{pmatrix}$ (svolta nell'esercizio Esercizio - Catena di Markov a tre stati, potenze di P e distribuzione stazionaria): $\pi=(\tfrac{25}{42},\tfrac5{21},\tfrac16)$ e i tempi medi di ritorno sono $\tfrac{42}{25}=1{,}68$ , $\tfrac{21}5=4{,}2$ , $6$ .

Velocità di convergenza e tempo di mescolamento

La distanza di variazione totale tra due leggi è $\|\mu-\nu\|_{TV}=\tfrac12\sum_j|\mu_j-\nu_j|=\max_A|\mu(A)-\nu(A)|$ . Il tempo di mescolamento è $\tau(\varepsilon)=\min\{n:\max_i\|P^n(i,\cdot)-\pi\|_{TV}\le\varepsilon\}$ . Se $P$ è diagonalizzabile, la distanza decade come $|\lambda_2|^n$ , dove $\lambda_2$ è il secondo autovalore in modulo: il gap spettrale $1-|\lambda_2|$ misura la velocità.

Esempio. Nel meteo $\lambda_2=1-a-b=0{,}4$ e dalla forma chiusa $\|P^n(1,\cdot)-\pi\|_{TV}=\tfrac16\,0{,}4^n$ , $\|P^n(2,\cdot)-\pi\|_{TV}=\tfrac56\,0{,}4^n$ . Il massimo è $\tfrac56\,0{,}4^n$ , che vale $0{,}0213$ per $n=4$ e $0{,}0085$ per $n=5$ : $\tau(0{,}01)=5$ giorni. Nell'esercizio sul server gli autovalori sono $1$ , $0{,}4$ , $0{,}3$ .

Il caso periodico si cura con la catena pigra $\tilde P=\tfrac12(I+P)$ : stessa $\pi$ (da $\pi\tilde P=\tfrac12(\pi+\pi P)=\pi$ ), ma con cappi in ogni stato, quindi aperiodica. Si usa per forzare la convergenza (per esempio nel modello di Ehrenfest, Esercizio - Modello di Ehrenfest con quattro palline e bilancio dettagliato).

Catene reversibili e bilancio dettagliato

Definizione. Una distribuzione $\pi$ e una matrice $P$ soddisfano il bilancio dettagliato se $\pi_iP_{ij}=\pi_jP_{ji}\qquad\text{per ogni coppia }i,j.$ Una catena con questa proprietà è reversibile (rispetto a $\pi$ ): in equilibrio il flusso $i\to j$ uguaglia il flusso $j\to i$ , quindi la catena osservata al contrario ha la stessa legge.

Teorema. Se $\pi$ è una distribuzione che soddisfa il bilancio dettagliato, allora $\pi$ è stazionaria.

Dimostrazione. Sommando su $i$ : $\sum_i\pi_iP_{ij}=\sum_i\pi_jP_{ji}=\pi_j\sum_iP_{ji}=\pi_j$ , perché la riga $j$ di $P$ somma a $1$ . $\blacksquare$

Il bilancio dettagliato è condizione sufficiente, non necessaria (il ciclo orientato di periodo $3$ ha $\pi$ uniforme ma $\pi_1P_{12}=\tfrac13\ne0=\pi_2P_{21}$ ). Il vantaggio: invece di risolvere un sistema, si indovina $\pi$ e si controlla coppia per coppia. È lo strumento di MCMC (Metodi Monte Carlo - stima, generazione di variabili aleatorie e MCMC) e della passeggiata su un grafo (Passeggiate aleatorie - rovina del giocatore, 2-SAT e grafi).

Esempio. $Q=\begin{pmatrix}\tfrac12&\tfrac12&0\\\tfrac14&\tfrac12&\tfrac14\\0&\tfrac12&\tfrac12\end{pmatrix}$ è una catena nascita-morte (si muove solo tra stati vicini). Si prova $\pi=(x,y,z)$ con $\pi_1Q_{12}=\pi_2Q_{21}$ : $\tfrac12x=\tfrac14y$ , $y=2x$ ; e $\pi_2Q_{23}=\pi_3Q_{32}$ : $\tfrac14y=\tfrac12z$ , $z=\tfrac y2=x$ . Con la somma $1$ : $x+2x+x=1$ , $\pi=(\tfrac14,\tfrac12,\tfrac14)$ . Le uniche altre coppie ( $1,3$ ) hanno entrambi i lati nulli. $Q$ è aperiodica (cappi) e $Q^2=\begin{pmatrix}3/8&1/2&1/8\\1/4&1/2&1/4\\1/8&1/2&3/8\end{pmatrix}$ , $Q^3=\begin{pmatrix}5/16&1/2&3/16\\1/4&1/2&1/4\\3/16&1/2&5/16\end{pmatrix}$ si avvicinano a righe tutte uguali a $\pi$ (la distanza dal secondo autovalore $1/2$ dimezza a ogni passo).

Codice: stazionaria e simulazione

python

import numpy as np

P = np.array([[0.9, 0.1],
              [0.5, 0.5]])

def stazionaria(P):
    """Risolve pi (P - I) = 0 con somma 1 (minimi quadrati su sistema sovradeterminato)."""
    k = len(P)
    A = np.vstack([P.T - np.eye(k), np.ones(k)])
    b = np.zeros(k + 1); b[-1] = 1
    return np.linalg.lstsq(A, b, rcond=None)[0]

def frequenze(P, passi, seed=1):
    """Simula la catena e restituisce la frazione di tempo in ogni stato."""
    rng = np.random.default_rng(seed)
    x, visite = 0, np.zeros(len(P))
    for _ in range(passi):
        x = rng.choice(len(P), p=P[x])
        visite[x] += 1
    return visite / passi

print(stazionaria(P))                         # [0.8333 0.1667]
print(np.linalg.matrix_power(P, 10)[0])       # [0.83335 0.16665]
print(frequenze(P, 200_000))                  # circa [0.83 0.17]

Domande d'esame

Dimostra che $\pi_i=1/h_{ii}$ . Si costruisce $\mu_j$ = visite medie a $j$ in un'escursione da $i$ ; $\mu P=\mu$ , $\sum_j\mu_j=h_{ii}$ , $\mu_i=1$ ; si normalizza (dimostrazione sopra).
Meteo ( $P$ sopra): probabilità di sole fra 3 giorni se oggi piove, e tempo medio tra due giorni di pioggia consecutivi nel lungo periodo. si usa $P^3=P^2P$ : la riga 2 di $P^2$ è $(0{,}70;\ 0{,}30)$ , quindi la riga 2 di $P^3$ è $(0{,}70\cdot0{,}9+0{,}30\cdot0{,}5,\ 0{,}70\cdot0{,}1+0{,}30\cdot0{,}5)=(0{,}78;\ 0{,}22)$ e la probabilità di sole è $0{,}78$ . Il tempo medio di ritorno alla pioggia è $h_{22}=1/\pi_2=6$ giorni.
Dimostra che il bilancio dettagliato implica la stazionarietà e fai vedere che non è necessario. Somma su $i$ (sopra); controesempio: il ciclo di periodo $3$ .
Perché una catena periodica non converge, e come si risolve? $P^n$ ha supporto che ruota con periodo $d$ ; la distribuzione al tempo $n$ non ha limite. Si passa a $\tfrac12(I+P)$ , con la stessa $\pi$ .

Versione ripasso

Catena di Markov: $P(X_{n+1}=j\mid X_n=i,\dots)=P_{ij}$ , la matrice $P$ è stocastica. Legge al tempo $n$ : $\pi^{(n)}=\pi^{(0)}P^n$ , e $(P^n)_{ij}$ è la probabilità di andare da $i$ a $j$ in $n$ passi; Chapman-Kolmogorov $P^{m+n}=P^mP^n$ (Formula delle probabilità totali e formula di Bayes). Meteo $P=\begin{pmatrix}0{,}9&0{,}1\\0{,}5&0{,}5\end{pmatrix}$ : $P^2$ ha righe $(0{,}86;0{,}14)$ e $(0{,}70;0{,}30)$ ; da sole dopo $1,2,3,5,10$ giorni: $0{,}9;0{,}86;0{,}844;0{,}83504;0{,}83335$ .
Due stati: $P^n=\frac1{a+b}\begin{pmatrix}b&a\\b&a\end{pmatrix}+\frac{(1-a-b)^n}{a+b}\begin{pmatrix}a&-a\\-b&b\end{pmatrix}$ ; con $a=0{,}1$ , $b=0{,}5$ il secondo termine decade come $0{,}4^n$ .
Classificazione: $i\to j$ se c'è un cammino nel grafo; classi comunicanti; irriducibile = una sola classe (grafo fortemente connesso). Classe chiusa se non si esce, assorbente se $P_{ii}=1$ . Periodo $d(i)=\gcd\{n:(P^n)_{ii}>0\}$ , uguale su tutta la classe; un cappio $P_{ii}>0$ rende l'irriducibile aperiodica. Ciclo orientato di lunghezza $3$ : periodo $3$ , $P^3=I$ , nessun limite.
Ricorrenza: $T_i$ tempo di primo ritorno, ricorrente se $P(T_i<\infty)=1$ , $h_{ii}=E[T_i]$ . In una catena finita: classe ricorrente $\iff$ chiusa; in una irriducibile $h_{ii}<\infty$ perché $P(T_i>mk)\le(1-\varepsilon)^m$ (da ogni stato si arriva a $i$ in al più $k$ passi con probabilità $\ge\varepsilon$ ). Esempio a quattro stati: $\{1\}$ transitorio ( $P_{11}=\tfrac14$ ), $\{2,3\}$ chiusa aperiodica, $4$ assorbente; assorbimento in $\{2,3\}$ da $1$ : $a=\tfrac14a+\tfrac12\Rightarrow a=\tfrac23$ .
Stazionaria: $\pi P=\pi$ , $\sum\pi_i=1$ (vettore riga, autovalore $1$ ); si risolvono le equazioni colonna per colonna, una è ridondante, poi si normalizza. Meteo: $0{,}5y=0{,}1x$ , $x=5y$ , $\pi=(\tfrac56,\tfrac16)$ . Server a tre stati: $\pi=(\tfrac{25}{42},\tfrac5{21},\tfrac16)$ , ritorni $1{,}68;4{,}2;6$ , autovalori $1;0{,}4;0{,}3$ .
Teorema fondamentale (finita irriducibile): $\pi$ unica e positiva; $\pi_i=1/h_{ii}$ ; teorema ergodico (frazione di tempo in $j$ $\to\pi_j$ , anche se periodica); se aperiodica $P^n\to\mathbf1\pi$ da qualunque stato.
Dimostrazione di $\pi_i=1/h_{ii}$ : $\mu_j=\sum_{t\ge0}P(X_t=j,T_i>t)$ = visite medie a $j$ in un'escursione da $i$ ; $\sum_j\mu_j=E[T_i]=h_{ii}$ ; $\sum_j\mu_jP_{jk}=\sum_tP(X_{t+1}=k,T_i>t)=\mu_k-\mathbf1[k=i]+\mathbf1[k=i]=\mu_k$ (le visite a $t+1>0$ danno $\mu_k$ meno il termine $t=0$ , il ritorno finale compensa); $\mu_i=1$ , quindi $\pi=\mu/h_{ii}$ .
Convergenza: accoppiamento di due copie (una da $\pi$ ), che si incontrano con coda geometrica grazie ad aperiodicità e irriducibilità; senza aperiodicità non si incontrano. Distanza in variazione totale $\tfrac12\sum|\mu_j-\nu_j|$ , decade come $|\lambda_2|^n$ . Meteo: $\tfrac56\,0{,}4^n$ , sotto $0{,}01$ da $n=5$ . Catena pigra $\tfrac12(I+P)$ .
Reversibilità: $\pi_iP_{ij}=\pi_jP_{ji}\Rightarrow\pi P=\pi$ (si somma su $i$ e la riga $j$ somma a $1$ ); è sufficiente, non necessaria (ciclo di periodo $3$ ). Esempio nascita-morte $Q$ : $\tfrac12x=\tfrac14y$ , $\tfrac14y=\tfrac12z$ , $\pi=(\tfrac14,\tfrac12,\tfrac14)$ , convergenza con $\lambda_2=\tfrac12$ . Usi: Passeggiate aleatorie - rovina del giocatore, 2-SAT e grafi, Metodi Monte Carlo - stima, generazione di variabili aleatorie e MCMC.
Domande tipiche: $\pi_i=1/h_{ii}$ ; sole fra $3$ giorni se oggi piove: $P^3=P^2P$ , riga $2$ $(0{,}78;0{,}22)$ ; perché la periodica non converge e come si risolve.
Verifiche numeriche: server a tre stati $P^2$ con prima riga $(0{,}62;0{,}24;0{,}14)$ , $(P^3)_{13}=0{,}156$ ; tempo per raggiungere il guasto $g_1=g_2=10$ ; $h_{33}=1+0{,}5\,g_1=6$ . Ehrenfest con $4$ palline: $\pi=\text{Bin}(4,\tfrac12)$ per bilancio dettagliato, periodo $2$ (nessun limite), catena pigra convergente.
Errori tipici: righe e colonne scambiate in $\pi P=\pi$ ; dimenticare la normalizzazione; credere che irriducibile basti per la convergenza (serve l'aperiodicità); confondere tempo di ritorno e di raggiungimento.