Past exam of the mathematics course of the University of Cambridge / 2008 / ii / Paper 1 / 26I (Applied Probability)

A continuous-time Markov chain started with distribution $\pi$ is reversible if its finite-dimensional distributions are unchanged by reversing time: for every $T>0$, $(X_t:0\le t\le T)$ and $(X_{T-t}:0\le t\le T)$ have the same law. In particular, reversibility includes stationarity. The detailed balance equations areFor a finite continuous-time Markov chain, these equations are equivalent to reversibility with initial distribution $\pi$. Equivalently, they imply ${\pi }_i{P}_{ij}(t)={\pi }_j{P}_{ji}(t)$ for every transition matrix $P(t)=e^{tQ}$.

Let $\pi$ be a probability vector satisfying detailed balance. Since each row of the infinitesimal generator matrix sums to zero,Thus $\pi Q=0$, and $\pi e^{tQ}=\pi$ for all $t\ge 0$. This proves that $\pi$ is an stationary distribution. The diagonal term causes no problem because its detailed balance equation is an identity.

A Discrete-time Markov chain with initial distribution $\hat{\pi }$ is reversible if $(Y_0,\dots ,Y_n)$ and $(Y_n,\dots ,Y_0)$ have the same law for every $n$. Its detailed balance equations are ${\hat{\pi }}_i{\hat{P}}_{ij}={\hat{\pi }}_j{\hat{P}}_{ji}$. These equations are equivalent to reversibility. Indeed, reversing every factor in the probability ${\hat{\pi }}_{i_0}{\prod }_{r=1}^n{\hat{P}}_{i_{r-1}{i}_r}$ gives the reverse path probability; the converse follows by taking $n=1$.

Summing detailed balance over $i$ givesHence $\hat{\pi }$ is an stationary distribution.

The jump chain records the successive states visited at actual jumps of the continuous-time Markov chain. Put $q_i=-q_{ii}$. For an irreducible chain with at least two states, all $q_i>0$, and its transition probabilities are ${\hat{P}}_{ij}=q_{ij}/q_i$ for $j\ne i$, with ${\hat{P}}_{ii}=0$. The holding time in state $i$ is exponential with mean $1/q_i$.

If $\pi Q=0$, set $C={\sum }_i{\pi }_i{q}_i$ and ${\hat{\pi }}_i={\pi }_i{q}_i/C$. ThenConversely, $\hat{\pi }\hat{P}=\hat{\pi }$ implies that ${\pi }_i=c{\hat{\pi }}_i/q_i$, normalized to sum one, satisfies $\pi Q=0$. ThereforeJump observations overrepresent states with short holding times. A one-state chain has no actual jumps; its trivial equilibrium can be handled separately, without using this division by $q_i=0$.

Use the equilibrium correspondence from the preceding part. For $i\ne j$,Consequently the detailed balance equations for the jump chain hold exactly when those for the continuous-time Markov chain hold. The reversibility characterizations already given prove the equivalence. Both chains here are started in their respective stationary distributions, which generally differ.

Write $q_{ij}=c{m}_{ij}$ for $i\ne j$, with a common positive constant $c$, and put $d_i={\sum }_{j\ne i}{m}_{ij}$. The infinitesimal generator matrix is symmetric because the graph is undirected. Thus the uniform distribution ${\pi }_i=1/|I|$ satisfies detailed balance, and the continuous-time random walk is reversible when started uniformly.

Its jump chain chooses a link uniformly from those incident to its current vertex:The flux ${\hat{\pi }}_i{\hat{P}}_{ij}=m_{ij}/{\sum }_j{d}_j$ is symmetric, so this random walk on a multigraph is also reversible. The continuous-time equilibrium is uniform because higher-degree vertices have shorter holding times; at jump times the equilibrium is degree-weighted. If the intended proportionality constant depends on the starting vertex, $q_{ij}=c_i{m}_{ij}$, reversibility still holds with ${\pi }_i\propto 1/c_i$, and the same jump chain results.