Prophet Inequalities for I.I.D. Random Variables with Random Arrival Times

Abstract

Suppose X ₁, X ₂,… are independent and identically distributed nonnegative random variables with finite expectation, and for each k, X _k is observed at the kth arrival time S _k of a Poisson process with a unit rate independent of the sequence {X _k }. For t > 0, comparisons are made between the expected maximum M(t) := E[max _k≥1 X _k  I(S _k  ≤ t)] and the optimal stopping value V(t) := sup_τ∊E[X _τ I(S _τ ≤ t)], where  is the set of all ℕ-valued random variables τ such that {τ = i} is measurable with respect to the σ-algebra generated by (X ₁, S ₁),…, (X _i , S _i ). For instance, it is shown that M(t)/V(t) ≤ 1 + α₀, where α₀ ≐ 0.34149 satisfies , and this bound is asymptotically sharp as t → ∞. Another result is that M(t)/V(t) < 2 − (1 − e ^−t )/t, and this bound is asymptotically sharp as t ↓ 0. Upper bounds for the difference M(t) − V(t) are also given, under the additional assumption that the X _k 's are bounded.

Keywords:

• Optimal stopping rule
• Poisson process
• Prophet inequality

Subject Classifications:

• 60G40
• 62L15

ACKNOWLEDGMENTS

The author thanks two anonymous referees for critically reading this paper, and for several valuable suggestions.

Notes

Recommended by Allan Gut