Past exam of the mathematics course of the University of Cambridge / 2013 / ib / Paper 1 / 20H (Markov Chains)

First realize the chain as a random walk on a multigraph: put three parallel edges between $a,b$, two between $a,c$, and one between $b,c$. There are six edges and vertex degrees $5,4,3$. Choosing an incident edge uniformly gives exactly the stated transition probabilities. The stationary distribution of a graph random walk is the degree divided by twelve, $\pi =(5,4,3)/12$, and detailed balance follows because each edge multiplicity contributes the same flux in both directions.

For the first positive return time, Kac's lemma givesFor passage to $b$, put $h_a=k(a,b)$ and $h_c=k(c,b)$. The first-step equations are $h_a=1+(2/5)h_c$ and $h_c=1+(2/3)h_a$, since reaching $b$ stops the clock. ThusA multigraph is essential: a simple graph on three vertices cannot have six edges.

Let $T_i$ be the expected time to complete the specified directed transition, starting at $i$. This is a transition-completion time in a Markov chain, rather than merely a first visit to $c$. First-step decomposition givesThe missing $b\to c$ continuation in the middle equation represents successful completion, but its step is counted by the leading one. Substitution givesThus the requested expectation from $a$ is $128/11$ steps.

The chain is a reversible Markov chain, so detailed balance makes the stationary path probabilityA path contains an ordered occurrence of $a$ followed later by $b$ exactly when its reversal contains $b$ followed later by $a$. These occurrences need not be adjacent. Therefore $\mathrm{Pr}(\tau (a,b)\le m)=\mathrm{Pr}(\tau (b,a)\le m)$ for every $m$, and in particular the two finite expectations are equal. This is ordered-state visit times in a reversible chain.

To decompose the expectations, distinguish the entrance time $h(i,j)$, which allows time zero and has $h(j,j)=0$, from the positive return convention $k(j,j)$ in part (i). The Strong Markov property at the first visit to $a$ or $b$ givesEquating them yields the difference formula with $h$. Replacing $h$ by $k$ in the sum adds ${\pi }_{a}k(a,a)-{\pi }_{b}k(b,b)=1-1=0$, again by Kac's lemma. HenceFor a numerical consistency check, the other entrance times are $k(b,a)=15/11$ and $k(c,a)=16/11$, while $k(b,b)=3$. Both sides of the displayed identity equal $-6/11$.