4
$\begingroup$

In the Metropolis-Hasting algorithm we choose the acceptance probability $A(x \rightarrow x')$ as following:

$$A(x \rightarrow x') = min \left[1, \frac{\pi(x')Q(x' \rightarrow x)}{\pi(x)Q(x \rightarrow x')} \right]$$

For me this formula is not 100% clear and would like to clarify why we need the min operator and the fractional part of the equation.

Let $T(x \rightarrow x')$ be the transition probability for our markov chains. Define it as follows wrt to the acceptance probability A and proposer probability Q:

$$T(x \rightarrow x') = Q(x \rightarrow x') A(x \rightarrow x')$$

$$T(x \rightarrow x) = Q(x \rightarrow x)+ \sum_{x \neq x'} Q(x \rightarrow x')(1- A(x \rightarrow x'))$$

Recall that the detailed balance equation (i.e. prob of going right is same as going left) is:

$$\pi(x)T(x \rightarrow x') =\pi(x')T(x' \rightarrow x)$$

Given that we have already chosen a (regular) proposal probability Q and that we want to define $T(x' \rightarrow x)$ to be stationary, then can just satisfy the detailed balance equation as follows (in the case of $x \neq x'$):

$$\pi(x)T(x \rightarrow x') =\pi(x')T(x' \rightarrow x)$$ $$\pi(x)A(x \rightarrow x')Q(x \rightarrow x') =\pi(x')A(x' \rightarrow x)Q(x' \rightarrow x)$$ $$\frac{A(x \rightarrow x')}{A(x' \rightarrow x)} = \frac{\pi(x')Q(x' \rightarrow x)}{\pi(x)Q(x \rightarrow x')}$$

Which shows that we should choose the ratios of the $A's$ to be as above. Is the reason that we choose the min is to guarantee that the above ratio is always satisfied and therefore, that detailed balance is always satisfied?

Is the following reasoning correct:

Say that instead you always set $A(x \rightarrow x') = \frac{\pi(x')Q(x' \rightarrow x)}{\pi(x)Q(x \rightarrow x')}$. Then if you consider the other acceptance transition direction $A(x' \rightarrow x) = \frac{\pi(x)Q(x \rightarrow x')}{\pi(x')Q(x' \rightarrow x)}$ must have reciprocal values. If that is the case, then one is larger than 1 and the other less than 1 (or both equal to 1 I guess). However, to satisfy:

$$\frac{A(x \rightarrow x')}{A(x' \rightarrow x)} = \frac{\pi(x')Q(x' \rightarrow x)}{\pi(x)Q(x \rightarrow x')}$$

and having one of the acceptance direction be $A(x \rightarrow x') = \frac{\pi(x')Q(x' \rightarrow x)}{\pi(x)Q(x \rightarrow x')}$, then the other must be 1 (otherwise $\frac{A(x \rightarrow x')}{A(x' \rightarrow x)} = \frac{\pi(x')Q(x' \rightarrow x)}{\pi(x)Q(x \rightarrow x')}$ would not be satisfied). Therefore, let the one that is less than 1 be the intended ratio and the other be 1. Thats what the min is doing. Right?

Is that the reason we have the min for 1? just to make sure the other direction is 1 and thus, satisfy detailed balance?

$\endgroup$
1
$\begingroup$

$A(x \rightarrow x')$ is an acceptance probability, so it has to fit the [0, 1] range. But in practice it is not of much importance and can be omitted, like in an example of MH given by Robert and Casella (2010):

y = geneq(x[t])
if ( runif(1) < f(y) * q(y, x[t]) / ( f(x[t]) * q(x[t], y) ) ) {
   x[t+1] = y
} else {
   x[t+1] =x[t]
}

where geneq is a generator for $q(y|x)$. As you can see, if writing it this way it doesn't matter if $A(x \rightarrow x')$ is less than one, while it works just the same like in the original formula.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.