10 Mar, 2016

Markov Chain Monte Carlo

Markov Chain: A Markov Chain is a sequence of random variables $x_1,x_2,...$ defined on a probability space such that

\[P(X_t \in A \v X_{t-1},\cdots,X_{1}) = P(X_t \in A \v X_{t-1}=x_{t-1})\]

(depending on only the previous draw). MC’s are defined in terms of transition (proposal) kernel $\kappa$ such that $\forall x\in\Omega,~\kappa(x,.)$ is a probability measure.

Time Homogeneous Chain: A markov chain such that the transition kernel is the same $\forall t$.

When $\Omega$ is discrete, $[P]_{x,y} = P(X_t = y \v X_{t-1} = x)$.

If $\Omega$ is continuous: $P(X_t \in A \v X_{t-1} = x) = \int_A \kappa(x,x') dx'$

Assuming $\Omega$ discrete and finite, with $S$ possibile states, $\pi_t = (\pi_{t,1}, …, \pi_{t,s})’$ (the marginal at time $t$) and $\pi_{t,1}$ being the probability of being at state 1 at time $t$.

$\pi_{t+1}’ = \pi_t’P$, $P$ is the transition kernel.

$\pi_{t+k}’ = \pi_t’P^k$.

An MC has a stationary distribution $\tilde\pi$ if $\tilde\pi’=\tilde\pi’P$. (Review applied math class)

An MC ($\Omega$ countable) has a unique stationary distribution iff the chain is irreducible and positive recurrent.

Irreducible: A chain is irreducible if $\forall$ pairs of states $i,j$, we can find $n_{i,j}, n_{j,i}$ such that

\[\begin{cases} P(X_{n_{i,j}}=j\v X_1=i) \gt 0 \\ P(X_{n_{j,i}}=i\v X_1=j) \gt 0 \\ \end{cases}\]

Positive Recurrent: A state $i$ is positive recurrent if the time it takes to returning to a state is finite, if

\[m_i = \sum_{t=1}^\infty t {f_{i,i}}^t \lt \infty\]

where ${f_{i,i}}^t = P(T_i=t)$, and $T_i = \text{inf} \bc{t\ge1: X_t=i\v X_1=i}$. Chain is recurrent implies that all states are recurrent.

A markov chain has a limiting distribution of $\hat\pi$ if $\forall \pi_1, \lim_{n\rightarrow\infty} \pi_1'P^n=\hat\pi$.

Aperiodic: A state $i$ has period $k$ if any return to $i$ must occur muples of $k$. i.e.

\[k = \text{gcd} (n:P[X_n=i \v X_1 =i]\gt 0)\]

A state is aperiodic if $k=1$.

A markov chain has a unique limiting distribution if the chain is positive recurrent, irreducible and aperiodic. If all states are aperiodic then the chain is aperiodic.

In MCMC, we want to construct chains with unique limiting stationary distributions equal to the target distribution. In our case $p(\theta(x))$.