Hire the Best

Question

You interview n candidates in uniformly random order, observing only each candidate's rank relative to those already seen. After each interview you must irrevocably hire or pass; passed candidates never return. For large n, what is the probability of hiring the single best candidate when you play the optimal "observe, then leap" strategy, and what fraction do you observe?

Accepted Answer

Exact success probability of the cutoff rule. Hiring happens at position i ge r iff candidate i beats everyone before her and no one in r, dots, i-1 already triggered the rule. Success at i requires (a) i is the global best, probability frac1n, and (b) the best of the first i - 1 lies among the first r - 1 (so the rule was never triggered early), probability fracr-1i-1 by symmetry. Summing: P(r) = sum_i=r^n frac1ncdotfracr-1i-1 = fracr-1nsum_i=r^nfrac1i-1. The limit. Set x = r/n and let n to infty: P(x) = x int_x^1 fracdtt = -x ln x. Maximizing: fracddx(-xln x) = -ln x - 1 = 0 gives x^ = frac1e, and the optimal value is P(x^) = -frac1e ln frac1e = frac1e approx 0.368. Observe about 37% of candidates, then take the first new best; you land the single best with probability about 37%. For n = 100 the exact optimum is r = 38 with P approx 0.371, the asymptotic answer is accurate even at moderate n. Why this matters beyond trivia It is the cleanest solvable model of irrevocable choice under sequential information: the structure of accepting a block trade, lifting a quote that may not be re-shown, or committing capacity to a strategy mid-research. Two robust lessons transfer: an observat

Hire the Best

Problem

Your answer

Hints

More Probability to train on