Let $\left(X_{n}\right)_{n \geqslant 0}$ be a simple symmetric random walk on the integers, starting at $X_{0}=0$.

(a) What does it mean to say that a Markov chain is irreducible? What does it mean to say that an irreducible Markov chain is recurrent? Show that $\left(X_{n}\right)_{n} \geqslant 0$ is irreducible and recurrent.

[Hint: You may find it helpful to use the limit

$$\lim _{k \rightarrow \infty} \sqrt{k} 2^{-2 k}\left(\begin{array}{c} 2 k \\ k \end{array}\right)=\sqrt{\pi}$$

You may also use without proof standard necessary and sufficient conditions for recurrence.]

(b) What does it mean to say that an irreducible Markov chain is positive recurrent? Determine, with proof, whether $\left(X_{n}\right)_{n \geqslant 0}$ is positive recurrent.

(c) Let

$$T=\inf \left\{n \geqslant 1: X_{n}=0\right\}$$

be the first time the chain returns to the origin. Compute $\mathbb{E}\left[s^{T}\right]$ for a fixed number $0<s<1$.