  In the classical prophet inequality, a gambler observes a sequence of
stochastic rewards $V_1,...,V_n$ and must decide, for each reward $V_i$,
whether to keep it and stop the game or to forfeit the reward forever and
reveal the next value $V_i$. The gambler's goal is to obtain a constant
fraction of the expected reward that the optimal offline algorithm would get.
Recently, prophet inequalities have been generalized to settings where the
gambler can choose $k$ items, and, more generally, where he can choose any
independent set in a matroid. However, all the existing algorithms require the
gambler to know the distribution from which the rewards $V_1,...,V_n$ are
drawn.
  The assumption that the gambler knows the distribution from which
$V_1,...,V_n$ are drawn is very strong. Instead, we work with the much simpler
assumption that the gambler only knows a few samples from this distribution. We
construct the first single-sample prophet inequalities for many settings of
interest, whose guarantees all match the best possible asymptotically,
\emph{even with full knowledge of the distribution}. Specifically, we provide a
novel single-sample algorithm when the gambler can choose any $k$ elements
whose analysis is based on random walks with limited correlation. In addition,
we provide a black-box method for converting specific types of solutions to the
related \emph{secretary problem} to single-sample prophet inequalities, and
apply it to several existing algorithms. Finally, we provide a constant-sample
prophet inequality for constant-degree bipartite matchings.
  We apply these results to design the first posted-price and multi-dimensional
auction mechanisms with limited information in settings with asymmetric
bidders.
