Esempi di processi stocastici Processi PAM Processi gaussiani Processi di Markov

esercitazione
esercitazione
Esempi di processi stocastici Processi PAM Processi gaussiani Processi di Markov
Tipo di risorsa Tipo: esercitazione
Materia di appartenenza Materia: Teoria dei segnali e dei fenomeni aleatori

Processi e catene di Markov

modifica

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

  • sole,  ;
  • nuvoloso,  .

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

  • sole con probabilità  ;
  • nuvoloso con probabilità  .

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

  • sole con probabilità  ;
  • nuvoloso con probabilità  .

 

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   è un processo di Markov se
 


In altre parole, possiamo scrivere che una variabile casuale   dipende solo dalla variabile casuale  , mentre è indipendente da tutte le variabili casuali precedenti l'istante  .

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, è
 
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

modifica
  •  
  •  

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

Classificazione

modifica

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

modifica

Si ha

  •  
  •  

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

  • la probabilità incondizionata
 
  • la matrice delle probabilità di transizione  .

Si ha

 

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

 

La stessa condizione si può esprimere con

 

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

 

dove la somma dei valori di ogni singola riga è  

 
 

Per ogni coppia  , il valore di   sarà diverso. Si ha

 

 

 

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

 

da cui si ha

 

Per caratterizzare una catena di Markov, basta conoscere:

  •  
  •  
  •  


Esempio: Caso 1
Si ha
 
 

La sequenza degli stati è deterministica,

  •  
  •  



Esempio: Caso 2
Si ha
 
 

da cui

 
 

da cui si deduce che vale

 



Definizione: Catena di Markov omogenea
Una catena di Markov è detta omogenea se
 
ossia, la matrice di probabilità di transizione ad un passo   è la stessa per tutti i  .



Esempio:
Si ha

 

 

da cui

  •  
  •  
  •  



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

tale che

  •  
  •  

da cui, nel caso in cui  , allora si ottiene

 


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


Esempio:
Sia
 

da cui si ha

  •  
  •  
  •  



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
 


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


Definizione: Distribuzione limite
Una distribuzione stazionaria   si dice distribuzione limite se
 
Questo deve valere  , 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  .



Esempio:
Catena periodica di periodo  :

 

In questo caso,  .



Esempio:
Catena di Markov aperiodica:

 

In questo caso,  .


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   è una distribuzione limite se

 


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
 



Esempio:

 

 

Si ha

  •  
  •  

da cui

 
 

si ottiene

 
che è una matrice stocastica.