Catene di Markov, stazionarietà, mixing

Una catena di Markov è un grafo percorso a caso, dove il prossimo passo dipende solo da dove ti trovi adesso e non da come ci sei arrivato. Da questa regola minimale — l’assenza di memoria — discende una macchina sorprendente: la catena, se ben costruita, dimentica da dove è partita e converge a una distribuzione fissa. Questo capitolo mostra come, quanto in fretta, e perché tre cose lontane fra loro — il ranking delle pagine di Google, il campionamento di un posterior bayesiano, i modelli di linguaggio prima dei transformer — sono tutte la stessa idea.

Perché questo capitolo

Nel 1906 un matematico russo costruisce un oggetto astratto per vincere una disputa su Dio e il libero arbitrio. Novant’anni dopo, lo stesso oggetto decide in quale ordine vedi i risultati di una ricerca sul web, permette ai statistici di stimare modelli altrimenti intrattabili, e regge la generazione di testo per mezzo secolo prima che arrivino i transformer. Le catene di Markov sono uno dei casi più puliti, nella matematica applicata, in cui una definizione di due righe genera una tecnologia.

La definizione di due righe è la proprietà di Markov: il futuro dipende dal passato solo attraverso il presente. Una pallina che gira in un labirinto, e che a ogni stanza sceglie una porta in base soltanto a quale stanza occupa — senza tenere un diario di dove è stata. Sembra una limitazione, e a prima vista lo è. Ma è proprio questa povertà di memoria a rendere la catena analizzabile: si può scrivere tutta la sua dinamica in una matrice, calcolarne il comportamento a lungo termine elevando quella matrice a potenza, e dimostrare un teorema — il teorema ergodico — che dice quando e come la catena converge a un comportamento stabile.

Per chi costruisce sistemi AI, questo capitolo è un prerequisito nascosto di parecchie cose. L’MCMC, il metodo standard per campionare distribuzioni di probabilità complicate, è letteralmente la costruzione di una catena di Markov fatta su misura. I modelli n-gram, che hanno dominato l’elaborazione del linguaggio fino agli anni 2010, sono catene di Markov sulle parole. Il forward process di un modello di diffusione è una catena di Markov che aggiunge rumore. E capire perché i transformer non sono catene di Markov sul testo — perché l’attention rompe l’assenza di memoria — è uno dei modi più precisi per capire cosa l’attention faccia davvero. La Parte IV ha trattato la probabilità come una fotografia statica; il capitolo Processi stocastici e dinamiche casuali ha aggiunto l’asse del tempo. Qui si guarda il sottoinsieme più maneggevole e più usato di quei processi: tempo discreto, stati discreti, e una regola di transizione senza memoria.

C’è anche una ragione concettuale, oltre a quelle operative, per cui le catene di Markov meritano un capitolo a sé. Sono il primo posto, in questa Parte, dove tre linguaggi che il lettore ha incontrato separatamente si fondono: la probabilità (le transizioni sono distribuzioni), l’algebra lineare (la dinamica è una moltiplicazione di matrici, la stazionaria è un autovettore), e la teoria dei grafi (la catena è un grafo orientato e pesato). Il teorema ergodico è il punto in cui i tre linguaggi dicono la stessa cosa: un fatto probabilistico (la catena dimentica l’inizio), un fatto algebrico (le potenze di una matrice convergono a una matrice di rango 1), un fatto sui grafi (un grafo ben connesso e non periodico ha un equilibrio unico). Vedere questa triplice traduzione è un esercizio prezioso di per sé, indipendentemente dalle applicazioni.

Contesto

Andrey Andreyevich Markov (matematico russo, 1856-1922), allievo di Pafnuty Chebyshev alla scuola di San Pietroburgo, introduce le catene che oggi portano il suo nome nel 1906, in un lavoro dal titolo Estensione della legge dei grandi numeri a quantità mutuamente dipendenti. La motivazione non è un’applicazione: è una polemica accademica, e la polemica ha radici teologiche.

Pavel Nekrasov (matematico russo, 1853-1924), figura vicina agli ambienti religiosi e conservatori di Mosca, aveva sostenuto in un lavoro del 1902 che l’indipendenza delle variabili è una condizione necessaria per la validità della legge dei grandi numeri. La legge dei grandi numeri è il teorema — trattato nel capitolo Legge dei grandi numeri e teorema del limite centrale — secondo cui la media di tante osservazioni converge al valore atteso. Da questa premessa Nekrasov traeva una conclusione che usciva dalla matematica: i dati sociali — matrimoni, crimini, suicidi raccolti dalle statistiche dell’epoca — mostrano regolarità stabili; se la legge dei grandi numeri richiede l’indipendenza, allora gli atti umani che generano quei dati devono essere indipendenti l’uno dall’altro; e atti indipendenti, senza catena causale, sono atti liberi. La regolarità statistica come prova del libero arbitrio.

Markov, ateo dichiarato e avversario pubblico di Nekrasov, demolisce l’argomento alla base. Per farlo gli serve un contro-esempio: una famiglia di variabili palesemente dipendenti l’una dall’altra, per cui la legge dei grandi numeri valga lo stesso. Costruisce la catena. Parte dal caso minimo — due stati, quattro probabilità di transizione tutte strettamente comprese fra 0 e 1 — e dimostra che, per quanto le variabili siano concatenate, la frequenza con cui la catena visita ciascuno stato converge a un valore fisso. L’indipendenza non è necessaria. La premessa di Nekrasov è falsa, e con essa cade la conclusione sul libero arbitrio. La catena di Markov nasce, letteralmente, come arma in una disputa su determinismo e teologia.

Nel 1913 Markov le dà la prima applicazione empirica, e la sceglie significativa. Prende il testo di Eugenio Onegin, il romanzo in versi di Aleksandr Puskin, e conta a mano i primi 20.000 caratteri, ignorando spazi e punteggiatura. Li classifica in due categorie, vocali e consonanti — circa 8.638 vocali e 11.362 consonanti — e stima le probabilità di transizione: dopo una vocale, quanto è probabile una consonante? Trova che la sequenza non è una serie di estrazioni indipendenti: dopo una vocale una consonante è più probabile della sua frequenza media, e viceversa. È la prima volta che una catena di Markov viene fittata a dati reali, e che quei dati sono un testo. La linea che da qui porta ai modelli di linguaggio statistici è diretta.

Il dettaglio dell’esperimento di Onegin merita un istante in più, perché chiarisce cosa una catena cattura e cosa no. Se le lettere fossero estratte in modo indipendente, la probabilità che una vocale sia seguita da una vocale sarebbe semplicemente la frequenza delle vocali, circa $0{,}43$ . Markov misura invece una probabilità molto più bassa: dopo una vocale, un’altra vocale è raro. La sequenza ha struttura locale — l’alternanza vocale/consonante è un vincolo fonologico del russo —, e la catena di Markov a due stati la cattura esattamente perché le sue transizioni sono progettate per registrare la dipendenza dal carattere immediatamente precedente. Quello che la catena a due stati non cattura è qualunque struttura più lunga: la grammatica, il significato, la metrica del verso. È il modello più semplice possibile che sia già più ricco dell’indipendenza, e proprio per questo era l’arma giusta contro Nekrasov — bastava un filo di dipendenza per far cadere la sua premessa.

Il quadro teorico si completa più tardi. L’equazione di Chapman-Kolmogorov — che governa la composizione delle transizioni su più passi — prende il nome da Sydney Chapman (1928) e da Andrey Kolmogorov, che nel 1933 inserisce le catene nell’assiomatizzazione moderna della probabilità. La teoria del mixing time, cioè della velocità di convergenza, è invece soprattutto un prodotto degli anni 1980-2000: i lavori di David Aldous, Persi Diaconis, László Lovász, Alistair Sinclair e Mark Jerrum nascono dalle esigenze dell’MCMC e dell’informatica teorica, dove serviva sapere non solo che una catena converge, ma quando.

C’è un filo che vale la pena tirare per intero, perché lega la genesi della catena al suo uso moderno. Markov inventa l’oggetto nel 1906 per una disputa teorica; nel 1948 Shannon lo usa per modellare il linguaggio; nel 1953 il gruppo di Los Alamos attorno a Metropolis lo rovescia in un metodo di calcolo — l’MCMC — per simulare sistemi fisici; negli anni 1990 l’MCMC diventa lo strumento standard della statistica bayesiana applicata; nel 1998 Brin e Page lo applicano al web. Lo stesso oggetto matematico attraversa la teologia, la teoria dell’informazione, la fisica computazionale, la statistica e l’informatica, senza mai cambiare definizione. È un esempio raro di concetto che invecchia bene: la regola di due righe del 1906 è ancora quella che si usa oggi.

Nel grafo della wiki, questo è il nono capitolo della Parte VI. Poggia su Processi stocastici e dinamiche casuali, che fornisce il vocabolario generale — la catena di Markov è il caso a tempo discreto e stato discreto di quel quadro — e su Variabili aleatorie, convergenza, disuguaglianze, da cui arrivano i mattoni: variabile aleatoria, modi di convergenza, la legge dei grandi numeri stessa.

L’ordine del capitolo è il seguente. Prima i tre angoli di intuizione: la catena come grafo percorso a caso, come macchina che dimentica l’inizio, come distribuzione su una nuvola di stati. Poi la meccanica: la matrice di transizione e le sue potenze, la classificazione degli stati, il random walk come caso limite, la distribuzione stazionaria e il teorema ergodico, i tempi di raggiungimento, il mixing time e il bilancio dettagliato. Quindi cinque esempi eterogenei — numerico, in codice, di classificazione, due applicativi — e le applicazioni vere, con l’MCMC al centro. Infine la sezione “dove si rompe”, ampia di proposito, perché i modi in cui questo strumento fallisce o viene frainteso valgono quanto i modi in cui funziona.

L’intuizione, primo angolo: il labirinto senza diario

Prima di qualsiasi formula, una scena concreta. Una pallina si muove fra le stanze di un labirinto. Ogni stanza ha alcune porte, e a ciascuna porta è associata una probabilità: dalla stanza C, la porta verso D si imbocca con probabilità 0.5, quella verso A con probabilità 0.3, quella che riporta in C stessa con probabilità 0.2. La pallina, arrivata in C, lancia un dado truccato secondo queste probabilità, attraversa la porta estratta, arriva in una nuova stanza, e ripete.

La regola che rende questa una catena di Markov è una sola, e va vista bene: la pallina non tiene un diario. Quando si trova in C, le probabilità delle sue prossime mosse dipendono soltanto dal fatto che è in C. Non da come ci è arrivata — se da A o da D —, non da quante stanze ha visitato prima, non dall’ora. Il “dove sono adesso” è tutto ciò che serve per descrivere il “dove andrò”. In gergo, lo stato corrente è una statistica sufficiente per il futuro.

Questo è il senso preciso dell’espressione “assenza di memoria”, o proprietà di Markov. Attenzione a non fraintenderla: non significa che la storia sia irrilevante. Significa che tutto ciò che della storia è rilevante per il futuro è già riassunto nello stato corrente. Se il labirinto fosse fatto in modo che la prossima mossa dipenda dalle ultime due stanze, basterebbe ridefinire lo “stato” come la coppia (stanza precedente, stanza attuale) e si tornerebbe a una catena di Markov. La markovianità non è un limite del fenomeno: è una proprietà di come si è scelto di descrivere lo stato. Tornerà più volte, questa idea.

Una conseguenza pratica dell’assenza di memoria, spesso citata, è che il tempo di permanenza in uno stato segue una legge geometrica. Se da uno stato $i$ la catena resta in $i$ con probabilità $p_{ii}$ a ogni passo, allora la probabilità di restarci esattamente $k$ passi prima di uscire è $p_{ii}^{k-1}(1 - p_{ii})$ . Questo significa che, finché la catena è in $i$ , la probabilità di uscire al prossimo passo non dipende da quanto tempo è già rimasta lì: la catena non “invecchia” nello stato. È la versione discreta della famosa assenza di memoria della distribuzione esponenziale, e una buona spia per riconoscere quando un modello markoviano è — o non è — adeguato a un fenomeno reale, dove spesso la probabilità di un evento cresce col tempo di attesa.

L’oggetto matematico che cattura il labirinto è il diagramma degli stati: un grafo orientato in cui i nodi sono le stanze e gli archi sono le porte, ciascun arco etichettato con la sua probabilità. Da ogni nodo, le etichette degli archi uscenti sommano a 1 — la pallina deve prendere una porta. Tutta la dinamica del sistema è in questo disegno.

Conviene fissare subito perché la proprietà di Markov non è una verità del mondo ma una scelta di descrizione, perché è il fraintendimento numero uno. Prendi un fenomeno con memoria genuina: il prossimo carattere di una parola dipende, di solito, da più di un carattere precedente. Questo non è una catena di Markov sui singoli caratteri. Ma diventa una catena di Markov se ridefinisci lo stato come la coppia (o la tripla) degli ultimi caratteri: lo stato più ricco assorbe la memoria, e rispetto a quello stato la regola torna a dipendere solo dal presente. La domanda giusta non è “questo fenomeno è markoviano?” — quasi nessun fenomeno lo è sui suoi dati grezzi — ma “esiste una scelta di stato rispetto a cui lo diventa, e quanto deve essere grande quello stato?”. La risposta a quest’ultima parte decide se la catena è uno strumento utile o un mostro intrattabile, e ci torneremo nella sezione finale.

L’intuizione, secondo angolo: la dimenticanza dello stato iniziale

Il primo angolo descrive cos’è una catena. Il secondo descrive cosa fa nel lungo periodo, ed è qui che la catena rivela il suo comportamento meno ovvio.

Immagina di non sapere con certezza in quale stanza si trovi la pallina all’inizio. La tua conoscenza è una distribuzione di probabilità sugli stati: un vettore che assegna, per esempio, probabilità 0.7 alla stanza A e 0.3 alla stanza B. Chiamalo $\mu_0$ , la distribuzione iniziale. Dopo che la pallina ha fatto un passo, la tua conoscenza è cambiata: c’è una nuova distribuzione $\mu_1$ . Dopo $n$ passi, $\mu_n$ .

La domanda centrale del capitolo è: cosa succede a $\mu_n$ quando $n$ cresce? La risposta, per una classe molto ampia di catene, è sorprendente. La distribuzione $\mu_n$ converge a un vettore fisso $\pi$ — e questo $\pi$ non dipende da $\mu_0$ . Qualunque fosse la tua ignoranza iniziale, dopo abbastanza passi la distribuzione della pallina è la stessa. La catena ha dimenticato da dove era partita.

Questa è la proprietà più importante e meno intuitiva delle catene di Markov. Una catena ergodica — vedremo fra poco cosa serve perché lo sia — agisce come una macchina che lava via le condizioni iniziali. Se parti certo che la pallina è in A, o certo che è in B, o totalmente incerto: dopo un numero sufficiente di passi finisci sempre nella stessa distribuzione $\pi$ . Quel $\pi$ si chiama distribuzione stazionaria, perché ha una proprietà di equilibrio: se la pallina è distribuita secondo $\pi$ , dopo un passo è ancora distribuita secondo $\pi$ . È il punto fisso della dinamica.

Perché questa dimenticanza non è scontata vale la pena dirlo esplicitamente. Si potrebbe immaginare che la storia di dove la pallina è partita resti, in qualche misura, “scritta” nella sua posizione anche dopo molti passi — che partire da A lasci una traccia permanente rispetto al partire da B. Per le catene ergodiche non è così: la traccia esiste, ma svanisce in modo esponenziale, e dopo abbastanza passi è al di sotto di qualunque soglia di misurabilità. È il rumore della transizione casuale a cancellarla: ogni passo aggiunge un po’ di incertezza nuova che non dipende dall’inizio, e l’incertezza nuova finisce per sommergere quella che codificava il passato. La condizione iniziale non viene “dimenticata” per decreto, ma diluita finché non conta più.

Quanto in fretta avviene la dimenticanza è una domanda a sé, e ha una risposta quantitativa: il mixing time, il numero di passi oltre il quale la distribuzione è praticamente indistinguibile da $\pi$ . Una catena può dimenticare in pochi passi o impiegarne miliardi, e la differenza — vedremo — è scritta negli autovalori della sua matrice.

C’è un terzo modo di guardare la stessa scena, che fa da ponte fra i primi due ed è quello che useranno le applicazioni. Invece di seguire una pallina, immagina una nuvola di palline — un milione di palline — distribuite all’inizio in qualche modo sugli stati. A ogni passo ogni pallina salta secondo $P$ . La nuvola, vista come distribuzione, evolve come $\mu_0 P^n$ . La stazionaria $\pi$ è la configurazione della nuvola che non cambia più: tante palline lasciano ogni stato quante ne arrivano. Questa vista “di popolazione” è quella giusta per PageRank — la frazione di navigatori su ogni pagina — e per l’MCMC — la nuvola dei campioni che si assesta sul bersaglio. La pallina singola è l’intuizione per cosa fa la catena; la nuvola è l’intuizione per cosa calcola.

I tre modi sono complementari e non in conflitto. Il primo dice che la catena è un grafo pesato percorso a caso; il secondo dice che, percorrendolo abbastanza a lungo, il punto di partenza smette di contare; il terzo dice che il punto di arrivo è una distribuzione di equilibrio su tutti gli stati insieme. Tenerli a mente tutti e tre è la chiave per leggere la meccanica senza perdersi.

La meccanica

Matrice di transizione e distribuzione a n passi

Una catena di Markov a stati discreti è descritta da due oggetti. Il primo è lo spazio degli stati $S$ , l’insieme — finito o numerabile — dei valori che la catena può assumere: le stanze del labirinto, le facce di un dado, le parole di un vocabolario. Il secondo è la matrice di transizione $P$ , una matrice $|S| \times |S|$ il cui elemento $p_{ij}$ è la probabilità di passare dallo stato $i$ allo stato $j$ in un passo.

La matrice di transizione e il diagramma degli stati sono due notazioni per lo stesso oggetto: il diagramma è un grafo, la matrice è la sua rappresentazione tabellare. Un arco dal nodo $i$ al nodo $j$ etichettato $0.3$ è la cella $p_{ij} = 0.3$ ; l’assenza di arco è uno zero in matrice. Il diagramma è più leggibile per catene piccole e per ragionare sulla classificazione degli stati; la matrice è indispensabile appena si vuole calcolare — moltiplicare, elevare a potenza, trovare autovalori. Conviene saper passare dall’uno all’altra senza pensarci, perché ogni argomento del capitolo è più naturale in una delle due forme.

$P$ ha due proprietà che la definiscono: ogni elemento è non negativo, $p_{ij} \geq 0$ , e ogni riga somma a 1, $\sum_j p_{ij} = 1$ . La seconda condizione dice che dallo stato $i$ la catena deve andare da qualche parte. Una matrice con queste due proprietà si chiama matrice stocastica (per righe). Assumeremo sempre che $P$ non cambi nel tempo — la catena è omogenea —; questo è il caso standard e quasi sempre quello che serve.

Una convenzione di notazione, perché è fonte di errori silenziosi. In questo capitolo le distribuzioni sono vettori riga e la matrice si applica a destra: $\mu P$ . È la convenzione che rende $p_{ij}$ la probabilità da $i$ a $j$ leggendo la riga $i$ , ed è quella standard nella letteratura probabilistica. Parte della letteratura — soprattutto quella di algebra lineare e quella su PageRank — usa la convenzione opposta, vettori colonna e $P^\top \mu$ , con $P$ trasposta. Le due descrizioni dicono la stessa cosa; ma mescolarle in un calcolo, o leggere una formula nella convenzione sbagliata, produce risultati senza senso. Quando si prende una formula da una fonte, il primo controllo è sempre: righe o colonne?

La distribuzione iniziale $\mu_0$ è un vettore riga di probabilità sugli stati. La regola per farla evolvere è una sola moltiplicazione di matrici:

$\mu_1 = \mu_0 P, \qquad \mu_n = \mu_0 P^n.$

In parole povere: per sapere dove sarà la catena fra $n$ passi, parti dalla tua incertezza iniziale e moltiplicala per la matrice di transizione elevata alla $n$ . La componente $j$ -esima di $\mu_0 P$ si calcola sommando, su tutti gli stati $i$ , la probabilità di partire da $i$ per la probabilità $p_{ij}$ di andare da $i$ a $j$ : è esattamente la regola della probabilità totale.

La potenza $P^n$ ha un’interpretazione altrettanto diretta. L’elemento $(P^n)_{ij}$ è la probabilità di trovarsi in $j$ esattamente $n$ passi dopo essere partiti da $i$ . Questo segue dall’equazione di Chapman-Kolmogorov:

$P^{m+n} = P^m \, P^n.$

In parole: per andare da $i$ a $k$ in $m+n$ passi, la catena deve trovarsi in qualche stato intermedio $j$ dopo i primi $m$ passi; sommando su tutti i possibili $j$ il prodotto “probabilità $i \to j$ in $m$ passi” per “probabilità $j \to k$ in $n$ passi” si ottiene la probabilità $i \to k$ in $m+n$ passi. Calcolare la dinamica di una catena di Markov, fino in fondo, è elevare a potenza una matrice. Tutta la difficoltà del capitolo è capire cosa succede a quelle potenze quando $n$ diventa grande.

Vale la pena fermarsi un momento sulla distinzione fra le due quantità che girano in queste formule, perché si confondono facilmente. La matrice $P$ — e le sue potenze — descrive le transizioni condizionate: $(P^n)_{ij}$ presuppone di sapere con certezza di essere partiti da $i$ . Il vettore $\mu_n$ descrive invece lo stato di conoscenza non condizionato: pesa tutte le possibili partenze secondo $\mu_0$ . La riga $i$ -esima di $P^n$ è essa stessa una distribuzione — è la $\mu_n$ che si otterrebbe partendo certi dello stato $i$ . Quando il teorema ergodico dirà che “tutte le righe di $P^n$ tendono a $\pi$ ”, starà dicendo che la distribuzione a lungo termine è la stessa qualunque sia la riga di partenza: di nuovo, la dimenticanza dell’inizio, vista questa volta dal lato della matrice.

Una nota sul costo. Elevare $P$ alla potenza $n$ con la moltiplicazione ripetuta costa, ma non quanto sembra: con l’esponenziazione veloce (quadrare ripetutamente) bastano dell’ordine di $\log n$ moltiplicazioni di matrici. In pratica, però, quando interessa solo il comportamento a lungo termine non si calcola $P^n$ affatto: si risolve direttamente l’equazione $\pi P = \pi$ , un sistema lineare. La potenza serve quando interessa il transitorio — la catena a un orizzonte finito specifico — non il limite.

Classificazione degli stati

Non tutte le catene si comportano allo stesso modo nel lungo periodo. Quattro proprietà degli stati decidono il destino della catena.

Una premessa di metodo: questa classificazione è una proprietà qualitativa della catena, leggibile dal solo diagramma degli stati senza calcoli numerici. Conta quali transizioni hanno probabilità non nulla, non quanto valgono. Due catene con gli stessi archi ma probabilità diverse appartengono alla stessa classe — entrambe irriducibili, o entrambe periodiche di periodo 2. È il grafo, non i numeri, a decidere il destino qualitativo della catena; i numeri decidono solo la velocità.

Comunicazione. Lo stato $i$ comunica con lo stato $j$ se esiste un numero di passi $n$ per cui $(P^n)_{ij} > 0$ — cioè da $i$ si può raggiungere $j$ — e viceversa. La relazione “comunica con” partiziona gli stati in classi comunicanti: gruppi di stati tutti mutuamente raggiungibili.

Irriducibilità. La catena è irriducibile se ha una sola classe comunicante: da ogni stato si raggiunge ogni altro stato, prima o poi. Niente regioni isolate, niente trappole da cui non si esce. Una catena riducibile è in realtà più catene cucite insieme, e ciascun pezzo va studiato a parte.

Periodo e aperiodicità. Il periodo di uno stato $i$ è il massimo comun divisore di tutti gli $n > 0$ per cui $(P^n)_{ii} > 0$ , cioè di tutti i numeri di passi con cui si può tornare in $i$ . Se quel massimo comun divisore è 1, lo stato è aperiodico. Un esempio di stato periodico: uno stato in cui si può tornare solo dopo un numero pari di passi ha periodo 2 — la catena lo visita a passi alterni e mai in mezzo. In una catena irriducibile tutti gli stati condividono lo stesso periodo, quindi si può parlare di catena aperiodica senza ambiguità. Un modo semplice per garantire l’aperiodicità: se anche un solo stato ha un auto-anello, $p_{ii} > 0$ , e la catena è irriducibile, allora è aperiodica.

Ricorrenza e transienza. Lo stato $i$ è ricorrente se, partendo da $i$ , la probabilità di tornarci almeno una volta è esattamente 1. È transiente se quella probabilità è strettamente minore di 1: esiste una possibilità non nulla di non rivedere mai più $i$ . Tra gli stati ricorrenti si distingue ancora: $i$ è ricorrente positivo se il tempo medio di ritorno è finito, ricorrente nullo se è ricorrente ma il tempo medio di ritorno è infinito. La distinzione positivo/nullo emerge solo su spazi di stati infiniti — il caso da manuale è il random walk simmetrico sulla retta degli interi, che torna all’origine con probabilità 1 ma con tempo medio di ritorno infinito. In una catena finita e irriducibile, fortunatamente, tutti gli stati sono automaticamente ricorrenti positivi, e questo caso copre la grande maggioranza delle applicazioni.

Queste quattro proprietà non sono curiosità da catalogare: decidono se il teorema centrale del capitolo si applica. La regola pratica da portare via è breve. Su una catena finita, irriducibilità più aperiodicità sono tutto ciò che serve — e sono quasi sempre facili da garantire o da forzare, come fa PageRank. Su una catena infinita, anche la ricorrenza positiva diventa una condizione da verificare, perché può semplicemente mancare. Quando si modella un sistema con una catena di Markov, il primo controllo da fare è sempre lo stesso: in quale di queste categorie cade, e quindi quali garanzie si hanno diritto di pretendere.

Una nota sul perché irriducibilità e aperiodicità siano proprietà diverse, dato che entrambe parlano di “connessione”. L’irriducibilità riguarda quali stati si raggiungono — tutti, da tutti. L’aperiodicità riguarda quando — non solo a multipli di un periodo. Una catena può raggiungere ogni stato (irriducibile) ma solo a passi che rispettano una cadenza rigida (periodica): il ciclo a tre stati dell’Esempio 3 è esattamente questo. Le due proprietà tagliano la realtà lungo assi indipendenti, ed entrambe servono al teorema ergodico per ragioni che la sezione successiva rende esplicite.

Distribuzione stazionaria e teorema ergodico

Una distribuzione $\pi$ — vettore riga, componenti non negative, somma 1 — è stazionaria, o invariante, se soddisfa

$\pi P = \pi.$

In parole: se la catena è distribuita secondo $\pi$ a un certo istante, dopo un passo è ancora distribuita secondo $\pi$ . La stazionaria è un punto fisso della dinamica. Attenzione a cosa significa: non vuol dire che la singola pallina smette di muoversi — continua a saltare di stato in stato a ogni passo. Vuol dire che la distribuzione sull’intera popolazione di palline non cambia: tante ne escono da uno stato quante ne entrano. È un equilibrio dinamico, non statico — come una città la cui popolazione resta costante mentre i singoli abitanti vanno e vengono. Dal punto di vista dell’algebra lineare, $\pi$ è un autovettore sinistro di $P$ relativo all’autovalore 1. Ogni matrice stocastica ha 1 come autovalore — il vettore colonna di tutti 1 è sempre un suo autovettore destro, perché le righe sommano a 1 — quindi una stazionaria esiste sempre, almeno una. Il capitolo Autovalori e autovettori a intuizione fornisce il linguaggio: qui basta sapere che un autovettore è una direzione che la matrice non ruota, ma solo riscala, e $\pi$ è la direzione che $P$ lascia ferma del tutto.

Il risultato centrale del capitolo lega la stazionaria al comportamento a lungo termine:

Teorema ergodico (per catene finite). Se una catena di Markov a stati finiti è irriducibile e aperiodica, allora esiste un’unica distribuzione stazionaria $\pi$ , e per qualunque distribuzione iniziale $\mu_0$ vale $\lim_{n \to \infty} \mu_0 P^n = \pi.$ In modo equivalente, $P^n$ converge a una matrice in cui ogni riga è $\pi$ — una matrice di rango 1.

Questa è una relazione provabile, un teorema nel senso pieno: la dimostrazione, per le catene finite, è una conseguenza del teorema di Perron-Frobenius sugli autovalori delle matrici a entrate non negative. Vale la pena vedere a cosa servono le due ipotesi, perché lavorano per motivi diversi.

L’irriducibilità garantisce l’unicità. Se la catena avesse due regioni isolate, ciascuna avrebbe la sua distribuzione stazionaria, e il limite $\mu_0 P^n$ dipenderebbe da dove parti — niente dimenticanza. Una sola classe comunicante forza una sola stazionaria.

L’aperiodicità garantisce la convergenza vera. Senza di essa la catena può avere un’unica stazionaria $\pi$ e ciononostante $P^n$ non converge: oscilla per sempre. Caso minimo, due stati con $P = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ : la catena salta avanti e indietro a ogni passo, $P^n$ alterna fra l’identità e $P$ senza mai stabilizzarsi, eppure $\pi = (0.5,\ 0.5)$ è l’unica stazionaria. La periodicità impedisce alla distribuzione di assestarsi, anche quando il bersaglio esiste ed è unico.

Una catena irriducibile e aperiodica si dice ergodica, ed è la classe per cui il teorema dà tutto: esistenza, unicità, convergenza da qualunque punto.

Conviene non dare per scontato perché il teorema sia vero, almeno a livello di intuizione. La dimostrazione passa per il teorema di Perron-Frobenius, ma l’idea si afferra anche senza. Una matrice stocastica $P$ , applicata a un vettore di probabilità, è un’operazione che mescola: ogni componente del risultato è una media pesata delle componenti di partenza. Mediare ripetutamente tende a livellare le differenze — è lo stesso motivo per cui mescolare a lungo due liquidi li uniforma. L’irriducibilità garantisce che il mescolamento raggiunga ogni angolo (nessuna regione resta isolata e quindi non livellata); l’aperiodicità garantisce che il mescolamento non si limiti a far girare la massa in cerchio senza fonderla. Con entrambe, ogni distribuzione iniziale viene mescolata fino a diventare la stessa $\pi$ . Il teorema ergodico è, in fondo, la formalizzazione del fatto che mescolare abbastanza a lungo uniforma — dove “uniforma” significa “porta a $\pi$ ”, non necessariamente alla distribuzione uniforme.

Esiste anche una versione più debole ma più robusta, che vale sotto la sola irriducibilità, senza chiedere aperiodicità: la frazione di tempo che la catena passa nello stato $i$ — non la probabilità a un istante fissato, ma la media su un lungo cammino — converge a $\pi_i$ . È questa la forma che Markov dimostrò nel 1906 per battere Nekrasov: una legge dei grandi numeri per variabili dipendenti. Ne segue anche un’identità elegante: $\pi_i = 1 / (\text{tempo medio di ritorno a } i)$ . Gli stati che la catena rivede spesso sono quelli con tempo di ritorno breve, ed è esattamente la stazionaria a misurarlo.

Questa identità chiarisce una volta per tutte cosa sia la distribuzione stazionaria, al di là della definizione algebrica $\pi P = \pi$ . La componente $\pi_i$ è la frazione di tempo che la catena, lasciata correre per sempre, passa nello stato $i$ . È una media temporale lungo una singola traiettoria — non una media su tante traiettorie. Il teorema ergodico, nella sua versione forte, dice che le due medie coincidono: la frazione di tempo lungo un cammino infinito (orizzontale) eguaglia la probabilità a un istante lontano (verticale). È questa coincidenza fra media temporale e media di ensemble a giustificare il nome “ergodico”, preso in prestito dalla fisica statistica, dove l’ipotesi ergodica afferma esattamente che seguire un sistema a lungo equivale a osservarne tante copie in un istante.

Mixing time e secondo autovalore

Il teorema ergodico dice che la catena converge. Non dice quanto in fretta. La distinzione non è pedante: in pratica è la più importante. Una catena può essere perfettamente ergodica e impiegare un numero astronomico di passi a dimenticare l’inizio, e una catena lenta usata come se fosse veloce produce risultati silenziosamente sbagliati.

Per quantificare serve una misura di distanza fra distribuzioni. Lo standard è la distanza in variazione totale: date due distribuzioni $\mu$ e $\nu$ sugli stessi stati, la loro distanza è metà della somma dei valori assoluti delle differenze, $d_{TV}(\mu, \nu) = \tfrac{1}{2} \sum_i |\mu_i - \nu_i|$ . Vale 0 quando le distribuzioni coincidono, 1 quando sono concentrate su stati disgiunti. Il mixing time $t_{mix}(\varepsilon)$ è allora il numero di passi necessario perché la distanza dalla stazionaria scenda sotto $\varepsilon$ , misurata nel caso peggiore rispetto allo stato di partenza.

Perché la velocità conti davvero, e non sia un dettaglio per teorici, basta un confronto. Una catena con mixing time di dieci passi e una con mixing time di dieci miliardi di passi soddisfano lo stesso teorema ergodico, con le stesse garanzie asintotiche. Ma la prima è uno strumento usabile e la seconda no: nessun calcolo reale gira per dieci miliardi di passi. Il teorema ergodico stabilisce che la destinazione esiste; il mixing time dice se il viaggio è fattibile. In ogni applicazione concreta — MCMC, PageRank, algoritmi randomizzati — è il mixing time, non il teorema, a separare i metodi che funzionano da quelli che restano belli sulla carta.

Cosa governa la velocità? Lo spettro di $P$ , cioè i suoi autovalori. Gli autovalori di una matrice stocastica hanno tutti modulo $\leq 1$ ; il più grande è sempre $\lambda_1 = 1$ , e corrisponde alla stazionaria. Chiamiamo $\lambda_\star$ il secondo autovalore per modulo. Si definiscono:

$\text{spectral gap} = 1 - |\lambda_\star|, \qquad t_{rel} = \frac{1}{1 - |\lambda_\star|} \quad (\text{relaxation time}).$

L’intuizione è questa. La distribuzione iniziale $\mu_0$ , scomposta nella base degli autovettori di $P$ , ha una componente lungo $\pi$ (che resta, perché ha autovalore 1) e componenti lungo gli altri autovettori. A ogni applicazione di $P$ , la componente relativa all’autovalore $\lambda$ viene moltiplicata per $\lambda$ . Le componenti con $|\lambda| < 1$ si contraggono; dopo $n$ passi sono moltiplicate per $\lambda^n$ . La più lenta a sparire è quella relativa a $\lambda_\star$ : l’errore residuo decade come $|\lambda_\star|^n$ . Il secondo autovalore è il tasso di dimenticanza dell’inizio.

Questo si vede in modo netto scrivendo la decomposizione spettrale. Per una catena reversibile con autovalori $1 = \lambda_1 > \lambda_2 \geq \dots \geq \lambda_{|S|}$ e autovettori associati, la probabilità a $n$ passi si scrive come somma:

$(P^n)_{ij} = \pi_j + \sum_{k \geq 2} \lambda_k^n \, c_{ijk},$

dove i coefficienti $c_{ijk}$ dipendono dagli autovettori ma non da $n$ . Il primo termine è la stazionaria, costante; ogni altro termine è moltiplicato per $\lambda_k^n$ e quindi svanisce con $n$ , tanto più in fretta quanto più $|\lambda_k|$ è piccolo. Il termine più lento a sparire è quello con $|\lambda_\star|$ : l’errore residuo $(P^n)_{ij} - \pi_j$ decade, alla lunga, come $|\lambda_\star|^n$ . È la formula che rende rigorosa l’intuizione “il secondo autovalore è il tasso di dimenticanza”.

Per le catene reversibili questo si rende preciso con una stima a sandwich (Levin, Peres, Wilmer):

$(t_{rel} - 1)\,\log\!\frac{1}{2\varepsilon} \ \le\ t_{mix}(\varepsilon)\ \le\ t_{rel}\,\log\!\frac{1}{\varepsilon\,\pi_{min}},$

dove $\pi_{min}$ è la più piccola componente di $\pi$ . In parole: il mixing time è essenzialmente l’inverso dello spectral gap, a meno di un fattore logaritmico. Gap grande significa mixing veloce; gap piccolo significa mixing lento. Il caso patologico è una catena fatta di due cluster di stati ben connessi al loro interno ma collegati fra loro da pochi archi a bassa probabilità — un collo di bottiglia. Una catena del genere ha $|\lambda_\star|$ vicinissimo a 1, gap quasi nullo, e mixing time enorme: la catena resta intrappolata in un cluster per moltissimi passi prima di passare all’altro.

Un caso limite istruttivo: il random walk

Prima di passare al bilancio dettagliato, conviene fermarsi su una catena particolare, perché illumina quasi tutti i concetti visti finora e fa da contrappeso al caso comodo delle catene finite.

Il random walk simmetrico sulla retta degli interi ha come stati i numeri interi $\dots, -2, -1, 0, 1, 2, \dots$ e una regola minimale: da ogni stato $i$ si va in $i+1$ con probabilità $1/2$ e in $i-1$ con probabilità $1/2$ . È la dinamica del caso puro, senza direzione preferita — il modello giocattolo di tutto ciò che vaga senza meta.

Questa catena è irriducibile (da ogni intero si raggiunge ogni altro) e aperiodica solo se si aggiunge una probabilità di restare fermi — così com’è ha periodo 2, perché torna in $0$ solo a passi pari. Ma il punto interessante è un altro: il random walk simmetrico non ha distribuzione stazionaria. Non esiste un vettore di probabilità $\pi$ con $\pi P = \pi$ che sommi a 1, perché l’unica soluzione di $\pi P = \pi$ è la distribuzione uniforme su infiniti stati, e quella non si può normalizzare. La catena vaga, e la sua “distribuzione” si allarga indefinitamente senza assestarsi.

C’è di più, ed è il fatto controintuitivo che separa le catene finite da quelle infinite. Il random walk simmetrico in una dimensione è ricorrente: parte da $0$ e ci torna con probabilità $1$ , prima o poi. Ma è ricorrente nullo: il tempo medio per tornare a $0$ è infinito. Torna di sicuro, ma in media impiega un tempo illimitato. In due dimensioni vale ancora la ricorrenza; in tre dimensioni e oltre il random walk diventa transiente — con probabilità positiva non torna mai più all’origine, vaga via per sempre. È il celebre risultato riassunto nella battuta di Kakutani: “un ubriaco prima o poi ritrova la strada di casa, un uccello ubriaco potrebbe perdersi per sempre”. Tutto questo non esiste sulle catene finite, dove ogni stato è ricorrente positivo: è il prezzo dell’infinito, e va tenuto a mente ogni volta che si modella uno spazio di stati illimitato.

Tempi di assorbimento e di raggiungimento

C’è una seconda famiglia di domande che si pongono a una catena, oltre a “dove finisce nel lungo periodo”. Sono le domande sul transitorio: quanti passi servono, in media, per raggiungere un certo stato? Con quale probabilità la catena raggiunge $A$ prima di $B$ ? Queste quantità — i tempi di raggiungimento (hitting time) e i tempi di assorbimento — non si leggono dalla stazionaria, ma da un sistema lineare.

L’idea è la condizionamento sul primo passo. Sia $h_i$ il tempo medio per raggiungere un insieme bersaglio partendo da $i$ . Se $i$ è già nel bersaglio, $h_i = 0$ . Altrimenti, la catena fa un passo — costo 1 — e si ritrova in qualche stato $j$ con probabilità $p_{ij}$ , da cui le servirà ancora $h_j$ in media. Quindi

$h_i = 1 + \sum_j p_{ij}\, h_j \qquad (\text{per } i \text{ fuori dal bersaglio}).$

È un sistema lineare in tante incognite quanti gli stati non bersaglio, e si risolve come qualunque sistema lineare. Lo stesso schema di condizionamento sul primo passo dà le probabilità di assorbimento — la probabilità di finire in un certo pozzo piuttosto che in un altro — sostituendo " $1 +$ " con un’equazione senza il costo di passo. È lo strumento con cui si analizza il classico problema della rovina del giocatore: un giocatore con un capitale che a ogni mano sale o scende di un’unità, e ci si chiede con quale probabilità si rovini prima di raggiungere un obiettivo. Quel problema è una catena di Markov su una linea di stati con due pozzi assorbenti agli estremi, e la risposta esce da questo sistema lineare. Tenere separate le due famiglie di domande — comportamento asintotico via $\pi P = \pi$ , comportamento transitorio via condizionamento sul primo passo — evita gran parte della confusione su cosa una catena sappia dire.

Bilancio dettagliato e reversibilità

C’è un modo speciale, e molto utile, in cui una catena può essere in equilibrio. Una catena soddisfa il bilancio dettagliato (detailed balance) rispetto a una distribuzione $\pi$ se per ogni coppia di stati $i, j$ vale

$\pi_i\, p_{ij} = \pi_j\, p_{ji}.$

In parole: a regime, il flusso di probabilità che va da $i$ a $j$ eguaglia esattamente il flusso che va da $j$ a $i$ — non globalmente, ma coppia per coppia. È una condizione di equilibrio locale, e va distinta dalla stazionarietà, che è un equilibrio globale: $\pi P = \pi$ chiede solo che il flusso totale entrante in ogni stato eguagli quello uscente, lasciando libero come i singoli flussi si bilancino fra loro.

Il bilancio dettagliato è più forte: implica la stazionarietà. La dimostrazione è una riga — somma l’equazione su $i$ :

$\sum_i \pi_i\, p_{ij} = \sum_i \pi_j\, p_{ji} = \pi_j \sum_i p_{ji} = \pi_j,$

dove l’ultimo passaggio usa che le righe di $P$ sommano a 1. Il membro sinistro è la componente $j$ -esima di $\pi P$ , il destro è $\pi_j$ : quindi $\pi P = \pi$ . Il viceversa non vale. Esistono catene con una stazionaria che non soddisfano il bilancio dettagliato — il caso tipico è un ciclo a senso unico, dove la probabilità gira sempre nello stesso verso e i flussi fra coppie sono palesemente sbilanciati.

Il bilancio dettagliato ha anche un vantaggio operativo di pura verifica: controllare la stazionarietà via $\pi P = \pi$ richiede di moltiplicare un vettore per una matrice, mentre controllare il bilancio dettagliato richiede solo di confrontare coppie di numeri, $\pi_i p_{ij}$ contro $\pi_j p_{ji}$ , una coppia alla volta. Quando si sospetta che una certa $\pi$ sia stazionaria per una catena reversibile, verificare il bilancio dettagliato è la via più rapida — e se passa, la stazionarietà è garantita gratis.

Una catena che soddisfa il bilancio dettagliato rispetto a $\pi$ si dice reversibile: filmata all’indietro a partire dalla stazionaria, ha la stessa legge del processo in avanti — non si distingue il film proiettato dritto da quello proiettato a rovescio. La reversibilità è preziosa per due ragioni. La prima è tecnica: una catena reversibile ha una matrice $P$ simmetrizzabile, dunque diagonalizzabile con autovalori tutti reali, il che rende rigorosa la stima a sandwich del mixing time vista sopra. La seconda è costruttiva, ed è il cuore della prossima sezione: il bilancio dettagliato è la leva con cui si progetta una catena con una stazionaria voluta.

Un modo intuitivo di vedere la differenza fra equilibrio globale e locale è pensare al flusso di un fluido fra serbatoi. La stazionarietà chiede che il livello di ogni serbatoio resti costante: ciò che entra eguaglia ciò che esce, in totale. Il bilancio dettagliato chiede di più — che ogni singolo tubo fra due serbatoi porti la stessa portata nei due versi. Si può avere il livello costante con il fluido che gira in cerchio fra tre serbatoi (globale soddisfatto, locale no): è la catena ciclica, stazionaria ma non reversibile. Il bilancio dettagliato esclude ogni circolazione netta, ed è questa assenza di “correnti” a far sì che il film all’indietro sia indistinguibile da quello in avanti.

Esempi

Esempio 1 — numerico: il meteo a due stati

Due stati, Sole ( $S$ ) e Pioggia ( $R$ ). La matrice di transizione:

$P = \begin{pmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{pmatrix}$

Da Sole si resta Sole con probabilità 0.8; da Pioggia si resta Pioggia con 0.6. La catena è irriducibile (da ognuno si raggiunge l’altro) e aperiodica (gli auto-anelli garantiscono il periodo 1): il teorema ergodico si applica.

Per la stazionaria $\pi = (\pi_S, \pi_R)$ si impone $\pi P = \pi$ . La prima componente dà $\pi_S = 0.8\,\pi_S + 0.4\,\pi_R$ , e insieme al vincolo $\pi_S + \pi_R = 1$ si ricava

$\pi_S = \tfrac{2}{3} \approx 0.667, \qquad \pi_R = \tfrac{1}{3} \approx 0.333.$

Ora la dimenticanza, vista coi numeri. Parti certo che oggi c’è il Sole, $\mu_0 = (1,\ 0)$ . Passo dopo passo: $\mu_1 = (0.8,\ 0.2)$ , $\mu_2 = (0.72,\ 0.28)$ , $\mu_3 = (0.688,\ 0.312)$ , e la successione tende a $(0.667,\ 0.333)$ . Parti invece certo che piove, $\mu_0 = (0,\ 1)$ : ottieni $\mu_1 = (0.4,\ 0.6)$ , $\mu_2 = (0.56,\ 0.44)$ , e di nuovo la successione tende a $(0.667,\ 0.333)$ . Le due traiettorie, partite da estremi opposti, convergono allo stesso punto: la catena dimentica il meteo iniziale. Gli autovalori di $P$ sono $1$ e $0.4$ , quindi $\lambda_\star = 0.4$ : l’errore residuo si contrae di un fattore $0.4$ a ogni passo — mixing rapido, bastano una manciata di passi.

Vale la pena verificare anche il bilancio dettagliato su questo esempio, perché è la catena reversibile più piccola che si possa scrivere. La condizione $\pi_S\, p_{SR} = \pi_R\, p_{RS}$ diventa $\tfrac{2}{3} \cdot 0.2 = \tfrac{1}{3} \cdot 0.4$ , cioè $0.1333\ldots = 0.1333\ldots$ : vera. La catena del meteo è reversibile — il che, per una catena a due stati, è sempre il caso, perché con due soli stati c’è un’unica coppia e l’unica equazione di flusso coincide con quella di stazionarietà. Le catene non reversibili compaiono solo da tre stati in su, dove diventa possibile far circolare la probabilità in un verso preferito.

Esempio 2 — in codice: tre strade per la stessa stazionaria

Lo stesso meteo, calcolato in tre modi indipendenti che il teorema ergodico promette diano lo stesso risultato.

import numpy as np

P = np.array([[0.8, 0.2],
              [0.4, 0.6]])

# (a) potenze della matrice: P^n tende a una matrice con righe = pi
Pn = np.linalg.matrix_power(P, 50)
print(Pn)            # entrambe le righe ~ [0.667, 0.333]

# (b) simulazione: la frazione di tempo conferma il teorema ergodico
stato, conteggi = 0, np.zeros(2)
for _ in range(100_000):
    conteggi[stato] += 1
    stato = np.random.choice(2, p=P[stato])
print(conteggi / conteggi.sum())   # ~ [0.667, 0.333]

# (c) autovettore sinistro di P relativo all'autovalore 1
vals, vecs = np.linalg.eig(P.T)
pi = vecs[:, np.argmin(np.abs(vals - 1))].real
print(pi / pi.sum())               # [0.667, 0.333]

La strada (a) eleva la matrice a potenza e legge la matrice limite di rango 1. La (b) non calcola nulla in forma chiusa: simula un singolo lungo cammino e misura la frazione di tempo passata in ciascuno stato — è la versione “media temporale” del teorema. La (c) risolve direttamente il problema agli autovalori. Tre angoli — algebra delle potenze, simulazione, spettro — convergono allo stesso $\pi$ . È il contenuto operativo del teorema ergodico messo alla prova.

Esempio 3 — classificazione: tre catene a confronto

Vale la pena vedere la classificazione degli stati su esempi minimi, perché i nomi astratti diventano concreti solo davanti a un disegno.

Prima catena, tre stati $A, B, C$ con $A \to B \to C \to A$ ciascuno con probabilità 1: un ciclo deterministico. È irriducibile (da ognuno si raggiunge ognuno), tutti gli stati sono ricorrenti positivi, ma è periodica di periodo 3 — si torna in $A$ solo dopo 3, 6, 9… passi. Ha un’unica stazionaria, $\pi = (1/3,\ 1/3,\ 1/3)$ , ma $\mu_0 P^n$ non converge: la massa di probabilità gira in tondo per sempre. È il contro-esempio che mostra perché serve l’aperiodicità.

Seconda catena, tre stati con $A \to B$ , $B \to A$ o $B \to C$ , e $C \to C$ con probabilità 1: $C$ è un pozzo assorbente. Questa catena non è irriducibile: ci sono due classi comunicanti, $\{A, B\}$ e $\{C\}$ , e da $\{A, B\}$ si esce verso $C$ ma non si rientra. Gli stati $A$ e $B$ sono transienti — prima o poi la catena cade in $C$ e non li rivede —, $C$ è ricorrente. L’unica stazionaria è concentrata su $C$ : $\pi = (0, 0, 1)$ . La dimenticanza qui è totale e banale, la catena finisce sempre nello stesso buco.

Terza catena, il meteo dell’Esempio 1: irriducibile e aperiodica, dunque ergodica. È l’unica delle tre per cui il teorema ergodico dà tutto — esistenza, unicità, convergenza da qualunque punto. Le tre catene, messe in fila, sono la tassonomia in miniatura: il ciclo ha unicità ma non convergenza, il pozzo ha convergenza ma una stazionaria degenere, il meteo ha entrambe in forma piena.

Esempio 4 — scenario reale: PageRank come catena di Markov

PageRank, l’algoritmo con cui Google ordinava le pagine alle origini, è il calcolo di una distribuzione stazionaria. Il web è un grafo: le pagine sono i nodi, i link gli archi. Si immagina un navigatore casuale (random surfer) che parte da una pagina e, a ogni passo, clicca un link a caso scelto uniformemente fra quelli uscenti dalla pagina corrente. Questa è una catena di Markov sullo spazio delle pagine. Il PageRank di una pagina è definito come la sua probabilità stazionaria $\pi$ : la frazione di tempo che il navigatore, lasciato libero per sempre, passerebbe su quella pagina.

C’è un problema: il web non è una catena ergodica. Esistono pagine senza link uscenti — i dangling nodes, da cui il surfer non saprebbe dove andare — e cluster di pagine isolati dal resto. La catena non è né irriducibile né (sempre) aperiodica, e il teorema ergodico non si applica. Sergey Brin e Larry Page, nel paper del 1998 che descrive il prototipo di Google, lo risolvono con il damping factor $d = 0.85$ : a ogni passo, con probabilità $0.85$ il navigatore clicca un link, con probabilità $0.15$ “si annoia” e salta a una pagina qualsiasi del web scelta a caso uniformemente. La matrice diventa

$G = d\, M + (1 - d)\,\tfrac{1}{N}\, J,$

dove $M$ è la matrice dei link, $N$ il numero di pagine e $J$ la matrice di tutti 1. Il termine di salto rende $G$ irriducibile e aperiodica per costruzione — da ogni pagina si può saltare a ogni altra —, quindi il teorema ergodico garantisce un’unica stazionaria, e quella stazionaria è il ranking. PageRank è, alla lettera, il calcolo della distribuzione stazionaria di una catena di Markov resa ergodica a forza con un termine di teletrasporto.

C’è un dettaglio che lega PageRank al mixing time e spiega perché l’algoritmo era praticabile su un web di miliardi di pagine. La stazionaria di $G$ non si calcola risolvendo il sistema $\pi G = \pi$ — sarebbe un sistema con miliardi di incognite. Si calcola con la power iteration: si parte da una distribuzione qualsiasi e la si moltiplica ripetutamente per $G$ , esattamente il $\mu_0 G^n$ del teorema ergodico. La convergenza è governata dal secondo autovalore di $G$ , e si dimostra che per la matrice di Google quel secondo autovalore è limitato dal damping factor: $|\lambda_\star| \leq d = 0.85$ . Lo spectral gap è almeno $0.15$ , il mixing time è dunque piccolo — bastano alcune decine di iterazioni perché il ranking si stabilizzi. Il valore $0.85$ non è solo una stima del comportamento dei navigatori reali: è anche la leva che garantisce che l’algoritmo converga in fretta. Abbassare $d$ accelererebbe il calcolo ma distorcerebbe il ranking; alzarlo lo renderebbe più fedele ma più lento. È un compromesso fra fedeltà del modello e mixing time, e $0.85$ è il punto scelto.

Esempio 5 — linguaggio: i modelli n-gram

Prima dei transformer, il modo standard di modellare il linguaggio statisticamente era il modello n-gram, ed è una catena di Markov. Un modello bigramma assume che la probabilità della parola successiva dipenda solo dalla parola corrente: è una catena di Markov sullo spazio del vocabolario, con la matrice di transizione stimata contando, in un grande corpus, quante volte ogni parola segue ogni altra. Un modello trigramma usa come “stato” la coppia delle due parole precedenti — ed è ancora una catena di Markov, su uno spazio di stati più grande, esattamente il trucco di allargare lo stato visto nel primo angolo di intuizione.

Claude Shannon, nel saggio fondativo A Mathematical Theory of Communication (1948), genera testo inglese campionando da catene di Markov stimate sulle frequenze di lettere e di parole, mostrando che un modello markoviano cattura una quantità sorprendente di struttura statistica del linguaggio. È la continuazione diretta di quello che Markov aveva fatto a mano su Eugenio Onegin nel 1913.

L’esperimento di Shannon è istruttivo proprio nei suoi limiti. Una catena di ordine basso — il prossimo carattere dipende da pochi precedenti — produce testo che sembra inglese da vicino: le combinazioni di lettere sono plausibili, le parole brevi spesso esistono. Ma allargando lo sguardo il testo non significa nulla: non ci sono frasi, non c’è coerenza oltre la manciata di simboli che lo stato ricorda. Alzare l’ordine della catena migliora la coerenza locale ma fa esplodere lo spazio degli stati, e con esso il numero di parametri da stimare. È il compromesso strutturale di ogni modello markoviano del linguaggio: la coerenza che si riesce a catturare è grande quanto lo stato, e lo stato non può crescere all’infinito. Vedere questo limite chiaramente è il modo migliore per capire cosa abbiano aggiunto i transformer.

Vale la pena marcare con precisione la classe del legame con i modelli di oggi. Gli n-gram discendono dall’analisi di Markov: filiazione storica documentata, Shannon cita esplicitamente le catene di Markov. I transformer, invece, non sono catene di Markov sul testo, e qui non c’è filiazione ma una rottura. L’attention legge l’intera sequenza in contesto: la probabilità del prossimo token dipende da tutti i token precedenti nella finestra, non da uno stato di dimensione fissa. Si potrebbe obiettare che basta definire lo “stato” come l’intera sequenza vista finora per recuperare la proprietà di Markov — ma quello stato cresce a ogni token, quindi non è una catena di Markov a spazio di stati fisso nel senso classico, ed è la finitezza dello stato a dare alle catene le loro proprietà. La proprietà di Markov vale banalmente solo se lo stato è “tutto il passato”, il che svuota la condizione di ogni contenuto. La differenza fra un n-gram e un transformer è esattamente la differenza fra una memoria riassunta in uno stato compatto e una memoria che attende all’intero contesto.

C’è una sfumatura che vale la pena non perdere. Generare testo con un transformer, token dopo token, sembra un processo markoviano: a ogni passo il modello produce una distribuzione sul prossimo token e ne campiona uno. Ma lo “stato” rispetto a cui quella distribuzione è calcolata è l’intera sequenza generata finora — un oggetto che si allunga a ogni token. Non c’è una matrice di transizione fissa, non c’è uno spazio di stati di dimensione costante, e quindi non c’è nulla che possa avere una distribuzione stazionaria nel senso del teorema ergodico. La generazione autoregressiva di un transformer è un processo, ma non è una catena di Markov a stati finiti; è proprio l’assenza di un riassunto compatto del passato — il fatto che il modello rilegga ogni volta tutto il contesto — la caratteristica architetturale che lo distingue dai suoi antenati n-gram. È un buon esempio di affermazione da maneggiare con cura: la somiglianza superficiale (campiono il prossimo simbolo) è un’analogia, non un’equivalenza.

Applicazioni pratiche

MCMC: costruire una catena la cui stazionaria è il bersaglio

L’applicazione più importante delle catene di Markov nella statistica e nel machine learning è il Markov chain Monte Carlo (MCMC), e l’idea è una delle più eleganti del campo.

Il problema. Spesso si deve campionare da una distribuzione $\pi$ che si conosce solo a meno di una costante di normalizzazione. È la situazione tipica dell’inferenza bayesiana: il posterior — la distribuzione del parametro dati i dati, trattata nei capitoli MAP, prior, posterior e Maximum likelihood — è proporzionale al prodotto di verosimiglianza e prior, ma la costante che lo rende una vera distribuzione richiede un integrale su tutto lo spazio dei parametri, di norma intrattabile. Conosci la forma di $\pi$ , non la sua normalizzazione, e campionarne direttamente è impossibile.

L’idea dell’MCMC ribalta il problema. Invece di campionare $\pi$ a mano, si costruisce una catena di Markov ergodica la cui distribuzione stazionaria È esattamente $\pi$ . Poi la si fa girare. Dopo un numero di passi superiore al mixing time — la fase di burn-in, che si scarta — gli stati che la catena visita sono campioni da $\pi$ . Correlati fra loro, perché passi vicini di una catena sono vicini anche come stati, ma campioni da $\pi$ . Il teorema ergodico è la garanzia che funzioni: la catena dimentica il punto di partenza arbitrario e finisce per esplorare $\pi$ .

Il metodo classico per costruire quella catena è Metropolis-Hastings, introdotto da Nicholas Metropolis e collaboratori nel 1953 e generalizzato dallo statistico canadese W. Keith Hastings nel 1970. Da uno stato $x$ , si propone un candidato $x'$ estraendolo da una distribuzione di proposta $q(x' \mid x)$ — per esempio una piccola perturbazione gaussiana di $x$ . Poi si accetta il candidato con probabilità

$A(x \to x') = \min\!\left(1,\ \frac{\pi(x')\, q(x \mid x')}{\pi(x)\, q(x' \mid x)}\right).$

Se il candidato è rifiutato, la catena resta in $x$ e si riprova. Due cose rendono questa regola notevole. La prima: nel rapporto $\pi(x')/\pi(x)$ la costante di normalizzazione di $\pi$ — quella intrattabile — si cancella. Basta conoscere $\pi$ a meno di costante, che è esattamente ciò che si ha. La seconda: la regola di accettazione è progettata di proposito perché la catena risultante soddisfi il bilancio dettagliato rispetto a $\pi$ . È il bilancio dettagliato usato come strumento di ingegneria. Si parte dalla stazionaria voluta — $\pi$ , il posterior — e si costruisce la catena all’indietro, scegliendo le transizioni in modo che $\pi_i\, p_{ij} = \pi_j\, p_{ji}$ . Per la proprietà vista nella meccanica, il bilancio dettagliato garantisce che $\pi$ sia stazionaria; l’ergodicità garantisce che la catena ci converga. La catena è costruita su misura del bersaglio.

Per rendere concreta la cancellazione della costante, ecco un Metropolis-Hastings minimo che campiona una distribuzione $\pi$ definita solo a meno di normalizzazione — qui una gaussiana non normalizzata, ma il codice non userebbe la costante anche se ci fosse:

import numpy as np

# pi noto solo a meno di costante: forma di una gaussiana
def pi_non_normalizzata(x):
    return np.exp(-0.5 * x**2)        # manca il fattore 1/sqrt(2 pi)

x, campioni = 0.0, []
for _ in range(100_000):
    x_prop = x + np.random.normal(0, 1)          # proposta simmetrica
    rapporto = pi_non_normalizzata(x_prop) / pi_non_normalizzata(x)
    if np.random.rand() < min(1.0, rapporto):     # regola di accettazione
        x = x_prop                                 # accetta
    campioni.append(x)                             # (altrimenti resta in x)

# dopo il burn-in, i campioni hanno media ~0 e deviazione ~1
print(np.mean(campioni[1000:]), np.std(campioni[1000:]))

La proposta qui è simmetrica — $q(x' \mid x) = q(x \mid x')$ — quindi i termini $q$ si elidono e resta il solo rapporto $\pi(x')/\pi(x)$ , in cui la costante mancante si cancella comunque. La catena costruita ha la gaussiana come stazionaria per costruzione, perché la regola di accettazione le impone il bilancio dettagliato; il codice non ha mai avuto bisogno di sapere quanto valesse la normalizzazione.

Il Gibbs sampling, introdotto da Stuart e Donald Geman nel 1984, è un caso speciale per distribuzioni multivariate: aggiorna una componente alla volta, campionandola dalla sua condizionale completa date tutte le altre. Si dimostra che è un Metropolis-Hastings in cui la probabilità di accettazione è sempre 1 — la proposta è già la condizionale esatta, quindi non c’è mai nulla da rifiutare. È la scelta naturale quando le condizionali sono facili da campionare anche se la congiunta non lo è.

L’intuizione del Gibbs sampling è geometrica e vale la pena vederla. Per campionare un punto in uno spazio a molte dimensioni — il vettore di tutti i parametri — il Gibbs non si muove in diagonale: si muove un asse alla volta. Fissa tutte le coordinate tranne una, e ricampiona quella dalla sua distribuzione condizionata; poi passa alla coordinata successiva. Dopo aver percorso tutti gli assi, ha completato un passo della catena. È come esplorare una stanza muovendosi solo lungo le pareti, mai in diagonale: più passi servono, ma ogni passo è un’estrazione esatta e semplice. Il prezzo, e il punto debole, è che quando le coordinate sono fortemente correlate — la “stanza” è uno stretto corridoio diagonale — muoversi solo lungo gli assi è lentissimo, e il mixing crolla. È un’altra istanza dello stesso tema: la catena converge, ma la velocità dipende dalla geometria del problema.

Sulla pratica vale un’ultima parola. La fase di burn-in — i primi passi della catena, scartati perché ancora contaminati dallo stato iniziale arbitrario — non ha una durata calcolabile a priori in modo esatto: dipende dal mixing time, che spesso non si conosce. In pratica la si stima guardando le tracce della catena (i valori dei parametri passo per passo): quando le tracce smettono di “andare verso” qualcosa e iniziano a oscillare attorno a un livello stabile, il burn-in è probabilmente finito. È una diagnosi visiva e fallibile, e questo è esattamente il punto: l’MCMC è teoricamente garantito ma operativamente delicato, e la garanzia del teorema ergodico non solleva da una verifica empirica della convergenza.

C’è un avvertimento operativo, e collega l’MCMC al mixing time. L’efficienza del metodo dipende interamente da quanto in fretta la catena costruita mescola. Se la catena ha uno spectral gap piccolo — un collo di bottiglia nello spazio dei parametri — i campioni sono fortemente correlati, la catena resta intrappolata in una regione, e le stime risultano rumorose o, peggio, sistematicamente sbagliate. Diagnosticare il mixing — guardare l’autocorrelazione dei campioni, far girare più catene da punti diversi e confrontarle con la statistica $\hat{R}$ di Gelman-Rubin — non è un optional: è parte essenziale di un MCMC fatto bene.

Vale la pena ribadire l’inversione concettuale che rende l’MCMC elegante, perché è il punto in cui la teoria di questo capitolo diventa tecnologia. Tutto il capitolo, fino alle applicazioni, è stato “data una catena, qual è la sua stazionaria?”. L’MCMC pone la domanda al contrario: “data la stazionaria che voglio, quale catena la produce?”. Il teorema ergodico, letto da sinistra a destra, è un risultato di analisi — descrive cosa fa una catena. Letto da destra a sinistra, diventa un principio di progettazione — se costruisci una catena ergodica con la stazionaria giusta, hai un campionatore. Il bilancio dettagliato è lo strumento che rende la costruzione meccanica: invece di inventare $P$ e sperare, si impone $\pi_i p_{ij} = \pi_j p_{ji}$ e si lascia che l’equazione detti le transizioni. È uno dei casi più limpidi, nella matematica applicata, in cui un teorema descrittivo viene rovesciato in una ricetta costruttiva.

Altre applicazioni

Le catene di Markov compaiono in molti altri punti dei sistemi AI e del software. I modelli n-gram sono stati la base del riconoscimento vocale e della traduzione automatica statistica fino a metà anni 2010. Gli Hidden Markov Models — catene di Markov il cui stato non è osservato direttamente, trattati nel capitolo hmm (in preparazione) — reggono il part-of-speech tagging, lo speech recognition pre-deep-learning e l’allineamento di sequenze in bioinformatica; gli algoritmi di Viterbi e forward-backward operano proprio su di esse. Il forward process di un modello di diffusione — la famiglia dietro Stable Diffusion e simili — è una catena di Markov che aggiunge rumore gaussiano a un’immagine passo dopo passo, e il modello impara a invertirla. Nella teoria delle code e dell’affidabilità, le catene modellano code di richieste e cicli di guasto/riparazione di componenti. E in informatica teorica, gli algoritmi randomizzati per il conteggio approssimato e per il campionamento quasi-uniforme di strutture combinatorie — il lavoro di Sinclair e Jerrum, la stima del volume di corpi convessi — funzionano costruendo catene che mescolano rapidamente.

Una nota sulla diffusione, perché chiude il cerchio con il capitolo precedente. Il forward process di un modello di diffusione costruisce una catena di Markov che a ogni passo aggiunge una piccola dose di rumore gaussiano a un’immagine; dopo abbastanza passi, l’immagine è indistinguibile da rumore puro — la catena ha raggiunto la sua “stazionaria”, una gaussiana. Il modello generativo impara a percorrere quella catena al contrario, da rumore a immagine. È un caso in cui la convergenza alla stazionaria non è il risultato che interessa ma il punto di partenza della generazione: si sfrutta il fatto che la catena dimentica l’immagine originale per avere una sorgente di rumore pulita da cui far partire il processo inverso.

Un punto che lega tutte queste applicazioni: in ognuna, la difficoltà reale non è l’esistenza della stazionaria — il teorema ergodico la regala quasi sempre — ma il mixing time. Per l’MCMC è il numero di campioni da scartare e la correlazione di quelli tenuti; per PageRank è il numero di iterazioni del power method; per gli algoritmi randomizzati è direttamente il tempo di calcolo. La teoria del mixing, sviluppata dagli anni 1980 in poi, è nata proprio perché sapere che una catena converge non basta a chi deve far girare il calcolo su un computer in tempo finito. Il messaggio operativo del capitolo è questo: l’esistenza è facile, la velocità è il problema vero, e la velocità si legge nello spettro.

Dove si rompe

Le catene di Markov sono uno strumento potente, ma i modi in cui falliscono — o vengono fraintese — sono altrettanto istruttivi quanto i modi in cui funzionano.

L’assenza di memoria non è gratis. La proprietà di Markov è un’assunzione di modellazione, e per molti fenomeni reali è sbagliata. Il prossimo stato di un sistema dipende spesso da una storia lunga, non solo dall’ultimo passo. Il rimedio — allargare lo stato per inglobare la storia rilevante — funziona, ma ha un costo che esplode. Per un modello di linguaggio, passare dal bigramma al trigramma al 4-gram fa crescere lo spazio degli stati come una potenza della dimensione del vocabolario: il numero di stati diventa rapidamente troppo grande perché le frequenze si possano stimare in modo affidabile, e la maggior parte delle n-uple non compare mai nel corpus. È esattamente questo muro — la curse of dimensionality applicata allo stato markoviano — ad aver limitato gli n-gram e ad aver lasciato spazio a modelli che non riassumono il passato in uno stato finito.

Convergenza non vuol dire convergenza rapida. Il fraintendimento più costoso. Il teorema ergodico è un risultato asintotico: dice che $\mu_0 P^n \to \pi$ , ma non dice niente su quanto valga $n$ . Una catena può essere irriducibile, aperiodica, perfettamente ergodica, e avere un mixing time di miliardi di passi. In MCMC questa è la fonte principale di risultati sbagliati che sembrano giusti: la catena è teoricamente corretta, ha la stazionaria voluta, ma in un numero realistico di passi non ha mescolato — è rimasta intrappolata in una regione dello spazio, e i “campioni” raccolti non rappresentano $\pi$ ma solo quella regione. Senza diagnostica di convergenza, l’errore è invisibile.

I colli di bottiglia sono ovunque. Le catene con mixing lento non sono una curiosità da manuale. Ogni volta che lo spazio degli stati ha una struttura a cluster — regioni di alta probabilità separate da valli di bassa probabilità — la catena fatica a passare da un cluster all’altro, lo spectral gap si schiaccia e il mixing time esplode. In un posterior multimodale, un MCMC ingenuo può restare per sempre intorno a una sola moda e non scoprire mai le altre. Le tecniche per aggirare il problema — parallel tempering, catene non reversibili progettate apposta per mescolare più in fretta, metodi a gradiente come Hamiltonian Monte Carlo — esistono proprio perché il collo di bottiglia è il nemico ricorrente.

Reversibile non è sempre desiderabile. Si tende a pensare alla reversibilità come a una proprietà “buona”, ed è comoda per l’analisi. Ma una catena reversibile, per costruzione, non ha una direzione preferita: esplora avanzando e tornando indietro in egual misura, come un random walk. Catene non reversibili, che violano di proposito il bilancio dettagliato introducendo una deriva, possono mescolare quadraticamente più in fretta. La ricerca recente sull’MCMC sfrutta proprio la non reversibilità: la proprietà comoda da dimostrare non è la proprietà ottimale da usare.

Lo stato sbagliato rende la catena inutile. L’intera macchina poggia sulla scelta dello spazio degli stati. Se lo stato non cattura l’informazione che conta davvero per il futuro, la catena è markoviana per definizione ma inutile come modello: predice male perché ha buttato via ciò che serviva. La proprietà di Markov non è una verità sul mondo; è un contratto che si firma scegliendo cosa mettere nello stato, e un contratto firmato male non si vede dalla matematica — si vede solo dalle previsioni che sbagliano.

La correlazione fra campioni inganna sulla quantità di informazione. In MCMC i campioni vengono da una catena, dunque sono correlati: due stati consecutivi sono vicini. Diecimila campioni MCMC non valgono diecimila campioni indipendenti — valgono molti meno, quanti ne “vale” la catena dopo aver scontato l’autocorrelazione (il sample size effettivo). Chi tratta i campioni MCMC come se fossero indipendenti sottostima le barre d’errore e si convince di una precisione che non ha. Quanto sia grave dipende, di nuovo, dal mixing: catena rapida, correlazione breve, sample size effettivo vicino al nominale; catena lenta, il divario può essere di ordini di grandezza.

Spazi di stati infiniti complicano tutto. Quasi tutto ciò che è stato detto qui in forma pulita — esistenza e unicità della stazionaria, convergenza — vale per catene finite. Su spazi di stati infiniti compaiono fenomeni che sulle catene finite non esistono: la ricorrenza nulla (il random walk simmetrico sugli interi torna a casa con probabilità 1 ma con tempo medio di ritorno infinito), catene che non hanno alcuna distribuzione stazionaria, catene transienti che vagano via senza tornare. Le catene a stati continui — come quelle dell’MCMC su parametri reali — richiedono un apparato tecnico ulteriore, e gli enunciati puliti del teorema ergodico vanno riformulati con cura.

La stima della matrice di transizione è un problema statistico. In questo capitolo $P$ è data. In pratica, quasi sempre $P$ va stimata da dati osservati — contando transizioni in un corpus, in un log, in una traiettoria sperimentale. La stima è soggetta a tutto ciò che affligge la statistica: transizioni rare osservate poche volte o mai (e una probabilità stimata a zero rende la catena riducibile per artefatto), rumore di campionamento, dati non stazionari il cui $P$ vero cambia nel tempo. Una catena di Markov “fittata male” eredita i difetti del fit, e nessuna proprietà elegante del teorema ergodico li ripara. Negli n-gram questo è il problema centrale: la stragrande maggioranza delle n-uple possibili non compare nel corpus, e servono tecniche di smoothing per assegnare loro una probabilità non nulla — un cerotto statistico su un modello che il teorema, da solo, dà per scontato.

La proprietà di Markov nasconde le cause. Una catena di Markov ben fittata predice bene il prossimo stato, ma non dice perché si transita da $i$ a $j$ . Le probabilità di transizione sono correlazioni osservate, non meccanismi. Usare una catena per intervenire — cambiare una transizione e prevedere l’effetto — è un salto che la catena non autorizza: confonde la dinamica osservata con la dinamica causale. È la stessa distinzione fra correlazione e causalità che vale ovunque in statistica, e una matrice di transizione, per quanto accurata, resta dal lato della correlazione.

La stazionaria non è la distribuzione uniforme. È un’aspettativa che si insinua facilmente, ma è sbagliata. La stazionaria coincide con l’uniforme solo nel caso speciale di una catena doppiamente stocastica, in cui anche le colonne di $P$ sommano a 1. In generale $\pi$ è disuniforme, e proprio la sua disuniformità è ciò che la rende utile: in PageRank è il ranking — alcune pagine valgono mille volte altre —, nel meteo è $(2/3,\ 1/3)$ . Trattare $\pi$ come “circa uniforme” porta a interpretazioni sbagliate ovunque la stazionaria sia il risultato che interessa.

Periodicità nascosta da una discretizzazione. Una catena può sembrare aperiodica e non esserlo, se la periodicità vive in una struttura che lo spazio degli stati scelto non rende visibile. Catene costruite da grafi bipartiti — stati che si dividono in due gruppi e ogni transizione attraversa il confine — sono periodiche di periodo 2 anche quando il diagramma, disegnato distrattamente, non lo suggerisce. Il sintomo è che $P^n$ non converge ma $P^{2n}$ sì. Il rimedio standard, quando la periodicità non è voluta, è la lazyfication: si rimpiazza $P$ con $\tfrac{1}{2}(I + P)$ , cioè a ogni passo si lancia una moneta e con probabilità $1/2$ si resta fermi. Gli auto-anelli così introdotti rompono ogni periodo e rendono la catena aperiodica senza cambiarne la stazionaria.

Collegamenti

Processi stocastici e dinamiche casuali — la catena di Markov è il caso a tempo discreto e stato discreto del quadro generale dei processi stocastici; quel capitolo fornisce il vocabolario (traiettoria, distribuzione congiunta, proprietà di Markov in forma generale) su cui questo si appoggia.
Variabili aleatorie, convergenza, disuguaglianze — i mattoni di base: variabile aleatoria, valore atteso, modi di convergenza. Il teorema ergodico è una legge dei grandi numeri per variabili dipendenti.
Autovalori e autovettori a intuizione — la stazionaria è un autovettore con autovalore 1, lo spectral gap è una differenza di autovalori; senza l’intuizione spettrale il mixing time resta opaco.
Legge dei grandi numeri e teorema del limite centrale — Markov estese proprio questa legge alle variabili dipendenti; è il cuore matematico della disputa con Nekrasov.
MAP, prior, posterior, regolarizzazione — l’MCMC esiste per campionare il posterior bayesiano quando la costante di normalizzazione è intrattabile.
Maximum likelihood — il complemento frequentista del precedente; il posterior che l’MCMC campiona è verosimiglianza per prior.
markov-decision-process (Parte VII, in preparazione) — un MDP è una catena di Markov a cui si aggiungono azioni e ricompense; la proprietà di Markov è precisamente il “Markov” in MDP.
hmm (Parte XVIII, in preparazione) — gli Hidden Markov Models sono catene di Markov con stato non osservato; gli algoritmi di Viterbi e forward-backward operano su di esse.
attention-intuizione (Parte XXI, in preparazione) — il contrasto chiave del capitolo: l’attention rende i transformer non markoviani sul testo, a differenza dei modelli n-gram.

Per andare oltre

D. A. Levin, Y. Peres, E. L. Wilmer, Markov Chains and Mixing Times, 2a ed., AMS 2017. Il testo di riferimento moderno su mixing time, spectral gap e stime di convergenza. PDF dell’autore liberamente disponibile.
B. Hayes, “First Links in the Markov Chain”, American Scientist 101(2), 2013. Racconto storico accurato e leggibile della disputa Markov-Nekrasov, dell’angolo sul libero arbitrio e dell’analisi di Eugenio Onegin.
C. E. Shannon, “A Mathematical Theory of Communication”, Bell System Technical Journal, 1948. Il saggio che usa le catene di Markov per modellare e generare testo: l’origine dei modelli n-gram.
R. G. Gallager, Discrete Stochastic Processes, cap. 3, MIT OpenCourseWare 6.262. Trattazione didattica della classificazione degli stati e del teorema ergodico per catene finite, con le dimostrazioni.
S. Brin, L. Page, “The Anatomy of a Large-Scale Hypertextual Web Search Engine”, WWW7, 1998. Il paper originale di Google: PageRank presentato come distribuzione stazionaria del navigatore casuale.
A. Sinclair, M. Jerrum, “Approximate counting, uniform generation and rapidly mixing Markov chains”, Information and Computation, 1989. Il lavoro che collega il mixing rapido di una catena alla possibilità di contare e campionare in modo efficiente — il ponte fra catene di Markov e algoritmi randomizzati.