Prophet Regions for Discounted,Uniformly Bounded Random Variables

Abstract

Let X ₁, X ₂,… be any sequence of [0,1]-valued random variables. A complete comparison is made between the expected maximum E(max _j≤n Y _j ) and the stop rule supremum sup _t E Y _t for two types of discounted sequences: (i) Y _j  = b _j X _j , where {b _j } is a nonincreasing sequence of positive numbers with b ₁ = 1; and (ii) Y _j  = B ₁… B _j?1 X _j , where B ₁, B ₂,… are independent [0,1]-valued random variables that are independent of the X _j , having a common mean β. For instance, it is shown that the set of points {(x, y): x = sup _t E Y _{{(x, y): x=sup t E Y} and y = E(max _j≤n Y _j ), for some sequence X ₁,…,X _n and Y _j  = b _j X _j }, is precisely the convex closure of the union of the sets {(b _j x, b _j y): (x, y) ∈ C _j }, j = 1,…,n, where C _j  = {(x, y):0 ≤ x ≤ 1, x ≤ y ≤ x[1 + (j ? 1)(1 ? x ^1/(j?1))]} is the prophet region for undiscounted random variables given by Hill and Kertz [8 Hill , T.P. , and R.P. Kertz . 1983 . Stop rule inequalities for uniformly bounded sequences of random variables . Trans. Amer. Math. Soc. 278 : 197 – 207 . [CSA]  [Google Scholar]]. As a special case, it is shown that the maximum possible difference E(max _j≤n β ^j?1 X _j ) ? sup _t E(β ^t?1 X _t ) is attained by independent random variables when β ≤ 27/32, but by a martingale-like sequence when β > 27/32. Prophet regions for infinite sequences are given also.