0

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$?

Mathematicing
  • 6,253
  • When the text says "by the definition of $\alpha$", it is a good idea to look back at the definition of $\alpha$ if what follows is unclear. Have you done that? What part of this seems not to follow from the definition? – Misha Lavrov Apr 22 '23 at 02:47
  • @MishaLavrov I stared at it for 12 whole hours today and I still don't get it. I saw the definition of what alpha is. Either I am missing something or that the author could have made explicit his intention but did not. The author also does not explain the motivation for his arguments, making it difficult to decipher when he is making a conceptual move and when is he making an algebraic move – Mathematicing Apr 28 '23 at 10:46
  • Now I feel bad; I did not mean at you to stare at anything for 12 hours, just to explain more about what you're confused by. I'm still not 100% clear on that, but I'll do my best to answer. – Misha Lavrov Apr 28 '23 at 14:53

1 Answers1

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.

Misha Lavrov
  • 142,276