The rank that remembers every value

The stopping problems on this path have each named one thing to be good at. When to stop looking wanted the single best candidate and counted anything else as failure. When every value comes from the same hat wanted the largest value on average and did not care about rank. Between those lies an objective that sounds modest and turns out to be the hardest of them: keep one value whose rank among all of them is as low as possible on average, where rank 1 is the best, rank 2 the second best, and so on.

The difference from the secretary problem is that near misses count. Keeping the second best is not a failure; it costs one rank rather than everything. The difference from the prophet problem is that only order matters: keeping a value that is barely beaten costs the same as keeping one that is beaten by a mile, provided the number of values beating it is the same.

The figure’s rising curve is what a simple rule achieves as the number of values grows. The horizontal lines are what is known about every rule. The gap between the bottom two, $1.908$ and $2.3267$, is the size of the ignorance: after three decades of work nobody knows the best achievable expected rank to within four tenths.

Told only who leads: 3.8695 #

Start with the version that is solved. The values are hidden; at each arrival the chooser learns only whether the newcomer beats everything so far, or more generally its rank among the values seen so far.

Yuan Shih Chow, Shigeru Moriguti, Herbert Robbins and Stephen Samuels solved this in 1964, and giving up on the best follows their backward induction step by step. The best rule keeps the $i$-th arrival when its relative rank among the first $i$ is at most a cutoff that rises as the end approaches: early on only a leader is acceptable, later a second-best-so-far will do, near the end almost anything. As the number of values grows, the expected rank of what the best rule keeps rises to the limit

$$\prod_{j=1}^{\infty} \Big(1 + \frac{2}{j}\Big)^{1/(j+1)} \approx 3.8695.$$

Two things are worth noting. The limit is finite: with a million values, the best rule keeps something whose rank is under four on average, even though it never sees a single value. And the rule is memoryless in a precise sense — the decision at each arrival depends only on its relative rank and its position, not on the pattern of ranks before it. The relative ranks of successive arrivals are independent, the same fact add the odds from the end used for leaders, so the past carries no information about the future and nothing needs to be remembered.

Two values, by hand #

The smallest case already shows what the values are worth. With two values and only ranks seen, the first arrival carries no information at all — it leads a field of one — so every rule is equivalent to guessing, and the expected rank is $1.5$.

Shown the values, the chooser keeps the first value $x$ when that costs less than waiting. Keeping it costs $1$ plus the chance $x$ that the second value beats it; waiting costs $1$ plus the chance $1 - x$ that the first value, now rejected, beats the second. So the first value is kept when $1 + x \le 2 - x$, that is when $x \le \tfrac12$. The expected rank is then

$$\int_0^{1/2} (1 + x)\,dx + \int_{1/2}^1 (2 - x)\,dx = \tfrac58 + \tfrac58 = 1.25.$$

Already at two values the second term shows the feature that makes the whole problem hard: the cost of waiting depends on the value rejected, because it stays in the field and may beat what comes next. At two values that dependence is harmless, since there is nothing left to decide. From three values on, it is the whole difficulty.

Shown the values #

Now show the values, drawn independently and evenly from $0$ to $1$ with low good, as in the prophet problem. A value of $0.003$ is excellent whatever else has been seen; a value of $0.4$ early in a long sequence is poor, however it compares with its predecessors. The value tells the chooser how good the arrival is against the whole population, not only against the handful seen so far.

That information is worth a great deal. The simplest rule that uses it keeps the first value below a bar that depends only on the position,

$$t_i = \frac{c}{n - i + c},$$

where $n - i$ is the number of values still to come after position $i$ and $c$ is one constant. The bar starts near $c/n$, rises slowly and shoots up to $1$ at the end, where anything must be accepted.

The shape of the bar has a one-line explanation. With $k$ values still to come, a value $x$ will be beaten by about $kx$ of them. Keeping it costs about $1 + kx$ ranks from the future, plus whatever values already seen beat it. Waiting costs a fixed amount, roughly the expected rank the rule will get from the rest. So the rule should keep $x$ when $kx$ is below a constant — that is, when $x$ is below a constant over $k$. The $+c$ in the denominator just keeps the bar finite at the end.

At forty values the three runs keep ranks 1, 2 and 3. The rule never looks at anything but the value in hand and the count of what is left.

The one constant, and why it barely matters #

The whole family is indexed by $c$, and for each number of values there is a best choice.

For ten values the best constant is $1.42$, for a hundred $1.78$, for eight hundred $1.90$, drifting upwards as the number grows. The expected rank at those minima is $1.814$, $2.228$ and $2.313$, and it keeps rising, towards a limit Moshe Assaf and Ester Samuel-Cahn computed in 1996 as about $2.3318$.

The curves are flat at the bottom. For a hundred values, moving $c$ from $1.5$ to $2.1$ costs less than two hundredths of a rank. What matters is the shape of the bar, not its exact height: a standard that relaxes like one over the number of values left. That shape is exactly what a rule seeing only relative ranks cannot express, because it has no way of saying “this value is in the bottom one per cent” — it can only say “this value leads the eleven seen so far”. The step from $3.87$ to $2.33$ is the value of that one piece of information.

A run that settles late #

The average hides how widely the outcomes spread.

Twelve values, three runs. The first finds an excellent value at the second position and keeps it — the best of the twelve, a stroke of luck the bar was set to exploit. The second keeps its seventh value, ranked third. The third run is the instructive one: nothing falls below the bar until position eleven, by which time the bar has risen above one half, and it keeps a value that five of the twelve beat.

The rule is not wrong in the third run. Its early bar was low because accepting a mediocre early value would have been expensive against the many values still to come; the run was simply poor, and the bar’s rise near the end is what limits the damage. The expected rank, just under two at twelve values, averages many runs like the first against a few like the third. It is a smaller number than the secretary problem’s success chance suggests, because the secretary problem counts rank 2 as a total loss and this one counts it as nearly a win.

Why the best rule has to remember #

Here is where the problem changes character. In every stopping problem earlier on this path, the best rule could be found by backward induction on a small state: the position and the value in hand, or the position and the relative rank. That is because the reward depended only on the thing kept.

Rank does not. The rank of the value kept is one plus the number of values that beat it, and that includes values already rejected. So the reward from keeping $x$ at position $i$ depends on how many of the previous values were below $x$ — which depends on all of them. The state of the problem at position $i$ is the whole list of values seen, and that list grows with $i$.

The figure below is the best rule for three values, computed exactly. It is the smallest case where history matters.

The derivation fits in a paragraph. Keeping the third value costs, on average, $1$ plus the chance that each of the first two beats it: $1 + (1 - x_1) + (1 - x_2) = 3 - x_1 - x_2$. Keeping the second value costs $1$, plus one if the first value beat it, plus the chance $x_2$ that the third will. So at the second position the rule keeps $x_2$ when $1 + [x_1 < x_2] + x_2 \le 3 - x_1 - x_2$. When $x_2$ beats $x_1$ this is $x_2 \le 1 - x_1/2$; when $x_1$ beats $x_2$ it would need $x_2 \le (1 - x_1)/2$, which cannot happen together with $x_2 > x_1$ once $x_1 > 1/3$, and the first value is only ever rejected when it exceeds $0.349$. So the second value is kept only when it leads, and then only up to the bar $\min(x_1,\, 1 - x_1/2)$.

The bar for the second value depends on the first. And in a direction that looks backwards at first: a worse first value makes the rule stricter at the second. At $x_1 = 0.5$ the second is kept if it is below $0.5$; at $x_1 = 0.9$ only if it is below $0.55$ — hardly more generous, although a first value of $0.9$ is far worse. The reason is that a bad first value also helps the third: whatever comes last will probably beat it, so going on is cheaper than it would be after a good first value. The rejected value has not gone away; it sits in the rank of everything that comes after.

The gain from remembering is small at three values — $1.3915$ against $1.4009$, less than one per cent — but it is not zero, and it cannot be had by any rule with one bar per position. For larger numbers of values the exact best rule has not been computed, because the state grows with every arrival.

The bounds, and what lies between #

The last figure puts every number on one scale.

The two middle bars are close together and far from both ends. Most of the improvement over the rank-only rule comes from the simplest possible use of the values, and everything cleverer that has been tried since has moved the upper bound in its third decimal. The same pattern appeared in half of what an oracle takes, where one fixed threshold already secured the guarantee the best rule could not beat by much.

The lower bound, $1.908$, is due to F. Thomas Bruss and Thomas Ferguson in 1993. It comes from a relaxed problem: allow the chooser, at each step, to know slightly more than it should — enough to make the problem memoryless again — and solve that. Whatever the relaxed chooser can achieve, the real one cannot beat. The upper bound comes from exhibiting rules. Assaf and Samuel-Cahn’s one-constant family gives about $2.3318$ in the limit; later rules with more carefully shaped bars, still memoryless, bring it to about $2.3267$.

Bruss and Ferguson also showed that for every number of values from three upwards the truly best rule is history-dependent, as the three-value picture shows. What is not known is whether that dependence is worth anything in the limit. It is conceivable that as the number of values grows, the best memoryless rules come within any given margin of the best rule overall, in which case the answer is somewhere near $2.33$ and the lower bound is simply weak. It is also conceivable that remembering is worth a real fraction of a rank, and the answer is nearer $2$.

Why this is harder than the prophet problem #

It is worth saying exactly what separates this problem from the solved ones, because the difference is small to state.

In the prophet problem the reward is the value kept. A value is a function of the present alone, so backward induction runs on one number per position — the bar $v_k$ — and the whole rule is a list of $n$ numbers. In the full-information secretary problem of when the numbers are shown the reward is whether the value kept is the best, and that depends on the past only through its best value; a value that does not lead is never kept, so the past can be summarised by one number, and the rule is again a list of bars. In the rank-only version the relative ranks are independent, and again the past is irrelevant.

In Robbins’ problem the reward depends on the count of past values below the one kept, and on the future through the same kind of count. Neither can be summarised by one number. A rule that is optimal at a thousand values must, in principle, respond to the whole configuration of 999 previous values — and whether that response is worth computing is the open question.

This is the same distinction the rule that forgets where it came from makes for chains: a process whose next step depends only on its present state can be analysed one state at a time, and one that depends on its history cannot, unless the history can be folded into a bigger state. Here it can be folded only into a state that grows without bound.

What the figures can and cannot show #

The family’s expected ranks are exact. For a rule with a bar per position, the expected rank of what it keeps is a finite sum over positions of the chance of stopping there times the expected rank given stopping there, and each term is a polynomial in the bars. The curve in the first figure evaluates that sum; it is not a simulation. The runs in the third and fifth figures are simulations, shown only to make the rule visible.

Only one value is kept. Allowing two or more acceptances, as the thresholds that nest did for the chance of holding the best, changes the objective again — the rank of the best of those kept — and inherits the same dependence on everything rejected.

The three-value rule is exact up to the numerical integral. Its region and its value, $1.3915$, come from the formulas above, integrated on a fine grid; the best one-bar-per-position rule is found by searching every pair of bars on a grid of spacing $0.0025$.

The bounds are quoted. Neither $1.908$ nor $2.3267$ is computed here. The first is Bruss and Ferguson’s; the second is the best memoryless rule in the literature. The figure checks only that the one-constant family stays above the second and below the family’s own limit.

Still open: does remembering pay in the limit? #

The question Herbert Robbins asked is one number: the limit, as the number of values grows, of the least expected rank any rule can achieve. It is known to exist, because the least expected rank rises with the number of values and is bounded. It is known to lie between $1.908$ and $2.3267$.

Its value is not known, and neither is the answer to a sharper question: whether rules that use the history do better, in the limit, than the best rules that use only the position and the value in hand. If they do not, the problem is essentially a problem about memoryless bars, and the answer is somewhere very close to the upper bound. If they do, the best rule is something genuinely new — a rule whose bar at each moment is shaped by the configuration of everything it has already let go — and nobody has written one down.

One word changed #

The habit worth keeping is to ask of an objective what it depends on.

Three problems on this path use the same arrivals, the same irrevocable decisions and the same backward reasoning. One asks for the largest value, one for the best rank, one for a low rank. The first two collapse to a list of numbers, because what they reward depends on the present alone or on the past through one summary. The third rewards something that depends on everything, and the same apparatus that solved the others in a page has left it open for three decades. Changing what counts as winning changed what has to be remembered, and what has to be remembered decided whether the problem could be solved.