  Suppose a customer is faced with a sequence of fluctuating prices, such as
for airfare or a product sold by a large online retailer. Given distributional
information about what price they might face each day, how should they choose
when to purchase in order to maximize the likelihood of getting the best price
in retrospect? This is related to the classical secretary problem, but with
values drawn from known distributions. In their pioneering work, Gilbert and
Mosteller [\textit{J. Amer. Statist. Assoc. 1966}] showed that when the values
are drawn i.i.d., there is a thresholding algorithm that selects the best value
with probability approximately $0.5801$. However, the more general problem with
non-identical distributions has remained unsolved.
  In this paper we provide an algorithm for the case of non-identical
distributions that selects the maximum element with probability $1/e$, and we
show that this is tight. We further show that if the observations arrive in a
random order, this barrier of $1/e$ can be broken using a static threshold
algorithm, and we show that our success probability is the best possible for
any single-threshold algorithm under random observation order. Moreover, we
prove that one can achieve a strictly better success probability using more
general multi-threshold algorithms, unlike the non-random-order case. Along the
way, we show that the best achievable success probability for the random-order
case matches that of the i.i.d.\ case, which is approximately $0.5801$, under a
"no-superstars" condition that no single distribution is very likely ex ante to
generate the maximum value. We also extend our results to the problem of
selecting one of the $k$ best values.
