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

Until the walk first reaches $B$, it is the simple random walk on a path of length $n$ with reflection at the endpoint $A$. If $h_i$ is the expected hitting time of $B$ from the vertex at distance $i$ from $A$, thenSolving this second-difference equation gives $h_i=n^2-i^2$. Therefore

A complete excursion from $B$ along any one arm and back to $B$ has mean length $L=2n$. This follows from the same path recurrence, or from Kac's lemma: the graph has $3n$ edges, the stationary distribution of simple random walk assigns mass $\mathrm{deg}(B)/(2|E|)=3/(6n)=1/(2n)$ to $B$, so its mean return time is $L=2n$.

Let $x$ be the mean time to hit $E$ starting at $B$. On each visit to $B$, the first step reaches $E$ with probability $1/3$; with probability $2/3$ it begins a wrong-arm excursion of mean duration $L$, after which the problem restarts. ThusThe walk first takes mean time $n^2$ to reach $B$, so the requested time from $A$ is

Let $v_i$ be the vertex $i$ steps from $B$ toward $C$, and let $x_i$ be the mean time to reach $v_{i+1}$ from $v_i$. Part (b) gives $x_0=4n+1$. For $1\le i<n$, first-step analysis at $v_i$ givesbecause a step to $v_{i-1}$ must be followed by a fresh passage of mean $x_{i-1}$ back to $v_i$ before trying again. HenceBy the Strong Markov property, the expected time from $B$ to $C$ is the sum of these successive passage times:Adding the initial mean time $n^2$ from $A$ to $B$ gives