Prophet inequality
In the theory of online algorithms and optimal stopping, a prophet inequality is a bound on the expected value of a decision-making process that handles a sequence of random inputs from known probability distributions, relative to the expected value that could be achieved by a "prophet" who knows all the inputs (and not just their distributions) ahead of time. These inequalities have applications in the theory of algorithmic mechanism design and mathematical finance.

Single item
The classical single-item prophet inequality was published by , crediting its tight form to D. J. H. (Ben) Garling. It concerns a process in which a sequence of random variables  arrive from known distributions . When each  arrives, the decision-making process must decide whether to accept it and stop the process, or whether to reject it and go on to the next variable in the sequence. The value of the process is the single accepted variable, if there is one, or zero otherwise. It may be assumed that all variables are non-negative; otherwise, replacing negative values by zero does not change the outcome. This can model, for instance, financial situations in which the variables are offers to buy some indivisible good at a certain price, and the seller must decide which (if any) offer to accept. A prophet, knowing the whole sequence of variables, can obviously select the largest of them, achieving value  for any specific instance of this process, and expected value  The prophet inequality states the existence of an online algorithm for this process whose expected value is at least half that of the prophet:  No algorithm can achieve a greater expected value for all distributions of 

One method for proving the single-item prophet inequality is to use a "threshold algorithm" that sets a parameter  and then accepts the first random variable that is at least as large  If the probability that this process accepts an item is , then its expected value is  plus the expected excess over  that the selected variable (if there is one) has. Each variable  will be considered by the threshold algorithm with probability at least  and if it is considered will contribute  to the excess, so by linearity of expectation the expected excess is at least  Setting  to the median of the distribution of  so that  and adding  to this bound on expected excess, causes the  and  terms to cancel each other, showing that for this setting of  the threshold algorithm achieves an expected value of at least  A different threshold,  also achieves at least this same expected value.

Generalizations
Various generalizations of the single-item prophet inequality to other online scenarios are known, and are also called prophet inequalities.

Comparison to competitive analysis
Prophet inequalities are related to the competitive analysis of online algorithms, but differ in two ways. First, much of competitive analysis assumes worst case inputs, chosen to maximize the ratio between the computed value and the optimal value that could have been achieved with knowledge of the future, whereas for prophet inequalities some knowledge of the input, its distribution, is assumed to be known. And second, in order to achieve a certain competitive ratio, an online algorithm must perform within that ratio of the optimal performance on all inputs. Instead, a prophet inequality only bounds the performance in expectation, allowing some input sequences to produce worse performance as long as the average is good.

References

External links
Matroid Prophet Inequalities and Mechanism Design, The Matroid Union
An Economic View of Prophet Inequalities

Online algorithms
Sequential experiments
Mechanism design