Introduzione alle catene di Markov

La proprietà di Markov

Una sequenza di variabili aleatorie $X_1,X_2,X_3,\dots$ gode della proprietà di Markov se vale:

$$P(X_n|X_{n-1},X_{n-2},\dots ,X_1)=P(X_n|X_{n-1})$$

Ossia posso scordarmi tutta la storia precedente, mi interessa solamente lo stato precedente per sapere la probabilità attuale.

Da un punto di vista filosofico/fisico, ha senso perché mi sta dicendo che posso predire lo stato successivo se ho una conoscenza (completa, (lo dico io completo, originariamente non esiste)) del presente.

La catena di Markov

La catena di Markov è una successione di variabili aleatorie che possiede la proprietà di Markov. Solitamente lo rappresentiamo a grafi oppure tramite la matrice di transizione. A me piace più la versione a grafi. Matematicamente scriviamo $X=\left\{X_t\mid t=0,1,\dots \right\}$ su uno spazio di stati $S=\left\{0,1,2,\dots \right\}$ tali per cui per ogni $t,j,i_0,\dots i_t\in S$ abbiamo:

$$\mathbb{P}(X_{t+1}=j\mid X_0=i_0,\dots ,X_t=i_t)=\mathbb{P}(X_{t+1}=j\mid X_t=i_t)=P_{ij}$$

Queste catene sono dette time-homogeneus. Con la probabilità di Markov si può dimostrare che se $X_0\sim {\mu }_0$ con ${\mu }_0$ il vettore riga, allora la probabilità della distribuzione $X_t$ sarà ${\mu }_t={\mu }_0{P}^t$. We have that $\mu$ is a stationary distribution if $\mu =\mu P$ is valid. A study of this property is sometimes interesting.

Catena di 3 variabili

Siano $X,Y,Z$ è chiaro che se viene formata la Catena di Markov $X\to Y\to Z$ allora deve valere

$$p(x,y,z)=p(x)p(y|x)p(z|y)$$

Con Bayes si può dimostrare che vale anche la catena contraria:

$$p(x,y,z)=p(z)p(y|z)p(x|y)$$

Altra cosa è che deve fare se e solo se $X,Z$ sono indipendenti, dato $Y$ ossia se vale

$$P(x,z|y)=P(x|y)P(z|y)$$

Che dovrebbe essere una conseguenza diretta della parte di sopra. Una altra osservazione è che se vale quella catena, vale anche l'inversa, ossia $Z\to Y\to X$.

Abbiamo analizzato molte catene di questo genere quando abbiamo parlato di d-separabilità in Counterfactual Invariance.

Data processing inequality

Se abbiamo una catena di Markov $X\to Y\to Z$ allora vale che

$$I(X;Y)\ge I(X;Z)$$

Perché una parte di computazione è possibile modellarlo con la catena di Markov. E mi sta dicendo che l'informazione comune all'input $X$ con l'output $Y$ o output $Z$ dopo seguente computazione viene sempre meno con più computazione, e anche che non aggiungo informazione con più computazione.

The Data Processing Inequality states that given three random variables and the given graphical model:

$$X\to Y\to Z$$

Then it is true that:

$$I(X;Y)\ge I(X;Z)$$

If the equality is satisfied then $Z$ is the sufficient statistic for $Y$. This has some relation with The Exponential Family.

Dimostrazione Sappiamo che la mutua informazione è sempre non negativa. Possiamo poi utilizzare la propria della mutua informazione condizionale:

$$\begin{array}{rl}I(X;Z)& =I(X;Y,Z)-I(X;Y\mid Z)\\ & =I(X;Y)-I(X;Z\mid Y)-I(X;Y\mid Z)\\ & ⟹I(X;Y)\ge I(X;Z)\end{array}$$

Definizioni Comuni

Raggiungibilità

Il nodo $j$ è raggiungibile da un nodo $i$ se esiste un numero di passi $m$, tale per cui

$$P_{ij}^m>0$$

Molto più facile vedere sta cosa se lo rappresentiamo come un comunissimo grafo.

Classe di stati

Sono un insieme di stati tutti raggiungibili fra di loro (comunque presi due stati all'interno della classe, esiste un percorso che parte da uno e finisce sull'altro per dire).

Recurrent vs Transient

È recurrent se per ogni nodo, tutti i nodi raggiungibili da un nodo $i$ raggiungono anche il nodo $i$ stesso. Transient se non è recurrent. Alcuni chiamano la recurrent come irreducible come in (Cover & Thomas 2012).

Periodic vs Aperiodic

Sia $d$ il massimo comune divisore per tutti gli $m$ tali per cui vale $P_{ii}^m>0$ (ossia può raggiungere sé stesso con probabilità non nulla), allora è periodico se $d>1$ altrimenti è aperiodico. Questo implica che non esistono cicli di passi che siano divisibili per un numero $d$, e abbiamo una definizione un poco più intuitiva di periodicità. Una catena di Markov è aperiodica se tutti i nodi sono aperiodici.

Ergodic Markov Chain

Una catena di Markov si dice Ergodico se è recurrent e aperiodico. Si può anche definire come se esista un $t$ finito tale per cui tutti gli stati siano raggiungibili da tutti gli altri in esattamente $t$ steps, questa è una definizione molto più intuitiva, che è anche giustificata dal teorema seguente.

Possiamo avere un teoremino carino su queste tipologie di catene, ed è più o meno il motivo per cui si chiamano ergodiche, ossia che una particella che segue questa legge prima o poi va a visitare tutti gli stati una volta. Abbiamo come teorema:

$$P_{ij}^{(M-1{)}^2+1}>0$$

Con $M$ il numero totale di stati, e $ij$ qualunque stato iniziale o finale. Dimostrazione è un esercizio. Può essere molto utile il Chicken McNugget Theorem per dimostrare questo, e fare ragionamenti sul massimo risultato ottenibile. Comunque possiamo dire che esiste un $t$ tale per cui tutti gli stati sono raggiungibili da tutti gli altri in $t$ steps, la dimostrazione si può trovare nel teorema 1.7 di questo Originariamente preso da qui al corso di discrete stochastic processes.

Unichain

Una catena che contiene una singola classe recurrent più alcuni stati transienti

Chapman-Kolmogorov Equation

Alla fine è una relazione molto semplice, che deriva in modo facile dalle matrici di transizione, dice che Sia $P$ una matrice di transizione per un processo di Markov, allora

$$P_{ij}^{n+m}=\sum _{k=0}^N{P}_{ik}^n{P}_{kj}^m$$

Ossia posso moltiplicare matrici di transizione assieme per avere la probabilità di muovermi da uno stato $i$ a uno stato $j$ in $n+m$ passi.

Possiamo scrivere questa equazione nella forma continua, che è utile per l'analisi di processi di diffusione: Quando scritto è preso da qui, pagina 30: in questo caso $t$ sono i passi di tempo

Convergenza

Ha senso pensare che una catena di Markov converga nel proseguire delle transazioni.

Teorema di convergenza per catene ergodiche

Questo è un teorema importante. Fatto sta che esiste una distribuzione stazionaria una volta che ho fatto abbastanza passi. Da fare.

Convergenza per unichains ergodiche.

Stationary distributions

Una distribuzione $\pi$ è detta stazionaria se vale che $\pi =\pi P$. ossia la probabilità di finire in uno stato $x$ dopo aver fatto una altra mossa seguendo la distribuzione $\pi$ è uguale a $\pi (x)$.

The Ergodic Theorem

Questa è una generalizzazione della Legge dei grandi numeri (guarda qui Central Limit Theorem and Law of Large Numbers), per catene di Markov ergodiche. In generale ci permette di utilizzare catene di markov per fare stime di probabilità, elementi che risultano molto utili per fare Markov Chain Monte Carlo.

Questo teorema asserisce che data una catena di Markov $(X_t{)}_{t\in {\mathbb{N}}_0}$ con distribuzione stazionaria $\pi$ se spazio finito $S$ e una funzione $f:S\to \mathbb{R}$ allora vale che

$$\underset{n\to \infty }{\lim }\frac{1}{n}\sum _{t=0}^{n}f(X_t)=\sum _{x\in S}\pi (x)f(x)\approx {\mathbb{E}}_{x\sim \pi }[f(x)]$$

Questo teorema ci permetterà di fare sampling, utilizzando catene di Markov.

See appendix C of “Markov chains and mixing times” (Levin and Peres, 2017) for a proof.

Questo ci dice che l'estimatore che abbiamo è unbiased.

Inoltre abbiamo un burn-in time prima di iniziare a fare sampling in modo corretto, quindi i primi samples vengono scartati.

Detailed Balance Equation

Intuitivamente questa assunzione ci dice che per catene di Markov Ergodiche tale che per cui probabilità di andare da $x\to x^{\prime }$ e da $x^{\prime }\to x$ è esattamente uguale, cosa non ovvia per catene di Markov qualunque, ammettono una distribuzione stazionaria $Q(x)$ per ogni stato $Q$. Questo ci da un modo per costruire Markov Chains in modo che producano seguendo una distribuzione $Q$ data a priori.

Diciamo che una catena di Markov soddisfa questa equazione rispetto a una distribuzione $\pi$ se vale che

$$\pi (x)P(x\mid y)=\pi (y)P(y\mid x)$$

Queste catene di Markov si dicono anche reversible per l'osservazione di sopra.

Se una catena di Markov è reversible per una certa distribuzione $\pi$ allora quella è la distribuzione stazionaria della catena.

Dimostriamo quanto sopra.

$$\begin{array}{rlr}P(X_{t+1}=x^{\prime })=& & \\ \sum _x\pi (X_t=x)P(X_{t+1}=x^{\prime }\mid x)=& & \text{ using marginalization and product}\\ \sum _x\pi (X_t=x^{\prime })P(X_{t+1}=x\mid x^{\prime })=& & \text{reversibility}\\ \pi (X_t=x^{\prime })\sum _{x}P(X_{t+1}=x\mid x^{\prime })=\pi (x^{\prime })& & \end{array}$$

Che è la distribuzione stazionaria che volevamo. Si vede che è stazionaria perché facendo un update della catena, la probabilità resta ancora la stessa, per ogni stato di partenza.

Con rewards

Vogliamo associare a ogni stato $i$ un reward $r_i$ Si può creare allora una altra variabile aleatoria che prende la variabile aleatoria di Markov $X_i$ e lo mappa a un reward. Quello che ci interessano di più sono le expectation dei rewards.

Noi vogliamo il valore

$$E[R(X_n)|X_0=i]=\sum _j{r}_j{P}_{ij}^n$$

E per la proprietà di Markov credo sia la stessa cosa quando non parto da step 0.

Aggregate reward function

Questo è definito anche come value function in Reinforcement Learning, a introduction.

$v_i(n)=E[R(X_m)+\cdots +R(X_{m+n-1})|X_m=i]$

Se la catena è convergente, abbiamo che anche il value function è convergente a un valore preciso, ed è:

$$g=\sum {\pi }_j{r}_j=\vec{\pi }\cdot \vec{r}$$

Indipendentemente allo stato iniziale (che stupisce molto).

References

[1] Cover & Thomas “Elements of Information Theory” John Wiley & Sons 2012