Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 215 / 1

A stopping time $T$ is a strong stationary time iffor every $x,y,t$. Thus $X_T\sim \pi$ and is independent of $T$. The separation distance isFor any strong stationary time,Hence $1-P^t(x,y)/\pi (y)\le {\mathbb{P}}_x(T>t)$, and maximizing proves the claim.

Observe the lazy walk on ${\mathbb{Z}}_{2^k}$ only after every second genuine jump. Two independent nearest-neighbor signs have sum $-2,0,2$ with probabilities $1/4,1/2,1/4$. Division by two therefore produces one step of the lazy simple random walk on ${\mathbb{Z}}_{2^{k-1}}$. The Strong Markov property at successive jump times proves

At $T_{{\tau }_{k-1}}^{(k)}$, part b and the strong-stationarity assumption make $X^{(k)}/2$ uniform on ${\mathbb{Z}}_{2^{k-1}}$ and independent of the stopping index. One further lazy step either stays or moves by one, each parity occurring with probability one half; conditional on the even residue already selected, this chooses uniformly between its two lifts to ${\mathbb{Z}}_{2^k}$. Thushas a uniform terminal state independent of ${\tau }_k$, and is a strong stationary time.

Take ${\tau }_0=0$ and apply part c recursively. A lazy walk makes a genuine jump with probability $1/2$, so the expected time required for $2j$ jumps is $4j$. Using the stated independence,The initial value zero solves this recurrence as