Closure and Truncation of Stopping Times

Combining Stopping Times

A stopping time records when an event has occurred using information available up to that time. If two events are being monitored, it is natural to ask when the first occurs and when both have occurred. These are the minimum and maximum of their event times. A related operation is to cap an event time at a fixed deadline. Each operation preserves the stopping-time property, but the reason is the information available at each time: by time \(n\), one can determine whether either event has happened, whether both have happened, and whether a deadline has been reached.

Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\) with a discrete-time filtration \((\mathcal{F}_n)_{n\ge0}\), meaning that each \(\mathcal{F}_n\) is a sigma-field and \(\mathcal{F}_n\subseteq\mathcal{F}_{n+1}\). A random time takes values in \(\{0,1,2,\ldots\}\cup\{\infty\}\). The value \(\infty\) allows for an event that never occurs.

Definition: A random time \(\tau\) is a stopping time for \((\mathcal{F}_n)\) if \(\{\tau\le n\}\in\mathcal{F}_n\) for every integer \(n\ge0\). Thus the information available by time \(n\) suffices to decide whether \(\tau\) has occurred by then. For two random times, write \(\tau\wedge\sigma=\min(\tau,\sigma)\) and \(\tau\vee\sigma=\max(\tau,\sigma)\), with the usual conventions for \(\infty\).

The Closure and Truncation Rules

Theorem: If \(\tau\) and \(\sigma\) are stopping times for the same filtration, then \(\tau\wedge\sigma\) and \(\tau\vee\sigma\) are stopping times. If \(c\) is a deterministic nonnegative integer, then \(\tau\wedge c\) and \(\tau\vee c\) are also stopping times. In particular, \(\tau\wedge c\) is a bounded stopping time, with values at most \(c\).

Proof. Fix an integer \(n\ge0\). The minimum has occurred by time \(n\) if and only if at least one of the two times has occurred by then. Hence \(\{\tau\wedge\sigma\le n\}=\{\tau\le n\}\cup\{\sigma\le n\}\). Both events on the right belong to \(\mathcal{F}_n\), so their union does too. The maximum has occurred by time \(n\) if and only if both times have occurred by then. Thus \(\{\tau\vee\sigma\le n\}=\{\tau\le n\}\cap\{\sigma\le n\}\), which is also in \(\mathcal{F}_n\). These equivalences remain valid if either time is \(\infty\), so no finite-time case is omitted. For the deterministic minimum, if \(n<c\), then \(\{\tau\wedge c\le n\}=\{\tau\le n\}\); if \(n\ge c\), then \(\{\tau\wedge c\le n\}=\Omega\). Both events are in \(\mathcal{F}_n\). For the deterministic maximum, if \(n<c\), then \(\{\tau\vee c\le n\}=\varnothing\); if \(n\ge c\), then \(\{\tau\vee c\le n\}=\{\tau\le n\}\). The empty set and the whole space belong to every sigma-field, and \(\{\tau\le n\}\in\mathcal{F}_n\). This proves all four claims, including \(c=0\). \(\square\)

The proof uses only the defining events for a stopping time. It does not require independence, a Markov property, or finiteness of either random time. The minimum is the first of two events; the maximum is the time by which both have occurred, if both occur. Truncation at \(c\) replaces any later value by \(c\), whereas \(\tau\vee c\) postpones any earlier value to at least \(c\).

The event identities also give distribution formulas. For \(n\ge0\), define \(F_\tau(n)=\mathbb{P}(\tau\le n)\), and similarly \(F_\sigma(n)\). For any two random times, not necessarily independent, inclusion-exclusion and the event identities imply

\begin{aligned} \mathbb{P}(\tau\vee\sigma\le n) &=\mathbb{P}(\tau\le n,\ \sigma\le n),\\ \mathbb{P}(\tau\wedge\sigma\le n) &=F_\tau(n)+F_\sigma(n)-\mathbb{P}(\tau\le n,\ \sigma\le n). \end{aligned}

If the two times are independent, the joint probability in these expressions is \(F_\tau(n)F_\sigma(n)\). For a nonnegative integer-valued time \(T\), its mass at \(k\ge0\) is \(\mathbb{P}(T=k)=\mathbb{P}(T\le k)-\mathbb{P}(T\le k-1)\), where \(F_T(-1)\) is defined to be \(0\). This difference is useful for converting a cumulative probability into an exact-time probability.

Worked Competing-Event Calculations

Worked Example: First and Last Heads in Independent Streams

On a probability space carrying two independent sequences of fair coin tosses, let \(Y_n=(Y_n^{(1)},Y_n^{(2)})\) be the pair of outcomes at time \(n\), with state space \(S=\{H,T\}^2\). Let \(\mathcal{F}_n=\sigma(Y_1,\ldots,Y_n)\), with \(\mathcal{F}_0=\{\varnothing,\Omega\}\). Let \(\tau\) and \(\sigma\) be the first times a head appears in stream 1 and stream 2, respectively. Each is a stopping time: whether its stream has shown a head by time \(n\) is determined by \(\mathcal{F}_n\). Find the distributions of \(\tau\wedge\sigma\) and \(\tau\vee\sigma\).

For each stream, the probability of no head in its first \(n\) tosses is \(2^{-n}\). Thus \(F_\tau(n)=F_\sigma(n)=1-2^{-n}\), and independence gives \(\mathbb{P}(\tau>n,\sigma>n)=2^{-n}2^{-n}=4^{-n}\). Consequently, \(\mathbb{P}(\tau\wedge\sigma>n)=4^{-n}\), so for \(k\ge1\),

\mathbb{P}(\tau\wedge\sigma=k) =4^{-(k-1)}-4^{-k} =\frac{3}{4^k}.

In particular, the first two masses are \(\mathbb{P}(\tau\wedge\sigma=1)=1-\tfrac14=\tfrac34\) and \(\mathbb{P}(\tau\wedge\sigma=2)=\tfrac14-\tfrac1{16}=\tfrac3{16}\). The mass formula sums to one: \(\sum_{k=1}^{\infty}3/4^k=1\), by the geometric series formula.

For the maximum, independence gives \(F_{\tau\vee\sigma}(n)=(1-2^{-n})^2\). At time \(1\), this is \((1-\tfrac12)^2=\tfrac14\), so \(\mathbb{P}(\tau\vee\sigma=1)=\tfrac14\). At time \(2\), the cumulative probability is \((1-\tfrac14)^2=\tfrac9{16}\). Therefore the exact mass at \(2\) is \(\tfrac9{16}-\tfrac14=\tfrac5{16}\). At time \(3\), the cumulative probability is \((1-\tfrac18)^2=\tfrac{49}{64}\), so the mass at \(3\) is \(\tfrac{49}{64}-\tfrac9{16}=\tfrac{13}{64}\). The remaining probability is \(\mathbb{P}(\tau\vee\sigma>3)=1-\tfrac{49}{64}=\tfrac{15}{64}\).

Check: The masses at \(1,2,3\), and above \(3\) sum to \(\tfrac{16}{64}+\tfrac{20}{64}+\tfrac{13}{64}+\tfrac{15}{64}=1\). Also, \(\mathbb{P}(\tau\vee\sigma>2)=1-\tfrac9{16}=\tfrac7{16}\), and the masses at \(3\) and above \(3\) sum to \(\tfrac{13}{64}+\tfrac{15}{64}=\tfrac{28}{64}=\tfrac7{16}\), as required.

Worked Example: Truncating a First-Head Time

Let \((Y_n)_{n\ge1}\) be a sequence of independent fair coin tosses with state space \(S=\{H,T\}\), and let \(\mathcal{F}_n=\sigma(Y_1,\ldots,Y_n)\), with \(\mathcal{F}_0=\{\varnothing,\Omega\}\). Define \(\tau=\inf\{n\ge1:Y_n=H\}\) and cap it at \(c=2\). The event \(\{\tau\le n\}\) says that at least one of the first \(n\) tosses was a head, so \(\tau\) is a stopping time. The theorem ensures that \(\tau\wedge2\) is also a stopping time.

If the first toss is a head, then \(\tau\wedge2=1\), an event of probability \(\tfrac12\). If the first toss is a tail, then \(\tau\wedge2=2\), regardless of the second toss, also an event of probability \(\tfrac12\). Thus its full distribution is \(\mathbb{P}(\tau\wedge2=1)=\tfrac12\) and \(\mathbb{P}(\tau\wedge2=2)=\tfrac12\).

The stopping-time events verify the result directly. At \(n=0\), \(\{\tau\wedge2\le0\}=\varnothing\). At \(n=1\), \(\{\tau\wedge2\le1\}=\{Y_1=H\}\in\mathcal{F}_1\). For every \(n\ge2\), \(\{\tau\wedge2\le n\}=\Omega\in\mathcal{F}_n\). The probabilities of these events at \(n=1\) and \(n=2\) are \(\tfrac12\) and \(1\); their difference gives the two masses above.

For comparison, delaying this same time gives \(\tau\vee2\). Its value is \(2\) exactly when \(\tau\le2\), which has probability \(1-(\tfrac12)^2=\tfrac34\). For \(k>2\), the event \(\{\tau\vee2=k\}\) is \(\{\tau=k\}\), of probability \(2^{-k}\). For example, the mass at \(3\) is \(\tfrac18\). The total mass is \(\tfrac34+\sum_{k=3}^{\infty}2^{-k}=\tfrac34+\tfrac14=1\).

Check: The probability that the first two tosses are both tails is \(\tfrac12\cdot\tfrac12=\tfrac14\), so \(\mathbb{P}(\tau\le2)=1-\tfrac14=\tfrac34\), matching the mass at \(2\) for \(\tau\vee2\).

Worked Example: Competing Events from the Same Toss Stream

Use one sequence of independent fair tosses \((Y_n)_{n\ge1}\), with state space \(S=\{H,T\}\) and filtration \(\mathcal{F}_n=\sigma(Y_1,\ldots,Y_n)\). Let \(\tau\) be the first time a head appears and \(\sigma\) the first time a tail appears. Both are stopping times because the occurrence of either outcome by time \(n\) is determined by the first \(n\) tosses. These event times are dependent because they use the same stream.

The first toss must be either a head or a tail, so \(\tau\wedge\sigma=1\) with probability \(1\). For the maximum to equal \(k\ge2\), the first \(k-1\) tosses must all be the same outcome and the \(k\)th toss must be the other outcome. There are two such length-\(k\) sequences, each of probability \(2^{-k}\), so \(\mathbb{P}(\tau\vee\sigma=k)=2\cdot2^{-k}=2^{1-k}\). In particular, the masses at \(2\) and \(3\) are \(\tfrac12\) and \(\tfrac14\). The event \(\{\tau\vee\sigma>3\}\) means that the first three tosses were all heads or all tails; its probability is \(2\cdot2^{-3}=\tfrac14\).

Check: The probability at \(2\), at \(3\), and above \(3\) totals \(\tfrac12+\tfrac14+\tfrac14=1\). Unlike the independent-stream example, the maximum here is not distributed according to the product of two marginal cumulative probabilities. Independence is needed for that product formula, but it is not needed for the stopping-time closure result.

Common Pitfall: Subtracting the Wrong Event

To find an exact mass at time \(2\), subtract the cumulative probability through time \(1\) from the cumulative probability through time \(2\). For the maximum of the two independent head times in the first example, the cumulative probability through time \(2\) is \(\tfrac9{16}\). The probability that both streams have shown a head by time \(1\) is \((\tfrac12)^2=\tfrac14=\tfrac4{16}\), not \(\tfrac1{16}\). Therefore the mass at \(2\) is \(\tfrac9{16}-\tfrac4{16}=\tfrac5{16}\). The probability above time \(2\) is \(1-\tfrac9{16}=\tfrac7{16}\); together with the masses \(\tfrac14\) at time \(1\) and \(\tfrac5{16}\) at time \(2\), this gives total probability \(1\).

The general lesson is to distinguish an exact-time probability from a tail probability. For a maximum, \(\{\tau\vee\sigma\le n\}\) is the event that both times are at most \(n\), while \(\{\tau\vee\sigma>n\}\) is the event that at least one is greater than \(n\). The exact mass at \(n\) is the difference of successive cumulative probabilities, not a product of single-time probabilities unless the relevant events are independent.

Check Your Understanding

For each question, identify the event that must belong to the filtration and use exact probabilities where requested.

Show directly from the definition why \(\{\tau\wedge\sigma\le n\}\) is a union of two events in \(\mathcal{F}_n\).
For stopping times \(\tau,\sigma\), write the event \(\{\tau\vee\sigma\le n\}\) in terms of \(\{\tau\le n\}\) and \(\{\sigma\le n\}\).
If \(\mathbb{P}(\tau\le3)=\tfrac34\), what is \(\mathbb{P}(\tau\wedge3\le3)\)? What is \(\mathbb{P}(\tau\vee3\le2)\)?
For two independent first-head times in fair-coin streams, calculate the probability that their maximum equals \(2\) by subtracting successive cumulative probabilities.
For a first-head time \(\tau\), explain why \(\tau\wedge c\) is bounded even on outcomes where \(\tau=\infty\).

Closure and Truncation of Stopping Times

What You'll Learn