Half of what an oracle takes

The two rungs below measure a stopping rule against the best it can achieve — a probability of landing the best, or a smallest average rank. There is a third way of measuring, and it changes the subject.

Compare the rule against a prophet: somebody who is shown every value in advance and simply takes the largest. That is not a rule the chooser could follow, and the point of the comparison is precisely that it is not.

The theorem is that a single fixed threshold secures at least half the prophet’s expected take, whatever the distributions are, and the half cannot be improved.

The rule, which is one number #

The rule is as simple as a rule can be. Choose a threshold $\tau$ before anything arrives, take the first value exceeding it, and take the last value if none does.

No adaptation, no counting of what remains, no updating. The whole of the rule is one number chosen in advance, and the theorem says that number can be chosen so as to secure half the maximum’s expectation against any independent values whose distributions are known.

Two choices of $\tau$ both work and both have short arguments.

The median of the maximum. Take $\tau$ with $\Pr[\max > \tau] = \tfrac12$. Then with probability a half the rule collects at least $\tau$, and it also collects a share of whatever excess there is above $\tau$; adding the two gives half of $\mathbb{E}[\max]$.

That threshold is computable without any optimisation, which is the practical half of its appeal: it needs the distribution of the maximum and nothing else, and the distribution of a maximum of independent quantities is a product of the individual ones. The figures compute it alongside the swept optimum, and it clears the guarantee at every field size drawn while sitting a few per cent below the optimum — a rule requiring no search, within a few per cent of one requiring a sweep.

Half the expected maximum. Take $\tau = \tfrac12\mathbb{E}[\max]$. The argument is shorter and is the one usually given, and it is the reason the constant is a half rather than anything else.

The figures compute the best single threshold by sweeping, which is a different number from either, and report how much better it does — in the uniform case, more than nine tenths of the oracle rather than a half.

Why half, and the argument #

The proof is three lines and is worth having because the half falls out of them rather than being aimed at.

Let $\tau$ be the threshold and let $M$ be the maximum. The rule’s expected take is at least

$$\tau\Pr[\text{some value exceeds } \tau] + \mathbb{E}[(M - \tau)^+],$$

because it collects at least $\tau$ whenever anything clears the bar, and the excess above $\tau$ is at least the excess of the largest — with the second term being what the rule may miss by taking an early qualifier rather than the best one, bounded below by nought.

Now $\mathbb{E}[M] \le \tau + \mathbb{E}[(M-\tau)^+]$, always, since the maximum is either below $\tau$ or is $\tau$ plus its excess. Choosing $\tau$ so that $\Pr[\text{something clears it}] \ge \tfrac12$ and combining gives at least half of $\mathbb{E}[M]$.

The two terms are what the rule gets right and what it might miss, and the half is the price of not knowing which value to wait for.

The step worth pausing on is the second inequality, since it is where the maximum is being handled without ever being identified. $\mathbb{E}[M] \le \tau + \mathbb{E}[(M-\tau)^+]$ is true for any random quantity and any $\tau$, by inspection: below $\tau$ the left side is smaller and above it the two agree. A bound on an expectation of a maximum is obtained by never computing the maximum, and that is what makes the argument distribution-free.

The same manoeuvre — split a quantity at a threshold, bound each piece separately — is the workhorse of nearly every inequality of this kind. Chebyshev’s inequality is the same split applied to a squared deviation, and the family resemblance is not superficial: both replace a quantity that depends on the whole distribution by two quantities that depend on it only through one number.

Where half is all there is #

A guarantee is only as interesting as its tightness, and this one is tight — on an example with two values and one parameter.

The arithmetic is worth doing because it is short. The maximum is $1/\varepsilon$ with probability $\varepsilon$ and $1$ otherwise, so its expectation is $\varepsilon\cdot\tfrac{1}{\varepsilon} + (1-\varepsilon)\cdot 1 = 2 - \varepsilon$.

An online rule sees the first value — which is $1$, always — and must decide. Taking it collects $1$. Rejecting it collects $\tfrac{1}{\varepsilon}$ with probability $\varepsilon$, which is an expected $1$. Both choices are worth exactly one, so every online rule collects $1$ against the oracle’s $2 - \varepsilon$, and the ratio is $1/(2-\varepsilon)$, which approaches a half.

That example is worth staring at because it says exactly what the online rule is missing. It is not information about the distributions — those are known. It is that the prophet gets to choose after seeing, and on this example the choice is between a certain small prize and an unlikely large one whose expectations agree. The prophet takes whichever actually occurred; the online rule has to commit while they are still equal.

What the comparison is for #

Measuring against an oracle rather than against an achievable optimum looks like a strange choice and it is the standard one in this area, for a reason.

The achievable optimum is often uncomputable. The best online rule against arbitrary independent distributions is a backward induction over the whole product space, which for a hundred values is not a computation anybody performs. The prophet’s take is one expectation.

The ratio is distribution-free. The half holds for every choice of independent distributions, so a designer can quote it without knowing anything about the inputs. A guarantee against the best online rule would depend on the distributions and would say nothing in general.

And it composes. A rule guaranteeing half of the maximum can be used as a component in a larger mechanism with the guarantee carried through, which is why prophet inequalities are the standard tool in the design of auctions and online allocation.

The composability deserves the last word, because it is the property the others exist to serve. A guarantee stated as a ratio against a benchmark that is itself computable from the inputs can be chained: if a component secures half of some quantity, and the quantity is at least a third of what a larger design would want, the whole secures a sixth. Ratios multiply and absolute guarantees do not, so a bound in this form survives being used inside something else.

That is also why the benchmark has to be the impossible one. The best online rule’s take is not a quantity a larger design can reason about — it depends on the sub-problem’s whole structure — whereas the expected maximum is a number, and a number is what a composition argument needs.

The comparison has a name in the wider literature — the competitive ratio — and it is the same comparison made in the price of anarchy one field away: a ratio between what a constrained process achieves and what an unconstrained one would, with the constraint being irrevocability here and unilateral deviation there.

Why the uniform case does so much better #

The gap between the guarantee and the ninety per cent the figures compute is worth explaining, because it says what the worst case is made of.

The half is forced by an example in which one value carries almost all the expected maximum and almost never appears. Independent uniform values are the opposite: every value has the same modest range, the maximum is close to one with high probability, and no single value is decisive.

So the worst case needs a heavy tail and the uniform distribution has none. The adversarial example puts an expectation of one into an event of probability $\varepsilon$, which is a distribution whose whole mass is in a rare outcome — and any distribution without that structure sits far above the bound.

That is a general property of worst-case guarantees and it is worth reading as one. A tight bound is tight somewhere, and the somewhere is usually an instance constructed to make the bound tight rather than an instance anybody meets. The bound’s value is that it holds regardless; its cost is that it says nothing about the typical case, and the two figures on this page are the two halves of that.

Quoting the half as “what a threshold rule achieves” is therefore wrong in the direction that matters, and quoting the ninety per cent as a guarantee is wrong in the other. The honest statement carries both: at least a half always, and much more on anything resembling the distributions actually in hand.

What a stronger comparison buys #

The half is tight for a fixed threshold against adversarial distributions, and relaxing either hypothesis improves it.

Allow the threshold to change with position and the guarantee stays at a half — the adversarial example defeats adaptive rules too, since it defeats every online rule. So adaptivity buys nothing in the worst case.

Assume the values are identically distributed and the constant improves to about $0.745$. That is a genuinely better bound and it is tight, and the improvement comes entirely from the adversary losing the ability to make one value special.

Assume the order can be chosen — the rule picks which distribution to sample next — and the constant improves again, to about $0.745$ in the classical setting and higher in some variants. The freedom to choose the order is worth as much as identical distributions.

Assume only that the order is random rather than adversarial, and the constant improves to about $0.669$. That variant sits between the two ends and is the one closest to the secretary problem’s own hypothesis, which assumes a random arrival order and no distributional knowledge at all.

Laying the four side by side gives the ladder’s shape in one list: adversarial order gives a half, random order about two thirds, identical distributions about three quarters, and a chooser who sees the values and knows the distribution — the rung two below — wins outright three times in five under a completely different objective. Four constants, four sets of hypotheses, and no two of them measuring the same thing.

Every one of those is one hypothesis moved, and the pattern across this ladder’s four rungs is the same: the constant is a property of the hypotheses and not of the situation, and the way to find out which hypothesis a constant depends on is to move each.

Where the account needs care #

The distributions must be known and independent. Dependence breaks the argument at the first line, and unknown distributions are a different problem with its own literature.

The guarantee is on expectations. The rule secures half the expected maximum, and says nothing about any particular run — on which it may collect nothing at all while the prophet collects a great deal.

The tight example needs its parameter to shrink. At any fixed $\varepsilon$ the ratio is strictly above a half; the half is a limit, so no single instance attains it and the bound is not achieved. That is the ordinary shape of a tight constant — an infimum over a family rather than a minimum on one member — and the distinction matters when the bound is quoted as achieved.

And the uniform case’s ninety per cent is not a theorem. It is a computation for one family of distributions, and the theorem is the half. A reader taking the ninety as the guarantee has read a measurement as a bound, which is the standing hazard of drawing a favourable case beside a worst-case theorem.

Krengel, Sucheston, and a comparison invented for a different reason #

Krengel and Sucheston proved the inequality in 1977 and 1978, and the setting was martingale theory rather than decision-making: they were comparing the expected supremum of a process with the best stopping value, which is a question about processes and not about anybody choosing anything.

The name came with it. A “prophet” is the object that knows the whole path in advance, and the “prophet inequality” is a bound relating what a prophet gets to what a stopper does — a piece of terminology from a technical literature that turned out to be exactly the right framing for something else entirely.

The something else is mechanism design, which discovered the inequality in the 2000s and found that the threshold rule is not merely a bound but a good design: a posted price, which is the simplest possible mechanism, is within a factor of two of the best conceivable allocation. That connection is why the subject is active, and it arrived thirty years after the theorem.

The order is worth noticing and is the same one as several other results on this site. The theorem was proved for its own reasons, sat quietly, and was picked up when a different field found it was asking that question, which is the ordinary career of a good bound.

What the pictures cannot show #

The uniform curve is computed for seven field sizes and the theorem is about every collection of independent distributions. Nothing in the figure is evidence for the theorem; the figure shows one family comfortably inside the bound, and the tight example shows another family approaching it.

Neither figure shows a run. Both plot expectations, and the whole subject is about what happens on average — a picture of a single sequence of values with a threshold drawn on it would show one outcome and no ratio.

And the sweep over four thousand thresholds is a numerical optimisation of one number. That the optimum is where the sweep found it is a claim about a grid, and the theorem’s two named thresholds — the median of the maximum and half the expected maximum — are computed exactly and both clear the guarantee, which is the check with teeth.

The ladder from here #

Rungs above: the identical-distribution case and its constant $0.745$, which is tight and much harder to prove. The order-selection version, where the rule chooses which value to see next. Prophet inequalities for matroids and for combinatorial allocations, where several items are taken subject to a constraint. Posted-price mechanisms and their approximation guarantees, which is where the subject is used. And the secretary problem’s competitive version, where the values are adversarial and the order is random — the combination that connects this rung to the first.

Comparing against something impossible #

The habit is the one this rung is built on and it is counter-intuitive enough to state plainly: when the achievable optimum is intractable, compare against something unachievable instead.

The best online rule against arbitrary distributions is a computation nobody performs, so a guarantee stated against it would be a guarantee nobody could evaluate. The prophet’s take is a single expectation, computable from the distributions directly, and a ratio against it is a number anybody can check.

What is given up is tightness against the right benchmark. A rule securing half the prophet’s take might be securing ninety per cent of the best online rule’s, and the ratio does not say. What is gained is that the ratio exists, is distribution-free, and composes.

The general recommendation is to be explicit about which benchmark a guarantee is against, because the two differ by a lot and both are called “the approximation ratio”. The price of anarchy compares an equilibrium against a social optimum no participant could reach alone; this compares an online rule against an offline one nobody could run. In both cases the denominator is impossible on purpose, and that is what makes the numerator’s guarantee worth quoting.