7.8: Stopping Processes and Stopping Trials

The definition of stopping trials in Section 4.5 applies to arbitrary integer-time processes {\(Z_n; n ≥ 1\)} as well as to IID sequences. Recall that \(J\) is a stopping trial for a sequence {\(Z_n; n ≥ 1\)} of rv’s if \(\mathbb{I}_{J=n}\) is a function of \(Z_1, . . . , Z_n\) and if \(J\) is a rv.

If \(\mathbb{I}_{J=n}\) is a function of \(Z_1, . . . , Z_n\) and \(J\) is a defective rv, then \(J\) is called a defective stopping trial. For some of the results to follow, it is unimportant whether \(J\) is a random variable or a defective random variable (\(i.e.\), whether or not the process stops with probability 1). If it is not specified whether \(J\) is a random variable or a defective random variable, we refer to the stopping trial as a possibly-defective stopping trial; we consider \(J\) to take on the value \(\infty \) if the process does not stop.

Definition 7.8.1. A stopped process {\(Z^∗_n;\, n ≥ 1\)} for a possibly-defective stopping trial \(J\) relative to a process {\(Z_n; n ≥ 1\)} is the process for which \(Z^∗_n= Z_n\) for \(n ≤ J\) and \(Z^∗_n= Z_J\) for \(n > J\).

As an example, suppose \(Z_n\) models the fortune of a gambler at the completion of the \(n\)th trial of some game, and suppose the gambler then modifies the game by deciding to stop gambling under some given circumstances (\(i.e.\), at the stopping trial). Thus, after stopping, the fortune remains constant, so the stopped process models the gambler’s fortune in time, including the effect of the stopping trial.

As another example, consider a random walk with a positive and negative threshold, and consider the process to stop after reaching or crossing a threshold. The stopped process then stays at that point beyond the threshold as an artifice to simplify analysis. The use of stopped processes is similar to the artifice that we employed in Section 3.5 for first-passage times in Markov chains; recall that we added an artificial trapping state after the desired passage to simplify analysis.

We next show that the possibly-defective stopped process of a martingale is itself a mar­tingale; the intuitive reason is that, before stopping, the stopped process is the same as the martingale, and, after stopping, \(Z_n^∗= Z_{n-1}^∗\). The following theorem establishes this and the corresponding results for submartingales and supermartingales.

Theorem 7.8.1. Given a stochastic process {\(Z_n; n ≥ 1\)} and a possibly-defective stopping trial \(J\) for the process, the stopped process {\(Z^∗_n; n ≥ 1\)} is a submartingale if {\(Z_n; n ≥ 1\)} is a submartingale, is a martingale if {\(Z_n; n ≥ 1\)} is a martingale, and is a supermartingale if {\(Z_n; n ≥ 1\)} is a supermartingale.

Proof: First we show that, for all three cases, the stopped process satisfies \(\mathsf{E} [| Z_n^∗|] < \infty\) for any given \(n ≥ 1\). Conditional on \(J = i\) for some \(i < n\), we have \(Z^∗_n= Z_i\), so

\[ \mathsf{E}[|Z_n^*| \, | J=i] =\mathsf{E}[|Z_i| \, | J=i] <\infty \text{ for each } i<n \text{ such that Pr}\{J=i\}>0 \nonumber \]

The reason for this is that if \(\mathsf{E} [|Z_i|| J = i] = \infty\) and \(\text{Pr}\{J = i\} > 0\), then \(\mathsf{E} [|Z_i|] = \infty \), contrary to the assumption that {\(Z_n; n ≥ 1\)} is a martingale, submartingale, or super-martingale. Similarly, for \(J ≥ n\), we have \(Z^∗_n= Z_n\) so

\[ \mathsf{E}[|Z_n^*| \, |J\geq n] = \mathsf{E}[|Z_n| \, |J\geq n] < \infty \quad \text{if Pr}\{J\geq n\}>0 \nonumber \]

Averaging,

\[ \mathsf{E}[|Z^*_n|] = \sum^{n-1}_{i=1}\mathsf{E}[|Z^*_n| \, |J=i] \text{Pr}\{J=i \} + \mathsf{E}[|Z^*_n| \, |J\geq n] \text{Pr} \{J \geq n \} <\infty \nonumber \]

Next assume that {\(Z_n; n ≥ 1\)} is a submartingale. For any given \(n > 1\), consider an arbitrary initial sample sequence (\(Z_1 = z_1, Z_2 = z_2, . . . , Z_{n−1} = z_{n−1}\)). Note that \(z_1\) specifies whether or not \(J = 1\). Similarly, (\(z_1, z_2\)) specifies whether or not \(J = 2\), and so forth up to (\(z_1, . . . , z_{n−1}\)), which specifies whether or not \(J = n − 1\). Thus (\(z_1, . . . , z_{n−1}\)) specifies the sample value of \(J\) for \(J ≤ n − 1\) and specifies that \(J ≥ n\) otherwise.

For \((z_1, . . . , z_{n−1})\) such that \(\mathbb{I}_{J≥n} < n\), we have \(z_n^∗= z_{n-1}^∗\). For all such sample values,

\[ \mathsf{E}[Z_n^* | Z^*_{n-1}=z^*_{n-1},...,Z^*_1=z^*_1] = z^*_{n-1} \nonumber \]

For the remaining case, where \((z_1, . . . , z_{n−1})\) is such that \(\mathbb{I}_{J≥n} ≥ n\), we have \(z^∗_n= z_n\). Thus

\[ \mathsf{E} [Z_n^*|Z^*_{n-1}=z^*_{n-1},...,Z^*_1=z^*_1] \geq z^*_{n-1} \nonumber \]

The same argument works for martingales and supermartingales by replacing the inequality in (7.8.2) by equality for the martingale case and the opposite inequality for the supermartin­gale case.

\( \square \)

Theorem 7.8.2. Given a stochastic process {\(Z_n; n ≥ 1\)} and a possibly-defective stopping trial \(J\) for the process, the stopped process {\(Z^∗_n; n ≥ 1\)} satisfies the following conditions for all \(n ≥ 1\) if {\(Z_n; n ≥ 1\)} is a submartingale, martingale, or supermartingale respectively:

\[ \begin{align} &\mathsf{E}[Z_1] \quad \leq \quad \mathsf{E}[Z^*_n] \quad \leq \quad \mathsf{E}[Z_n] \qquad (\text{submartingale}) \\ &\mathsf{E}[Z_1] \quad = \quad \mathsf{E}[Z^*_n] \quad = \quad \mathsf{E}[Z_n] \qquad (\text{martingale}) \\ &\mathsf{E}[Z_1] \quad \geq \quad \mathsf{E}[Z^*_n] \quad \geq \quad \mathsf{E}[Z_n] \qquad (\text{supermartingale}) \end{align} \nonumber \]

Proof: Since a process cannot stop before epoch 1, \(Z_1 = Z_1^∗\) in all cases. First consider the case in which {\(Z_n; n ≥ 1\)} is a submartingale. Theorem 7.8.1 shows that {\(Z_n^∗; n ≥ 1\)} is a submartingale, and from (7.7.5), \(\mathsf{E} [Z_1] ≤ \mathsf{E} [Z^∗_n]\) for all \(n ≥ 1\). This establishes the first half of (7.8.3) and we next prove the second half. First condition on the set of sequences for which the initial segment \((z_1, . . . , z_i)\) specifies that \(\mathbb{I}_{J≥n} = i\) for any given \(i < n\). Then \(\mathsf{E} [Z^∗_n] = z_i\). From (7.7.3), \(\mathsf{E} [Z_n] ≥ z_i\), proving (7.8.3) for this case. For those sequences not having such an initial segment, \( Z_n^∗ = Z_n\), establishing (7.8.3) in that case. Averaging over these two cases gives (7.8.3) in general.

Finally, if {\(Z_n; n ≥ 1\)} is a supermartingale, then {\(−Z_n; n ≥ 1\)} is a submartingale, verifying (7.8.5). Since a martingale is both a submartingale and supermartingale, (7.8.4) follows and the proof is complete.

Consider a (non-defective) stopping trial \(J\) for a martingale {\(Z_n; n ≥ 1\)}. Since the stopped process is also a martingale, we have

\[ \mathsf{E}[Z^*_n] = \mathsf{E}[Z^*_1] = \mathsf{E}[Z_1]; n\geq 1 \nonumber \]

Since \(Z^∗_n= Z_J\) for all \(n ≥ J\) and since \(J\) is finite with probability 1, we see that \(\lim_{n→\infty } Z^∗_n= Z_J\) with probability 1. Unfortunately, in general, \(\mathsf{E} [Z_J ]\) is unequal to \(\lim_{n→\infty} \mathsf{E} [Z^∗_n] = \mathsf{E} [Z_1]\). An example in which this occurs is the binary product martingale in (7.6.6). Taking the stopping trial \(J\) to be the smallest \(n\) for which \(Z_n = 0\), we have \(Z_J = 0\) with probability 1, and thus \(\mathsf{E} [Z_J ] = 0\). But \(Z_n^∗= Z_n\) for all \( n\), and \(\mathsf{E} [Z_n^∗] = 1\) for all \(n\). The problem here is that, given that the process has not stopped by time \(n\), \(Z_n\) and \(Z_n^∗\) each have the value \(2^n\). Fortunately, in most situations, this type of bizarre behavior does not occur and \(\mathsf{E} [Z_J ] = \mathsf{E} [Z_1]\). To get a better understanding of when \(\mathsf{E} [Z_J ] = \mathsf{E} [Z_1]\), note that for any \(n\), we have

\[ \begin{align} \mathsf{E}[Z^*_n] \quad &= \quad \sum^n_{i=1} \mathsf{E}[Z^*_n| J=i ] \text{Pr} \{ J=i\} +\mathsf{E}[Z^*_n|J>n] \text{Pr}\{ J>n \} \\ &= \quad \sum^n_{i=1} \mathsf{E}[Z_J|J=i] \text{Pr} \{J=i \}+\mathsf{E} [Z_n |J>n] \text{Pr} \{J>n \} \end{align} \nonumber \]

The left side of this equation is \(\mathsf{E} [Z_1]\) for all \(n\). If the final term on the right converges to 0 as \(n →\infty \), then the sum must converge to \(\mathsf{E} [Z_1]\). If \(\mathsf{E} [|Z_J |] < \infty\), then the sum also converges to \(\mathsf{E} [Z_J ]\). Without the condition \(\mathsf{E} [|Z_J |] < \infty \), the sum might consist of alternating terms which converge, but whose absolute values do not converge, in which case \(\mathsf{E} [Z_J ]\) does not exist (see Exercise 7.21 for an example). Thus we have established the following lemma.

Lemma 7.8.1. Let \(J\) be a stopping trial for a martingale {\(Z_n; n ≥ 1\)}. Then \(\mathsf{E} [Z_J ] = \mathsf{E} [Z_1]\) if and only if

\[ \lim_{n\rightarrow \infty} \mathsf{E}[Z_n| J>n] \text{Pr} \{J>n \} = 0 \quad \text{and} \quad \mathsf{E}[|Z_J|]>\infty \nonumber \]

Example 7.8.1 (Random walks with thresholds) Recall the generating function prod­uct martingale of (7.6.7) in which {\(Z_n = \exp [rS_n − n\gamma (r)]; n ≥ 1\)} is a martingale defined in terms of the random walk {\(S_n = X_1+... +X_n; n ≥ 1\)}. From (7.8.4), we have \(\mathsf{E} [Z_n] = \mathsf{E} [Z_1]\), and since \(\mathsf{E} [Z_1] = \mathsf{E} [\exp \{ rX_1 − \gamma (r)\} ] = 1\), we have \(\mathsf{E} [Z_n] = 1\) for all \(n\). Also, for any possibly-defective stopping trial \(J\), we have \(\mathsf{E} [Z_n^∗] = \mathsf{E} [Z_1] = 1\). If \( J\) is a non-defective stopping trial, and if (7.8.9) holds, then

\[ \mathsf{E}[Z_J] = \mathsf{E} [\exp \{ rS_J-J \gamma \ref{r} \} ] = 1 \nonumber \]

If there are two thresholds, one at \( α> 0\), and the other at \(β< 0\), and the stopping rule is to stop when either threshold is crossed, then (7.8.10) is just the Wald identity, (7.5.1).

The nice part about the approach here is that it also applies naturally to other stopping rules. For example, for some given integer \( n\), let \(J_{n+}\) be the smallest integer \(i ≥ n\) for which \(S_i ≥ α\) or \(S_i ≤ β\). Then, in the limit \(β → −\infty, \text{ Pr}\{S_{J_n+} ≥ α\} = \text{Pr}\{\bigcup^{\infty}_{i=n}(S_i ≥ α)\}\). Assuming \(\overline{X} < 0\), we can find an upper bound to \(\text{Pr}\{S_{J_n+} ≥ α\}\) for any \(r > 0\) and \(\gamma \ref{r} ≤ 0\) (\(i.e.\), for \(0 < r ≤ r^∗\)) by the following steps

\[ \begin{align} &1=\mathsf{E}[\exp \{rS_{J_n+} - J_{n+}\gamma(r)\}] \geq \text{Pr}\{ S_{J_n+} \geq \alpha \} \exp [r\alpha - n\gamma(r) ] \nonumber \\ &\text{Pr} \{ S_{J_n+} \geq \alpha \} \leq \exp [-r\alpha +n\gamma (r)]; \qquad 0 \leq r \leq r^* \end{align} \nonumber \]

This is almost the same result as (7.5.21), except that it is slightly stronger; (7.5.21) bounded the probability that the first threshold crossing crossed \(α\) at some epoch \(i ≥ n\), whereas this includes the possibility that \(S_m ≥ α\) and \(S_i ≥ α\) for some \(m < n ≤ i\).