Bound on optimal stopping in random sequences
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 formula_1 arrive from known distributions formula_2. When each formula_1 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 formula_4 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 inputs.
One method for proving the single-item prophet inequality is to use a "threshold algorithm" that sets a parameter formula_5 and then accepts the first random variable that is at least as large as formula_5. If the probability that this process accepts an item is formula_7, then its expected value is formula_8 plus the expected excess over formula_5 that the selected variable (if there is one) has. Each variable formula_1 will be considered by the threshold algorithm with probability at least formula_11, and if it is considered will contribute formula_12 to the excess, so by linearity of expectation the expected excess is at least formula_13 Setting formula_5 to the median of the distribution of so that and adding formula_8 to this bound on expected excess, causes the formula_8 and formula_17 terms to cancel each other, showing that for this setting of formula_5 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.
 ;templatestyles src="Reflist/styles.css" / ;