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

preprint2006arXivOpen access

Abstract

Suppose X1,X2,...X_1,X_2,... are i.i.d. nonnegative random variables with finite expectation, and for each kk, XkX_k is observed at the kk-th arrival time SkS_k of a Poisson process with unit rate which is independent of the sequence {Xk}\{X_k\}. For t>0t>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 ττ such that {τ=i}\{τ=i\} is measurable with respect to the σσ-algebra generated by (X1,S1),...,(Xi,Si)(X_1,S_1),...,(X_i,S_i). For instance, it is shown that M(t)/V(t)≤1+α0M(t)/V(t)\leq 1+α_0, where α0≐0.34149α_0\doteq 0.34149 satisfies ∫01(y−yln⁡y+α0)−1dy=1\int_0^1(y-y\ln y+α_0)^{-1} dy=1; and this bound is asymptotically sharp as t→∞t\to\infty. Another result is that M(t)/V(t)<2−(1−e−t)/tM(t)/V(t)<2-(1-e^{-t})/t, and this bound is asymptotically sharp as t↓0t\downarrow 0. Upper bounds for the difference M(t)−V(t)M(t)-V(t) are also given, under the additional assumption that the XkX_k are bounded.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.