Why is One Choice Different?

David Assaf and Ester Samuel-Cahn

Let Xi be nonnegative independent random variables with finite expectations and Xn* = max {X1,..., Xn}. The value Xn* is what can be obtained by a "prophet". A "mortal" onthe other hand, may use k ≥ 1 stopping rules t1,...,tk yielding a return E[max i = 1,...,k X ti]. For n ≥ k the optimal return is Vkn (X1,...,Xn) = sup E[max i = 1,...,k X ti] where the supremum is over all stopping rules which stop by time n. The well known "prophet inequality" states that for all such Xi's and one choice EXn* < 2 V1n (X1,...,Xn) and the constant "2" cannot be improved on for any n ≥ 2. In contrast we show that for k=2 the best constant d satisfying EXn* < d V2n (X1,...,Xn) for all such Xi's depends on n. On the way we obtain constants ck such that EXk+1* < ck Vkk+1 (X1,...,Xk+1).

September, 2003
Published in: 
Journal of Statistical Planning and Inference 130 (2005), 127-132