proof that Metropolis - Hastings algo satisfy the detailed balance

Question

This is in reference to https://ermongroup.github.io/cs323-notes/probabilistic/mh/

In it is says *we want to show that $p$ satisfies detailed balance for all $i, j$. By the definition of $\alpha$, without loss of generality, assume that $\alpha(j, i) = 1$ and $\alpha(i, j) = \frac{w(j)q(j, i)}{w(i)q(i, j)}$ *

What is the motivation behind the above assumption $\alpha(j, i) = 1$ and $\alpha(i, j) = \frac{w(j)q(j, i)}{w(i)q(i, j)}$? Why does the author switches $p$ to $w$?

Answer 1

Our ultimate goal is to show that $p$ satisfies detailed balance for all $i,j$, which means showing that $p(i) P_{ij} = p(j) P_{ji}$. There is nothing to check here when $i=j$, and in the $i \ne j$ case, we have $P_{ij} = q(i,j) \alpha(i,j)$ and $P_{ji} = q(j,i) \alpha(j,i)$. So our first step is to understand $\alpha(i,j)$ and $\alpha(j,i)$.

From their definitions, we have $$ \alpha(i,j) = \min \left\{1, \frac{p(j)q(j,i)}{p(i)q(i,j)}\right\}, \qquad \alpha(j,i) = \min \left\{1, \frac{p(i)q(i,j)}{p(j)q(j,i)}\right\}. $$ (There's also an equivalent definition with $w(i), w(j)$ instead of $p(i), p(j)$, but that exists for practical purposes: when implementing the algorithm, we do not know $p(i)$, but we do know $w(i)$. In the proof, it does not matter which version we use, and the version above will be slightly more direct.)

Notice that $\frac{p(j)q(j,i)}{p(i)q(i,j)}$ and $\frac{p(i)q(i,j)}{p(j)q(j,i)}$ are reciprocals of each other. Therefore, if one of them is bigger than $1$, the other is smaller than $1$. There are two options:

1. If $\frac{p(j)q(j,i)}{p(i)q(i,j)} \ge 1$ and $\frac{p(i)q(i,j)}{p(j)q(j,i)} \le 1$, then $\alpha(i,j) =1$ and $\alpha(j,i) = \frac{p(i)q(i,j)}{p(j)q(j,i)}$.
2. If $\frac{p(j)q(j,i)}{p(i)q(i,j)} < 1$ and $\frac{p(i)q(i,j)}{p(j)q(j,i)} > 1$, then $\alpha(i,j) = \frac{p(j)q(j,i)}{p(i)q(i,j)}$ and $\alpha(j,i) = 1$.

When the proof says "without loss of generality, we assume [case 2]", it means that the proof would be essentially the same in both cases, so we picked just one of the cases to do. The reason the proof is the same in both cases is symmetry: detailed balance treats the indices $i$ and $j$ identically. If we were in case 1, we could swap $i$ and $j$ to end up in case 2, so we can assume we're in case 2.

Now that we have the assumption $\alpha(i,j) = \frac{p(j)q(j,i)}{p(i)q(i,j)}$ and $\alpha(j,i) = 1$, we can go ahead and evaluate $p(i) P_{ij}$ and $p(j) P_{ji}$, to show that they're equal (and conclude that detailed balance holds). For the left-hand side, $$p(i) P_{ij} = p(i) q(i,j) \alpha(i,j) = p(i) q(i,j) \cdot \frac{p(j)q(j,i)}{p(i)q(i,j)} = p(j) q(j,i).$$ For the right-hand side, $$p(j) P_{ji} = p(j) q(j,i) \alpha(j,i) = p(j) q(j,i) \cdot 1 = p(j)q(j,i).$$ The two are equal, so detailed balance holds.