Markov Chain Monte Carlo

Definition

Markov Chain Monte Carlo (MCMC) is a method to sample from a distribution $\pi$ by constructing a time reversible Markov chain.

Interpretation

Directly sampling from a complex high-dimensional distribution $\pi$ is often impossible. MCMC solves this by constructing a Markov chain whose stationary distribution equals $\pi$. After running the chain long enough (burn-in), the states visited approximate samples from $\pi$.

Metropolis-Hastings Algorithm

Given current state $i$:

1. Propose a candidate jump to $j$ from proposal distribution $q_{ij}$ (e.g., symmetric random walk: $q_{ij}=q_{ji}$)
2. Accept with probability: ${\alpha }_{ij}=\min \left(1,\frac{{\pi }_j{q}_{ji}}{{\pi }_i{q}_{ij}}\right)$ If accepted: move to $j$. If rejected: stay at $i$ (count $i$ again as a sample).

The acceptance ratio $\frac{{\pi }_j{q}_{ji}}{{\pi }_i{q}_{ij}}$ corrects for the proposal bias: if $j$ is more “desirable” under $\pi$, accept more often; if less, accept less often. This ensures $\pi$ is the stationary distribution.

Related

• Time Reversible Markov Chain