Metropolis–Hastings algorithm

Definition

Let $S$ be a countable set and let $\pi$ be a probability distribution on $S$ with $\pi(x) > 0$ for all $x \in S$. Let $Q = (Q(x, y))_{x, y \in S}$ be a transition matrix, the proposal, such that $Q(x, y) > 0$ if and only if $Q(y, x) > 0$. For $x \ne y$ with $Q(x, y) > 0$, the acceptance probability is $$\alpha(x, y) = \min\left(1, \frac{\pi(y) \, Q(y, x)}{\pi(x) \, Q(x, y)}\right).$$ The Metropolis–Hastings chain is the Markov chain $(X_n)$ built as follows. Given $X_n = x$, draw $Y$ from $Q(x, \cdot)$. With probability $\alpha(x, Y)$ set $X_{n+1} = Y$; otherwise set $X_{n+1} = x$. Its transition matrix has $P(x, y) = Q(x, y) \, \alpha(x, y)$ for $y \ne x$ and $P(x, x) = 1 - \sum_{y \ne x} P(x, y)$.