Why is one choice different?

Let Xi be nonnegative independent random variables with finite expectations and Xn*=max{X1,…,Xn}. The value EXn* is what can be obtained by a “prophet”. A “mortal” on the other hand, may use k⩾1 stopping rules t1,…,tk yielding a return E[maxi=1,…,kXti]. For n⩾k the optimal return is Vkn(X1,…,Xn)=supE[maxi=1,…,kXti] 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*<2V1n(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*