Reversible Markov Chain

Posted on by

1. Definition

Let X_1, X_2, cdots be a Markov chain with transition probabilities P_{ij}.

P_{ij} = Pr{X_{n+1} = j| X_n = i}

E.g. A sample realization is 1, 2, 3, 4, 5

Let X_n, x_{n-1}, cdots be the same sequence in reverse, i.e. cdots, 5, 4, 3, 2, 1, cdots

Let Q_{ij} be the transition probabilities of the reversed process. That is
Q_{ij} = Pr{X_{n-1} = j |X_n = i}
              = frac{Pr{X_{n-1} =j, X_n = i}}{Pr{X_n = i}}
              = frac{Pr{X_{n-1} = j} Pr{X_n =i | X_{n-1} = j}}{Pr{X_n = i}}
              = frac{Pr{X_{n-1} = j} P_{ji}}{Pr{X_n = i}}

2. Conclusion

In the steady state, assuming the limiting probabilities exist, we have
Q_{ij} = frac{pi_j P_{ji}}{pi_i}  or pi_i Q_{ij} = pi_j Q_{ji}

The above equation is saying that the rate of transmissions from i to j in the reversed chain is equal to the rate of transitions from j to i in the forward chain.

A DTMC is time reversible if Q_{ij} = P_{ij}

Leave a Reply