(i) Let $\mathcal{F}=\left\{\mathcal{F}_{n}\right\}_{n=0}^{\infty}$ be a filtration. Give the definition of a martingale and a stopping time with respect to the filtration $\mathcal{F}$.

(ii) State Doob's optional stopping theorem. Give an example of a martingale $M$ and a stopping time $T$ such that $\mathbb{E}\left(M_{T}\right) \neq \mathbb{E}\left(M_{0}\right)$.

(iii) Let $S_{n}$ be a standard random walk on $\mathbb{Z}$, that is, $S_{0}=0, S_{n}=X_{1}+\ldots+X_{n}$, where $X_{i}$ are i.i.d. and $X_{i}=1$ or $-1$ with probability $1 / 2$.

Let $T_{a}=\inf \left\{n \geqslant 0: S_{n}=a\right\}$ where $a$ is a positive integer. Show that for all $\theta>0$,

$$\mathbb{E}\left(e^{-\theta T_{a}}\right)=\left(e^{\theta}-\sqrt{e^{2 \theta}-1}\right)^{a} .$$

Carefully justify all steps in your derivation.

[Hint. For all $\lambda>0$ find $\theta$ such that $M_{n}=\exp \left(-\theta n+\lambda S_{n}\right)$ is a martingale. You may assume that $T_{a}$ is almost surely finite.]

Let $T=T_{a} \wedge T_{-a}=\inf \left\{n \geqslant 0:\left|S_{n}\right|=a\right\}$. By introducing a suitable martingale, compute $\mathbb{E}\left(e^{-\theta T}\right)$.