Proving the existence of a detailed balanced stationary distribution

1.2k Views Asked by At

Consider $$P = \begin{pmatrix} 0 & a & 0 & 1-a\\ 1-b & 0 & b & 0\\ 0 & 1-c & 0 & c\\ d & 0 & 1-d & 0\\ \end{pmatrix}$$ with $S = \{1,2,3,4\}$, and show that there is a stationary distribution satisfying the detailed balance condition if $$0 < abcd = (1 - a)(1 - b)(1 - c)(1 - d).$$

I know that the detailed balance condition requires $\pi_i p(i,j) = \pi_j p(j,i)$ for all $i, j \in S$. Thus, my initial idea was to rewrite the equality as follows: $$abcd = p(1,2) p(2,3) p(3,4) p(4,1)$$ and $$(1 - a)(1 - b)(1 - c)(1 - d) = p(2,1) p(3,2) p(4,3) p(1,4)$$ However, I'm unsure where to go from this point. I tried thinking about properties of the stationary distribution ($\sum_{i \in S} \pi_i = 1$, $\pi_2 p(1,2) + \pi_3 p(1,3) + \pi_4 p(1,4) = \pi_1$), but have thus far not been able to transform this into the detailed balance condition. Any advice is greatly appreciated!

1

There are 1 best solutions below

1
On BEST ANSWER

We can think of the four states of this Markov chain as being arranged in a cycle. We go clockwise from $i$ to $(i+1)\bmod 4$ with probabilities $a$, $b$, $c$, $d$ respectively, and counterclockwise from $i$ to $(i-1) \bmod 4$ with probabilities $1-a$, $1-b$, $1-c$, $1-d$, respectively.

Any time the detailed balance conditions are satisfied, if we start at one value of $\pi_i$, we can deduce the values of all others connected to it. In this example, we can write down $\pi_2$, $\pi_3$, and $\pi_4$ in terms of $\pi_1$: \begin{align} \pi_1 a = \pi_2 (1-b) &\implies \pi_2 = \frac{a}{1-b} \pi_1 \\ \pi_2 b = \pi_3 (1-c) &\implies \pi_3 = \frac{b}{1-c} \pi_2 = \frac{ab}{(1-b)(1-c)}\pi_1 \\ \pi_3 c = \pi_4 (1-d) &\implies \pi_4 = \frac{c}{1-d} \pi_3 = \frac{abc}{(1-b)(1-c)(1-d)}\pi_1. \end{align} With just these three equations, which are the detailed balance equations for $(1,2)$, $(2,3)$, and $(3,4)$, we've solved for $\pi_2, \pi_3, \pi_4$ in terms of $\pi_1$.

But there's one more equation we haven't used yet. It says that $\pi_4 d = \pi_1(1-a)$ and since we already know both sides, we can write it as $$\frac{a b c}{(1-b)(1-c)(1-d)}\pi_1 d = \pi_1 (1-a) \iff a b c d = (1-a)(1-b)(1-c)(1-d).$$ (We canceled $\pi_1$ from both sides, but that's okay: if we had $\pi_1 = 0$ then the equations above would tell us $\pi_2 = \pi_3 = \pi_4 = 0$ as well, which wouldn't be any good.)

In other words, starting with an arbitrary $\pi_1$, we can force detailed balance at $(1,2)$, $(2,3)$, and $(3,4)$ to hold by choosing $\pi_2, \pi_3, \pi_4$ appropriately. (We could now also work out $\pi_1$ by using the fact that $\pi_1 + \pi_2 + \pi_3 + \pi_4 = 1$, but we don't need to.) But we no longer have the freedom to force detailed balance to hold at $(1,4)$, since $\pi_1$ and $\pi_4$ are fixed. We can just hope that the equation turns out to hold anyway, and the above calculation shows that it does hold exactly when $a b c d = (1-a)(1-b)(1-c)(1-d)$.

(Once that's true, we have a solution that satisfies detailed balance, and therefore it must also be a stationary distribution.)