For a symmetric simple random walk $\left(X_{n}\right)$ on $\mathbb{Z}$ starting at 0 , let $M_{n}=\max _{i \leqslant n} X_{i}$.

(i) For $m \geqslant 0$ and $x \in \mathbb{Z}$, show that

$$\mathbb{P}\left(M_{n} \geqslant m, X_{n}=x\right)= \begin{cases}\mathbb{P}\left(X_{n}=x\right) & \text { if } x \geqslant m \\ \mathbb{P}\left(X_{n}=2 m-x\right) & \text { if } x<m\end{cases}$$

(ii) For $m \geqslant 0$, show that $\mathbb{P}\left(M_{n} \geqslant m\right)=\mathbb{P}\left(X_{n}=m\right)+2 \sum_{x>m} \mathbb{P}\left(X_{n}=x\right)$ and that

$$\mathbb{P}\left(M_{n}=m\right)=\mathbb{P}\left(X_{n}=m\right)+\mathbb{P}\left(X_{n}=m+1\right)$$

(iii) Prove that $\mathbb{E}\left(M_{n}^{2}\right)<\mathbb{E}\left(X_{n}^{2}\right)$.