Prophet Inequality for Independent Random Variables: Reward Sequences with a Discount Factor

摘要

Let Z(1),...,Z(n) be a sequence of independent (0,1)-valued random variables and let X(i) :=i sup(-1) Z(i), i=1,..., n. A complete comparison is made between the optimal stopping value V(X(1),...,X(n)) = sup (EX(tau) : tau is a stopping time for X(1),...,X(n)) and E(max X(i)). In fact it is shown that the set ((x,y):x = V(X(1),...,X(n)), y = E(max X(i)), X(i) = i sup(-1)Z(i), for some sequence of independent (0,1)-valued random variables Z(1),...,Z(n)) is precisely the set ((x,y) : x = or