Motivation. Imagine a gambling situation, where there is a sequence of prizes inside boxes. The gambler knows the distribution of these boxes, but is only shown one at a time. They can claim only one box, and once a box is opened the prize must be claimed or trashed. How can the gambler act?

def. (Optimal stopping problem) let prizes of random variables be distributed . The gambler only knows the distribution of each of these boxes, and the order in which the boxes are shown is shuffled randomly.

thm. Prophet Inequality. There is a strategy for the gambler to achieve at least of the optimal revenue, i.e.:


  • is the payoff to the gambler
  • let , a random variable. This is what the “Prophet” gets, i.e. a optimal strategy. Additionally, the theorem states that this strategy is a optimal cutoff strategy, which is one that stops if the payoff from the current opened box is larger than predetermined cutoff .

Proof. We know that where

  • base payoff is
  • excess payoff is , where is the box we stop at We also know that these two are random varibles:

Now, the expected payoff is:

We know that the probability of stopping at (from the first case of excess payoff) is:


(lemma 1) On the other hand, the expected prophet payoff is

(lemma 2) Noticing lemma 1 and lemma 2 both have term , we can organize for that:

Simplifying we get