Difference prophet inequalities for [0,1]-valued i.i.d. random variables with cost for observations
Holger Kösters · The Annals of Probability · 2004
Let X1,X2,… be a sequence of [0,1]-valued i.i.d. random variables, let c≥0 be a sampling cost for each observation and let Yi=Xi−ic, i=1,2,…. For n=1,2,…, let M(Y1,…,Yn)=E(max 1≤i≤nYi) and V(Y1,…,Yn)=sup τ∈CnE(Yτ), where Cn denotes the set of all stopping rules for Y1,…,Yn. Sharp upper bounds for the difference M(Y1,…,Yn)−V(Y1,…,Yn) are given under various restrictions on c and n.