Esempi di processi stocastici Processi PAM Processi gaussiani Processi di Markov

Processi e catene di Markov

Cominciamo col capire cosa sono le catene di Markov. Prendiamo un meteo, in cui si hanno soltanto due stati:

• sole, $S$;
• nuvoloso, $N$.

Se oggi c'è il sole, allora domani ci sarà

• sole con probabilità $\frac{1}{3}$;
• nuvoloso con probabilità $\frac{2}{3}$.

Al contrario, se oggi è nuvoloso, allora domani ci sarà

• sole con probabilità $\frac{1}{2}$;
• nuvoloso con probabilità $\frac{1}{2}$.

Questa è una catena di Markov. Il tempo di domani dipende dal tempo di oggi, e non dal tempo di ieri; inoltre, la probabilità che esce da ogni stato è unitaria, quindi anche la probabilità che in un dato istante si sia in un determinato punto soddisferà anch'essa la proprietà di uniterietà.

Definizione: Processo di Markov

Il processo $\{X(t),t\in T\}$ è un processo di Markov se

$P(X(t_n)|X(t_{n-1}),X(t_{n-2}),\cdots x(t_1))=P(X(t_n)|X(t_{n-1}))\mathrm{\forall }{t}_1<t_2<\cdots <t_n\in T$

In altre parole, possiamo scrivere che una variabile casuale $X(t_n)$ dipende solo dalla variabile casuale $X(t_{n-1})$, mentre è indipendente da tutte le variabili casuali precedenti l'istante $t_{n-1}$.

Implicazioni:

1. la probabilità del futuro, dato passato e presente, dipende solo dal presente.
2. la probabilità del futuro, congiunta a quella del passato e conoscendo il presente, è

$P(\text{futuro}|\text{passato},\text{presente})=P(\text{futuro}|\text{presente})\cdot P(\text{presente}|\text{passato})$

Gli eventi che soddisfano questa seconda condizione sono detti condizionalmente indipendenti, cioè sono indipendenti soltanto se vi è la conoscenza dello stato intermedio. Nel caso in cui non si conosca il presente, allora passato e futuro non sono più indipendenti.

Densità di probabilità del processo di Markov

• $f_{X(t_n)|X(t_{n-1})\cdots X(t_1)}(x_n|x_{n-1},x_{n-2}\cdots x_1)=f_{X(t_n)|X(t_{n-1})}(x_n|x_{n-1})$
• $\{\begin{array}{cc}& f_{X(t_n)X(t_{n-1})\cdots X(t_1)}(x_n,x_{n-1},\cdots ,x_1)=\\ & =f_{X(t_n)|X(t_{n-1}),X(t_{n-2})\cdots X(t_1)}(x_n|x_{n-1},x_{n-2}\cdots x_1)\times \cdots \times f_{X(t_2)|X(t_1)}(x_2|x_1)\times f_{X(t_1)}(x_1)\\ & =f_{X(t_n)|X(t_{n-1})}(x_n|x_{n-1})\times \cdots \times f_{X(t_2)|X(t_1)}(x_2|x_1)\times f_{X(t_1)}(x_1)\\ & =[{\mathrm{\Pi }}_{k=1}^{n-1}{f}_{X(t_{k+1})|X(t_k)}(x_{k+1}|x_k)]\cdot f_{X(t_1)}(x_1)\end{array}$

Per caratterizzare una catena di Markov è sufficiente conoscere la densità di probabilità del second'ordine, non serve scendere fino all'$n$-esimo ordine. In questo modo, la trattazione diventa molto più semplice, fino a renderla quasi banale.

Classificazione

I processi di Markov si possono classificare in base allo stato/tempo continuo/discreto:

• stato continuo e tempo continuo: processo a tempo continuo;
• stato continuo e tempo discreto: processo a tempo discreto;
• stato discreto e tempo continuo: catena a tempo continuo;
• stato discreto e tempo discreto: catena a tempo discreto.

Catene di Markov a tempo discreto

Si ha

• $T=\{0,1,\cdots \}$
• $S=\{1,2,\cdots \}$

che sono due insiemi discreti. La catena di Markov è caratterizzata da due quantità:

• la probabilità incondizionata

$P_i=P(X(n)=i)$

• la matrice delle probabilità di transizione $P_{ij}(m,n)=P(X(n)=j|X(m)=i)$.

Si ha

$P_i(n)\in [0,1]\mathrm{\forall }i\in S,\mathrm{\forall }n\in T|\sum _{i\in S}{P}_i(n)=1$

cioè, per ogni istante, la somma delle probabilità di tutti gli stati è unitaria; noto l'alfabeto $s$, la probabilità incondizionata si può scrivere come

$\underset{\_}{P}(n)=[P_1(n)P_2(n)\cdots P_{|s|}(n)]$

La stessa condizione si può esprimere con

$\underset{\_}{P}\cdot e^T=1e=[11\cdots 1]$

Fissati due istanti temporali $n<m$ e dato lo stato di partenza $n$, la somma delle probabilità degli stati di arrivo è unitaria.

$\underset{\_}{P}(m,n)=\left[\begin{array}{cccc}{P}_{1,1}(m,n)& P_{1,2}(m,n)& \cdots & P_{1,|s|}(m,n)\\ P_{2,1}(m,n)& P(2,2)(m,n)& \cdots & P_{2,|s|}(m,n)\\ ⋮& ⋮& \ddots & ⋮\\ P_{|s|,1}(m,n)& P_{|s|,2}(m,n)& \cdots & P_{|s|,|s|}(m,n)\end{array}\right]$

dove la somma dei valori di ogni singola riga è $1$

$\sum _{i=1,2,\cdots |s|}{P}_{i,j}(m,n)=1\mathrm{\forall }j\in [0,1,\cdots |s|]$

$\underset{\_}{P}(m,n)\cdot e^T=e^T=[11\cdots 1]$

Per ogni coppia $m,n$, il valore di $\underset{\_}{P}(m,n)$ sarà diverso. Si ha

$\underset{\_}{P}(n)=\underset{\_}{P}(m,n)\cdots \underset{\_}{P}(m)$

$\begin{array}{cc}{P}_{i,j}(m,n)& =P(X(n)=j|X(m)=j)\\ & =\sum _{l\in S}P(X(n)=j|X(u)=l,X(m)=i)\cdot P(X(u)=l|X(m=i))\\ & =\sum _{l\in S}{P}_{l,j}(u,n)\cdot P_{i,l}(m,n)\end{array}$

Quest'ultima è detta l'equazione di Chapman e Kolmogorov, che in forma matriciale si può scrivere come

$\underset{\_}{P}(m,n)=\underset{\_}{P}(m,u)\cdot \underset{\_}{P}(u,n)$

da cui si ha

$\underset{\_}{P}(m,n)=\prod _{k=m}^{n-1}\underset{\_}{P}(k,k+1)$

Per caratterizzare una catena di Markov, basta conoscere:

• $\underset{\_}{P}(0)$
• $\underset{\_}{P}(k,k+1)\mathrm{\forall }k\in T$
• $\underset{\_}{P}(n)=\underset{\_}{P}(0)\cdot \underset{\_}{P}(0,1)\cdot \underset{\_}{P}(1,2)\cdots \underset{\_}{P}(n-1,n)$

Esempio: Caso 1

Si ha

$\underset{\_}{P}(1)=\underset{\_}{P}(0)\cdot \underset{\_}{\underset{\_}{P}}=[10]\cdot \left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]=[01]$

$\underset{\_}{P}(2)=\underset{\_}{P}(0)\cdot {\underset{\_}{\underset{\_}{P}}}^2=[10]\cdot \left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]\cdot \left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]=[10]$

La sequenza degli stati è deterministica,

• $P(2m)=[10]\mathrm{\forall }m\in \mathbb{N}$
• $P(2m+1)=[01]\mathrm{\forall }m\in \mathbb{N}$

Esempio: Caso 2

Si ha

$\underset{\_}{\underset{\_}{P}}=\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]$

$P(0)=\left[\frac{1}{2}\frac{1}{2}\right]$

da cui

$\underset{\_}{P}(1)=\underset{\_}{P}(0)\cdot \underset{\_}{\underset{\_}{P}}=\left[\frac{1}{2}\frac{1}{2}\right]$

$\underset{\_}{P}(2)=\underset{\_}{P}(0)\cdot {\underset{\_}{\underset{\_}{P}}}^2=\left[\frac{1}{2}\frac{1}{2}\right]$

da cui si deduce che vale

$\underset{\_}{P}(m)=\left[\frac{1}{2}\frac{1}{2}\right]\mathrm{\forall }m\in T$

Definizione: Catena di Markov omogenea

Una catena di Markov è detta omogenea se

$\underset{\_}{P}(k,k+1)=\underset{\_}{\underset{\_}{P}}\mathrm{\forall }k\in T$

ossia, la matrice di probabilità di transizione ad un passo $(k,k+1)$ è la stessa per tutti i $k\in T$.

Esempio:

Si ha

$\underset{\_}{\underset{\_}{P}}=\left[\begin{array}{cc}{P}_{11}& P_{12}\\ P_{21}& P_{22}\end{array}\right]$

da cui

• $\underset{\_}{P}(0)=[P_1{P}_2]$
• $s=\{1,2\}$
• $T=\{0,1,\cdots \}$

Definizione: Distribuzione stazionaria

Data una catena di Markov omogenea, si definisce distribuzione stazionaria il vettore di probabilità

$\underset{\_}{\mathrm{\Pi }}=[{\pi }_1{\pi }_2\cdots {\pi }_{|s|}]$

tale che

• $\underset{\_}{\mathrm{\Pi }}\cdot \underset{\_}{\underset{\_}{P}}=\underset{\_}{\mathrm{\Pi }}$
• $\underset{\_}{\mathrm{\Pi }}\cdot e^T=1$

da cui, nel caso in cui $P(0)=\underset{\_}{\mathrm{\Pi }}$, allora si ottiene

$P(n)=\underset{\_}{\mathrm{\Pi }}\mathrm{\forall }n\in T$

In generale, una catena di Markov può avere più distribuzioni stazionarie.

Esempio:

Sia

$\underset{\_}{\underset{\_}{P}}=\left[\begin{array}{ccc}0& 1& 0\\ 1& 0& 0\\ 0& 0& 1\end{array}\right]$

da cui si ha

• ${\mathrm{\Pi }}_1=\left[\frac{1}{2}\frac{1}{2}0\right]$
• ${\mathrm{\Pi }}_2=[001]$
• ${\mathrm{\Pi }}_3=\left[\frac{1}{4}\frac{1}{4}\frac{1}{4}\right]$

Definizione: Catena di Markov irriducibile

Una catena di Markov si dice irriducibile se non è possibile portare la matrice di probabilità di transizione in una forma diagonale a blocchi, del tipo

$\left[\begin{array}{cc}\left\{\begin{array}{cc}0& 1\\ 1& 0\end{array}\right\}& \begin{array}{c}0\\ 0\end{array}\\ \begin{array}{cc}0& 0\end{array}& 1\end{array}\right]$

Se una catena di Markov è irriducibile, allora la distribuzione stazionaria esiste ed è unica.

Definizione: Distribuzione limite

Una distribuzione stazionaria $\underset{\_}{\mathrm{\Pi }}$ si dice distribuzione limite se

$\underset{n\to \mathrm{\infty }}{lim}\underset{\_}{P}(n)=\underset{\_}{P}$

Questo deve valere $\mathrm{\forall }P(0)$, cioè per qualsiasi condizione iniziale.

Definizione: Catena di Markov aperiodica

Una catena di Markov omogenea ed irriducibile è aperiodica se il massimo comun divisore delle lunghezze di tutti i cammini chiusi che si possono individuare sul diagramma delle transizioni è pari a $1$.

Esempio:

Catena periodica di periodo $3$:

In questo caso, $MDC=3$.

Esempio:

Catena di Markov aperiodica:

In questo caso, $MDC=1$.

Se una catena di Markov omogenea ed irriducibile è aperiodica, allora la distribuzione stazionaria è anche distribuzione limite. Per queste catene di Markov, a regime la probabilità assoluta è indipendente dal tempo, dando origine a processi stazionari.

Nota: una distribuzione $\underset{\_}{\mathrm{\Pi }}$ è una distribuzione limite se

$\underset{n\to \mathrm{\infty }}{lim}{\underset{\_}{\underset{\_}{P}}}^n=\left[\begin{array}{c}\underset{\_}{\mathrm{\Pi }}\\ \underset{\_}{\mathrm{\Pi }}\\ \underset{\_}{\mathrm{\Pi }}\end{array}\right]$

Definizione: Matrice doppiamente stocastica

Una matrice di probabilità di transizione è doppiamente stocastica se la somma degli elementi di ciascuna colonna è unitario; in tal caso, la distribuzione limite risulta essere

$\underset{\_}{\mathrm{\Pi }}=[\frac{1}{|s|}\frac{1}{|s|}\cdots \frac{1}{|s|}]$

Esempio:

Si ha

• $\underset{\_}{\underset{\_}{P}}=\left[\begin{array}{ccc}\frac{1}{4}& \frac{1}{4}& \frac{1}{2}\\ \frac{1}{4}& \frac{1}{4}& \frac{1}{2}\\ \frac{1}{2}& \frac{1}{2}& 0\end{array}\right]$
• $\underset{\_}{\mathrm{\Pi }}=[\underset{\_}{{\pi }_1}\underset{\_}{{\pi }_2}\cdots \underset{\_}{{\pi }_3}]$

da cui

$\{\begin{array}{c}\underset{\_}{\mathrm{\Pi }}\cdot \underset{\_}{\underset{\_}{P}}=\underset{\_}{\mathrm{\Pi }}\\ \underset{\_}{\mathrm{\Pi }}\cdot {\underset{\_}{e}}^T=1\end{array}$

$\{\begin{array}{cc}\frac{1}{4}{\pi }_1+\frac{1}{4}{\pi }_2+\frac{1}{2}{\pi }_3& ={\pi }_1\\ \cdots & ={\pi }_2\\ \frac{1}{2}{\pi }_1+\frac{1}{2}{\pi }_2& ={\pi }_3\\ {\pi }_1+{\pi }_2+{\pi }_3& =1\end{array}$

si ottiene

$\underset{\_}{\mathrm{\Pi }}=\left[\frac{1}{3}\frac{1}{3}\frac{1}{3}\right]$

che è una matrice stocastica.