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

A distribution $\pi$ is an invariant distribution whenfor every state $j$. The pair $(\pi ,P)$ satisfies detailed balance whenfor every $i,j$. Summing this identity over $i$ givesso detailed balance implies invariance.

For an irreducible positive recurrent Markov chain, Kac's lemma relates the invariant mass to the mean recurrence time:

The renewal-reward form of Kac's lemma says that the expected number of visits to state $i$ during one return cycle from $k$ to $k$ isHere time spent means the number of discrete time instants at which the chain occupies $i$ between consecutive visits to $k$.

The chain is a birth-death chain. Detailed balance between $0$ and $1$ givesFor $i\ge 1$, detailed balance between $i$ and $i+1$ givesConsequentlyThe expected occupation time of the positive even states during a return cycle to state $1$ is therefore

Normalizing the invariant distribution found in part (i) givesThe mean recurrence time formula now yields

Let $h_i={\mathbb{E}}_i{T}_0$ be the expected hitting time of state $0$. For $i\ge 1$, first-step analysis givesWith $d_i=h_i-h_{i-1}$ this becomesThe minimal nonnegative solution hasso

Equivalently, Kac's lemma gives ${\mathbb{E}}_0{T}_0^{+}=1/{\pi }_0$. A first step from $0$ either returns immediately with probability $1-p$ or moves to $1$ with probability $p$, soSubstituting ${\pi }_0=(q-1)/(q-1+q^{2}p)$ gives the same result.