Abstract:

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).

Website