The Odds Algorithm for Stopping on the Last Success

Suppose you observe a sequence of independent events one at a time — each either a "success" or not — and you must decide, on the spot, whether to stop at the current success or keep going, with no ability to go back. You want to maximize the chance you stop on the last success in the whole sequence. The odds algorithm (Bruss, 2000) gives an exact rule: at each step, compute the odds of success at that step (probability of success divided by probability of failure), sum those odds from the current step to the end, and stop at the first success once that remaining sum drops below 1.

The rule generalizes the classic secretary problem, where you interview candidates one by one and must accept or reject on the spot to maximize the chance of picking the single best candidate — that's the special case where each step's success probability is $1/k$ for the $k$-th candidate, and the odds algorithm's cutoff reproduces the familiar "reject the first 37% automatically, then take the next candidate better than all seen so far" rule.

Worked example

With independent success probabilities $p_1, \ldots, p_n$, the odds at step $k$ are $r_k = p_k / (1-p_k)$. If the sum of remaining odds $r_k + r_{k+1} + \cdots + r_n$ is still above 1 at step $k$, keep going even if step $k$ is a success; once that remaining sum first falls below 1, stop at the next success you see. For the secretary problem with $n=100$ candidates, this threshold works out to roughly candidate 37 — reject the first 37 outright, then accept the next one who beats everyone seen so far.