Why the Order of the Stopping Times Matters
Optional sampling compares the values of a process at random times. For a submartingale, the expected value cannot decrease when we move from an earlier stopping time to a later one, provided the times are bounded. For a supermartingale, the inequality reverses. The key is not that the process has positive or negative drift in an informal sense: the argument uses the conditional expected increment at each step and the fact that the decision to include that increment is made using information already available.
We work in discrete time. Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space, let \(S\) be a finite or countable state space, and let \((X_n)_{n\ge0}\) be an \(S\)-valued process adapted to a filtration \((\mathcal{F}_n)_{n\ge0}\). Adapted means that \(X_n\) is \(\mathcal{F}_n\)-measurable for every \(n\). Assume each \(X_n\) is integrable. A submartingale satisfies \(\mathbb{E}[X_{n+1}\mid\mathcal{F}_n]\ge X_n\) almost surely for every \(n\); a supermartingale satisfies the reverse inequality. A martingale satisfies equality.
The stopping-time condition matters because, at time \(k\), the event that a process has not yet stopped can be determined from \(\mathcal{F}_k\). This allows conditional expectations of the next increment to be used. The bound matters because it reduces the comparison to a finite sum; no limiting or integrability argument for an infinite sum is needed.
The Bounded Optional-Sampling Inequalities
Proof. Since \(\sigma,\tau\le N\), the stopped values are integrable: for example, \(X_\tau=\sum_{j=0}^{N}X_j\mathbf{1}_{\{\tau=j\}}\), a finite sum of integrable random variables. For every outcome, the increments from time \(\sigma\) up to, but not including, time \(\tau\) telescope. Thus $$ X_\tau-X_\sigma=\sum_{k=0}^{N-1}\mathbf{1}_{\{\sigma\le k<\tau\}}(X_{k+1}-X_k). $$ This also holds when \(\sigma=\tau\), since then every indicator in the sum is zero.
For each \(k\), the event \(A_k=\{\sigma\le k<\tau\}\) belongs to \(\mathcal{F}_k\): it is the intersection of \(\{\sigma\le k\}\in\mathcal{F}_k\) and \(\{\tau>k\}\), whose complement \(\{\tau\le k\}\) is in \(\mathcal{F}_k\). Consequently, the defining conditional inequality for a submartingale gives $$ \mathbb{E}[\mathbf{1}_{A_k}(X_{k+1}-X_k)] =\mathbb{E}\!\left[\mathbf{1}_{A_k}\mathbb{E}[X_{k+1}-X_k\mid\mathcal{F}_k]\right]\ge0. $$ Taking expectations in the finite telescoping sum shows \(\mathbb{E}[X_\tau-X_\sigma]\ge0\), which proves the submartingale claim. For a supermartingale each conditional expected increment is nonpositive, so every term has nonpositive expectation and the inequality reverses. For a martingale every conditional expected increment is zero, so the expected difference is zero. \(\square\)
The proof identifies the exact role of the hypotheses. Boundedness gives a finite sum; the stopping-time property makes the increment-selection event measurable at the time the increment begins; and the ordering ensures that the selected increments are precisely those between the two stopped values. The theorem concerns expectations, not a claim that \(X_\tau\ge X_\sigma\) or \(X_\tau\le X_\sigma\) on every sample path.
Worked Example: A Submartingale Stopped at a Favorable First Step
Let \(\Omega=\{-1,1\}^2\) with independent coordinates \(Y_1,Y_2\), where \(\mathbb{P}(Y_i=1)=\tfrac34\) and \(\mathbb{P}(Y_i=-1)=\tfrac14\). Set \(S=\mathbb{Z}\), \(X_0=0\), and \(X_n=\sum_{i=1}^nY_i\) for \(n=1,2\). Use the natural filtration \(\mathcal{F}_n=\sigma(Y_1,\ldots,Y_n)\), with \(\mathcal{F}_0=\{\varnothing,\Omega\}\). Since \(\mathbb{E}Y_i=\tfrac34-\tfrac14=\tfrac12\), the conditional expected increment is \(\tfrac12\), so this is a submartingale.
Take \(\sigma=0\) and let \(\tau=1\) if \(Y_1=1\), and \(\tau=2\) if \(Y_1=-1\). This is a stopping time, since the decision at time 1 uses \(Y_1\), and \(\sigma\le\tau\le2\). On \(\{Y_1=1\}\), \(X_\tau=X_1=1\). On \(\{Y_1=-1\}\), \(X_\tau=X_2=-1+Y_2\), whose conditional expectation given \(Y_1=-1\) is \(-1+\tfrac12=-\tfrac12\). Therefore $$ \mathbb{E}[X_\tau]=\tfrac34(1)+\tfrac14\left(-\tfrac12\right)=\tfrac34-\tfrac18=\tfrac58, \qquad \mathbb{E}[X_\sigma]=X_0=0. $$ The strict inequality has the predicted direction. As a check, the selected-increment formula gives \(\mathbb{E}Y_1=\tfrac12\) at time 0, and at time 1 adds \(\mathbb{P}(Y_1=-1)\mathbb{E}Y_2=\tfrac14\cdot\tfrac12=\tfrac18\). The total increase is \(\tfrac12+\tfrac18=\tfrac58\), agreeing with the direct calculation.
Worked Example: A Supermartingale and the Reversed Inequality
Let \(\Omega=\{-1,1\}^2\) have independent coordinates \(Y_1,Y_2\), now with \(\mathbb{P}(Y_i=-1)=\tfrac34\) and \(\mathbb{P}(Y_i=1)=\tfrac14\). Set \(S=\mathbb{Z}\), \(X_0=0\), \(X_n=\sum_{i=1}^nY_i\), and use the natural filtration. Here \(\mathbb{E}Y_i=-\tfrac34+\tfrac14=-\tfrac12\), so \((X_n)\) is a supermartingale.
Let \(\sigma=0\), and set \(\tau=1\) if \(Y_1=-1\), and \(\tau=2\) if \(Y_1=1\). The time is bounded by 2 and is a stopping time. If \(Y_1=-1\), then \(X_\tau=-1\). If \(Y_1=1\), then \(X_\tau=X_2=1+Y_2\), with conditional expectation \(1-\tfrac12=\tfrac12\). Hence $$ \mathbb{E}[X_\tau]=\tfrac34(-1)+\tfrac14\left(\tfrac12\right)=-\tfrac34+\tfrac18=-\tfrac58, \qquad \mathbb{E}[X_\sigma]=0. $$ Thus \(-\tfrac58\le0\), as required. Checking through increments gives \(\mathbb{E}Y_1=-\tfrac12\), followed by the time-1 increment only on \(\{Y_1=1\}\), contributing \(\tfrac14(-\tfrac12)=-\tfrac18\). Their sum is \(-\tfrac12-\tfrac18=-\tfrac58\), the same result.
Worked Example: Equality for a Martingale at Random Ordered Times
Let \(\Omega=\{-1,1\}^2\) have independent fair signs \(Y_1,Y_2\), so each sign has probability \(\tfrac12\). Set \(S=\mathbb{Z}\), \(X_0=0\), \(X_n=\sum_{i=1}^nY_i\), and take the natural filtration. Since each next sign has conditional mean zero, \((X_n)\) is a martingale. Let \(\sigma=0\), and set \(\tau=1\) when \(Y_1=1\), and \(\tau=2\) when \(Y_1=-1\). These are ordered bounded stopping times.
When \(Y_1=1\), \(X_\tau=1\); when \(Y_1=-1\), \(X_\tau=-1+Y_2\), whose conditional expectation is \(-1\). Therefore $$ \mathbb{E}[X_\tau]=\tfrac12(1)+\tfrac12(-1)=0=\mathbb{E}[X_\sigma]. $$ The increment calculation checks the equality directly: the time-0 increment has expectation \(\mathbb{E}Y_1=0\), and the time-1 increment is included only when \(Y_1=-1\), contributing \(\tfrac12\mathbb{E}Y_2=0\) by independence. The total expected change is zero.
Using the Result Correctly
A useful way to apply the theorem is to check the assumptions in order. First identify a filtration and verify that the process is adapted and integrable. Next establish the submartingale or supermartingale conditional inequality. Then verify that both random times are stopping times, that \(\sigma\le\tau\) almost surely, and that they are bounded by a common deterministic integer. Only after these checks should you choose the direction of the expectation inequality.
The common mistake is to include an increment whose starting time is already the stopping time. In the first worked example, the correct time-1 event is \(\{\tau>1\}=\{Y_1=-1\}\), not \(\{\tau\ge1\}\), which includes every outcome. Replacing the correct selection event by the latter would give the erroneous sum $$ \mathbb{E}Y_1+\mathbb{E}Y_2=\tfrac12+\tfrac12=1, $$ because it counts the time-1 increment even on \(\{Y_1=1\}\), where \(\tau=1\) and the process has already stopped. The actual expected stopped value is \(\tfrac58\). The strict inequality \(k<\tau\) in the increment formula prevents this extra step.
Ordering is also essential to this particular comparison: the sum from \(\sigma\) to \(\tau\) uses \(\sigma\le k<\tau\). If the times are not ordered, the difference can have increments in both directions, and the theorem does not give an inequality in either direction. Finally, bounded-time sampling should not be silently extended to unbounded stopping times. For an unbounded time, the finite-sum proof no longer applies as written; additional hypotheses are needed for optional-sampling conclusions.
Check Your Understanding
For each question, state which assumptions are relevant and justify the direction of any inequality.
- For a supermartingale and bounded stopping times \(\sigma\le\tau\), which direction does the expectation inequality take?
- In the increment decomposition, why is \(\{\sigma\le k<\tau\}\) measurable with respect to \(\mathcal{F}_k\)?
- If \((X_n)\) is a martingale and the stopping times satisfy the theorem's assumptions, what can be said about \(\mathbb{E}[X_\tau-X_\sigma]\)?
- In the submartingale worked example, calculate the contribution from the increment at time 1 using its correct selection event.
- Why does boundedness allow the proof to use a finite telescoping sum without an additional limit argument?