  In the prophet secretary problem, $n$ values are drawn independently from
known distributions, and presented in a uniformly random order. A
decision-maker must accept or reject each value when it is presented, and may
accept at most $k$ values in total. The objective is to maximize the expected
sum of accepted values.
  We analyze the performance of static threshold policies, which accept the
first $k$ values exceeding a fixed threshold (or all such values, if fewer than
$k$ exist). We show that an appropriate threshold guarantees $\gamma_k = 1 -
e^{-k}k^k/k!$ times the value of the offline optimal solution. Note that
$\gamma_1 = 1-1/e$, and by Stirling's approximation $\gamma_k \approx
1-1/\sqrt{2 \pi k}$. This represents the best-known guarantee for the prophet
secretary problem for all $k>1$, and is tight for all $k$ for the class of
static threshold policies.
  We provide two simple methods for setting the threshold. Our first method
sets a threshold such that $k \cdot \gamma_k$ values are accepted in
expectation, and offers an optimal guarantee for all $k$. Our second sets a
threshold such that the expected number of values exceeding the threshold is
equal to $k$. This approach gives an optimal guarantee if $k > 4$, but gives
sub-optimal guarantees for $k \le 4$. Our proofs use a new result for
optimizing sums of independent Bernoulli random variables, which extends a
classical result of Hoeffding (1956) and is likely to be of independent
interest. Finally, we note that our methods for setting thresholds can be
implemented under limited information about agents' values.
