Processo markoviano

Un processo stocastico markoviano o processo di Markov è un processo stocastico nel quale la probabilità di transizione che determina il passaggio ad uno stato di sistema dipende unicamente dallo stato di sistema immediatamente precedente (proprietà di Markov) e non dal come si è giunti a tale stato (in quest'ultima ipotesi si parla di processo non markoviano).

Tale processo prende il nome dal matematico russo Andrej Andreevič Markov che per primo ne sviluppò la teoria.

Modelli di tipo markoviano vengono anche utilizzati nel progetto di reti di telecomunicazioni; la teoria delle code che ne consegue trova applicazione in molti ambiti: dalla fila alle poste ai pacchetti in coda in un router.

Formalmente questo può essere scritto come

$P(X(t_{n+1})\leq x_{n+1}|X(t_n)= x_n, X(t_{n-1})= x_{n-1}, \ldots, X(t_0)= x_0) = P(X(t_{n+1})\leq x_{n+1}|X(t_n)=x_n)$

Questa è detta proprietà di Markov, o condizione di "assenza di memoria".

Catene di Markov

Una catena di Markov è un processo di Markov con spazio degli stati discreto, quindi si tratta di un processo stocastico che assume valori in uno spazio discreto e che gode della proprietà di Markov. L'insieme $S$ di spazio degli stati può essere finito o infinito (numerabile). Nel primo caso si parla di catena di Markov a stati finiti. Una catena di Markov può essere tempo-continua o tempo-discreta, in base all'insieme di appartenenza della variabile tempo (continuo o discreto).

Formalmente, una catena di Markov è un processo stocastico Markoviano caratterizzato da un parametro $t_i \in T$, da un insieme $S$ di stati e da una funzione probabilità di transizione $P: S \times S \times T \mapsto [0,1]$.

Essendo un processo Markoviano, $P$ gode come già detto della proprietà:

$P(X(t_{n+1})= x_{n+1}|X(t_n)= x_n, X(t_{n-1})= x_{n-1}, \ldots, X(t_0)= x_0) = P(X(t_{n+1})= x_{n+1}|X(t_n)=x_n)$

Nel caso di catena di Markov a tempo discreto (cioè con l'insieme $T$ discreto), si può assumere la notazione più semplice:

$P(X_{n+1}=x_{n+1}|X_n, X_{n-1}, \ldots, X_0) = P(X_{n+1}=x_{n+1}|X_n). \,$

Catene di Markov omogenee

Una catena di Markov omogenea è un processo markoviano nel quale la probabilità di transizione al tempo $t_i$ non dipende dal tempo stesso, ma soltanto dallo stato del sistema al tempo immediatamente precedente $S(t_{i-1})$. In altre parole, la probabilità di transizione è indipendente dall'origine dell'asse dei tempi e quindi dipende soltanto dalla distanza tra i due istanti temporali.

Per le catene omogenee vale la condizione

$P(X_{n+1}=x|X_n=y) =\ P(X_{n}=x|X_{n-1}=y)$

Più in generale si dimostra che in una catena di Markov omogenea la probabilità di transizione da uno stato a un altro in $n$ passi è costante nel tempo:

$P(X_{i+n}=x|X_i=y) =\ P(X_{i-1+n}=x|X_{i-1}=y) \ \ \ \ \ \forall i =\ 1,2,\ldots$

I sistemi reali che possono essere modellati con catene di Markov omogenee sono rari: è sufficiente pensare al sistema "tempo atmosferico" per capire come la probabilità di transizione da uno stato (per esempio "sole") ad un altro stato (per esempio "pioggia") dipende dalla stagione, quindi non è possibile modellare questo sistema come catena di Markov omogenea. Tuttavia, restringendo l'analisi del sistema ad un determinato intervallo di tempo, il comportamento si può considerare omogeneo: in questo caso, l'intervallo di tempo potrebbe essere una singola stagione.

Rappresentazione

Una catena di Markov omogenea a stati finiti, in cui l'insieme $S$ degli stati del sistema è finito e ha $N$ elementi, può essere rappresentata mediante una matrice di transizione $A \in \mathbb{R}^{N \times N}$ ed un vettore di probabilità iniziale $\tilde{\pi}_0 \in \mathbb{R}^N$.

Gli elementi di $A$ rappresentano le probabilità di transizione tra gli stati della catena: una catena che si trovi nello stato i ha probabilità $a_{ij}$ di passare allo stato j in un passo immediatamente successivo. In particolare gli elementi sulla diagonale principale di $A$, $a_{ii}$ indicano le probabilità di rimanere sullo stesso stato i. Il vettore $\tilde{\pi}_0$ definisce le probabilità che inizialmente la catena di Markov si trovi in ciascuno degli $N$ stati. Una catena di Markov omogenea è univocamente definita dalla coppia $(A,\tilde{\pi}_0)$.

Le probabilità che ad un tempo $t_n$ il sistema si trovi in ognuno degli $N$ stati (se al tempo $t_0$ ha la distribuzione di probabilità $\tilde{\pi}_0$), in questo caso sono date dal vettore $\tilde{\pi}_n$ così definito:

$(\tilde{\pi}_n)^T=(\tilde{\pi}_0)^T\cdot A^n$

dove $(\tilde{\pi}_n)^T$ indica la trasposta del vettore $\tilde{\pi}_n$.

Dalla definizione assiomatica della probabilità discendono le seguenti proprietà per la matrice $A$:

• $a_{ij} \ge 0, \forall i,j \in \{1\ldots N \}$

• $\sum_{j=1}^{N} a_{ij} = 1$.

La seconda proprietà equivale a richiedere che la somma degli elementi su una riga sia uguale a 1.

Per esempio, $A$ e $\tilde{\pi}_0$ possono essere i seguenti:

$A = \begin{pmatrix} 0.3&0.5&0.2\\ 0.1&0.8&0.1\\ 0.5&0.5&0 \end{pmatrix} , \quad \tilde{\pi}_0 = \begin{pmatrix} 0.4\\0.3\\0.3 \end{pmatrix}$

Nel caso di una catena di Markov omogenea a stati discreti si può invece adottare la notazione sintetica:

$P^{(n)}_{ij} \equiv P \left( X_{m+n}=s_j|X_{m}=s_i \right)= P \left( X_{n}=s_j|X_{0}=s_i \right)$

dove (n) non è da intendersi come un esponente bensì come un indice.

Si ha quindi $(\tilde{\pi}_n)_j=\sum_{i \in S} (\tilde{\pi}_0)_i(P^{(n)})_{ij}$.

Si hanno le seguenti proprietà:

• $P_{ij} \ge 0 \ \ \forall i,j \in S$

• $\sum_{j \in S} P_{ij} =1$.

Catene di Markov aperiodiche

Il periodo di uno stato $s_i \in S$ di una catena di Markov a stati discreti (con $S$ finito o infinito numerabile) è definito come il minimo numero di step temporali affinché vi sia una probabilità diversa da zero di tornare sullo stesso stato, partendo dallo stato $s_i$ al tempo $t_m$. Formalmente il periodo $d(s_i)$ è definito come segue:

$d(s_i,t_m)=MCD\{n \ge 1 : P\left(X_{m+n}=s_i|X_m=s_i \right) > 0\}$

dove MCD indica il massimo comune divisore.

Nel caso di una catena di Markov omogenea a stati finiti con un numero $N$ di stati, rappresentabile quindi con una matrice $A \in \mathbb{R}^N$, la definizione si può riformulare così:

$d(s_i)=MCD\{n \ge 1: (A^n)_{ii}>0 \}$.

Lo stato $s_i$ è detto aperiodico se il suo periodo è uguale a 1.

Una catena di Markov è detta aperiodica se tutti i suoi stati sono aperiodici, altrimenti è detta periodica.

Catene di Markov irriducibili

Una catena di Markov a stati discreti è detta irriducibile se partendo da ogni stato $s_i$ c'è una probabilità maggiore di zero di raggiungere ogni altro stato $s_j$. Formalmente, una catena di Markov è irriducibile se:

$\forall s_i,s_j \in S, \forall m \in \mathbb{N}, \exists n \in \mathbb{N} : P\left(X_{m+n}=s_j|X_m=s_i\right)>0$.

Distribuzioni stazionarie

Data una catena di Markov omogenea a stati discreti, una sua distribuzione stazionaria di probabilità (detta anche distribuzione di equilibrio) $\pi=\{\pi_1 \ldots \pi_n \ldots \}$ è una distribuzione discreta di probabilità che soddisfa le seguenti:

• $\forall i \in S, \pi_i \ge 0$

• $\sum_{i \in S} \pi_i = 1$

• $\forall j \in S, \sum_{i \in S} \pi_iP_{ij} = \pi_j$.

Euristicamente, una distribuzione stazionaria è una distribuzione di probabilità che si mantiene costante all'evolversi nel tempo della catena di Markov.

L'importanza delle distribuzioni stazionarie per le catene di Markov omogenee a stati discreti è data dai seguenti teoremi:

• Il teorema di esistenza e unicità afferma che data una catena di Markov omogenea a stati discreti, con probabilità di transizione $P_{ij}$ e spazio degli stati $S$, se la catena di Markov è irriducibile allora esiste un'unica distribuzione stazionaria $\pi$ per la catena di Markov.

• Il teorema della convergenza afferma che data una catena di Markov omogenea a stati discreti, con probabilità di transizione $P_{ij}$ e spazio degli stati $S$, se la catena di Markov è irriducibile ed aperiodica la distribuzione di probabilità $\tilde{\pi}_n$ al tempo $t_n$, converge alla distribuzione stazionaria $\pi$ per ogni distribuzione iniziale di probabilità $\tilde{\pi}_0$ scelta. Si ha cioè

$\forall \tilde{\pi}_0, \forall i,j \in S, \lim_{n \to \infty}\sum_{i \in S}(\tilde{\pi}_0)_i(P^{(n)})_{ij} = \pi_j$.

La convergenza di una catena di Markov a una distribuzione stazionaria, e la possibilità di costruire una catena con una distribuzione stazionaria scelta sono alla base del funzionamento dell'algoritmo di Metropolis-Hastings.

Catene di Markov ergodiche

Per approfondire, vedi Teoria ergodica.

Una catena di Markov si definisce ergodica se e solo se per ogni istante iniziale $t_0$ e per ogni condizione iniziale di probabilità $\tilde{\pi}(t_0)$ esiste ed è indipendente da $t_0$ e da $\tilde{\pi}(t_0)$, il limite della probabilità per tempi infiniti

$P=\lim_{t \to \infty}\tilde{\pi}(t)$.

Applicazioni

Il motore di ricerca Google assegna un valore all'importanza di un sito web tramite l'algoritmo PageRank: quest'ultimo si basa sull'assegnare una probabilità di transizione da un sito web A a un sito B basata sulla quantità di link che da A conducono a B. Conoscendo la probabilità di transizione è possibile ottenere la distribuzione stazionaria di probabilità della catena di Markov formata da tutti i siti web. La distribuzione stazionaria assegna un valore nell'intervallo [0,1] ad ogni sito (corrispondente alla quantità media di tempo spesa sul sito da un gran numero di utenti dopo un tempo tendente a infinito): tale valore, opportunamente riscalato, costituisce il Page Rank del sito.

Bibliografia

• (EN) Olle Häggström (2002), Finite Markov Chains and Algorithmic Applications, Cambridge University press, ISBN 0-521-81357-3

Voci correlate

• Processo stocastico
• Variabile casuale
• Processo di Wiener
• Modello di Markov nascosto
• Algoritmo di Metropolis-Hastings
• N-gramma
• Teoria ergodica

Collegamenti esterni

• Processo markoviano nel Tesauro della BNCF

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica