The Prophet Inequality

Imagine offers or trade opportunities arrive one at a time, each an independent random value from a known distribution, and you must accept or reject each one the instant it appears — no going back to a rejected offer, no waiting to see what's coming. A prophet who could see every future value in advance would simply pick the single best one. You can't. How much of that prophet's payoff can you guarantee to capture using only a real-time decision rule, with no foresight at all? The prophet inequality gives a strikingly clean, distribution-free answer: at least half, always, using nothing more exotic than a single fixed threshold.

An analogy: judging a live singing competition

Imagine judging contestants one at a time live, deciding to award the prize on the spot — once you pass on a contestant, they're gone for good. A prophet who's already heard everyone would obviously award the best one; judging live, you clearly can't always match that. The prophet inequality says something remarkable anyway: fix a single cutoff score in advance and award the prize to the first contestant who clears it, and you can guarantee capturing, on average, at least half of what the all-knowing prophet would have gotten — regardless of how scores are actually distributed, with no clever adaptive strategy needed.

The idea, one symbol at a time

Let $X_1, \ldots, X_n$ be independent (not necessarily identically distributed) non-negative random variables, revealed one at a time in order. A prophet, seeing all values in advance, achieves expected value $\mathbb{E}[\max(X_1,\ldots,X_n)]$. A real-time player uses a stopping rule $\tau$ — a rule that decides, using only what's been seen so far, whether to stop and take the current value. The prophet inequality states that there exists a single threshold $\theta$ (a fixed number, chosen in advance from the known distributions) such that stopping at the first $X_i \ge \theta$ guarantees:

$$\mathbb{E}[X_\tau] \ge \frac{1}{2} \, \mathbb{E}\big[\max(X_1,\ldots,X_n)\big] .$$

In plain English: the best single-threshold real-time rule guarantees, in expectation, at least half of what a perfect-foresight prophet would collect — no matter how the $n$ values are distributed, and $\frac{1}{2}$ is the best guarantee possible in general (some distributions let no online rule beat it). A common construction uses $\theta = \frac{1}{2}\mathbb{E}[\max(X_1,\ldots,X_n)]$: stop at the first value reaching half the prophet's expected best.

Worked example 1: two independent offers

Suppose two independent offers arrive: X_1 = \100 with probability 0.5, else \0; X_2 = \40$with certainty. The prophet's expected best:$\mathbb{E}[\max(X_1,X_2)] = 0.5 \times 100 + 0.5 \times 40 = 50 + 20 = 70$(since when$X_1=100$the max is 100, and when$X_1=0$the max is$X_2=40$). Set threshold$\theta = 70/2 = 35$. The rule: accept$X_1$if it clears 35 (i.e., if$X_1 = 100$); otherwise move to$X_2 = 40$, which also clears 35, so accept it. Expected value of this rule:$0.5 \times 100 + 0.5 \times 40 = 70$ — here the simple threshold actually matches the prophet exactly, because both realizations clear the threshold appropriately.

Worked example 2: a harder distribution

Now suppose X_1 = \M$(huge) with probability$1/M, else \0; and X_2 = \1$with certainty,$M$large. Prophet's expected best:$\mathbb{E}[\max] \approx \frac{1}{M}\times M + \frac{M-1}{M}\times 1 \approx 2$for large$M$— the rare huge win contributes about 1, the fallback about 1. Threshold$\theta \approx 1$. Rule: accept$X_1$only if it's the huge value$M$; otherwise fall through to$X_2 = 1$, which clears the threshold too, so accept it. Expected value$\approx 2$ again — but the guarantee of "at least half" is what protects the worst-case distributions where the online player genuinely cannot do this well, not a claim you always match the prophet.

What this means in practice

Prophet inequalities are the theoretical backbone of "sell now versus wait" decisions under genuine uncertainty and irrevocability: a trader shopping a large block to counterparties one at a time with no recall, or an execution algorithm deciding whether to take a currently visible price or wait for a better one that may never reappear. The value of the result is precisely that it needs no assumption about the shape of the distribution — a single, computable threshold gives a worst-case performance guarantee, which is a much stronger promise than "this works well on average in backtests."