Prophet regions for independent random variables with increasing bounds

Abstract

Let X = (X₁, …, X_n) be a sequence of independent, integrable[a_i, b_i]-valued random variables, where a₁ ≤ … ≤ a_n, b₁ ≤ … ≤ b_n . Considering the class of all such sequences, a complete comparison is made between M(X), the expected gain of a prophet (an observer with complete foresight), and V(X) the maximal expected gain of a gambler (an observer using only non-anticipatory stopping rules). The solution of this problem is a set in , the ‘prophet region’, which is explicitly characterized. This region yields a variety of prophet inequalities, e.g. M(X) ≤ V(X)/2 if b_n = 0, b_n-1 = -1, a_n = -2 and M(X) - V(X) ≤ a_n/2 if a_n > 0, b_n-1 = 2a_n, b_n = 3a_n .

Keywords:

• Optimal stopping
• Prophet inequalities
• Inequalities for stochastic processes

Additional information

Notes on contributors

Uwe Schmid

Uwe Saint-Mont