25 - Time-Reversal of a Markov Chain

Time-Reversal of a Markov Chain

Let $P$ be an irreducible transition matrix with stationary distribution $\pi$
Let $(X_0,X_1,\cdots ,X_N)$ be $\mathrm{Markov}(\pi ,P)$

For $0\le n\le N$ define

$$Y_n=X_{N-n}$$

Then

$$(Y_0,Y_1,\cdots ,Y_N)\text{ is }\mathrm{Markov}(\pi ,Q)$$

where transition matrix $Q=(q_{ij})$ is defined by

$$q_{ij}=\frac{{\pi }_j}{{\pi }_i}{p}_{ij}$$

and matrix $Q$ has stationary distribution $\pi$

Note that chain $Y$ is called the time-reversal of chain $X$

Proof

As

$$\sum _j{q}_{ij}=\frac{1}{{\pi }_i}\sum _j{\pi }_j{p}_{ji}=\frac{1}{{\pi }_i}{\pi }_i=1$$

Then $Q$ is a stochastic matrix

As $\pi$ is stationary for $P$ then

$$\sum _i{\pi }_i{q}_{ij}={\pi }_j\sum _i{p}_{ji}={\pi }_j$$

So $\pi$ is stationary for $Q$

Consider sequence of states $i_0,i_1,\cdots ,i_N$ then

$$\begin{array}{rl}\mathbb{P}(Y_0=i_0,& Y_1=i_1,\cdots ,Y_N=i_N)\\ & =\mathbb{P}(X_0=i_N,X_1=i_{N-1},\cdots ,X_N=i_0)\\ & ={\pi }_{i_N}{p}_{i_N{i}_{N-1}}{p}_{i_{N-1}{i}_{N-2}}\cdots p_{i_2{i}_1}{p}_{i_1{i}_0}\\ & ={\pi }_{i_N}\left(q_{i_{N-1}{i}_N}\frac{{\pi }_{i_{N-1}}}{{\pi }_{i_N}}\right)\left(q_{i_{N-2}{i}_{N-1}}\frac{{\pi }_{i_{N-2}}}{{\pi }_{i_{N-1}}}\right)\cdots \left(q_{i_1{i}_2}\frac{{\pi }_{i_1}}{{\pi }_{i_2}}\right)\left(q_{i_0{i}_1}\frac{{\pi }_{i_0}}{{\pi }_{i_1}}\right)\\ & ={\pi }_{i_0}{q}_{i_0{i}_1}{q}_{i_1{i}_2}\cdots q_{i_{N-2}{i}_{N-1}}{q}_{i_{N-1}{i}_N}\end{array}$$

Hence

$$Y\sim \mathrm{Markov}(\pi ,Q)$$