I do not understand the formal proof that the Metropolis Hastings update generates a Markov chain that satisfies detailed balance as it is given in the the Wikipedia article. Under "formal derivation" it states that


is fulfilled by the acceptance probability


where $x'$ is the candidate, $x$ the current state, $A(.)$ the acceptance probability, $P(.)$ the target distribution and $g(.)$ the proposal distribution.

I just do not see why this is formally correct.

Link to Wikipedia Article: https://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm#Formal_derivation


That follows by an easy case distinction: If $P(x')g(x|x')>P(x)g(x'|x)$, then $A(x'|x)=1$ and, by symmetry, $A(x|x')=\frac{P(x)g(x'|x)}{P(x')g(x|x')}$ and the claim holds. The case $P(x')g(x|x')\le P(x)g(x'|x)$ works similarly.

Maybe, the equality

$$A(x'|x)\cdot P(x)g(x'|x)= A(x|x')\cdot P(x')g(x|x')$$

is easier to see by plugging in the definition of $A$

$$\min(P(x)g(x'|x), P(x')g(x|x')) = \min(P(x')g(x|x'),P(x)g(x'|x))$$


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.