Catene di Markov

di Victor Powell

con testo di Lewis Lehe

Le catene di Markov, dal nome di Andrey Markov, sono sistemi matematici che saltano da uno “stato” (una situazione o insieme di valori) ad un altro. Per esempio, se si facesse un modello a catena di Markov del comportamento di un bambino, si potrebbe includere “giocare”, “mangiare”, “dormire” e “piangere” come stati, che insieme ad altri comportamenti potrebbero formare uno “spazio di stato”: una lista di tutti gli stati possibili. Inoltre, sopra lo spazio di stato, una catena di Markov vi dice la probabilità di passare, o “transizione”, da uno stato a qualsiasi altro stato – ad es, la possibilità che un bambino che sta giocando si addormenti nei prossimi cinque minuti senza piangere prima.

Una semplice catena di Markov a due stati è mostrata qui sotto.

velocità

Con due stati (A e B) nel nostro spazio di stato, ci sono 4 possibili transizioni (non 2, perché uno stato può retrocedere in se stesso). Se siamo in ‘A’ potremmo passare a ‘B’ o rimanere in ‘A’. Se siamo in ‘B’ potremmo passare ad ‘A’ o rimanere in ‘B’. In questo diagramma a due stati, la probabilità di transizione da qualsiasi stato a qualsiasi altro stato è 0,5.

Naturalmente, i modellatori reali non sempre disegnano diagrammi a catena di Markov. Invece usano una “matrice di transizione” per contare le probabilità di transizione. Ogni stato nello spazio di stato è incluso una volta come riga e di nuovo come colonna, e ogni cella della matrice vi dice la probabilità di transizione dallo stato della sua riga allo stato della sua colonna. Quindi, nella matrice, le celle fanno lo stesso lavoro che le frecce fanno nel diagramma.

Se lo spazio di stato aggiunge uno stato, aggiungiamo una riga e una colonna, aggiungendo una cella ad ogni colonna e riga esistente. Questo significa che il numero di celle cresce quadraticamente quando aggiungiamo stati alla nostra catena di Markov. Così, una matrice di transizione diventa utile abbastanza rapidamente, a meno che non vogliate disegnare un diagramma della catena di Markov nella giungla.

Un uso delle catene di Markov è quello di includere fenomeni del mondo reale nelle simulazioni al computer. Per esempio, potremmo voler controllare la frequenza con cui una nuova diga strariperà, che dipende dal numero di giorni di pioggia di seguito. Per costruire questo modello, iniziamo con il seguente schema di giorni piovosi (R) e soleggiati (S):

Un modo per simulare questo tempo sarebbe semplicemente dire “La metà dei giorni sono piovosi. Pertanto, ogni giorno della nostra simulazione avrà il cinquanta per cento di possibilità di pioggia”. Questa regola genererebbe la seguente sequenza nella simulazione:

Hai notato come la sequenza di cui sopra non assomiglia molto all’originale? La seconda sequenza sembra saltare, mentre la prima (i dati reali) sembra avere una “appiccicosità”. Nei dati reali, se un giorno c’è il sole (S), allora anche il giorno successivo è molto più probabile che ci sia il sole.

Possiamo minimizzare questa “viscosità” con una catena di Markov a due stati. Quando la catena di Markov è nello stato “R”, ha una probabilità di 0,9 di rimanere ferma e una probabilità di 0,1 di partire per lo stato “S”. Allo stesso modo, lo stato “S” ha 0,9 probabilità di rimanere fermo e 0,1 probabilità di passare allo stato “R”.

Nelle mani di metereologi, ecologisti, informatici, ingegneri finanziari e altre persone che hanno bisogno di modellare grandi fenomeni, le catene di Markov possono diventare piuttosto grandi e potenti. Per esempio, l’algoritmo che Google usa per determinare l’ordine dei risultati di ricerca, chiamato PageRank, è un tipo di catena di Markov.

Sopra, abbiamo incluso un “parco giochi” di catene di Markov, dove potete creare le vostre catene di Markov pasticciando con una matrice di transizione. Qui ce ne sono alcune su cui lavorare come esempio: ex1, ex2, ex3 o generarne una a caso. Il testo della matrice di transizione diventerà rosso se la matrice fornita non è una matrice di transizione valida. Le righe della matrice di transizione devono essere pari a 1. Ci deve essere anche lo stesso numero di righe e di colonne.

Puoi anche accedere ad una versione a schermo intero su setosa.io/markov