Candidates arrive one at a time in a random order and you can only ever compare them with the ones you have already seen. No values, no distribution, no second chances — and yet the chance of ending with the very best is nowhere near hopeless. The optimal rule rejects the first few whatever they are and then takes the first candidate better than all of them, and the probability it succeeds is a harmonic sum: an exact fraction, checked here by playing the rule out on every ordering there is.
Core ideas
Three ideas: what you are allowed to observe, why the rule has the shape it has, and why the exact table matters more than the famous constant.
When candidate k arrives you learn only whether it is the best of the first k. That is a much weaker signal than a number, and it is what makes the problem interesting: you cannot ask whether this one is good enough, only whether it is the best so far. It also makes the answer independent of whatever distribution the qualities came from, which is the unusual and attractive part.
A candidate is worth taking only if it is a record, and a record early on is weak evidence — the best of three is often not the best of twenty. So the rule spends a prefix learning the standard and then takes the first candidate that beats it. Rejecting too few means stopping on a weak record; rejecting too many means the best one goes past unclaimed. P(r) is that trade written out.
P(r) is a rational number for every r, so the whole table can be written in fractions and the best r read off it. The familiar n/e is where that best r sits in the limit as n grows, and the page holds it against how many you reject, which is r − 1 and is usually the whole number it rounds to. At small n it is not even an integer, and this course has not built the asymptotics that make it a limit. So it appears on the page rounded and labelled, beside a table that never needed it.
The material
What the rule is, where its probability comes from, and the brute-force count that checks every entry.
n candidates of distinct quality arrive one at a time in a uniformly random order. On each arrival you learn only its rank among those seen so far, and must accept or reject immediately; a rejection is final. You succeed only by accepting the best of all n.
The look-then-leap rule with parameter r rejects candidates 1 through r−1 whatever they are, then accepts the first candidate that is better than all of those — and accepts the last candidate if it reaches it. r = 1 means taking the first arrival.
For r ≥ 2, the rule with parameter r succeeds with probability P(r) = ((r−1)/n) × Σ 1/(i−1) summed over i from r to n. For r = 1 it is 1/n.
The argument: the rule succeeds when the best candidate is in position i ≥ r and the best of the first i−1 lies in the rejected prefix. Those are independent, with probabilities 1/n and (r−1)/(i−1). Summing over i gives the formula, and every term is rational.
The lab computes that sum as a difference of two harmonic numbers, exactly, in whole-number numerators and denominators. So the table it prints is a table of fractions rather than decimals, and the best r is whichever row holds the largest of them — a comparison between rationals, with no rounding anywhere in it.
Four candidates and a success rate of 11 in 24, which is a little over 45 per cent, from a rule that throws the first candidate away unseen. That is the surprise the problem is famous for, and at n = 4 you can verify it by hand: there are 24 orderings, the rule is unambiguous on each of them, and counting the wins takes a few minutes.
The closed form sums a harmonic series; the brute-force count plays the rule out on every permutation of the ranks and counts how often it ends with the best. The two computations share no line of arithmetic: one is a sum of reciprocals, the other is a loop over orderings comparing integers. The lab runs both for any n up to seven and compares them entry by entry, and shows the table as checked only when every entry agrees.
At n = 7 the best r is 3 — reject two, then take the next record — and it succeeds with probability 29/70, about 0.414286. The counts over all 5040 orderings are 720, 1764, 2088, 2052, 1776, 1320 and 720, and every one of the seven fractions matches the closed form exactly.
Notice r = 3 and r = 4 are close: 2088 wins against 2052, which is 29/70 against 57/140. Rounded to two decimals they are both 0.41, and a page that printed decimals would be unable to say which rule was better. That is what the exact table is for.
Push the candidate slider to its highest setting, a hundred, and the table is too long to print in full, so the lab shows every eighth row, the best one and the row either side of it. You reject 37, then take the first record, and that succeeds with probability 0.371043. Meanwhile n/e is 36.7879, printed rounded because 1/e is irrational — and rounded to a whole number it is 37, which is exactly how many you reject.
That looks like the constant giving the answer, so it is worth being exact about what it gave. n/e said to look near 37. It did not say that rejecting 37 beats rejecting 36 or 38; only the table does, and it says so by very little. Those are the rows r = 37, r = 38 and r = 39 — the rule’s parameter is one more than the number it rejects — and the lab prints them at 0.371015, 0.371043 and 0.370801. The winner and r = 37 agree to four decimal places and part in the fifth. Nor is the rounding dependable: walk the slider across all 98 settings it reaches and n/e rounded is the number you reject at 80 of them and one too many at the other 18.
This is the only rounded number anywhere on the course and the page labels it. The reason to keep it is that n/e is what a reader will meet everywhere else, and meeting it here as a limit sitting beside an exact table is the right way round: the table is the answer, the constant is a description of how the answer behaves for large n, and the asymptotic argument that makes it a limit is not one this path has built.
Every ordering is equally likely, which is the assumption doing nearly all of the work: it is what makes a record at position i mean the same thing whatever the underlying qualities were. The objective is also unusually harsh — you succeed only by getting the very best, and ending with the second best scores the same as ending with the worst. Change that to maximising expected rank and the optimal rule changes shape entirely.
And nobody can be recalled, nobody refuses, n is known in advance, and there is no cost to looking. Each of those is a modelling decision. The arithmetic here is exact and exhaustively checked, and it is exact about a situation with all four of them true.
Interactive
An exact harmonic sum, checked by playing the rule out on every ordering
Method
Four steps. The third is where the exactness earns its keep, and the fourth is the one people skip.
The best candidate is at position i, and the best of the first i−1 is inside the rejected prefix. Those two events are independent, which is the only probabilistic content of the whole derivation.
1/n for its position times (r−1)/(i−1) for the prefix condition, summed over i from r to n. The 1/n comes out of the sum and the rest is a difference of harmonic numbers.
At n = 7 the two best rules score 29/70 and 57/140, which round to the same two decimals. Deciding between them requires the exact values, and this is the ordinary case rather than a contrived one — the table is flat near its maximum by construction.
Up to seven candidates, play the rule out on every ordering and count. 7! is 5040 and a page can do it; 8! is 40320 and it cannot, so the honest thing at larger n is to say the table is the closed form alone, which is what the lab does.
At four candidates the whole problem fits on a page: 24 orderings, four rules, and every entry of the closed form checkable against a count.
The n = 7 row of decimals is the argument for exact arithmetic in one line. The best two rules differ by 36 orderings out of 5040, which is 1/140, and every rounding anyone would reach for erases it. The table is flat near its maximum because that is the shape of the trade, so this is the normal situation rather than an awkward instance.
For a rehearsal, work out the n = 3 table by hand: six orderings, three rules, and the answer is that r = 2 wins three times in six while r = 1 and r = 3 each win two. Then check it against the closed form. It is the smallest case with a genuine decision in it, and doing it by hand is the fastest way to understand what the rule actually does on a permutation.
The harder rehearsal: move the slider from three candidates upwards one at a time and write down, at each setting, how many the lab says to reject beside n/e rounded. The two agree at 80 of the 98 settings the slider reaches and part at 18 of them — 7, 10, 15, 18, 26, 29, 34, 37, 45, 48, 56, 64, 67, 75, 83, 86, 94 and 97 — and at every one of those the rounded constant is one too many. Finding the first four of them by hand takes a few minutes and settles what the constant is worth better than any sentence here can.
You should be able to state what is observed on each arrival, explain why the optimal rule rejects a prefix and then takes a record, derive the success probability as a sum over the best candidate's position, read the best r off an exact table rather than off a limit, and check a small case by playing the rule out on every ordering.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.