Is a fixed deadline a stopping time?

Yes. Its occurrence can be determined without future observations.

Can a stopping time be infinite?

Yes, if the definition allows it and the triggering event never occurs.

Does the same random time always qualify under every information structure?

No. Qualification depends on what is known at each stage.

AI Glossary / Graphs and symbolic AI / Intermediate

Stopping time

Definition

A stopping time is a random time whose occurrence can be determined using only the information available so far. It formalizes when a sequential process stops without looking into the future. Examples include the first observed success, the first time a monitored value crosses a threshold, or a fixed deadline. The definition concerns available information, not whether stopping is optimal.

What it means

Imagine observing a process one step at a time. At step n, you must be able to decide whether stopping has already occurred by that step. You do not need to know beforehand exactly which step will trigger the rule.
The distinction is subtle but important. “Stop at the first success” can be implemented as observations arrive. “Stop at the last success before the deadline” generally cannot, because a success seen now may be followed by another one. A retrospective time selected after inspecting the full sequence is not automatically a stopping time for the information available during the sequence.

How it works

Specify the information available at each step, conventionally written as a growing collection F_n. A discrete random time T is a stopping time when the event T ≤ n is determined by F_n for every n. In discrete time, an equivalent formulation checks whether T = n is determined at step n.
The information specification matters: revealing additional data can change whether a time qualifies. A stopping time may also be infinite if its triggering event never occurs. A finite cap can ensure termination, but that is a separate property from the no-future-information condition. Further probabilistic conclusions, such as optional-stopping identities, require their own assumptions.

Three practical examples

A bandit-learning simulation can record the first round when a history-based policy switches to its fallback.
A monitoring process can stop at the first observed threshold crossing or at a fixed maximum number of observations.
A randomized search experiment can measure the first iteration that produces a candidate meeting a predefined quality criterion.

Think of it this way

Think of a referee who sees each result as it arrives and must announce when the stopping condition has been met. The referee can use the current result and earlier results, but not tomorrow's score sheet. The analogy is limited because a formal stopping time is defined relative to an information structure, which can include more than one observed sequence.

Worked example

Consider an original sequence of independent trials, each producing success with probability one quarter and failure with probability three quarters. Observe at most four trials. Stop at the first success, or after the fourth trial if no earlier success has occurred. Let T be the number of trials observed.
The possible stopping times are one, two, three, and four. T = 1 occurs with probability 1/4. T = 2 requires a failure followed by success, so its probability is (3/4)(1/4) = 3/16. T = 3 requires two failures followed by success, giving 9/64.
T = 4 occurs whenever the first three trials fail, regardless of the fourth result. Its probability is (3/4)³ = 27/64. This event includes both success on trial four and failure on all four trials. Their probabilities are 27/256 and 81/256, which add to 108/256 = 27/64.
The distribution sums to one: 16/64 + 12/64 + 9/64 + 27/64 = 64/64. The expected number of observed trials is 1(1/4) + 2(3/16) + 3(9/64) + 4(27/64) = 175/64, approximately 2.734.
For the observed sequence failure, failure, success, the rule stops at three. At that moment, the observer has everything needed to decide; the fourth trial is irrelevant to whether stopping has occurred.
Now define L as the index of the last success among all four trials, with L = 0 if there is no success. After seeing a success on trial two, the observer cannot know whether L = 2 because trials three and four might contain another success. More formally, after two observed successes or failures, the event L ≤ 2 depends on whether later successes occur. L is therefore not a stopping time relative to observations revealed one trial at a time.
The capped first-success rule is implementable online; the last-success choice uses hindsight. Both are random times, but only the first satisfies the stated stopping-time condition.

Illustrative case study

In a fictional randomized-search study, a team stops each run when it first finds a solution above a preset score or reaches a fixed iteration limit. It records whether the run ended through success or through the cap.
The team distinguishes the actual stopping iteration from the iteration of the best result identified retrospectively in a longer stored trace. Those quantities answer different questions. This fictional case describes evaluation, without claiming a runtime advantage.

Common misconceptions and mistakes

A stopping time need not be known in advance, and it need not have a finite expected value. Being a stopping time also does not prove that the stopping policy is sensible or optimal.
Do not confuse the first occurrence of an observable event with the last occurrence before an unseen future deadline. Do not assume that every theorem involving stopping remains valid for every stopping time. In particular, optional-stopping results depend on conditions such as boundedness or integrability; the label alone is insufficient.

Business use

The concept helps teams design sequential systems that can make decisions from the evidence actually available. It also prevents evaluation methods from quietly giving a system access to future information.
For a search or monitoring study, specify when observations arrive, what the system may inspect, and whether a hard cap exists. Report successful stopping separately from budget exhaustion. When comparing elapsed effort, define whether the reported time is first success, final termination, or a retrospectively selected milestone.

Check your understanding

Why is the probability T = 4 larger than the probability of first success on trial four?

Answer: The rule also stops at four when every trial fails. The deadline creates an additional stopping outcome.

Related terms

Stopping rule
Random variable
Censoring
Filtration
Hitting time
Sequential decision
Optional stopping
Bandit problem

Learn next

Next, remove the four-trial cap. The first-success time has a geometric distribution with success probability one quarter and mean four. Compare that mean with 175/64 for the capped rule, and explain why the cap's smaller expected duration does not mean every run succeeds sooner.

Sources

Primary sources: Scott Sheffield, MIT, stopping-time definition and examples: https://math.mit.edu/~sheffield/2016175/Lecture15.pdf ; AIMA original bandit context: https://raw.githubusercontent.com/aimacode/aima-glossary/master/sentences.txt . The capped-trial distribution and arithmetic are original.

Previous: Stopping rule Next: Storage area network