Let \(X_{1}, X_{2}, \ldots\) be a sequence of independent random variables. The
nonnegative integer valued random variable \(N\) is said to be a stopping time
for the sequence if the event \(\\{N=n\\}\) is independent of \(X_{n+1}, X_{n+2},
\ldots .\) The idea being that the \(X_{i}\) are observed one at a time-first
\(X_{1}\), then \(X_{2}\), and so on-and \(N\) represents the number observed when
we stop. Hence, the event \(\\{N=n\\}\) corresponds to stopping after having
observed \(X_{1}, \ldots, X_{n}\) and thus must be independent of the values of
random variables yet to come, namely, \(X_{n+1}, X_{n+2}, \ldots\)
(a) Let \(X_{1}, X_{2}, \ldots\) be independent with
$$
P\left[X_{i}=1\right\\}=p=1-P\left(X_{i}=0\right\\}, \quad i \geqslant 1
$$
Define
$$
\begin{aligned}
&N_{1}=\min \left[n: X_{1}+\cdots+X_{n}=5\right\\} \\
&N_{2}=\left\\{\begin{array}{ll}
3, & \text { if } X_{1}=0 \\
5, & \text { if } X_{1}=1
\end{array}\right. \\
&N_{3}=\left\\{\begin{array}{ll}
3, & \text { if } X_{4}=0 \\
2, & \text { if } X_{4}=1
\end{array}\right.
\end{aligned}
$$
Which of the \(N_{i}\) are stopping times for the sequence \(X_{1}, \ldots ?\) An
important result, known as Wald's equation states that if \(X_{1}, X_{2},
\ldots\) are independent and identically distributed and have a finite mean
\(E(X)\), and if \(N\) is a stopping time
for this sequence having a finite mean, then
$$
E\left[\sum_{i=1}^{N} X_{i}\right]=E[N] E[X]
$$
To prove Wald's equation, let us define the indicator variables \(I_{i}, i
\geqslant 1\) by
$$
I_{i}=\left\\{\begin{array}{ll}
1, & \text { if } i \leqslant N \\
0, & \text { if } i>N
\end{array}\right.
$$
(b) Show that
$$
\sum_{i=1}^{N} X_{i}=\sum_{i=1}^{\infty} X_{i} I_{i}
$$
From part (b) we see that
$$
\begin{aligned}
E\left[\sum_{i=1}^{N} X_{i}\right] &=E\left[\sum_{i=1}^{\infty} X_{i}
I_{i}\right] \\
&=\sum_{i=1}^{\infty} E\left[X_{i} I_{i}\right]
\end{aligned}
$$
where the last equality assumes that the expectation can be brought inside the
summation (as indeed can be rigorously proven in this case).
(c) Argue that \(X_{i}\) and \(I_{i}\) are independent. Hint: \(I_{i}\) equals 0 or
1 depending on whether or not we have yet stopped after observing which random
variables?
(d) From part (c) we have
$$
E\left[\sum_{i=1}^{N} X_{i}\right]=\sum_{i=1}^{\infty} E[X]
E\left[I_{i}\right]
$$
Complete the proof of Wald's equation.
(e) What does Wald's equation tell us about the stopping times in part (a)?
