Time Reversible Markov Chain

Definition

A stationary Markov chain is time reversible if it satisfies the detailed balance equation:

${\pi }_i{P}_{ij}={\pi }_j{P}_{ji},\forall i,j$

Interpretation

${\pi }_i$ is the long-run/“overall” proportion of time spent in state $i$. $P_{ij}$ is the transition probability from $i$ to $j$ in one time step.

• $P_{ij}$ alone = probability of going $i\to j$ given you’re already in $i$
• ${\pi }_i{P}_{ij}$ = probability of going $i\to j$ unconditionally, accounting for how often you’re even in $i$ to begin with

Essentially, the rate at which the process goes from $i\to j$ is equal to the rate from $j\to i$.

Theorem: Kolmogorov’s Criterion

A chain is time reversible iff for any cycle of states $i\to i_1\to \cdots \to i_k\to i$, the product of transition probabilities is the same in both directions:

$P_{i,i_1}{P}_{i_1,i_2}\dots P_{i_k,i}=P_{i,i_k}{P}_{i_k,i_{k-1}}\dots P_{i_1,i}$

Examples

• Random Walk on Graphs (with symmetric weights $w_{ij}=w_{ji}$): $P_{ij}=\frac{w_{ij}}{\sum w_{ik}}$ is time reversible
• Ehrenfest Urn: State $i$ (number of balls in Urn 1) is time reversible with ${\pi }_i=\left(\genfrac{}{}{0ex}{}{M}{i}\right)(\frac{1}{2}{)}^M$
• One-closer rule: Reordering rule that is time reversible, unlike move-to-front

Related

• Markov Chain Monte Carlo