Let $X_{1}, X_{2}, \ldots$ be independent, identically distributed random variables with finite mean $\mu$. Explain what is meant by saying that the random variable $M$ is a stopping time with respect to the sequence $\left(X_{i}: i=1,2, \ldots\right)$.

Let $M$ be a stopping time with finite mean $\mathbb{E}(M)$. Prove Wald's equation:

$$\mathbb{E}\left(\sum_{i=1}^{M} X_{i}\right)=\mu \mathbb{E}(M)$$

[Here and in the following, you may use any standard theorem about integration.]

Suppose the $X_{i}$ are strictly positive, and let $N$ be the renewal process with interarrival times $\left(X_{i}: i=1,2, \ldots\right)$. Prove that $m(t)=\mathbb{E}\left(N_{t}\right)$ satisfies the elementary renewal theorem:

$$\frac{1}{t} m(t) \rightarrow \frac{1}{\mu} \quad \text { as } t \rightarrow \infty .$$

A computer keyboard contains 100 different keys, including the lower and upper case letters, the usual symbols, and the space bar. A monkey taps the keys uniformly at random. Find the mean number of keys tapped until the first appearance of the sequence 'lava' as a sequence of 4 consecutive characters.

Find the mean number of keys tapped until the first appearance of the sequence 'aa' as a sequence of 2 consecutive characters.