(a) Let $k \in\{1,2, \ldots\}$. For $j \in\{0, \ldots, k+1\}$, let $D_{j}$ be the first time at which a simple symmetric random walk on $\mathbb{Z}$ with initial position $j$ at time 0 hits 0 or $k+1$. Show $\mathbb{E}\left(D_{j}\right)=j(k+1-j)$. [If you use a recursion relation, you do not need to prove that its solution is unique.]

(b) Let $\left(S_{n}\right)$ be a simple symmetric random walk on $\mathbb{Z}$ starting at 0 at time $n=0$. For $k \in\{1,2, \ldots\}$, let $T_{k}$ be the first time at which $\left(S_{n}\right)$ has visited $k$ distinct vertices. In particular, $T_{1}=0$. Show $\mathbb{E}\left(T_{k+1}-T_{k}\right)=k$ for $k \geqslant 1$. [You may use without proof that, conditional on $S_{T_{k}}=i$, the random variables $\left(S_{T_{k}+n}\right)_{n \geqslant 0}$ have the distribution of a simple symmetric random walk starting at $i$.]

(c) For $n \geqslant 3$, let $\mathbb{Z}_{n}$ be the circle graph consisting of vertices $0, \ldots, n-1$ and edges between $k$ and $k+1$ where $n$ is identified with 0 . Let $\left(Y_{i}\right)$ be a simple random walk on $\mathbb{Z}_{n}$ starting at time 0 from 0 . Thus $Y_{0}=0$ and conditional on $Y_{i}$ the random variable $Y_{i+1}$ is $Y_{i} \pm 1$ with equal probability (identifying $k+n$ with $k$ ).

The cover time $T$ of the simple random walk on $\mathbb{Z}_{n}$ is the first time at which the random walk has visited all vertices. Show that $\mathbb{E}(T)=n(n-1) / 2$.