The Markov property, that the past and future are independent given the present, essentially treats the past and future symmetrically. However, there is a lack of symmetry in the fact that, in the usual formulation, we have an initial time 0, but not a terminal time. If we introduce a terminal time, then we can run the process backwards in time. In this section, we are interested in the following questions:
As usual, our starting point is a (time homogeneous) Markov chain \( \bs{X} = (X_0, X_1, X_2, \ldots) \) with state space \( S \) and transition probability matrix \( P \). Let \( m \) be a positive integer, which we will think of as the terminal time. Define \( Y_n = X_{m-n} \) for \( n \in \{0, 1, \ldots, m\} \). Thus, the process forward in time is \( \bs{X}_m = (X_0, X_1, \ldots, X_m) \) while the process backwards in time in \( \bs{Y_m} = (Y_0, Y_1, \ldots, Y_m) = (X_m, X_{m-1}, \ldots, X_0) \).
For every positive integer \( n \lt m \) and for every sequence of states \( (x_0, x_1, \ldots, x_{n-1}, x, y) \),
\[ \P(Y_{n+1} = y \mid Y_0 = x_0, Y_1 = x_1, \ldots, Y_{n-1} = x_{n-1}, Y_n = x) = \frac{\P(X_{m-n+1} = y) P(y, x)}{\P(X_{m-n} = x)} \]This result follows from the definition of conditional probability and the Markov property for \( \bs{X} \).
Since the right-hand side depends only on \( x \), \( y \), \( n \), and \( m \), the backwards process \( \bs{Y}_m \) is a Markov chain, but is not time-homogeneous in general. Note however, that the backwards chain will be time homogeneous if \( X_0 \) has an invariant distribution. Thus, from now on, we will assume that our original chain \( \bs{X} \) is irreducible and positive recurrent with (unique) invariant probability density function \( f \).
If \( X_0 \) has probability density function \( f \), then \( \bs{Y}_m \) is a time-homogeneous Markov chain with transition probability matrix \( Q \) given by
\[ Q(x, y) = \frac{f(y) P(y, x)}{f(x)}, \quad (x, y) \in S^2 \]This follows from Theorem 1. Recall that if \( X_0 \) has PDF \( f \), then \( X_i \) has PDF \( f \) for each \( i \in \N \).
If \( X_0 \) does not have probability density function \( f \), but \( \bs{X} \) is aperiodic, then the expression in Theorem 1 converges to \( Q(x, y) \) defined in Theorem 2 as \( n \to \infty \).
This follows from our study of the limiting behavior of Markov chains. Since \( \bs{X} \) is irreducible and positive recurrent, \( \P(X_k = x) \to f(x) \) as \( k \to \infty \) for every \( x \in S \).
Thus, we now define the time reverse of the chain \( \bs{X} = (X_0, X_1, X_2, \ldots) \) to be the Markov chain \( \bs{Y} = (Y_0, Y_1, Y_2, \ldots) \) with transition probability matrix \( Q \) defined in Theorem 2, regardless of the initial distribution of \( \bs{X} \) and without regard to a finite time horizon \( m \). The results in Theorem 1, Theorem 2, and Theorem 3 are motivation for this definition. Note that the fundamental relationship between the transition probability matrices \( P \) and \( Q \) is
\[ f(x) Q(x, y) = f(y) P(y, x), \quad (x, y) \in S^2 \]For \( x, \; y \in S \),
From part (b) it follows that the graphs of \( \bs{X} \) and \( \bs{Y} \) are reverses of each other. That is, to go from the graph of one chain to the graph of the other, simply reverse the direction of each edge.
For every sequence of states \( (x_1, x_2, \ldots, x_n) \),
\[ f(x_1) Q(x_1, x_2) Q(x_2, x_3) \cdots Q(x_{n-1}, x_n) = f(x_n) P(x_n, x_{n-1}) \cdots P(x_3, x_2) P(x_2, x_1) \]For every \( (x, y) \in S^2 \) and \( n \in \N \),
\[ f(x) Q^n(x, y) = f(y) P^n (y, x) \]The following properties hold:
Suppose that \( \bs{X} \) is only assumed to be irreducible. If there exists a probability density function \( f \) and a transition probability matrix \( Q \) such that \( f(x) Q(x, y) = f(y) P(y, x) \) for all \( (x, y) \in S^2 \), then
Clearly, an interesting special case occurs when the transition probability matrix of the time-reversed chain turns out to be the same as the original transition probability matrix. A chain of this type could be used to model a physical process that is stochastically the same, forward or backward in time.
Suppose again that \( \bs{X} = (X_0, X_1, X_2, \ldots) \) is an irreducible, positive recurrent Markov chain with transition probability matrix \( P \) and invariant probability density function \( f \). The chain \( \bs{X} \) is said to be reversible if
\[ f(x) P(x, y) = f(y) P(y, x), \quad (x, y) \in S^2 \]Thus, \( P \) is also the transition probability matrix of the time-reversed chain. Specifically, by Theorem 2, if \( X_0 \) has probability density function \( f \), then \( P \) is the transition probability matrix of the chain backwards in time relative to any terminal time \( m \).
\( \bs{X} \) is reversible if and only if for every sequence of states \( (x_1, x_2, \ldots x_n) \),
\[ f(x_1) P(x_1, x_2) P(x_2, x_3) \cdots P(x_{n-1}, x_n) = f(x_n) P(x_n, x_{n-1}), \cdots P(x_3, x_2) P(x_2, x_1) \]\( \bs{X} \) is reversible if and only if for every \( (x, y) \in S^2 \) and \( n \in \N \),
\[ f(x) P^n(x, y) = f(y) P^n(y, x) \]The basic reversibility condition uniquely determines the invariant probability density function.
Suppose that \( \bs{X} \) is only assumed to be irreducible. If there exists a probability density function \( f \) such that \( f(x) P(x, y) = f(y) P(y, x) \) for all \( (x, y) \in S^2 \), then
If we have reason to believe that a Markov chain is reversible (based on modeling considerations, for example), then the condition in the previous exercise can be used to find the invariant probability density function \( f \). This procedure is often easier than using the definition of invariance directly.
The following exercise gives a condition for reversibility that does not directly reference the invariant distribution. The condition is known as the Kolmogorov cycle condition, and is named for Andrei Kolmogorov
Suppose that \( \bs{X} \) is irreducible and positive recurrent. Then \( \bs{X} \) is reversible if and only if for every sequence of states \( (x_1, x_2, \ldots, x_n) \),
\[ P(x_1, x_2) P(x_2, x_3) \cdots P(x_{n-1}, x_n) P(x_n, x_1) = P(x_1, x_n) P(x_n, x_{n-1}) \cdots P(x_3, x_2) P(x_2, x_1) \]Suppose that \( \bs{X} \) is reversible. Applying the definition gives the Kolmogorov cycle condition. Conversely, suppose that the Kolmogorov cycle condition holds. Then \( P(x, y) P^k(y, x) = P(y, x)P^k(x, y) \) for every \( (x, y) \in S \) and \( n \in \N_+ \). Averaging over \( k \) from 1 to \( n \) gives
\[ P(x, y) \frac{1}{n} G_n(y, x) = P(y, x) \frac{1}{n} G_n(x, y), \quad (x, y) \in S^2, \; n \in \N_+ \]Letting \( n \to \infty \) we have \( f(x) P(x, y) = f(y) P(y, x) \) for \( (x, y) \in S^2 \), so \( \bs{X} \) is reversible.
Note that the Kolmogorov cycle condition states that the probability of visiting states \( (x_2, x_3, \ldots, x_n, x_1) \) in sequence, starting in state \( x_1 \) is the same as the probability of visiting states \( (x_n, x_{n-1}, \ldots, x_2, x_1) \) in sequence, starting in state \( x_1 \).
Recall the general two-state chain \( \bs{X} \) on \( S = \{0, 1\} \) with the transition probability matrix
\[ P = \left[ \begin{matrix} 1 - p & p \\ q & 1 - 1 \end{matrix} \right] \]where \( p \in (0, 1) \) and \( q \in (0, 1) \) are parameters. The chain \( \bs{X} \) is reversible and the invariant probability density function is \( f = \left( \frac{q}{p + q}, \frac{p}{p + q} \right) \).
Suppose that \( \bs{X} \) is a Markov chain on a finite state space \( S \) with symmetric transition probability matrix \( P \). Thus \( P(x, y) = P(y, x) \) for all \( (x, y) \in S^2 \). The chain \( \bs{X} \) is reversible and that the uniform distribution on \( S \) is invariant.
Consider the Markov chain \( \bs{X} \) on \( S = \{a, b, c\} \) with transition probability matrix \( P \) given below:
\[ P = \left[ \begin{matrix} \frac{1}{4} & \frac{1}{4} & \frac{1}{2} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{1}{2} & \frac{1}{2} & 0 \end{matrix} \right] \]Read the discussion of reversibility for the Ehrenfest chains.
Read the discussion of reversibility for the Bernoulli-Laplace chain.
Read the discussion of reversibility for the random walks on graphs.
Read the discussion of time reversal for the reliability chains.
Read the discussion of reversibility for the birth-death chains.