(i) Give the definitions of a recurrent and a null recurrent irreducible Markov chain.

Let $\left(X_{n}\right)$ be a recurrent Markov chain with state space $I$ and irreducible transition matrix $P=\left(p_{i j}\right)$. Prove that the vectors $\gamma^{k}=\left(\gamma_{j}^{k}, j \in I\right), k \in I$, with entries $\gamma_{k}^{k}=1$ and

$$\gamma_{i}^{k}=\mathbb{E}_{k}(\# \text { of visits to } i \text { before returning to } k), \quad i \neq k,$$

are $P$-invariant:

$$\gamma_{j}^{k}=\sum_{i \in I} \gamma_{i}^{k} p_{i j}$$

(ii) Let $\left(W_{n}\right)$ be the birth and death process on $\mathbb{Z}_{+}=\{0,1,2, \ldots\}$ with the following transition probabilities:

$$\begin{aligned} &p_{i, i+1}=p_{i, i-1}=\frac{1}{2}, i \geq 1 \\ &p_{01}=1 \end{aligned}$$

By relating $\left(W_{n}\right)$ to the symmetric simple random walk $\left(Y_{n}\right)$ on $\mathbb{Z}$, or otherwise, prove that $\left(W_{n}\right)$ is a recurrent Markov chain. By considering invariant measures, or otherwise, prove that $\left(W_{n}\right)$ is null recurrent.

Calculate the vectors $\gamma^{k}=\left(\gamma_{i}^{k}, i \in \mathbb{Z}_{+}\right)$for the chain $\left(W_{n}\right), k \in \mathbb{Z}_{+}$.

Finally, let $W_{0}=0$ and let $N$ be the number of visits to 1 before returning to 0 . Show that $\mathbb{P}_{0}(N=n)=(1 / 2)^{n}, n \geq 1$.

[You may use properties of the random walk $\left(Y_{n}\right)$ or general facts about Markov chains without proof but should clearly state them.]