Informazioni su questo esperimento
Una catena di Markov passa casualmente da uno stato all’altro, ma la probabilità di ogni passaggio dipende solo dallo stato in cui si trova ora, non da come ci è arrivata. Il tempo di domani dipende da quello di oggi, la pagina successiva visitata da un utente dipende da quella attuale e la forma successiva di una molecola dipende dalla sua forma presente. Qualunque sia il punto di partenza, una catena ben comportata dimentica la propria origine e converge a uno stato stazionario π. Modifica le probabilità di transizione, esegui la catena e osserva come convergono a π sia le frequenze a lungo termine sia la distribuzione pₙ.
Obiettivi di apprendimento
- Scrivi la matrice di transizione di una catena di Markov e verifica che la somma di ogni riga sia 1
- Calcola la distribuzione dopo n passaggi come p₀Pⁿ
- Trova la distribuzione stazionaria risolvendo πP = π
- Collega la velocità di convergenza al secondo autovalore più grande di P
- Riconosci le catene che non convergono, come le catene periodiche
Come si usa
- 1Nella catena meteorologica, premi «Esegui» e osserva il token. Poi premi «1000 passi». Quanto sono vicine le barre alle linee tratteggiate?
- 2Cambia lo stato iniziale. Lo stato stazionario cambia? Cambia la parte iniziale del grafico superiore?
- 3Verifica a mano lo stato stazionario: moltiplica π per la matrice e mostra che ottieni di nuovo π.
- 4Scegli «Mescolamento lento». Di quanti passi ha bisogno il grafico superiore per stabilizzarsi? Confronta con |λ₂| e il valore mostrato.
- 5Scegli «Ciclo periodico». Perché il grafico superiore non si stabilizza mai, anche se la proporzione di tempo trascorso in ciascuno stato sì?
- 6Scegli «Dimentica subito». Perché la distribuzione raggiunge π dopo un solo passo?
Il modello
Ipotesi
- Tre stati e probabilità di transizione omogenee nel tempo. Ogni riga si modifica con due cursori; la probabilità di restare nello stesso stato è quella rimanente.
- Il percorso campionato proviene da un generatore casuale con seme, quindi lo stesso numero di esecuzione produce sempre lo stesso percorso; «Nuova esecuzione» cambia il seme.
- Lo stato stazionario si trova risolvendo esattamente le equazioni lineari. Il numero di passi necessario per avvicinarsi entro l’1 % è stimato come ln 100 / (-ln |λ₂|).
Provalo in classe
- Q1Per P = [[0.9, 0.1], [0.5, 0.5]], trova la distribuzione stazionaria.
- Q2Dimostra che la distribuzione uniforme è stazionaria quando anche ogni colonna di P ha somma pari a 1.
- Q3Una catena ha |λ₂| = 0.95. Di quanti passi ha bisogno, all’incirca, per dimenticare il suo stato iniziale?
- Q4Spiega perché la catena a ciclo periodico ha una distribuzione stazionaria, ma pₙ non converge a essa.
- Q5Il PageRank originale di Google è la distribuzione stazionaria di un navigatore casuale. Perché ha aggiunto una piccola probabilità di saltare a qualsiasi pagina?
Domande frequenti
Che cosa significa qui «senza memoria»?
Il futuro dipende dal passato solo attraverso lo stato presente. Se sai che oggi piove, sapere che la settimana scorsa c’era il sole non ti dice nulla di più su domani.
Ogni catena ha uno stato stazionario?
Ogni catena finita ha almeno una distribuzione stazionaria. È unica se ogni stato è raggiungibile da tutti gli altri, e pₙ converge a essa da qualunque stato iniziale se, inoltre, la catena non è periodica.
Dove si usano le catene di Markov?
Nei modelli di code e affidabilità, in genetica, nel riconoscimento vocale, nella previsione del testo e nella finanza, nonché nel metodo Monte Carlo con catene di Markov, che costruisce una catena la cui distribuzione stazionaria è quella da cui si desidera estrarre campioni.