Compare an irreversible sequential choice with perfect hindsight, calculate the half-prophet guarantee, and see why its classical assumptions matter.
Prophet inequality
A prophet inequality bounds how much expected reward is lost when a decision must be made before the future is revealed. In its classical form, a decision maker can obtain at least half the expected reward of a “prophet” who sees every offer before choosing. For a quant, this separates a feasible sequential decision from a hindsight benchmark; the benchmark is not itself an executable strategy.
One choice, without recall
Suppose X1,…,Xn are independent, nonnegative random rewards with known distributions and finite expectations. Their distributions may differ. Observe them in a fixed order. At each step, accept the current reward and finish, or reject it permanently. At most one reward can be taken; taking none earns zero.
Let M=max1≤i≤nXi and let V be the largest expected reward achievable by a rule using only observations available so far. Such a rule must respect the information constraint of a stopping time. The classical comparison is
21E[M]≤V≤E[M].
The upper bound is immediate: every selected value is at most the realised maximum. The surprising lower bound can be achieved by a suitable single threshold: accept the first Xi≥t, or receive zero if none qualifies. The threshold is chosen using the distributions, before seeing the realised offers. This is an expectation guarantee, not a promise to capture half the maximum on every path. Roughgarden’s lecture, §2 states and proves the threshold result.
The prophet’s extra half-unit
Consider two fictional offers, measured in reward units:
The first offer is always X1=1.
The second is X2=2 with probability 1/2, and 0 otherwise.
At the first decision, accepting earns 1. Rejecting leaves an expected value of E[X2]=1. Randomising between these actions cannot improve on 1, so V=1.
The prophet chooses the first offer when the second is zero and the second offer when it is two:
E[M]=21⋅1+21⋅2=1.5.
The general guarantee is 0.75. A threshold of t=0.75 accepts the first offer and earns 1, so the actual ratio here is 1/1.5=2/3. The theorem gives a lower bound; it does not say every problem has ratio 1/2.
Fictional two-offer model: first offer 1; second offer 0 or 2 with equal probability. Accepting the first offer earns 1 in both outcomes. The prophet earns 1 or 2, averaging 1.5. The half-prophet guarantee is 0.75.
Original stipulated model. The best feasible expected reward is 1, above the 0.75 guarantee and below the prophet’s 1.5.
The prophet’s advantage is the ability to change its first decision after learning the second offer. The feasible decision maker never gets that information in time.
Why the factor cannot improve universally
Keep the first reward at 1, but let the second be 1/p with probability p and zero otherwise, for 0<p<1. Its expectation is still 1, so the best sequential value remains V=1. The prophet’s expectation is
E[M]=(1−p)⋅1+p⋅p1=2−p,E[M]V=2−p1⟶21as p↓0.
For example, p=0.01 gives a second reward of 100 with probability 1%, prophet expectation 1.99, and ratio approximately 0.5025. No constant larger than 1/2 works for all distributions in this model. This is a rescaled version of the sharpness construction in Koutsoupias’s Oxford notes, Lecture 3.
Where the analogy stops in finance
The comparison is useful when evaluating an irreversible selection rule against the best offer visible only in hindsight. It also clarifies why an ex-post “best exercise date” is too generous a benchmark for optimal stopping.
American option exercise shares the information constraint, but exercise payoffs across dates are generally dependent. Discounting, the pricing measure and the contract’s exercise rights also matter. The classical independent-reward theorem therefore does not establish a half-of-hindsight price bound for an American option. SelfMadeQuant’s American Options and Early Exercise develops the exercise-versus-continuation comparison in that setting; its public preview is open, while the full lesson requires membership.
Unknown distributions, negative rewards or several permitted selections change the problem. Their guarantees require separate assumptions and results. Assaf and Samuel-Cahn’s paper explicitly studies the multiple-choice extension.
