When the numbers are shown

The rung below established a ceiling: no rule for the secretary problem wins more than about $37\%$ of the time, however many candidates there are. That ceiling depends on a hypothesis that is easy to miss — the chooser is told only the relative ranking, and nothing about how good anybody actually is.

Change that one thing and the ceiling moves.

Three in five rather than one in three, and the whole difference is information.

Why the value tells more than the ranking #

A candidate who leads the field so far, in the relative-ranking version, has told the chooser one bit: better than everything seen. A candidate with a value has told them much more.

Suppose the values are drawn independently from the uniform distribution on $[0,1]$, which is known to the chooser — a piece of prior knowledge used exactly as a prior is used in updating, to turn an observation into a probability. A candidate with value $x$ and $j$ still to come is the overall best exactly when all $j$ remaining fall below $x$, and that probability is $x^{j}$ — a number that can be computed rather than a ranking that cannot.

So accepting is worth $x^j$ and continuing is worth whatever optimal play from here is worth, and comparing the two is a comparison of two numbers. The rule is: accept when $x^j$ exceeds the value of continuing, which is a threshold on $x$.

The relative-ranking version has no such comparison available. A leader at position $i$ is the overall best with probability $i/n$ whatever their quality, so the only lever is position — which is why its rule has one number in it and this one has a different threshold at every step.

The thresholds fall #

The rule’s shape is the informative part, and it is the opposite of what the relative-ranking rule does.

Early on, with many candidates still to come, a value has to be very high to be worth taking: $x^{j}$ is small unless $x$ is close to one. Late on, with two left, a moderately good value is worth taking because there is little chance of improvement.

So the thresholds decrease as the end approaches, from close to one at the start down towards nothing at the last position — where anything is accepted, since the alternative is nothing.

That is a genuinely different shape of rule. The relative-ranking version has a hard switch: reject everything for a while, then take the first leader, with the standard never changing. This one never rejects outright and never accepts outright; it demands a falling standard throughout.

Both are threshold rules and they threshold different quantities — one thresholds the position, the other the value — and the difference is exactly what the extra information buys.

There is a consequence for how the two rules behave when they are set slightly wrong, and it favours the poorer one. The relative-ranking rule’s success curve is flat near its peak: passing over two, three or four of seven candidates all win between $33$ and $36$ per cent, so a rule tuned by guesswork loses almost nothing. The value-based rule’s thresholds are a list of real numbers, and a systematic error in the assumed distribution shifts all of them in the same direction, which compounds down the sequence rather than cancelling.

A rule that uses less is harder to break, which is a general property of procedures that consume little information and is the reason the relative-ranking version survives in practice even where values are available.

Where the constant comes from #

$0.5802$ is not a number with a closed form as tidy as $1/e$, and knowing what it is a solution to is worth more than the digits.

The backward induction produces a sequence of thresholds, and in the limit the $k$-th from the end behaves like $1 - c/k$ for a constant $c$ satisfying an equation involving an integral of $(e^t - 1)/t$. The success probability converges to $0.580164\ldots$, and the constant is defined by that equation rather than by any familiar expression.

The absence of a tidy form is informative. The $1/e$ in the relative-ranking version comes from maximising $x\ln(1/x)$, which is one line of calculus; this one comes from a recursion that does not collapse, and the difference is that the relative-ranking problem forgets everything except the position while this one carries a real number of state.

The figures compute the answer numerically and check it against the two sizes where an exact answer is known: $3/4$ at two candidates and $0.6842$ at three. Reproducing a known exact value is the only available check on a grid computation, and it is what the assertions are.

What the extra information is worth #

Putting the two versions beside each other gives a number for the value of information, which is a thing this field rarely produces so cleanly.

Relative rankings only: $1/e \approx 0.368$. Values from a known distribution: $0.580$.

The ratio is about $1.58$, so knowing the distribution and seeing the numbers is worth a bit over half as much again. That is a large gain and it is bounded: even with complete information about the distribution, four times in ten the best candidate is missed.

Why it is bounded is the interesting half. The remaining loss is not ignorance about the distribution; it is the irrevocability. A very good candidate arriving first is genuinely ambiguous — it may be the best, and the chooser must decide without knowing — and no amount of distributional information resolves that. What remains after the information is added is the cost of having to decide at all — and that cost, unlike ignorance, cannot be bought off.

The rule the rung below found converges too, and to a smaller number by a different route, so its curve is worth having beside this one.

And one more constant from the same family, which this rung turns into evidence for a caution the rung below issued.

What backward induction is doing #

The computation deserves a paragraph on its own, because it is the standard method for every problem on this ladder and its shape is worth recognising.

The question is what to do now, and the answer depends on what would be done later — so the calculation runs from the end, where there is nothing later and the answer is forced. With no candidates remaining the value of continuing is nought. With one, accept whatever arrives. With two, the value of continuing is what the one-candidate case is worth, and the threshold follows.

Each step is a comparison between a number that can be computed and a number computed at the previous step, and the recursion never looks forward. That is what makes it finite: the future has been summarised into a single quantity before the present is considered.

The rung below’s argument has the same shape and is simpler because its state is smaller. There, the value of continuing depends only on how many remain; here it depends on how many remain and on the best value seen, so the summary is a function rather than a number and the recursion carries a whole curve from step to step.

That is the general cost of information. Knowing more means the state carries more, and the state is what a backward induction has to summarise — so a better-informed problem is a harder computation, and the two are not independent. A chooser told the values has a better rule and a much more expensive one to find.

What the rule needs to know #

The gain has a price and it is worth listing exactly what has been assumed.

The distribution is known. Not merely that one exists — the chooser needs it to compute $x^j$. Knowing the values without knowing the distribution is a third problem, and it is much closer to the relative-ranking one.

The values are independent and identically distributed. Dependence between candidates changes every conditional probability, and a trend over time — candidates getting better — changes the whole shape of the answer.

And the scale does not matter. Any strictly increasing transformation of the values leaves the problem unchanged, since the rule only ever compares — the same invariance a rank-based statistic has and for the same reason. So the uniform distribution is not a special case: any known continuous distribution gives the same $0.5802$, with the thresholds transformed accordingly.

That last is the reassuring one. The answer depends on knowing the distribution and not on which distribution it is, which is what makes the constant a constant.

What the rule looks like at the start and at the end #

Two extremes are worth working out because they are where the falling standard is most visible and where it is easiest to check by hand.

At the last position the threshold is nought. Nothing remains, so accepting wins whenever the current value is the overall best, and rejecting wins never. Any value is accepted.

At the second-to-last position the threshold is $1/2$, and the arithmetic is the two-candidate case from the section above: accepting a value $x$ wins with probability $x$, continuing wins with probability $1 - x$, and the two are equal at a half.

Earlier than that the arithmetic stops being a line. With two still to come, accepting a value $x$ wins with probability $x^2$; continuing is not worth the two-candidate problem’s $3/4$, because rejecting $x$ forfeits the game entirely if $x$ turns out to be the overall best. The continuation value therefore depends on $x$ itself, through the largest value already passed over, and the comparison is between a power and a function rather than between a power and a number.

That is exactly the point at which the problem stops being solvable by hand and the backward induction has to carry a curve. The figures compute those thresholds; the caption reports the first few, and they rise towards one as the number still to come grows.

Read from the end the thresholds rise; read forwards they fall, and the second reading is the one a chooser uses: demand a great deal early, relax steadily, and take whatever is offered at the last position.

Where the computation is delicate #

The state is a real number. The relative-ranking problem’s state is a position and a bit — the whole reduction its rung below turns on — and this one’s is the value of the best seen so far, a continuous quantity, so the backward induction is over a function rather than over a list. The figures discretise it, and the check that the discretisation is fine enough is the reproduction of the exact small cases.

The recursion is over functions. At each step the value of continuing is a function of the current best, and the integral defining it is over the whole range. Computing it naively costs the square of the grid size at every step; the figures use a running suffix integral, which is one pass.

And the limit is approached slowly. At forty-six candidates the answer is still above $0.586$ against a limit of $0.5802$, so the figures show a curve heading somewhere rather than arriving. The relative-ranking version converges much faster, which is the difference between a discrete optimisation and a continuous one.

The distribution has to be the right one, and knowing it is a strong assumption. In every application the values come from somewhere whose distribution is estimated rather than given, and a rule computed against the wrong distribution can do worse than the relative-ranking rule, which assumed nothing. That is the standing hazard of a method that uses more information: it is better when the information is right and it has further to fall when it is not.

There is a middle position worth naming, because it is where practice sits. If the distribution is unknown but the values are shown, the chooser can estimate it from the candidates already seen — and the resulting rule performs between the two constants, converging to the full-information answer as the field grows and to nothing better than $1/e$ when it is short. Learning the distribution costs candidates, and the cost is paid out of the same budget the choosing is paid from.

That trade has a shape this collection has met elsewhere. Passing over a third of the field is spending candidates to learn the scale of the field, and it is the same expenditure — the relative-ranking rule is already a learning rule, and what distinguishes it is that what it learns is only a ranking.

Gilbert and Mosteller, and a problem stated three ways #

John Gilbert and Frederick Mosteller published the full-information version in 1966, in a paper that treats several variants of the stopping problem at once — and that is the useful thing about it, because the variants differ in what the chooser is told and the answers differ correspondingly.

Their paper computes the case where values are known and drawn from a known distribution, the case where the number of candidates is random, and the case where several may be chosen — each of which is one hypothesis of the original problem moved. Each variant is one hypothesis changed and each has its own constant, which is a good demonstration that the famous $1/e$ belongs to a specific and rather restrictive setting.

The relative-ranking problem itself has no clear origin — Martin Gardner popularised it in 1960 and it was circulating before that — which is a common shape for a puzzle. The full-information version has a paper and a date because it needed one: the answer cannot be found without a computation.

That is worth registering. A problem whose answer is a line of calculus circulates as a puzzle; a problem whose answer is a numerical recursion needs a publication. The two versions differ by one hypothesis and belong to different literatures for that reason alone.

What the pictures cannot show #

The curve is ten computed points and the claim is about a limit. The last point is at forty-six candidates and the limit is at infinity, and the figure shows a descent that has not finished.

The thresholds themselves are computed and reported in the caption rather than drawn, because a plot of thresholds against position would be a second figure and the one thing worth knowing about them — that they fall — fits in a sentence.

And nothing here draws the value of information as such. Two numbers are computed under two hypotheses and the difference is arithmetic; what the difference means is a comparison between two problems, and a picture of one problem cannot contain it.

The ladder from here #

Rungs above: the expected-rank objective, where success is redefined and the answer becomes a rank rather than a probability. The prophet inequality, where the comparison is against a rule that has seen everything. The random-number-of-candidates variant, where not knowing $n$ changes the answer’s shape. The multiple-choice version, where several may be accepted and the thresholds nest. And the case where the distribution is unknown and must be learned from the candidates seen — which sits between the two versions on this page and is the one practice actually faces.

The ceiling that belonged to a hypothesis #

The habit is about how a bound gets read.

The rung below proved a ceiling: no rule beats $1/e$. That is a theorem and it is true, and it is a theorem about a class of rules operating on a particular kind of information. Quoted as “the secretary problem’s answer is $1/e$”, it reads as a fact about the situation rather than about the hypothesis.

Changing the hypothesis moves the ceiling by a factor of one and a half, and there is nothing about the original statement to say which hypothesis was doing the work. The way to find out is the one this rung takes: change each hypothesis in turn and see which one the constant depends on.

Here the answer is that it depends on the information, not on the irrevocability and not on the arrival order being random. The irrevocability costs something and it costs the same in both versions; what the relative-ranking assumption costs is the difference between $0.368$ and $0.580$, and that number is only available once both have been computed.