Detailed-balance proof without skipped cases
Section of Markov chains, Gibbs sampling, and Metropolis–Hastings, part of Bayesian statistics
Detailed-balance proof without skipped cases
| Type | Section |
| Taught in | Markov chains, Gibbs sampling, and Metropolis–Hastings |
| Part | Bayesian statistics |
Theorem 1 (Metropolis–Hastings invariance) The Metropolis–Hastings transition defined by Equation (5) in Markov chains, Gibbs sampling, and Metropolis–Hastings satisfies detailed balance with respect to \pi. Consequently, \pi is stationary.
Proof. Proof. Let
r(x,y)=\frac{\pi(y)q(x\mid y)} {\pi(x)q(y\mid x)}.
For y\neq x, \begin{align*} \pi(x)q_{\mathrm{MH}}(y\mid x) &=\pi(x)q(y\mid x)\min\{r(x,y),1\}. \end{align*} There are two cases.
If r(x,y)\leq1, then \begin{align*} \pi(x)q_{\mathrm{MH}}(y\mid x) &=\pi(x)q(y\mid x)r(x,y)\\ &=\pi(x)q(y\mid x) \frac{\pi(y)q(x\mid y)}{\pi(x)q(y\mid x)}\\ &=\pi(y)q(x\mid y). \end{align*} Since r(y,x)=1/r(x,y)\geq1, the reverse move is accepted with probability one, so
\pi(y)q_{\mathrm{MH}}(x\mid y) =\pi(y)q(x\mid y).
If r(x,y)>1, then the forward move is accepted with probability one:
\pi(x)q_{\mathrm{MH}}(y\mid x)=\pi(x)q(y\mid x).
Now r(y,x)<1, so \begin{align*} \pi(y)q_{\mathrm{MH}}(x\mid y) &=\pi(y)q(x\mid y)r(y,x)\\ &=\pi(y)q(x\mid y) \frac{\pi(x)q(y\mid x)}{\pi(y)q(x\mid y)}\\ &=\pi(x)q(y\mid x). \end{align*} Thus detailed balance holds in both cases. For x=y, both sides of the detailed-balance equation are identical. Therefore \pi is stationary.
The theorem establishes invariance, not convergence from an arbitrary starting value and not efficiency. The ergodicity conditions stated earlier are still needed for convergence, while proposal design determines how much useful information the dependent output contains.
Used in
See also
Markov chain · Stationarity and detailed balance · Detailed balance implies stationarity · Systematic-scan Gibbs sampler · Warm-up is not a convergence proof · Metropolis–Hastings update · Metropolis–Hastings invariance · Markov chains and equilibrium