Let $\left(X_{n}\right)_{n \geqslant 0}$ be a simple, symmetric random walk on the integers $\{\ldots,-1,0,1, \ldots\}$, with $X_{0}=0$ and $\mathbb{P}\left(X_{n+1}=i \pm 1 \mid X_{n}=i\right)=1 / 2$. For each integer $a \geqslant 1$, let $T_{a}=\inf \left\{n \geqslant 0: X_{n}=a\right\}$. Show that $T_{a}$ is a stopping time.

Define a random variable $Y_{n}$ by the rule

$$Y_{n}= \begin{cases}X_{n} & \text { if } n<T_{a} \\ 2 a-X_{n} & \text { if } n \geqslant T_{a}\end{cases}$$

Show that $\left(Y_{n}\right)_{n} \geqslant 0$ is also a simple, symmetric random walk.

Let $M_{n}=\max _{0 \leqslant i \leqslant n} X_{n}$. Explain why $\left\{M_{n} \geqslant a\right\}=\left\{T_{a} \leqslant n\right\}$ for $a \geqslant 0$. By using the process $\left(Y_{n}\right)_{n \geqslant 0}$ constructed above, show that, for $a \geqslant 0$,

$$\mathbb{P}\left(M_{n} \geqslant a, X_{n} \leqslant a-1\right)=\mathbb{P}\left(X_{n} \geqslant a+1\right),$$

and thus

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

Hence compute

$$\mathbb{P}\left(M_{n}=a\right)$$

when $a$ and $n$ are positive integers with $n \geqslant a$. [Hint: if $n$ is even, then $X_{n}$ must be even, and if $n$ is odd, then $X_{n}$ must be odd.]