You interview 100 candidates one at a time in random order, learning only each candidate's rank against those already seen, and you must accept or reject on the spot with no recall. What rule maximises the probability of hiring the best of the 100, and what is that probability?

You interview 100 candidates one at a time in random order, learning only each candidate's rank against those already seen, and you must accept or reject on the spot with no recall. What rule maximises the probability of hiring the best of the 100, and what is that probability?

Approach: Restrict attention to threshold rules that reject the first k candidates and then take the first one better than everything seen. Write the success probability as a sum over the arrival position of the best candidate and optimise over k.

Reject the first 37 candidates, then hire the first one who beats everything seen, which succeeds with probability 0.3710. Under a threshold rule with cutoff k the best candidate is hired when it arrives at position j > k and the best of the first j-1 lies in the first k, so the success probability is (k/100) sum_{j=k+1}^{100} 1/(j-1). For large n this tends to x log(1/x) with x = k/n, whose optimal stopping point is x = 1/e with value 1/e = 0.3679. Rounding 100/e = 36.8 gives k = 37 and an exact value of 0.3710. The curve is flat near the optimum, so k = 33 or k = 42 still wins about 0.37, and the random arrival order is the only thing the rule exploits.

Follow-up: How does the optimal rule change if your goal is to minimise the expected rank of the hire instead?

Key concepts: threshold rule, optimal stopping, success probability, random arrival order.