Why is One Choice Different?

Let X_i be nonnegative independent random variables with finite expectations and X^*_n = max {X_1, ..., X_n}. The value EX^*_n is what can be obtained by a ``prophet". A ``mortal" on the other hand, may use k >= 1 stopping rules t_1, ..., t_k yielding a return E[max_{i=1, ..., k} X_{t_i}]. For n >= k the optimal return is V^n_k(X_1, ..., X_n) = sup E[max_{i=1, ..., k} X_t_i}] where the supremum is over all stopping rules which stop by time n. The well known ``prophet inequality" states that for all such X_i's and one choice EX^*_n < 2 V^n_1 (X_1, ..., X_n) 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 EX^*_n < dV^n_2 (X_1, ...,X_n) for all such X_i's depends on n. On the way we obtain constants c_k such that EX^*_{k+1} < c_k V^{k+1}_k (X_1, ..., X_{k+1}).