What is a martingale? What is a stopping time? State and prove the optional sampling theorem.

Suppose that $\xi_{i}$ are independent random variables with values in $\{-1,1\}$ and common distribution $\mathbb{P}(\xi=1)=p=1-q$. Assume that $p>q$. Let $S_{n}$ be the random walk such that $S_{0}=0, S_{n}=S_{n-1}+\xi_{n}$ for $n \geqslant 1$. For $z \in(0,1)$, determine the set of values of $\theta$ for which the process $M_{n}=\theta^{S_{n}} z^{n}$ is a martingale. Hence derive the probability generating function of the random time

$$\tau_{k}=\inf \left\{t: S_{t}=k\right\}$$

where $k$ is a positive integer. Hence find the mean of $\tau_{k}$.

Let $\tau_{k}^{\prime}=\inf \left\{t>\tau_{k}: S_{t}=k\right\}$. Clearly the mean of $\tau_{k}^{\prime}$ is greater than the mean of $\tau_{k}$; identify the point in your derivation of the mean of $\tau_{k}$ where the argument fails if $\tau_{k}$ is replaced by $\tau_{k}^{\prime}$.