Why does the Metropolis-Hastings procedure satisfy the detailed balance
criterion?
Kris Hauser
10/21/2013

Given an (unnormalized) target distributionthat is hard to sample from and simple proposal
distribution, the Metropolis-Hastings (MH) algorithm generates a sequence of iterates
whose distribution, with sufficiently large , approximate . However, this fact is rarely proven when
the algorithm is presented. This document attempts to shed some light on the subject in a way that isunderstandable to, say, an upper-level engineering undergraduate or introductory graduate student
who has had some basic exposure to the method.
MH is typically stated as follows:
Metropolis-Hastings( , , )For
do:
1. Sample from).
2. With acceptance probability
3. Otherwise, set
If(() (|)), set.

.

is set in Step 2, we call it an accepted step, otherwise we call it a rejected step.

It is usually stated without proof that as grows large and with relatively mild restrictions on and ,the distribution ofapproaches . But why? The answer is completely unobvious on a first,second, or even third glance. The acceptance probability is mysterious, with its naughty minimization
term. It fights against our instincts, as we were taught as gospel that nonsmooth transformations wreak
havoc with probability distributions.
Students at this point typically nod with deer-like expressions on their faces, assuming the professor
knows some black magic that leads to a proof. In fact, he/she is probably employing the trusted Jedi
mind trick, taking a tip from good ol’ Fermat with his famous margin scribbles. (If you substitute“reader” for “student” and “author” for “professor”, this description describes hundreds if not
thousands of academic papers.)
Proof.
First, the detailed balance criterion of a Markov Chain with transition distribution
statesthat a stationary distribution
satisfies. This is a necessary
condition for a random walk to asymptotically reach a stationary distribution; additional considerations
like ergodicity (that is, there is a nonzero probability of reaching any state from any other state) must besatisfied to make the walk truly converge to . A good professor will wave his/her hands about detailedbalance. Few tread into the next steps of the proof.
Now, we must examine whether each subsequent iterate of the MH algorithm satisfies detailed balance.
The argument is somewhat subtle.
The transition distribution of the MH sampling sequence is given by distribution ofafter each inner
MH loop completes, given the value of at the beginning of the loop. Examine the followingequations. Let Case A denote the case whereand let Case B indicate. A Case A
transition can only be achieved with an accepted MH step, which happens with probability:

A Case B transition can be achieved with an accepted step that luckily lands back at the same point aswell as a rejected step:∫()

The first term is the probability of luckily being accepted back on the same point, and the second term isthe probability of a rejection. Don’t get hung up on the complexity of the second term, as the form of
the transition distribution for Case B doesn’t really matter. Here, we have
, and so it is triviallyevident that the detailed balance conditionis satisfied in CaseB.

Now let’s return to Case A and expand thein the transition probability, then apply a bit of algebra:()()

Observe that the two terms inside the minimization are symmetric with respect to switching of. Simply switching them in the equation above, we have()So, in Case A, we have
()

()

and

Fulfilling the detailed balance condition as desired. Since detailed balance holds for both Case A andCase B, it holds everywhere.
Derivation of MH.
Another way to think about MH is how should we design the acceptance probability function
sothat detailed balance is satisfied? First, it doesn’t matter what is for Case B to hold. So, let’s turn ourattention to detailed balance in Case A. Expanding this out, we require that satisfy:

In other words,

with some algebraic manipulation.

For to yield a valid probability, it must be nonnegative and no greater than 1. By inspecting what
happens whenis limited by 1, we see that
becomes not limited, and theequation holds as it should. The equation also holds in the opposite condition when the numerator is
not limited and the denominator is. Hence, the MH acceptance probability satisfies this requirement.
Metropolis-Hastings is Optimal.
An interesting thought experiment would ask to design a different acceptance probability function. Let cbe the rhs of the above equation. Then can we design a function
whose range is in [0,1] andsatisfies
for all x,y,c?
Yes, this is obviously true for any constant scaling in (0,1], and other solutions may exist as well.
But can we design a function that leads to fewer rejections than the Metropolis acceptance probability?
Metropolis has a nonzero probability of rejecting whenever() (|if we were to use a higher probability of accepting the sample, say
have a problem:
Metropolis acceptance probability leads to a maximum number of accepted steps.

)

is less than 1. But, then we’d. Hence, the