The Secretary Problem

Reject the first n/e candidates; then accept the first one who exceeds every prior candidate. P(success) → 1/e ≈ 36.8%.

Let k be the number of candidates you reject before switching to 'accept the first best-so-far'. Given this rule, we win if and only if the best candidate appears at position i > k AND the best among the first i-1 candidates appeared in the first k positions (so we haven't accepted anyone yet when the true best arrives).

For fixed i > k, the probability that the best candidate is at position i is 1/n, and (conditional on the best being at i) the probability that the best of the first i-1 was in the first k is k/(i-1). Summing:

$P(\text{win} \mid k) = \sum_{i=k+1}^{n} \frac{1}{n} \cdot \frac{k}{i-1} = \frac{k}{n} \sum_{i=k+1}^{n} \frac{1}{i-1}$

As n → ∞, with x = k/n, this tends to $-x \ln(x)$. Maximising over x: take the derivative, set to zero: $\ln(x) + 1 = 0$, so $x = 1/e$. At the optimum, success probability is also $-\tfrac{1}{e} \ln(\tfrac{1}{e}) = 1/e ≈ 0.368$.