Additive Prophet Inequalities for Transforms of Uniformly Bounded Pairwise Independent Random Variables

摘要

E(Summation of i=l to i=n) of (x(i)-x(i-l)) sup + and E(Summation of i=l to i=n), of (EX(i)-X((il))+ are the maximal expected returns of pairwise independent uniformly bounded random variables X(0)....X(n) transformed respectively by random variables taking values in (0,1) and predictable random variables taking values in (0,1). Probabilistically, these quantities are respectively the maximal gain of a prophet (player with complete foresight) and the maximal gain of a gambler (player who knows only the past and the present). Best possible upperbounds are given for the difference E(Summation of i=1 to i=n) of (X9i) - x(i-1))sup + E(Summation of i=1 to i=n), of (EX(i)-X(i-1))+ in the identically distributed case and the case of nonincreasing expectations. Also, a best possible implicity defined upperbound is given in the general case.