Simple Ratio Prophet Inequalities for a Statistician with Multiple Choices

David Assaf & Ester Samuel-Cahn

Let X_i>=0 be independent, i=1,...,n, with known distributions and let X^*_n=max(X_1,...,X_n). The classical "ratio prophet inequality" compares the return to a prophet, which is EX^*_n, to that of a statistician, who observes the X_i's sequentially, and must resort to a stopping rule t. The statistician's return is V(X_1,...,X_n) = maxEX_t where the maximum is over all stopping rules. The classical inequality states that EX^*_n < 2V(X_1,...,X_n) . In the present paper the statistician is given k >= 1 chances to choose. If he uses stopping rules t_1,...,t_k his return is E(max(X_t_1,...,X_t_k)). Let t(b) be the "simple threshold stopping rule" defined by t(b) =smallest i for which X_i >= b,=n otherwise. We show that there always exists a proper choice of k thresholds, such that EX^*_n <= ((k+1)/k)E(max(X_t_1,...,X_t_k)) , where t_i is of the form t(b_i) with some added randomization. Actually the thresholds can be taken to be the j/(k+1) percentile points of the distribution of X^*_n,j = 1,...,k. Thus, for example, the value to the prophet is never more than 1.5 times the value to a statistician using two proper threshold rules, and with four choices such a statistician is guaranteed at least 80% of the prophet's value, no matter how large n .

August, 1999
Published in: 
Journal of Applied Probability 37 (2000) 1084-1091