Add the odds from the end

The secretary problem looks like a problem about ranks: candidates in random order, compared with those already seen, and a single chance to pick the best. Its solution passes over about a third of the field and then takes the first candidate who beats everyone so far.

There is a way of reading the same problem in which ranks never appear, and in which the answer becomes a rule of one line for a much larger family of problems.

To stop on the last of a sequence of independent events that happen, add their odds from the end backwards until the total reaches one, and stop at the first event that happens from that point on. F. Thomas Bruss proved in 2000 that no rule does better, whatever the chances are.

The secretary problem, with the ranks taken out #

The reading comes from one fact about random orders. The $k$th candidate is the best of the first $k$ with chance exactly $1/k$, and — less obviously — whether it is has nothing to do with whether any earlier candidate was the best of its own prefix. The events “candidate $k$ is best so far”, for $k = 1, 2, \ldots, n$, are independent, with chances $1, \tfrac12, \tfrac13, \ldots, \tfrac1n$.

The best candidate overall is the last one that is best so far. So picking the best is exactly stopping on the last of these events to happen, and the ranks can be forgotten: all the problem needs is a sequence of independent events with known chances, watched in order, and a single chance to say “this one is the last”.

Put that way, nothing requires the chances to be $1/k$. A sequence of trials each succeeding with chance $p$, a set of opportunities of varying reliability, a series of observations in which the last positive result is the one that matters — all are the same problem with different numbers, and the figures on this page treat them together.

Why being best so far is independent #

The independence is what everything else rests on, and it has a short reason.

In a uniformly random order, the first $k$ candidates arrive in a uniformly random order among themselves. So the $k$th candidate’s rank among the first $k$ is equally likely to be any of $1, 2, \ldots, k$ — which is where the chance $1/k$ of being best so far comes from. And that rank says nothing about how the first $k - 1$ are ordered among themselves: every ordering of the first $k - 1$ is equally likely whichever place the $k$th slots into. Where a newcomer ranks among those before it is independent of how those before it rank among each other, and whether an earlier candidate was best so far is a fact about the earlier ones alone.

Applied at every position in turn, that makes the whole sequence of “best so far” events independent. It is not obvious — being best so far at position 5 feels as if it should make being best so far at position 6 harder — and it is exactly what fails if the candidates’ values are shown and drawn from a known distribution, where a large value seen early does change what the later values must beat.

The chance of winning from a given start #

A rule of the natural kind picks a starting event $s$ and stops at the first success at or after $s$. It wins exactly when there is exactly one success from $s$ on: then the first success from $s$ is also the last.

Write $p_k$ for the chance of event $k$, $q_k = 1 - p_k$ for the chance it fails, and $r_k = p_k/q_k$ for its odds. The chance of exactly one success among events $s$ to $n$ is the sum over which one it is, of that one succeeding and the others failing:

$$W(s) = \sum_{k=s}^{n} p_k \prod_{j \ne k} q_j = \left(\prod_{k=s}^{n} q_k\right)\left(\sum_{k=s}^{n} r_k\right).$$

The chance of winning is the chance that everything from $s$ on fails, times the total odds from $s$ on. The figures compute it both ways — the sum of products, which handles a certain event without dividing by nought, and the product times the sum wherever no chance is one — and separately enumerate every pattern of successes and failures among the events, 4,096 of them for twelve events, adding up the chances of the patterns on which the rule wins. The three agree for every starting event.

In the secretary case this is the classical formula exactly. The failures from $s$ on multiply to $\tfrac{s-1}{s}\cdot\tfrac{s}{s+1}\cdots\tfrac{n-1}{n} = \tfrac{s-1}{n}$, and the odds of event $k$ are $\tfrac{1/k}{1 - 1/k} = \tfrac{1}{k-1}$, so $W(s)$ is $\tfrac{s-1}{n}$ times a stretch of the harmonic series. The figure requires the odds formula to reproduce the rank-based chance at every starting point, and it does, to twelve places.

Three events, by hand #

Take three independent events, each happening with chance one half. Each has odds of exactly one.

Starting at event 3, the rule stops if event 3 happens, and it wins exactly then: a chance of one half. The formula agrees — the failures from event 3 multiply to a half, and the odds from event 3 add to one. Starting at event 2, the rule wins when exactly one of events 2 and 3 happens, which is a chance of one half again; the formula gives a quarter times two. Starting at event 1, it wins when exactly one of the three happens, three chances of one in eight, three eighths; the formula gives an eighth times three.

Adding the odds from the end, event 3’s odds are already one, so the rule starts at event 3. Starting at event 2 does exactly as well, and the comparison in the next section says why: the odds after event 2 add to exactly one, and at exactly one the two neighbouring starts tie. Only when the later odds pass one does starting earlier lose, and here starting at event 1 — with odds of two after it — does.

Why the odds decide where to start #

The rule says to start at the last event from which the odds add up to at least one. The reason is a comparison of neighbouring starts, and it is short enough to do in full.

Compare starting at $s$ with starting at $s + 1$. Write $R$ for the total odds from $s + 1$ on and $Q$ for the product of the failures from $s + 1$ on. Then $W(s+1) = QR$, and $W(s) = q_s Q\,(r_s + R) = Q\,(p_s + q_s R)$. Subtracting,

$$W(s) - W(s+1) = Q\,p_s\,(1 - R).$$

Starting one event earlier is better exactly when the odds after it add to less than one. As $s$ moves back from the end, $R$ only grows, so the comparison can switch once and never back: the win chance rises as the start moves back while the later odds total less than one, and falls once they total more. Its peak is at the last event from which the odds reach one — which is the rule.

That argument compares the rule only with other starting points, and Bruss’s theorem says more: no rule of any kind, however it uses what it has seen, does better. The reason is that once the remaining odds total less than one, stopping at the next success is better than waiting for a later one no matter what has happened, and before that point stopping is never better than waiting. The figures check the part they can check exhaustively, that the odds rule’s start is the best of all the starts.

Chances that do not change #

The simplest case is a sequence of trials with the same chance every time.

With every odds equal to $p/(1-p)$, the rule watches the last $m$ trials, where $m$ is the smallest number whose odds add to at least one, and the win chance is $(1-p)^m$ times that total. For $p = 0.2$, $m = 4$ and the chance is $0.8^4 = 0.4096$.

Starting one trial earlier, at event 8, does exactly as well. The odds after event 8 add to exactly one, and at exactly one the comparison of neighbouring starts gives a tie: starting at event 8 wins with chance $0.8^5 \times 5 \times 0.25$, which is also $0.4096$. So the curve in the figure has two equal highest points, at events 8 and 9, and the rule’s choice of the later one is a matter of convention. Whenever the odds from the end land exactly on one, the start is not unique — the three events of chance one half showed the same thing — and whenever they overshoot it, the start is.

As $p$ shrinks, $m$ is about $1/p$ and the win chance is about $(1-p)^{1/p}$, which tends to $1/e$. The rarer the successes, the closer the answer comes to the secretary problem’s, and in the limit the two are the same number for the same reason: the constant that counts arrangements with nothing in its place is the chance that a long run of rare events produces none, and the rule wins when exactly one occurs.

The secretary problem, again #

In the secretary case the odds of event $k$ are $1/(k-1)$, and adding them from the end, $\tfrac{1}{n-1} + \tfrac{1}{n-2} + \cdots$, reaches one when about a fraction $1/e$ of the field remains unwatched at the start — because the harmonic sum from $s$ to $n$ is about $\ln(n/s)$, and that equals one at $s = n/e$. Passing over a third of the candidates is where the odds add up to one, and the rank-based argument of the original essay was computing the same thing in a different notation.

Seen this way the secretary rule’s constant is not special to ranks at all. It is the answer for any sequence of events whose odds add up slowly from the end, and the $1/e$ is the answer for any such sequence in which the successes become rare. Bruss also showed that whenever the odds add up to at least one, the rule wins at least a fraction $1/e$ of the time, so the secretary problem is the worst case of its own generalisation in that range — the figures require that bound for every case they draw in which the odds reach one.

Chances that fall along the sequence #

Nothing in the rule needs the chances to follow a pattern. Early events that are very likely to happen have large odds, but they are far from the end, and the rule never reaches them: what matters is how quickly the odds accumulate counting backwards. A sequence whose last few events are likely would start watching very late; one whose last events are unlikely starts early. The rule reads the whole sequence of chances through one number, the point at which the backward total crosses one.

When the odds never reach one #

If every event is unlikely and there are not many of them, the odds may add up to less than one even counted from the very first event. Then the rule starts at the beginning and stops at the first success of all.

That is the right thing to do, and the comparison of neighbouring starts says so: with the later odds always below one, starting earlier is always at least as good. The chance of winning is still the failures multiplied by the total odds, and it is small. With ten events of chance 0.05 each the odds add to about 0.53, the rule watches all ten, and it wins when exactly one of them happens — about 32 per cent of the time.

The rule’s answer does not have to be a good chance; it has to be the best one available, and when successes are too rare to expect even one, the best available is to take the first that comes. The lower bound of $1/e$ quoted above applies only once the odds reach one, and a sequence too short or too unlikely to reach it can fall well below.

Where the theorem needs its hypotheses #

The events must be independent. The win chance factorises into a product and a sum only because the events do not influence each other, and the comparison of neighbouring starts uses that factorisation. In the secretary problem the independence is a theorem about random orders; in a model of real observations it is an assumption that has to be justified.

The chances must be known in advance. The rule is computed before anything is observed. If the chances have to be estimated from the events themselves, the rule becomes a guess about the odds, and the theorem does not cover the guess.

The goal is the last success, and nothing else. Stopping on one of the last two successes, on a good rank rather than the best, or on the largest of several values, is a different problem; the full-information version and several acceptances each needed their own analysis.

And the enumeration covers fourteen events at most. The figures list every pattern of successes, $2^n$ of them, which is why they stop there; the formula and the theorem hold for any number.

Where the rule came from #

Bruss published Sum the odds to one and stop in the Annals of Probability in 2000. The title is the theorem. Its interest was not that the secretary problem had been unsolved — it had been solved for forty years — but that a problem previously solved by a calculation particular to ranks turned out to be one instance of a rule so simple it could be stated in six words, and that the same rule applied at once to problems nobody had connected with the secretary problem at all.

It also sits at the opposite end from the prophet inequality, where a single threshold fixed in advance is measured against someone who sees everything: there the question is how much a simple rule gives up, and here the answer is that the simple rule gives up nothing.

The comparison of neighbouring starts that proves the rule is an instance of what is called the monotone case in the theory of optimal stopping: a region of the problem in which, once entered, it never pays to look further than one step ahead. The secretary problem, the odds problem and many of their relatives have that structure, and it is why their answers are thresholds rather than something more complicated.

Still open: what replaces the odds when the events depend on each other #

Everything on this page used independence twice: to write the win chance as a product times a sum, and to know that the odds still to come do not depend on what has already happened. Take independence away — let a success make the next success more likely, or less — and both uses fail at once.

For some kinds of dependence the structure survives in a modified form. When the events are linked in a chain, each depending only on the one before, there are versions of the rule in which the odds are replaced by conditional odds updated as the sequence runs. But there is no single number, computable in advance and read off once, that plays the part the backward sum of the odds plays here, and the question of when a rule of that simplicity still exists does not have a general answer on this page.

A problem about ranks that was not about ranks #

The habit is about recognising what a problem is actually using.

The secretary problem is always stated in terms of ranks — comparisons between candidates, a best so far, a best overall. The solution used those ranks in only one way: to produce a sequence of independent events with chances $1/k$. Everything else about ranks was scaffolding, and removing it left a problem whose answer is a rule anybody can apply to any chances.

That is a common shape. A problem arrives dressed in the vocabulary of its first application, and its solution depends on only a fraction of what the vocabulary describes. Finding that fraction — here, a sequence of independent events and the goal of stopping on the last — is often the whole of the generalisation, and the generalised answer is usually simpler than the special one it replaces.