Stop rule and supremum expectations of i.i.d. random variables: A complete comparison by conjugate duality

A complete comparison is made between the value V(X1,..., Xn) = sup{EXt: t is a stop rule for X1,...,Xn} and E(maxj <= nXj) for all uniformly bounded sequences of i.i.d. random variables X1, ..., Xn. Specifically, the set of ordered pairs {(x,y): X = V(X1, ..., Xn) and Y = E(maxj<=nXj) for some i.i.d.r.v.'s X1,..., Xn taking values in [0, 1]} is precisely the set {(x, y): x<=y<=[Gamma]n(x); 0 <=x<=1}, where the upper boundary function [Gamma]n is given in terms of recursively defined functions. The result yields families of inequalities for the "prophet" problem, relating the motal's value of a game V(X1, ..., Xn) to the prophet's value of the game E(maxj<=nXj). The proofs utilize conjugate duality theory, probabilistic convexity arguments, and functional equation analysis. Asymptotic analysis of the "prophet" regions and inequalities is also given.