Simple ratio prophet inequalities for a mortal with multiple choices (Q2725302)

Let \(X_i\geq 0\) \((1\leq i\leq n)\) be independent random variables with finite expectations and put \(X^*_n= \max(X_1,\dots, X_n)\). A prophet (knowing in advance the realization of the whole sequence \((X_n)\)) obtains a return equal to \(E[X^*_n]\) whereas the mortal's return is \(V(X_1,\dots, X_n)= \sup E[X_t]\) (the supremum taken over all stopping times). The classical prophet inequality states that \(E[X^*_n]< 2\cdot V(X_1,\dots, X_n)\). The authors study the situation in which the mortal has \(k\) choices (where \(1\leq k< n\)). The main result says that there exist \(k\) stopping times \(t_1\leq t_2\leq\cdots\leq t_k\) such that NEWLINE\[NEWLINEE[X^*_n]\leq ((k+ 1)/k) E[\text{max}(X_{t_1},\dots, X_{t_k})],NEWLINE\]NEWLINE where each \(t_j\) is of the form \(t_j= \min\{1\leq i\leq n\mid X_i\geq b_j\}\wedge n\) (\(b_j>0\) being a constant).