Let $\left(X_{n}\right)_{n \geqslant 0}$ be a Markov chain.

(a) What does it mean to say that a state $i$ is positive recurrent? How is this property related to the equilibrium probability $\pi_{i}$ ? You do not need to give a full proof, but you should carefully state any theorems you use.

(b) What is a communicating class? Prove that if states $i$ and $j$ are in the same communicating class and $i$ is positive recurrent then $j$ is positive recurrent also.

A frog is in a pond with an infinite number of lily pads, numbered $1,2,3, \ldots$ She hops from pad to pad in the following manner: if she happens to be on pad $i$ at a given time, she hops to one of pads $(1,2, \ldots, i, i+1)$ with equal probability.

(c) Find the equilibrium distribution of the corresponding Markov chain.

(d) Now suppose the frog starts on pad $k$ and stops when she returns to it. Show that the expected number of times the frog hops is $e(k-1)$ ! where $e=2.718 \ldots$ What is the expected number of times she will visit the lily pad $k+1$ ?