  The setting of the classic prophet inequality is as follows: a gambler is
shown the probability distributions of $n$ independent, non-negative random
variables with finite expectations. In their indexed order, a value is drawn
from each distribution, and after every draw the gambler may choose to accept
the value and end the game, or discard the value permanently and continue the
game. What is the best performance that the gambler can achieve in comparison
to a prophet who can always choose the highest value? Krengel, Sucheston, and
Garling solved this problem in 1978, showing that there exists a strategy for
which the gambler can achieve half as much reward as the prophet in
expectation. Furthermore, this result is tight.
  In this work, we consider a setting in which the gambler is allowed much less
information. Suppose that the gambler can only take one sample from each of the
distributions before playing the game, instead of knowing the full
distributions. We provide a simple and intuitive algorithm that recovers the
original approximation of $\frac{1}{2}$. Our algorithm works against even an
almighty adversary who always chooses a worst-case ordering, rather than the
standard offline adversary. The result also has implications for mechanism
design -- there is much interest in designing competitive auctions with a
finite number of samples from value distributions rather than full
distributional knowledge.
