When every value comes from the same hat

Half of what an oracle takes compared a rule that sees values one at a time with a prophet who sees them all in advance. Each value is drawn from its own known distribution; the rule must keep or discard each as it arrives and may keep only one; the prophet simply keeps the largest. One fixed threshold secures half of the prophet’s expected take, whatever the distributions — and there is an example, with one value that is almost always nought and occasionally enormous, on which half is all any rule can get.

That example needed the distributions to differ. Its trick was to put all the danger in one position: a modest sure value first, then a long shot that pays off rarely and hugely. Suppose instead that every value comes from the same distribution, independently — the same hat, drawn from again and again. The adversary can no longer make one position special. How much does that buy?

The answer, in the figure, is a great deal. For values uniform on $[0, 1]$ the best rule collects $99.5\%$ of the prophet’s take by two hundred values. For exponential values it collects $90\%$ and climbing. For heavy-tailed values it holds at about four fifths. And in no case, for any distribution and any number of values, does it fall below $0.745$ — a constant found in 1986 and proved to be the exact answer only in 2017.

The best rule is a falling standard #

With identical values the best rule is easy to describe, and it is the same shape when the numbers are shown found for a different objective: a standard that falls as the end approaches.

Work backwards. With one value left, there is no choice: it must be kept, and it is worth its mean, $v_1 = \mathbb E[X]$. With two left, the value in hand should be kept exactly when it beats what the last value is worth on average, $v_1$; so two values are worth $v_2 = \mathbb E[\max(X, v_1)]$. In general

$$v_k = \mathbb E[\max(X,\, v_{k-1})] = v_{k-1} + \mathbb E\big[(X - v_{k-1})^+\big],$$

and the rule, with $k$ values still to come after the one in hand, keeps it exactly when it is at least $v_k$.

For twelve uniform values the standard starts at $0.871$ and falls to $0.500$ at the second-last position, where the only alternative is one last value worth $\tfrac12$ on average. The rule collects $0.879$ against the prophet’s $12/13 \approx 0.923$ — the prophet’s expected maximum of $n$ uniform values is $n/(n + 1)$ — so it loses less than five per cent. As $n$ grows the standard starts closer and closer to $1$, and a value that high comes along soon; the rule’s shortfall shrinks towards nothing.

How fast the gap closes, and the constant it closes to #

The recursion can be followed to the end, and for the two light-tailed distributions it lands on two different kinds of answer.

For the uniform distribution the step is $v_k = (1 + v_{k-1}^2)/2$, and writing $v_k = 1 - \varepsilon_k$ turns it into $\varepsilon_k = \varepsilon_{k-1} - \varepsilon_{k-1}^2/2$. A gap that shrinks by half its own square at every step behaves like $2/k$: at a hundred values the rule falls short of $1$ by $0.0188$, at a thousand by $0.00198$, at ten thousand by $0.000200$. The prophet falls short of $1$ by $1/(n + 1)$. So the rule loses about twice what the prophet loses, and since both losses shrink to nothing, the share climbs to one. The factor of two is the whole price of not knowing the future when the values are bounded: the prophet waits for the top value, and the rule accepts anything in roughly the top $2/n$ of the range.

The exponential distribution is more interesting. There the step is $v_k = v_{k-1} + e^{-v_{k-1}}$, whose solution grows like $\ln k$, and the prophet’s expected maximum of $n$ exponential values is the harmonic number $H_n = 1 + \tfrac12 + \dots + \tfrac1n$. Both grow without bound, and their difference settles:

The difference converges to $0.5772\ldots$, which is Euler’s constant $\gamma$ — the amount by which the harmonic numbers overshoot the logarithm, because the rule’s value is essentially $\ln n$ and the prophet’s is $H_n$. So for exponential values the rule loses a fixed amount, not a fixed share, and the share creeps towards one only as fast as $1 - \gamma/\ln n$. That is why the exponential curve in the first figure is still climbing at two hundred values and has barely passed $0.9$: it will reach $0.96$ at a million.

One threshold and the constant 1 − 1/e #

A single fixed threshold does worse than the falling standard but is simpler to state, easier to prove things about, and is how a seller posting one price to a queue of buyers behaves.

Choose the threshold $\tau$ so that each value exceeds it with chance exactly $1/n$, and keep the first value that does. The chance that some value crosses is $1 - (1 - 1/n)^n$, which is never less than $1 - 1/e \approx 0.632$ — the same $1/e$ that nobody gets their own hat found as the chance that a random shuffle leaves every hat with a stranger. And the argument that this secures $1 - 1/e$ of the prophet’s take is short. The prophet’s maximum is at most $\tau$ plus the total by which the values exceed $\tau$, so its expectation is at most $\tau + n\,\mathbb E[(X - \tau)^+]$. The rule collects at least $\tau$ whenever some value crosses, plus the excess of the first crossing value, and the $i$-th value’s excess is collected whenever no earlier value crossed, which has chance $(1 - 1/n)^{i-1}$. Summed over the $n$ positions those chances come to $n\,\big(1 - (1 - 1/n)^n\big)$, so the excess part of the rule’s take is at least $1 - (1 - 1/n)^n$ times the excess part of the prophet’s bound — the same factor as the $\tau$ part. Both halves of the bound are matched at the same rate, and the rate never drops below $1 - 1/e$.

The argument uses the sameness of the distributions in exactly one place: the chance of crossing is the same $1/n$ at every position, so the chance that nobody earlier crossed is a clean geometric factor. With different distributions the threshold would have to be tuned to the whole list at once, and the best any single threshold can do falls to the half of half of what an oracle takes.

In the figure the dashed curves sit above $1 - 1/e$ for every distribution and every $n$, and for the uniform distribution they sink towards it as $n$ grows. A single threshold wastes the information the falling standard uses — how many values are left — and for large $n$ that information is worth the whole gap between $0.632$ and nearly one.

What a heavy tail costs #

The figure’s bottom curves are the Pareto distributions, whose chance of exceeding $x$ falls like a power of $x$, and they are where the rule loses most.

With a tail exponent of $1.2$ the average value is $6$, but the standard at the first of twelve values is $34.4$: waiting is worth that much because among eleven more draws there is a real chance of something huge. The rule collects $36.8$ against the prophet’s $44.4$. The prophet’s advantage here is that it knows when the huge value comes, and in a heavy-tailed world almost all of the maximum is that one value.

Sweeping the tail exponent shows the cost as a curve. Light tails, on the right, cost little. As the tail grows heavier the share falls, bottoming out at $0.788$ for fifty values when the exponent is near $1.45$, and then rising again as the tail becomes so heavy that the prophet’s maximum and the rule’s catch are both dominated by an almost certain enormous value. No Pareto distribution reaches $0.745$; the distributions that approach it are tuned to the number of values, with a tail shaped exactly to make waiting and taking equally bad.

Why a power tail never lets the gap close #

The Pareto curves in the first figure go flat, and unlike the exponential they stay flat however long they are followed. The reason is that a power tail has no scale.

For a Pareto distribution with tail exponent $\alpha$, the chance of exceeding $x$ is $x^{-\alpha}$ for $x \ge 1$, and the excess over a bar $v$ is $\mathbb E[(X - v)^+] = v^{1-\alpha}/(\alpha - 1)$. The recursion becomes $v_k = v_{k-1} + v_{k-1}^{1-\alpha}/(\alpha - 1)$, which grows like $\big(\tfrac{\alpha}{\alpha - 1}\,k\big)^{1/\alpha}$. The prophet’s maximum grows like $\Gamma(1 - 1/\alpha)\, n^{1/\alpha}$. Both are the same power of $n$, so their ratio tends to a constant:

$$\frac{\text{rule}}{\text{prophet}} \;\longrightarrow\; \frac{\big(\alpha/(\alpha - 1)\big)^{1/\alpha}}{\Gamma(1 - 1/\alpha)}.$$

At $\alpha = 2$ this is $\sqrt 2/\Gamma(\tfrac12) = \sqrt{2/\pi} \approx 0.798$, and the curve for tail exponent $2$ in the first figure is already at $0.802$ by two hundred values. At $\alpha = 1.2$ the limit is $0.7996$; at $\alpha = 3$ it is $0.845$. Minimised over every exponent it is $0.776$, at $\alpha \approx 1.46$ — the same place the fifty-value sweep bottoms out, a little lower because fifty values have not yet reached the limit.

So among power tails the worst share is about $0.776$, and it persists for ever. A heavy tail is what the tail is not a bell described from the other side: the largest of many values is not a slightly larger typical value but a different kind of event, and a rule that must decide at each moment cannot recognise that event any better at the millionth value than at the fiftieth. The constant $0.745$ lies below every Pareto limit; reaching it needs a distribution whose tail is reshaped as $n$ changes, which no single fixed distribution can do.

The constant, and how long it took #

The number $0.745$ has a history longer than its proof.

Theodore Hill and Robert Kertz showed in 1982 that for identical distributions the prophet’s advantage is bounded by a constant well below the factor of two that different distributions allow, and Kertz identified the candidate in 1986 as $1/\beta$, where $\beta \approx 1.342$ solves an integral equation that arises from the worst-case distribution — a distribution designed so that the best rule is indifferent between stopping and continuing at every step. For thirty years the best proved guarantee was lower: $1 - 1/e$, from the single threshold, and then slight improvements. José Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk and Tjark Vredeveld proved in 2017 that the best rule always achieves Kertz’s constant, and the guarantee is tight.

Their proof has a feature worth noting. It does not analyse the best rule directly; it analyses a family of thresholds, one per position, chosen as quantiles of the distribution in a pattern fixed in advance, and shows that the family already reaches $0.745$. So the constant is achieved by a rule that looks only at the position and the value — like the falling standard, and unlike the single threshold — without needing the exact backward induction.

Where half is still all there is #

The improvement from half to $0.745$ is entirely the adversary’s loss of one power.

The tight example for different distributions puts a sure value of one first and a long shot second: a value of $1/\varepsilon$ with chance $\varepsilon$. The prophet collects about two; any rule must decide at the first value, without knowing whether the long shot will pay, and collects about one either way. That example requires two different distributions, and making them identical destroys it — a second draw from the first distribution is another sure one, and a first draw from the second is the long shot itself. Identical distributions forbid the one move that made half tight.

Selling to a queue #

The problem is the one a seller faces with one item and a stream of buyers.

Buyers arrive one at a time, each with a private value drawn from a distribution the seller knows, and each will buy if the posted price is below their value. A seller who could see every value in advance would sell to the highest; the seller who cannot must decide on a price for each buyer before the next arrives. With a single fixed price, set so that each buyer accepts with chance $1/n$, the seller’s expected welfare is at least $1 - 1/e$ of the prophet’s; with prices that fall as the queue shortens, at least $0.745$. The same bounds hold when revenue rather than welfare is the target, after the values are transformed in the standard way that auction theory uses.

That is why these constants became central in the design of online markets: a posted price is simple, honest and strategy-proof — no buyer gains by misreporting, since nobody reports anything — and the prophet inequalities say exactly how little it costs.

What the curves can and cannot show #

The curves are computed, not simulated. The best rule’s value comes from the backward recursion, the prophet’s expected maximum from the order statistics of each distribution — exactly for the uniform, as a harmonic sum for the exponential, through the gamma function for the Pareto — and the threshold rule’s value from its quantile. Every number in the figures is a formula evaluated, not an average of random runs.

The worst case is not drawn. The distributions that approach $0.745$ are constructed differently for each number of values, and none of the four distributions in the figure comes near; the constant appears as a line, quoted from Kertz and from Correa and his colleagues, and checked only in the sense that every curve stays above it.

Only one item is kept. Everything here is about keeping a single value; the versions with several items, or with a constraint on which sets of values may be kept together, are where the thresholds that nest began, and their constants for identical distributions are known only in special cases.

Still open: values from different hats, in random order #

Between the two settings on this page lies a third. The values come from different distributions, as in the adversarial case, but in a random order, as if the hats were shuffled before the draws. The adversary chooses the distributions but loses control of where the dangerous one appears.

This “prophet secretary” problem has a guarantee of at least $1 - 1/e$, found in 2015, and the best known rules now secure a little more than two thirds. The best upper bound shows that no rule can guarantee more than about $0.7235$ — so shuffling different hats is strictly worse for the rule than drawing from one hat, since $0.7235 < 0.745$. The exact constant is not known: it lies somewhere in a window of about five hundredths, above two thirds and below $0.7235$, and it is the most natural unsettled number on the path from half to three quarters.

What makes it hard is that the random order restores some of the adversary’s power without restoring all of it. The dangerous distribution is still there, but the rule does not know when it arrives; a rule can use the time elapsed as information, as when to stop looking used it for ranks, and the best known rules do exactly that, with thresholds that fall as a continuous function of the fraction of the sequence that has passed.

A different question with the same values #

The rule on this page maximises the expected value of what it keeps. The older problem asks for something else: the chance of keeping the single largest value. Giving up on the best and add the odds from the end treat that objective, and it behaves very differently.

When only the ranks are seen, the best chance of keeping the largest is $1/e$. When the values themselves are seen and come from a known distribution — the full-information secretary problem — the best chance rises to about $0.580$, found by Gilbert and Mosteller in 1966, and it is the same for every continuous distribution, because the values can be transformed into uniform ones without changing which is largest. The expected-value objective has no such invariance: the uniform and the Pareto give very different curves above, since a rule that keeps the second-largest of a thousand uniform values loses almost nothing, while one that keeps the second-largest of a thousand Pareto values may lose nearly everything.

The objective decides what information is worth. For the chance of the best, knowing the distribution is worth the step from $0.368$ to $0.580$ and the tail is irrelevant; for the expected value, the tail is the whole story.

What sameness buys #

The habit worth keeping is the accounting of what the adversary lost.

The guarantee of one half was tight because the distributions could differ: one position could be safe and another a lottery, and no rule deciding at the safe one could know what the lottery would bring. Making the distributions identical takes away that single power, and the guarantee jumps to three quarters. The size of a guarantee measures what the worst case is allowed to do, and the constants on this page — $\tfrac12$, $1 - 1/e$, $0.745$, nearly one for bounded values — are a list of successively weaker adversaries, each with one power fewer than the last.