Prophet inequalities for i.i.d. random variables with random arrival times

Abstract

Suppose $X_1,X_2,...$ are i.i.d. nonnegative random variables with finite expectation, and for each $k$, $X_k$ is observed at the $k$-th arrival time $S_k$ of a Poisson process with unit rate which is independent of the sequence $\{X_k\}$. For $t>0$, comparisons are made between the expected maximum $M(t):=\rE[\max_{k\geq 1} X_k \sI(S_k\leq t)]$ and the optimal stopping value $V(t):=\sup_{τ\in\TT}\sE[X_τ\sI(S_τ\leq t)]$, where $\TT$ is the set of all $\NN$-valued random variables $\tau$ such that $\{\tau =i\}$ is measurable with respect to the $\sigma$-algebra generated by $(X_1,S_1),...,(X_i,S_i)$. For instance, it is shown that $M(t)/V(t)\le 1+{\alpha }_0$, where ${\alpha }_0\doteq 0.34149$ satisfies ${\int }_0^1(y-y\ln y+{\alpha }_0{)}^{-1}dy=1$; and this bound is asymptotically sharp as $t\to \infty$. Another result is that $M(t)/V(t)<2-(1-e^{-t})/t$, and this bound is asymptotically sharp as $t\downarrow 0$. Upper bounds for the difference $M(t)-V(t)$ are also given, under the additional assumption that the $X_k$ are bounded.

arXiv comment16 pages with 1 figure; submitted to Sequential Analysis in shortened form