Secretary Problem

Reject the first n/e, then take the next record — wins with probability 1/e.

The idea

The secretary problem asks how to select the best of a sequence of candidates when every decision is final. Candidates arrive one at a time in random order. You can rank the ones you have seen against each other, but after each interview you must accept or reject on the spot: a rejected candidate is gone for good, and an acceptance ends the search. Only ending with the best candidate of all counts as success.

A candidate can only be judged against those already seen. Accept early, and a later arrival may have been better; wait too long, and the best may already be rejected. At the very start you cannot judge at all, because you have no standard of comparison yet.

This suggests a family of strategies with a single parameter, a cutoff $r$.

Algorithm.

Algorithm: Look-Then-Leap Input: n candidates arriving in random order, a cutoff r < n Output: the one candidate accepted; success means accepting the best of all n 1. interview and reject candidates 1 through r regardless of quality; standard = the best of them 2. interview the next candidate; if it beats the standard, accept and stop // beating the standard beats everyone seen so far 3. otherwise reject; if candidates remain, go to step 2 4. if the sequence runs out, the search has failed // the best of all n was among the first r, already rejected

A small $r$ gives a weak standard; a large $r$ leaves few candidates on which to use it. The problem is to choose $r$ so that the probability of ending with the best candidate is as large as possible.

Ways to work on it

• Walkthrough. Derive the look-then-leap rule's success probability by conditioning on the best candidate's position.
• Practice. Multiple-choice checks on when the look-then-leap rule works and what it wins.
• Hardest. Find the cutoff that maximizes the success probability, and the probability it achieves.

Not sure where to start? Take the ten-question placement test.