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.

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.

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.

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.

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.

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.

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.

Hierarchy paths (5) — routes to 5 parentless roots

• Odds Algorithm → Optimal Stopping Rule → Decision → Constraint

Show alternative paths (4)

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