mercoledì, marzo 12, 2008

Servizio Pubblico - Catene di Markov (I)

Per qualche motivo a me ancora ignoto (o meglio: probabilmente per questo motivo), la maggior parte dei visitatori del blog provenienti da motori di ricerca erano alla ricerca di informazioni su "catene di markov". Per non deludere ulteriormente questi visitatori, ecco un post sulle catene di Markov.

Premetto che Andrey Markov è stato un matematico russo della fine del 1800, membro dell'accademia di San Pietroburgo, allievo di Chebyshev, e con alcuni discendenti abbastanza famosi, come Lebiscovitsch, Sacks e Zygmund. Non entro nei dettagli storici e biografici, che possono essere trovati qui.

Cos'è una catena di Markov? Il caso che considero è quello di una catena a stati finiti.
Supponiamo di avere un oggetto (una particella, una persona, un ente divino) che può trovarsi in diversi stati, che chiameremo k, con k che varia fra 1 e n. Ad esempio, Se l'oggetto in considerazione è una persona, e l'unica informazione che ci interessè la sua età, allora i diversi stati sono numeri naturali, e per andare sul sicuro poniamo n=130.

Quello che vogliamo descrivere è l'evoluzione di questo oggetto: cioè come passa da uno stato all'altro; nelle catene di Markov questi cambiamenti di stato avvengono in step temporali discreti (che chiamiamo t e che è un numero naturale) e in maniera probabilistica. Per tornare al nostro esempio precedente: se fissiamo lo step temporale ad un anno, allora la persona in osservazione passa in ogni step temporale dallo stato k allo stato k+1 con probabilità 1. Se chiamiamo x(t) lo stato del nostro oggetto al tempo t, allora

x(t)=k \quad \Rightarrow \quad x(t+1)=k+1

per ogni t e per ogni k.

Ciò non è veramente probabilitstico (e per altro non si capisce che succede quando x(t)=130 per qualche t, si veda sotto), ma permette di evidenziare un aspetto importante: la probabilità che l'oggetto si trovi in un qualche stato nello step temporale t+1 deve essere 1: gli oggetti non possono essere distrutti in questa descrizione (e anche se lo potessero, si potrebbe correggere il tutto aggiungendo lo stato: oggetto distrutto - questo serve per correggere l'esempio precedente con le età sopra i 130 anni).

Riassumendo: quello che dobbiamo specificare per determinare l'evoluzione temporale di x, è la probabilità P(x(t)=k) che l'oggetto si trovi nello stato k al tempo t.

Introduciamo adesso il concetto fondamentale per una catena di Markov; supponiamo che per k=1, ... , n e t=1,2,... sia definita una famiglia di numeri 0 < P(x(t)=k) < 1 con la proprietà

\left[\sum_{k=1}^n P(x(t)=k)\right] = 1

per ogni t.

Allora la famiglia P(x(t)=k) definisce una catena di Markov omogenea se e solo se esiste una famiglia di vettori f_k=(f_k(1), ... , f_k(n)) tale che

P(x(t+1)=k) = f_k(P(x(t)=h)

Parlando in italiano, questo vuol dire che la probabilità che x si trovi in k al tempo t+1 dipende solamente da dove x si trovava al tempo t, e non dipende ne dal tempo t, ne' dalla storia di x fino al tempo t-1.

[La prossima volta che ho un po' di tempo, cerco di spiegare il rapporto fra catene di Markov e sistemi dinamici discreti, e poi fra questi e i random walks su grafi].

6 commenti:

hronir ha detto...

Ad esser precisi, la trduzione in italiano dell'ultima formula dovrebbe essere:

[...] dipende solamente dalla distribuzione di probabilità di x al tempo t, e non dipende [...]

giusto?

Lap(l)aciano ha detto...

mmhh... lasciami pensare. Io ho scritto il post supponendo di avere una sola particella che si muove fra diversi stati.

Da questo punto di vista del random walk, la probabilità di trovare la particella x nel punto k in t è effettivamente una funzione di x(t-1).

Quello che è nascosto nella mia frase in italiano è che io suppongo di sapere con certezza dove si trovava x in t-1, cioè sto calcolando le proabibilità condizionate di trovare x in k a t+1 sapendo che x si trovava in h a t.

La domanda giusta: è sufficiente conoscere questi numeri per identificare la catena di Markov?

Se vuoi vedere da un punto di vista dell'algebra lineare perchè è sufficiente conoscere gli f_k, osserva che questi ultimi altro non sono che i valori

P(x(t+1)=k | x(t)=h )_{h=1,...,n}

Questi vettori, dal canto loro, altro non solo che i risultati dell'applicazione della matrice di transizione ai vettori della base canonica; e quindi sono sufficienti per determinare la matrice di transizione, che determina univocamente la tua catena di Markov.

Mi pare che il ragionamento fili, giusto?

hronir ha detto...

Sì, sì, il ragionamento fila.
E infatti di solito si definisce la catena di markov più similmente alla tua frase in italiano (in termini, cioè, di probabilità condizionata) e poi si notano le proprietà della matrice di transizione e delle distribuzioni di probabilità...
La mia era solo la solita pendanteria: la frase in italiano non è la "pedisseuqa traduzione" della formula... :)

Ciocionheart ha detto...

Che palle... questo argomento mi interessava e speravao di capirci qualcosa... ma alle ultime righe mi sono perso! Vabbé... te lo chiedere sfruttando la Biomathematics Hotline ;)

ciao ciao

Lap(l)aciano ha detto...

ciao giugiu,

dimmi, dove ti sei perso? evidentemente ho scritto in maniera poco chiara!

a presto
stefano

Ciocionheart ha detto...

Ciao Stefano,

la traduzione in italiano rispecchia piú o meno quel poco che ne sapevo, ma l'ultima formula non l'ho capita. Non ti preoccupare, me la spiegherai un giorno dal vivo, che é piú semplice :)

ciao ciao