Past exam of the mathematics course of the University of Cambridge / 2013 / ib / Paper 1 / 20H / i / Solution

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.