For a Markov chain $X$ on a state space $S$ with $u, v \in S$, we let $p_{u v}(n)$ for $n \in\{0,1, \ldots\}$ be the probability that $X_{n}=v$ when $X_{0}=u$.

(a) Let $X$ be a Markov chain. Prove that if $X$ is recurrent at a state $v$, then $\sum_{n=0}^{\infty} p_{v v}(n)=\infty$. [You may use without proof that the number of returns of a Markov chain to a state $v$ when starting from $v$ has the geometric distribution.]

(b) Let $X$ and $Y$ be independent simple symmetric random walks on $\mathbb{Z}^{2}$ starting from the origin 0 . Let $Z=\sum_{n=0}^{\infty} \mathbf{1}_{\left\{X_{n}=Y_{n}\right\}}$. Prove that $\mathbb{E}[Z]=\sum_{n=0}^{\infty} p_{00}(2 n)$ and deduce that $\mathbb{E}[Z]=\infty$. [You may use without proof that $p_{x y}(n)=p_{y x}(n)$ for all $x, y \in \mathbb{Z}^{2}$ and $n \in \mathbb{N}$, and that $X$ is recurrent at 0.]