Odds Algorithm¶

An optimal-stopping algorithm that sums independent Bernoulli success odds backward to a unit threshold, then stops on the first later success to maximize catching the final success.

Version: v2 · 2026-09-06 · History
Domain-specific #: 2413
Origin domain: optimal stopping
Subdomain: last success problems
Aliases: Bruss algorithm, Sum-the-odds algorithm, Odds strategy

Core Idea¶

The odds algorithm solves a precise last-success stopping problem. A decision maker observes a finite sequence of independent Bernoulli indicators \(I_1,\ldots,I_n\) in order. Success probabilities \(p_i=\Pr(I_i=1)\) are known, earlier observations cannot be revisited, and a stop wins exactly when it occurs on the sequence's final success. The algorithm converts each probability into odds \(r_i=p_i/(1-p_i)\), accumulates those odds backward, and begins accepting at the last index where the remaining odds sum reaches one.

From that threshold onward, the decision maker stops on the first observed success. Bruss proved that this rule maximizes the probability of stopping on the last success for independent indicators.^[1] The identity is not “choose a likely event” but a theorem-bound package: finite ordered independent trials, known individual probabilities, last-success reward, no recall, reverse cumulative odds, unit threshold, and first-success stopping.

Structural Signature¶

Finite horizon: the last possible observation \(n\) is specified.
Independent indicators: \(I_i\in\{0,1\}\) are mutually independent.
Known probabilities: \(p_i\) is available before the stopping decision at \(i\).
Last-success objective: reward is one exactly when the chosen success has no later success.
Irrevocable observation: the decision maker can stop now or continue, without recall.
Odds conversion: \(r_i=p_i/(1-p_i)\) and \(q_i=1-p_i\).
Backward threshold: sum odds from the end until the total first reaches or exceeds one.
Forward execution: ignore successes before the threshold, then stop at the first success.
Closed-form value: the winning probability at the threshold is a product-of-failures times a sum-of-odds.

Recognition test. If the reward is for the largest numerical observation, the first success, any one success, or the \(m\)-th success, the original algorithm does not automatically apply. If indicators are dependent or probabilities are learned online, its theorem assumptions are absent.

What It Is Not¶

The odds algorithm is not optimal stopping in general. Optimal Stopping Rule names a far broader decision structure, while the odds theorem supplies an explicit solution to one independent-indicator, last-success class.

It is not the classical secretary rule itself. Record indicators in the random-order secretary problem can instantiate the theorem, but the odds algorithm also handles unequal known success probabilities and many sequences that are not rankings of candidates. Conversely, secretary variants with unknown horizon, recall, multiple selections, or nonrandom order need other results.

It is not “stop when accumulated probability reaches one.” Probabilities are converted to odds before summation. It is not backward execution: only the threshold is computed backward; observations and decisions still occur forward. Nor does it guarantee a win. It maximizes win probability among stopping rules under the assumptions.

Scope of Application¶

The exact theorem applies to finite independent success/failure observations with known, possibly unequal probabilities. Examples include stopping on the final occurrence of a designated result in repeated trials, last record events when their indicator probabilities are known and independent, and operational decisions whose payoff is tied literally to the last qualifying opportunity.

The model allows \(p_i=0\), which contributes zero odds. The usual clean statement takes \(p_i<1\). A deterministic success with \(p_i=1\) yields infinite odds and must be handled explicitly—by conditioning, decomposing around the last deterministic success, or using a limiting convention—rather than silently dividing by zero.

Extensions cover multiple stopping rights, dependent trials, unknown probabilities, random horizons, and nonuniform payoffs, but their rules are not automatically the original odds algorithm. Bruss's 2003 note establishes the sharp uniform \(1/e\) lower bound in the relevant unit-crossing case; it does not remove the original independence or information assumptions.^[2]

Clarity¶

Let

\[ q_i=1-p_i,\qquad r_i=\frac{p_i}{q_i} \]

for \(0\le p_i<1\). Define

\[ s=\max\left\{k\in\{1,\ldots,n\}: \sum_{j=k}^{n}r_j\ge 1\right\}, \]

with \(s=1\) if the set is empty. Reject observations \(1,\ldots,s-1\), then stop on the first \(I_i=1\) for \(i\ge s\). If no such success occurs, no winning stop is made.

Write \(Q_s=\prod_{j=s}^{n}q_j\) and \(R_s=\sum_{j=s}^{n}r_j\). Exactly one success in the suffix occurs with probability

\[ Q_sR_s =\sum_{i=s}^{n}p_i\prod_{\substack{j=s\\j\ne i}}^{n}q_j. \]

Stopping on the suffix's first success wins precisely in that exactly-one-success event. The theorem shows the chosen suffix makes this strategy globally optimal, not merely locally plausible.^[1]

Manages Complexity¶

A generic finite-horizon stopping problem can invite dynamic programming over every time and information state. The odds algorithm compresses this problem class into one backward pass and one forward pass. Given the \(p_i\), computing odds, suffix sums, and the threshold costs \(O(n)\) time and \(O(1)\) extra storage if accumulated in place.

The compression also exposes sensitivity. Large late odds move the threshold later; many small odds may collectively cross one earlier. A probability near one dominates because odds, not probability, measure success relative to failure. This makes the rule interpretable and auditable.

The simplicity depends on structural assumptions. Dependence means the chance of later success can change after each observation; unknown probabilities require estimation; alternate rewards change the Bellman comparison. The algorithm manages complexity by exploiting a special factorization, not by solving all sequential selection problems.

Abstract Reasoning¶

Suppose a threshold \(k\) is fixed and the rule stops on the first success at or after \(k\). It wins exactly when the suffix contains one success. Independence factors that probability into \(Q_kR_k\). Moving the threshold backward adds one odds term while multiplying by another failure probability. The comparison changes sign around the point where the remaining odds sum crosses one, producing the sum-the-odds criterion.

This reasoning explains why summing probabilities would be wrong. For two events, the probability of exactly one success is \(p_1q_2+q_1p_2=q_1q_2(r_1+r_2)\); odds linearize the exactly-one-success expression after the common all-failure product is factored out.

It also yields a diagnostic inference: if \(R_1<1\), there is no unit crossing and the threshold is the first observation. When a unit crossing exists, the success probability under the optimal rule is at least \(1/e\), and that lower bound is sharp across the theorem class.^[2]

Knowledge Transfer¶

The algorithm transfers exactly when a practice can encode “interesting now” as independent indicators with known probabilities and values success only at the final interesting event. The surface meaning of success may change—from a target die face to a record candidate—but the probabilistic roles must remain literal.

Transfer is not licensed merely because a decision is sequential. A medical example, sale example, or maintenance example requires defensible independence and known-probability modeling; otherwise it is only motivational. Likewise, record indicators in the classical random-permutation secretary problem have special probability structure, but arbitrary candidate qualities do not automatically become independent Bernoulli trials.

The portable residue is Optimal Stopping Rule. The reverse-odds threshold remains domain-specific mathematical machinery.

Examples¶

Four equal trials: with \(n=4\) and \(p_i=0.2\), every \(r_i=0.25\). The total suffix odds equal one at \(s=1\); stop at the first success. The win probability is \(4(0.2)(0.8)^3=0.4096\).
Ten die throws: calling a six a success gives odds \(1/5\). A five-trial suffix has odds sum one, so one optimal threshold begins at throw six and stops on the first later six.
Unequal trials: late observations with larger \(p_i/(1-p_i)\) can cause the unit threshold to lie late even when many earlier trials exist.
Secretary instantiation: in a random ordering, “current candidate is best so far” produces record indicators; under the classical assumptions the last record is the overall best.
Not covered: correlated equipment failures violate independence because one failure may change later risk.
Not covered: selecting the largest observed value, rather than the last binary success, requires a different state and reward model.

Structural Tensions¶

Optimality vs. assumption fragility: the rule is exact under independence and known odds but can fail when either is wrong. Diagnostic: test conditional success probabilities after observed history.
Simple threshold vs. semantic encoding: computation is short, but deciding what counts as success may be contested. Diagnostic: define the indicator and reward before estimating \(p_i\).
Last opportunity vs. expected reward: catching the final success may not maximize payoff when successes have unequal values. Diagnostic: compare the binary win criterion with the actual utility function.
Known horizon vs. operational uncertainty: the theorem uses a finite terminal index. Diagnostic: determine whether \(n\) is fixed before observation.
Odds dominance vs. numerical stability: \(p_i\) near one creates very large odds. Diagnostic: handle deterministic or near-deterministic events explicitly.
No recall vs. practical reversibility: some applications allow returning to an earlier offer. Diagnostic: verify that rejected successes truly cannot be recovered.

Structural–Framed Character¶

The algorithm is strongly structural within optimal stopping: any qualifying application has the same indicators, odds, suffix threshold, forward stop, and last-success objective. It is framed by probability and decision theory because independence, filtration, stopping time, and Bernoulli odds are literal technical roles.

Replacing success with a metaphorical “good moment” without a probability model destroys the theorem. Thus the candidate is not promoted to a prime despite its clean skeletal form.

Structural Core vs. Domain Accent¶

The structural core is “accumulate evidence backward to set a forward action threshold.” That shape appears elsewhere, but the unit boundary and optimality depend specifically on the algebra of independent Bernoulli odds and a last-success reward.

Optimal Stopping Rule captures the general choice of when to stop under sequential uncertainty. Odds Algorithm adds a theorem-specific sufficient statistic and policy. Its autonomous residual therefore warrants a domain-specific node.

Optimal Stopping Rule is the proposed minimal parent. The odds algorithm is a strict specialization supplying a closed-form optimal rule for a last-success subclass. It inherits irrevocable sequential choice and adds independent indicators, known odds, reverse unit crossing, and first-success execution.

Probability, thresholding, and backward accumulation are related ideas but are less literal parents. The secretary problem is an instantiation or neighbor, not a genus.

Relationships to Other Abstractions¶

Current abstraction Odds Algorithm Domain-specific

Parents (1) — more general patterns this builds on

Odds Algorithm is a kind of Optimal Stopping Rule Prime

Optimal Stopping Rule is the proposed minimal parent.

Neighborhood in Abstraction Space¶

Odds Algorithm sits in a sparse region of the domain-specific corpus (96^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

Bellman Equation — 0.78
Negative Hypergeometric Distribution — 0.77
Progress Indicator — 0.76
Generalized Semi-Infinite Programming — 0.76
Problem of Points — 0.76

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Optimal Stopping Rule: the general parent class.
Secretary problem: a particular best-choice family, only some forms of which instantiate the odds theorem.
Odds ratio: a statistical comparison measure, not this stopping algorithm.
Probability threshold: the algorithm sums odds rather than raw probabilities.
Last-arrival problem: a related stopping family with different observation structure.
Multiple-stopping odds algorithms: extensions with more than one stopping opportunity.

References¶

[1] F. Thomas Bruss, “Sum the Odds to One and Stop,” The Annals of Probability 28, no. 3 (2000): 1384–1391, https://doi.org/10.1214/aop/1019160340. registry ↩a ↩b

[2] F. Thomas Bruss, “A Note on Bounds for the Odds Theorem of Optimal Stopping,” The Annals of Probability 31, no. 4 (2003): 1859–1861, https://doi.org/10.1214/aop/1068646368. registry ↩a ↩b