Time reversal

For Markov Chains, the past and the future are indipendent, given the present. This suggests looking at the Markov Chain with time running backwards. On the other end, Convergence to equilibrium for ergodic chains is an irreversible process. So we must start at equilibrium.

Theorem Let $P$ be irreducible and have an invariant distribution $\pi$. Suppose that $(X_n{)}_{n\ge 0}\sim Markov(\pi ,P)$ define the reverse chain $Y_n=X_{N-n}$. Then $(Y_n{)}_{0\le n\le N}$ is $Markov(\pi ,\tilde{P})$, where the new transition matrix is given by

$$(\tilde{P}{)}_{ji}=\frac{{\pi }_i}{{\pi }_j}(P{)}_{ij}$$

and $\tilde{P}$ is also irreducible with invariant distribution $\pi$.

Proof First we check that $\tilde{P}$ is a stochastic matrix:

$$\sum _i(\tilde{P}{)}_{ji}=\sum _i\frac{{\pi }_i}{{\pi }_j}(P{)}_{ij}=\frac{1}{{\pi }_j}{\pi }_j=1$$

next we check that $\pi$ is invariant for $\tilde{P}$:

$$\sum _j{\pi }_j(\tilde{P}{)}_{ji}=\sum _j{\pi }_j\frac{{\pi }_i}{{\pi }_j}(P{)}_{ij}={\pi }_i$$

To prove that $Y_n$ is $Markov(\pi ,\tilde{P})$ we use this characterization of Markov Chains:

$$P(Y_0=i_0,\dots Y_N=i_N)=P(X_N=i_0,\dots X_0=i_N)$$ $$={\pi }_{i_N}{p}_{i_N,i_{N-1}}\dots p_{i_1,i_0}$$

using the definition of $\tilde{P}$, $p_{i_1,i_0}=\frac{{\pi }_{i_0}}{{\pi }_{i_1}}{\tilde{p}}_{i_0,i_1}$

$$={\pi }_{i_N}\frac{{\pi }_{i_{N-1}}}{{\pi }_N}{\tilde{p}}_{i_{N-1},i_N}\cdots ={\pi }_{i_0}{\tilde{p}}_{i_0,i_1}\dots {\tilde{p}}_{i_{N-1},i_N}$$

so that $Y\sim Markov(\pi ,\tilde{P})$. Irreducibility follows from reversing a given path. $\square$