Question

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)?

Short answer

The stopping times for the given sequence of random variables are \(N_1\) and \(N_2\), as the value of \(N_1\) is determined by the sum of random variables and \(N_2\) relies only on the value of \(X_1\). Wald's equation holds for these stopping times, implying that \(E\left[\sum_{i=1}^{N_1} X_{i}\right]=E[N_1] E[X]\) and \(E\left[\sum_{i=1}^{N_2} X_{i}\right]=E[N_2] E[X]\) are valid for stopping times \(N_1\) and \(N_2\). \(N_3\) is not a stopping time, as it relies on the value of \(X_4\), so we cannot find a relationship between the expected values of the sum of random variables and the stopping time \(N_3\).

Step-by-step solution

Part (a): Identify Stopping Times

For each random variable defined as N_1, N_2, and N_3, we need to check whether or not it is a stopping time for the sequence of random variables \(X_{1}, X_{2}, \ldots\). This means that the event \(\{N_i = n\}\) should be independent of \(X_{n + 1}, X_{n + 2}, \ldots\), for \(i = 1, 2, 3\). For \(N_1\), it is the minimum value of n such that the sum of the first n random variables is 5. The event \(\{N_1 = n\}\) means that the sum of the first n random variables is 5, and none of the previous random variables can affect whether the sum will be equal to 5. Therefore, \(N_1\) is a stopping time. For \(N_2\), the value of \(N_2\) relies only on the value of \(X_1\). Thus, \(N_2\) is independent of the random variables \(X_{2}, X_{3}, \ldots\). Therefore, \(N_2\) is a stopping time. For \(N_3\), the value of \(N_3\) relies on the value of \(X_4\). Thus, \(N_3\) is not a stopping time because the value of \(X_4\) affects its values.

Part (b): Define Sum of Products

We are given that the sum of products for stopping time N is \[ \sum_{i=1}^{N} X_{i}=\sum_{i=1}^{\infty} X_{i} I_{i} \] This equation represents that the sum of the first N random variables is equal to the sum of the infinite series of random variables multiplied by their corresponding stopping times.

Part (c): Prove Independence

We are asked to argue that \(X_{i}\) and \(I_{i}\) are independent. As a hint, we know \(I_{i}\) must equal 0 or 1 depending on whether or not we stopped after observing a certain number of random variables. Notice that the value of the indicator variable \(I_i\) is determined by whether we have stopped observing random variables up to the i-th position in the sequence. Since N is a stopping time, the event \(\{N=n\}\) is independent of \(X_{n+1}, X_{n+2}, \ldots .\) Therefore, \(I_i\) is also independent of \(X_{n+1}, X_{n+2}, \ldots.\)

Part (d): Complete Proof of Wald's Equation

We have the following equation from part (c): \[ E\left[\sum_{i=1}^{N} X_{i}\right]=\sum_{i=1}^{\infty} E[X] E\left[I_{i}\right] \] Since \(X_i\) and \(I_i\) are independent, we have \(E[X_i I_i] = E[X_i]E[I_i]\). Now, we can substitute this back into the equation above: \[ E\left[\sum_{i=1}^{N} X_{i}\right]=\sum_{i=1}^{\infty} E[X] E\left[I_{i}\right] = E[X] \sum_{i=1}^{\infty} E\left[I_{i}\right] \] Now, using the fact that \(E[N] = \sum_{i=1}^{\infty} E[I_{i}]\), we can rewrite the equation above as: \[ E\left[\sum_{i=1}^{N} X_{i}\right] = E[N] E[X] \] This completes the proof of Wald's equation.

Part (e): Application of Wald's Equation

By applying Wald's equation to the stopping times found in part (a), we can find a relationship between the expected values of the sum of random variables and the stopping times for those random variables. For \(N_1\) and \(N_2\), since they are stopping times, Wald's equation holds, which implies that \(E\left[\sum_{i=1}^{N_1} X_{i}\right]=E[N_1] E[X]\) and \(E\left[\sum_{i=1}^{N_2} X_{i}\right]=E[N_2] E[X]\) are valid for the stopping times \(N_1\) and \(N_2\). For \(N_3\), since it is not a stopping time, Wald's equation does not hold true, so we cannot find a relationship between the expected values of the sum of random variables and the stopping time \(N_3\).