Detailed Balance¶

The Markov Chains that we have been studying have stationary distributions that contain much information about the behavior of the chain. The stationary distribution of a chain is a probability distribution that solves the balance equations. For some chains it is easy to identify a distribution that solves the balance equations. But for other chains, the solution can be complicated or tedious. Let's see if we can find a simple way to solve the balance equations.

Recall our earlier image of what is being balanced in the equations. Imagine a large number of independent replications of the chain. For example, suppose a large number of particles are moving among the states according to the transition probabilities of the chain, all moving at instants 1, 2, 3, $\ldots$ independently of each other.

Suppose the chain is in steady state. As we said earlier, if you think of $\pi(k)$ as the proportion of particles leaving state $k$ at any instant, then the balance equations

$$ \pi(j) = \sum_{k \in S} \pi(k)P(k, j) $$

say that the proportion of particles leaving state $j$ is the same as the number of particles entering it. Hence the chain is balanced.

Notice that the left hand side is just the proportion of particles leaving $j$; there is no information about where the particles are going.

Now suppose there is detailed balance, given by

$$ \pi(i)P(i, j) = \pi(j)P(j, i) ~~~ \text{for all states } i \ne j $$

These are called the detailed balance equations. They say that for every pair of states $i$ and $j$, the proportion of particles that leave $i$ and move directly to $j$ is the same as the proportion that leave $j$ and move directly to $i$. In the case $i = j$ the equations carry no information and hence are left out.

That turns out to be a stronger condition than balance.

Detailed Balance Implies Balance¶

Suppose there is a probability distribution $\pi$ that solves the detailed balance equations. Then $\pi$ also solves the balance equations.

\begin{align*} \sum_{k \in S} \pi(k)P(k, j) &= \sum_{k \in S} \pi(j)P(j, k) ~~~ \text{(detailed balance)} \\ &= \pi(j) \sum_{k \in S} P(j, k) \\ &= \pi(j) \cdot 1 ~~~~~~~~~~~~~~ \text{(sum of }j\text{th row of transition matrix)} \\ &= \pi(j) \end{align*}

What we learn from this is that if we can find a solution to the detailed balance equations, we will also have solved the balance equations.

This is helpful for two reasons:

• The detailed balance equations are simple.
• There are lots of them; indeed if there are $s$ states then there are $\binom{s}{2}$ detailed balance equations in $s$ unknowns. This gives us lots of ways to try to solve them.

Of course all the $\binom{s}{2}$ equations need not be consistent, in which case there will not be a solution to the detailed balance equations. In such situations we'll have to slog our way through solving the balance equations directly. But here is an example that shows that if the detailed balance equations do have a solution, we have an easy way at arriving at the stationary distribution of the chain.

Ehrenfest Chain¶

We have returned to this example because it is one where solving the balance equations involves some labor. We will show that for this chain and others like it, the detailed balance equations can easily be solved, giving us a quick route to the stationary distribution.

The state space is the integers 0 through $N$. Recall how the transitions work: at each step, the chain either goes up by 1, stays the same, or goes down by 1. Such chains are called birth and death chains and are used to model many different random quantities such as gamblers' fortunes or population sizes. In our example, we are modeling the size of the population of gas particles in a container.

For such chains, most of the transition probabilities are 0 because in one step the chain can only move to the two neighboring states. So most of the detailed balance equations are trivially true. For the ones the involve positive tranistion probabilities, the states $i$ and $j$ have to be separated by 1 (remember that the detailed balance equations specify $i \ne j$). And in that case both $P(i, j)$ and $P(j, i)$ are positive, as the chain is irreducible.

This allows us to solve the detailed balance equations, for example by starting at the lowest state and moving up. Remember the transition rules:

• At each step, select one of the $N$ particles at random and place it into one of the two containers at random; the chain counts the number of particles in Container 1.

The detailed balance equations are easy to solve sequentially:

\begin{align*} \pi(0)\frac{1}{2} &= \pi(1)\frac{1}{2N} ~~ \implies ~~ \pi(1) = N\pi(0) = \binom{N}{1}\pi(0) \\ \\ \pi(1)\frac{N-1}{2N} &= \pi(2)\frac{2}{2N} ~~ \implies ~~ \pi(2) = \frac{N-1}{2}\pi(1) = \frac{N(N-1)}{2}\pi(0) = \binom{N}{2}\pi(0) \\ \\ \pi(2)\frac{N-2}{2N} &= \pi(3)\frac{3}{2N} ~~ \implies ~~ \pi(3) = \frac{N-2}{3}\pi(2) = \frac{N(N-1)(N-2)}{3\cdot 2} \pi(0) = \binom{N}{3}\pi(0) \end{align*}

and so on, so that for $1 \le k \le N$, $$ \pi(k) = \binom{N}{k} \pi(0) $$ by a far easier induction than the one needed to solve the balance equations. The sum of the terms in the solution is

$$ \pi(0)\big{(} 1 + \sum_{k=1}^N \binom{N}{k} \big{)} = \pi(0)\sum_{k=0}^N \binom{N}{k} = \pi(0)2^N $$

by the binomial theorem. So $\pi(0) = 2^{-N}$ and the stationary distribution is binomial $(N, 1/2)$.

At this point it is worth remembering that for numerical value of $N$ you can just use steady_state to find the stationary distribution, relying on Python to do all the work for you. This has some clear advantages but also some disadvantages:

• Python will not be able to handle the computation when $N$ is very large.
• You will either not see that the distribution is just binomial or will see it and not know why. That is why, even in the age of powerful personal computers, it is still important to find good ways of solving problems using math.

Random Walk on a Circle¶

Suppose a chain has states 0, 1, 2, 3, 4 arranged in sequence clockwise on a circle. Suppose that at each step the chain moves to its clockwise neighbor with probability $p \in (0, 1)$ and to its counterclockwise neighbor with probability $q = 1-p$.

It is clear that the transition matrix is doubly stochastic: each column has one entry equal to $p$ and another equal to $q$, and all the others are 0. So the stationary distribution of the chain is uniform on the five states.

So we don't need the detailed balance equations to find the stationary distribution. But let's see if they are satisfied. Unlike the Ehrenfest chain above, this chain can "loop back around." So it's not clear that the detailed balance equations have to be consistent.

The detailed balance equations are:

\begin{align*} \pi(0)p = \pi(1)q ~~~~ \implies \pi(1) = \frac{p}{q}\pi(0) \\ \pi(1)p = \pi(2)q ~~~~ \implies \pi(2) = \frac{p^2}{q^2}\pi(0) \\ \pi(2)p = \pi(3)q ~~~~ \implies \pi(3) = \frac{p^3}{q^3}\pi(0) \\ \pi(3)p = \pi(4)q ~~~~ \implies \pi(4) = \frac{p^4}{q^4}\pi(0) \end{align*}

So far so good, but now for the moment of truth:

$$ \pi(4)p = \pi(0)q ~~~~ \implies \pi(4) = \frac{q}{p}\pi(0) $$

For this system of equations to be consistent and have a positive solution, the two expressions for $\pi(4)$ must be equal, which is equivalent to

$$ \frac{p^4}{q^4} = \frac{q}{p}, ~~~ \text{that is, } ~p^5 = q^5 $$

This can only happen if $p = 1/2$, and in that case the detailed balance equations say that all the entries of $\pi$ are equal, which we already knew.

To summarize:

• No matter what $p$ is, the stationary distribution of the chain is uniform on all the states. The uniform distribution satisfies the balance equations.
• When $p = 1/2$, the detailed balance equations have a positive solution which is the stationary distribution.
• When $p \ne 1/2$ the detailed balance equations have no solution that is a probability distribution.

Clearly, $p = 1/2$ has a special status. What exactly does that mean for the behavior of this chain? That's the topic of the next section.