The best rule for finding the best finishes twentieth
A hundred people apply. They arrive one at a time in no
particular order, and after each one you must say yes or no on the spot: no
going back, no shortlist. You cannot score anybody — you can only say where
this one stands against the ones you have already seen. Take somebody and the
rest never arrive. Refuse everybody and you are left with the hundredth.
The famous answer is to let thirty-seven go by, then take the first one
better than all of those. It lands the actual best of the hundred
37 per cent of the time, which is astonishing for a rule that never
sees a number. It also hands you, on average, the twentieth best person
in the queue — because when no record turns up at all, it is standing there at
the end holding whoever walked in last, and that happens 37.4 per cent of
the time. Those two 37s are different numbers, near each other because both are
heading for 1/e.
Play it — twenty candidates, one at a time
Each card is a candidate. You are told only how this one ranks against everyone you have seen so far. Take ends the round; Pass is final. If you pass on all twenty you are given the twentieth.
The queue you were dealt on opening is the first shuffle out of
seed 20260906 — not one picked for what it shows.
Every later queue is the next shuffle from the same seed, so the round you
are playing is one a test can play again; tests/test_secretary.py
rebuilds this generator in Python and fails if the two ever part.
How much to let go by
Pass on the first k whatever they are, then take the first one who
beats all of them. That is one rule with one dial, and the dial has a best
setting. Turn it: at k = 0 you are taking whoever walks in first and
win one time in a hundred; at the far end you are
holding out for a record that will not come and end up with the last person.
The peak sits near n/e, and it is remarkably flat around there.
Two routes agree on that curve and the page compares them: a closed form — k/n times the sum of 1/(i−1) over the places you might stop — and a forward sweep that carries the chance of still being empty-handed at each step and never mentions a sum at all.
And what it actually hands you
Winning means the very best. Everything else counts as losing equally,
which is a strange thing to want and is the whole reason the rule behaves
the way it does. Score it instead by the rank of the person you end
up with — 1 is the best, 100 the worst — and the famous rule comes
apart. Its average grows in step with the queue, at about n/2e,
because roughly one round in e ends with it holding a stranger
drawn at random from the whole hundred.
The other rule on this chart is the one that minimises exactly that average. It is not a cutoff at all: it starts fussy and gets less fussy as the queue runs down, and its average rank stops climbing. However long the queue, it lands you a shade under 3.87 from the top.
What the second rule is doing
It has no cutoff and no record-chasing. At each step it will accept anyone inside a band, and the band widens as the queue runs out: near the start it wants the best it has seen, and by the end it will take almost anybody, because almost anybody beats a lottery ticket on the last person. Below is the whole rule for a hundred candidates — accept if this candidate's standing among those seen so far is inside the shaded band.
Both rules, both scores
Read across a row and the trade is plain. Neither column is the right one to want in general — if you are hiring, rank 4 out of 500 is a fine outcome and the hunting rule's 37 per cent is a coin flip with a 92-place tail behind it. If you are buying the one lottery ticket that pays, only first place exists and the hunting rule is optimal. The rule you should use is a fact about your losses, not about the queue.