Skip to content

Odds algorithm

Find the optimal last-success selection window with Bruss’s backward odds rule, and distinguish this objective from maximising trading reward.

The odds algorithm is Bruss’s rule for maximising the probability of selecting the last success in a finite sequence of independent binary trials, observed one at a time without recall. It turns this particular optimal stopping problem into a backward sum. For quant modelling, its first lesson is to specify the objective: correctly identifying the final qualifying signal is different from maximising a trade’s expected profit.

Build the window backward; make the choice forward

Let IjI_j be a Bernoulli indicator, with Ij=1I_j=1 denoting success. Assume a fixed horizon nn, mutually independent trials and probabilities pj=P(Ij=1)p_j=\mathbb{P}(I_j=1) known before observation. Here we restrict to 0≤pj<10\le p_j<1, so the odds are finite:
qj=1−pj,rj=pjqj.q_j=1-p_j,\qquad r_j=\frac{p_j}{q_j}.

You may select one observed success and cannot return to a rejected one. Selecting a success followed by another success loses; a sequence with no successes also loses.

Starting at trial nn, add rn,rn−1,…r_n,r_{n-1},\ldots until the running total first reaches or exceeds one. Call that index ss. If the total never reaches one, set s=1s=1. Ignore trials before ss, then select the first success at or after ss. If none appears, lose. This is the optimal rule among all decisions based on observations so far, not just among rules with a fixed starting index. See Bruss’s original theorem and algorithm, §§2–2.1.
The backward calculation uses known probabilities; the forward decision uses the current observation. It never reveals future outcomes. Also, sum odds, not probabilities.

Three chances, one irreversible selection

Take the stipulated probabilities

(p1,p2,p3)=(0.20,0.50,0.25),(r1,r2,r3)=(14,1,13).(p_1,p_2,p_3)=(0.20,0.50,0.25),\qquad (r_1,r_2,r_3)=\left(\frac14,1,\frac13\right).

Working backward, trial 3 contributes 1/3<11/3<1. Adding trial 2 gives 4/3≥14/3\ge1, so s=2s=2. Discard trial 1 even if it succeeds. Then:

  • If trial 2 succeeds, select it; win only if trial 3 fails. This event has probability 0.50×0.75=0.3750.50\times0.75=0.375.
  • If trial 2 fails and trial 3 succeeds, select trial 3 and win. This event has probability 0.50×0.25=0.1250.50\times0.25=0.125.

The win probability is therefore 0.375+0.125=0.5000.375+0.125=0.500. Trial 1 can have either outcome: an earlier discarded success does not prevent a later selection from being the last success.

Known independent success probabilities are 0.20, 0.50 and 0.25. Backward odds cross one at trial 2. Starting acceptance at trials 1, 2 and 3 gives last-success win probabilities 0.475, 0.500 and 0.250 respectively.
Known independent success probabilities are 0.20, 0.50 and 0.25. Backward odds cross one at trial 2. Starting acceptance at trials 1, 2 and 3 gives last-success win probabilities 0.475, 0.500 and 0.250 respectively.
Original stipulated example. The acceptance window begins at trial 2; the three bars compare probabilities of selecting the last success, not expected payoffs.

Starting at trial 1 instead wins with probability 0.4750.475; waiting until trial 3 wins with probability 0.2500.250. Accepting earlier creates a risk of stopping before the final success. Waiting longer sacrifices the chance to select trial 2 when it is the final success.

Why the odds enter

For any starting index kk, the first success in the suffix k,…,nk,\ldots,n is also its last exactly when that suffix contains one success. Write its win probability as WkW_k. Independence gives
Wk=∑j=knpj∏i=k\i≠jnqi=(∏i=knqi)(∑j=knrj).W_k=\sum_{j=k}^{n}p_j\prod_{\substack{i=k\i\ne j}}^{n}q_i =\left(\prod_{i=k}^{n}q_i\right)\left(\sum_{j=k}^{n}r_j\right).

In the example, W2=(0.50×0.75)(1+1/3)=0.500W_2=(0.50\times0.75)(1+1/3)=0.500. A useful check on the threshold comes from subtracting neighbouring choices:

Wk−Wk+1=pk(∏i=k+1nqi)(1−∑j=k+1nrj).W_k-W_{k+1} =p_k\left(\prod_{i=k+1}^{n}q_i\right) \left(1-\sum_{j=k+1}^{n}r_j\right).
Including trial kk helps when the later odds sum is below one and hurts when it is above one, provided pk>0p_k>0. Equality can produce tied thresholds. This explains the backward crossing; the theorem additionally establishes optimality over observation-dependent rules. Bruss’s later author note, §2 restates the threshold and value.

Where the shortcut stops

With two independent trials each having p=0.10p=0.10, total odds are 2/9<12/9<1. Start immediately: the win probability is 2(0.10)(0.90)=0.182(0.10)(0.90)=0.18. A threshold rule does not ensure a high chance of winning when successes are scarce.

A certain success, pj=1p_j=1, lies outside the finite-odds formulas used here; direct substitution divides by zero. Bruss treats that case separately. Unknown probabilities and dependence also require further analysis: past outcomes can then change what should be believed about future trials.

For a financial comparison, American Options and Early Exercise develops exercise versus continuation to maximise expected discounted payoff (public preview; full lesson requires membership). That objective and its dependent price process require their own stopping analysis; applying this last-success threshold to price increases does not establish an optimal exit policy.

Sources

Last updated
  • optimal stopping
  • bernoulli trials
  • odds
  • sequential selection
Keep connecting the ideas
← Back to the glossaryBack to top ↑