# Markov Chain Monte-Carlo Methods¶

• Often no closed form for $f({\boldsymbol \theta}|{\boldsymbol y})$

• Further, even if computing $f({\boldsymbol \theta}|{\boldsymbol y})$ is feasible, obtaining $f(\theta_{i}|{\boldsymbol y})$ would require integrating over many dimensions

• Thus, in many situations, inferences are made using the empirical posterior constructed by drawing samples from $f({\boldsymbol \theta}|{\boldsymbol y})$

• Gibbs sampler is widely used for drawing samples from posteriors

## Gibbs Sampler¶

• Want to draw samples from $f(x_{1},x_{2},\ldots,x_{n})$

• Even though it may be possible to compute $f(x_{1},x_{2},\ldots,x_{n})$, it is difficult to draw samples directly from $f(x_{1},x_{2},\ldots,x_{n})$

• Gibbs:

• Get valid a starting point $\mathbf{x}^{0}$

• Draw sample $\mathbf{x}^{t}$ as: $$\begin{matrix}x_{1}^{t} & \text{from} & f(x_{1}|x_{2}^{t-1},x_{3}^{t-1},\ldots,x_{n}^{t-1})\\ x_{2}^{t} & \text{from} & f(x_{2}|x_{1}^{t},x_{3}^{t-1},\ldots,x_{n}^{t-1})\\ x_{3}^{t} & \text{from} & f(x_{3}|x_{1}^{t},x_{2}^{t},\ldots,x_{n}^{t-1})\\ \vdots & & \vdots\\ x_{n}^{t} & \text{from} & f(x_{n}|x_{1}^{t},x_{2}^{t},\ldots,x_{n-1}^{t}) \end{matrix}$$

• The sequence ${\boldsymbol x}^{1},{\boldsymbol x}^{2},\ldots,{\boldsymbol x}^{n}$ is a Markov chain with stationary distribution $f(x_{1},x_{2},\ldots,x_{n})$

## Making Inferences from Markov Chain¶

Can show that samples obtained from a Markov chain can be used to draw inferences from $f(x_{1},x_{2},\ldots,x_{n})$ provided the chain is:

• Irreducible: can move from any state $i$ to any other state $j$

• Positive recurrent: return time to any state has finite expectation

• Markov Chains, J. R. Norris (1997)