Algebra lineare · Catena di Markov

Catena di Markov

In una catena di Markov lo stato cambia a caso e le probabilità dello stato successivo dipendono solo da quello corrente. Con la matrice di transizione P, la distribuzione di domani è quella di oggi moltiplicata per P. Ripetendo, spesso si tende a una distribuzione stazionaria π con πP = π, autovettore sinistro di autovalore 1.

Catena di Markov in questa visualizzazione

In una catena di Markov le probabilità dello stato successivo dipendono solo da quello attuale. Qui gli stati sono sole, nubi e pioggia. La riga ii della matrice di transizione PP dà le probabilità di domani se oggi lo stato è ii: ogni riga è un vettore di probabilità. Se la distribuzione di oggi è il vettore riga pp, domani è pPpP e dopo nn giorni è pn=p0Pnp_n = p_0 P^n. Con tre stati, ogni distribuzione è un punto di un triangolo: i vertici corrispondono a stati certi e le probabilità sono i pesi dei vertici. I punti scuri sono le righe di PP, il blu è l’inizio e il percorso rosso unisce p0,p1,p2,…p_0, p_1, p_2, \dots.

Cosa succede in un passo

Un passo manda ogni vertice nella sua riga: al sole certo segue la distribuzione della prima riga. Ogni distribuzione pp è una media pesata dei vertici, così pPpP è la stessa media delle righe. Il triangolo intero entra in quello formato dalle righe; dopo due passi, in quello delle righe di P2P^2. Se una potenza di PP ha tutte le entrate positive, i triangoli annidati si stringono su un punto: la distribuzione stazionaria π\pi.

Perché π è un autovettore e quanto rapidamente pₙ vi si avvicina

Il punto fisso soddisfa πP=π\pi P = \pi: π\pi è un autovettore sinistro di autovalore 1 (in colonne, PTπT=πTP^{\mathsf T}\pi^{\mathsf T} = \pi^{\mathsf T}). Le componenti della differenza p0−πp_0 - \pi sommano a 0. Su questo sottospazio PP ha gli altri due autovalori λ2,λ3\lambda_2, \lambda_3. Un vettore in una direzione propria viene moltiplicato per il relativo autovalore a ogni passo. Se i due moduli sono minori di 1, pnp_n tende a π\pi e il modulo maggiore ∣λ2∣|\lambda_2| determina il ritmo. Per il meteo ∣λ2∣≈0.462|\lambda_2| \approx 0.462, quindi per nn grande resta poco meno della metà della distanza a ogni passo, purché l’inizio abbia una componente nella direzione di λ2\lambda_2. Con autovalori complessi, il percorso ruota mentre si contrae.

Quando la distribuzione non converge

Nel ciclo sole, nubi e pioggia si susseguono. Gli altri due autovalori hanno modulo 1 e pnp_n continua a girare, salvo che inizi in π\pi. Con due stati assorbenti sole e pioggia persistono: l’autovalore 1 è doppio e ogni miscela dei due è fissa. pnp_n converge, ma il limite dipende dall’inizio. In una catena finita, pnp_n tende allo stesso π\pi da ogni inizio se e solo se esiste una sola classe chiusa di stati comunicanti ed essa è aperiodica. Gli stati della classe sono raggiungibili l’uno dall’altro e non se ne può uscire. È sufficiente che una potenza PmP^m abbia tutte le entrate positive.

Cosa osservare

  • Per qualunque inizio, la distribuzione stazionaria dà le probabilità del meteo di un giorno lontano. Il tempo continua a cambiare di giorno in giorno.
  • Con più di tre stati le distribuzioni riempiono un simplesso, analogo del triangolo in dimensione superiore. Il ragionamento resta valido.

Comandi

  • Trascina un punto scuro per cambiare una riga della matrice o il blu per cambiare l’inizio. Le frecce spostano il punto selezionato di un centesimo.

Concetti correlati