Prophet Inequalities for Optimal Stopping Rules with Probabilistic Recall

David Assaf & Ester Samuel-Cahn

Let X_i,i=1,...,n be independent random variables, and 1>=p_1 >=...>=p_n-1 >=0, and consider an optimal stopping problem where an observation not chosen in the past is still available i steps later, with some probability p_i. Only one object may be chosen. After formulating the general solution to this optimal stopping problem we consider "prophet inequalities" for this situation. Let V_p(X_1,...X_n) be the optimal value to the statistician. We show that for all non=trivial nonnegative X_i and all n>=2 the "ratio prophet inequality" E[max(X_1,...,X_n)[<(2-p_n-1)V_p(X_1,...,X_n) holds, and (2-p_n-1) is the "best constant". This generalizes the classical prophet inequality with no recall, in which the best constant is 2. For any 0<=X_i<=1, the "difference prophet inequality" E[max(X_1,...,X_n)]-V_p(X_1,...,X_n)<= (1-p_n-1)[1-(1-p_n)^1/2]^2/p^2_n-1 holds. Prophet regions are also discussed.

February, 2000
Published in: 
Bernoulli 8 (2002), 39-52