The Secretary Problem: Picking from the Top 10 Percent

Somebody offers you a hundred houses. You will see them one at a time, in a random order, and each time you must say yes or no on the spot. Say no, and that house is gone for good. Here is the kind part. You do not need the best of the hundred. Any of the ten best would make you perfectly happy, and that single change turns a famously hard problem into an easy one. Let me build a scale to measure this on. Give every house a score, and hand the scores one to a hundred out to the hundred houses, one each. So a hundred is the best house there is, and one is the worst. They arrive in a random order, so they land anywhere along it. The first house scores forty two. The second scores sixty eight, better, and both are already gone, because you turned them down. One warning about this picture. We are outside the story, so we can read the scores. The buyer cannot. All the buyer can ever do is hold two houses side by side and say which of them is better. Now the target. The ten best houses are the ten highest scores, ninety one up to a hundred, so winning means landing under this brace at the top of the scale. Compare that with the famous version, where nothing but the very best house will do. That target is a single point, and everything else is failure. The known answer is to look at thirty seven houses, buy nothing, then take the first one that beats them all. It wins about thirty seven times in a hundred. Now widen the target to ten points and keep that very same strategy, cutoff and all. Whenever it buys a house, the house it buys is one of the ten best better than ninety eight times in a hundred. Making sure it buys at all is the only job left over.

Here is one journey through a hundred houses, seen from outside. Along the bottom, the order they arrive in. Up the side, their scores, with the ten best of them inside the red band at the top. I will not draw all hundred houses. I will draw one thing instead: the best score seen so far. That line can only climb, and every step in it is a house that beat everything before it. There are only five or six of those steps in a random hundred, and they thin out as you go, because beating the best of fifty is far harder than beating the best of five. Now the strategy, in three lines. One: let the first thirty seven houses go past, whatever they are, and buy nothing at all. Two: take the best score among those thirty seven. Here it is, ninety three, at house twenty six. That score is now your bar. Three: from house thirty eight onward, buy the first house that clears the bar. And that is the whole rule. Look for a third of the list, then take the first house that beats everything you saw while you were looking. Watch it run. House forty one is pleasant enough. House forty nine scores eighty seven, better than almost anything you have seen, and you must let it go, because it does not clear the bar. Then house fifty eight scores ninety seven. That clears the bar, so you buy it and stop. And look where it landed, inside the band. It is the fourth best house of the hundred. The very best house of all, the one scoring a hundred, turns up much later, at house eighty four. You never see it, and it does not matter in the slightest. You were not trying to find it. Two things could have gone wrong, and both are about where that dashed line stands. Stop looking after five houses and the bar would sit at sixty eight, low enough for an ordinary house to clear it. Look at ninety and the bar would be a hundred, which nothing left could ever beat. So why is a bar built from only thirty seven houses good enough? Let me take the climbing line away and mark the ten best houses instead. There they are. Ten houses inside the band, landing anywhere, because the order is random. Now count how many arrived in your first thirty seven. Exactly one, the ninety three that set your bar. One is all you need, and that is the secret. Each of these ten, on its own, has a sixty three percent chance of landing after the line. For your bar to miss the band, every single one of them has to. Sixty three percent, ten times over, is about one chance in a hundred. The ten crowd each other slightly, so the true figure is smaller still, about one chance in a hundred and thirty five. Which means the bar you built out of thirty seven houses is itself one of the ten best, ninety nine times in a hundred. And here is the step that turns that into a promise. Suppose the bar is inside the band. The band runs from the bar up to the top of the scale, so every score above the bar is inside the band as well. So any house clearing the bar is one of the ten best. Not probably. Certainly. The only way this rule hands you a bad house is if the bar itself missed the band, and that is the one chance in a hundred and thirty five. Which leaves exactly one weakness, and it is not about buying badly. It is about never buying at all.

Here is a different hundred houses, in a different order, and this time the luck runs the other way. The best house in the whole set, the one scoring a hundred, arrives at house twelve, while you are still only looking. So the best of your first thirty seven is a hundred, and your bar sits at the very top of the scale. Nothing can clear it. You watch the remaining sixty three houses go past, turn every one of them down, and reach the end of the list having bought nothing at all. And this is no freak. The best house of the hundred is equally likely to be anywhere, so it lands inside your looking window thirty seven times in a hundred, and every one of those runs ends empty handed. Here is the cure, drawn as a second picture. Along the bottom, the order again. Up the side, how many houses you are willing to have above the one you buy. At first you accept nothing but the best you have seen. As the list runs out you relax. After fifty, the second best of what you have seen will do, then the third, and near the end you take almost anything decent. Why is that safe? The second best of fifty houses misses the top ten only if nine or ten of the ten best hid in the second half. That is like ten coin flips coming up almost all heads, about eleven chances in a thousand. Relax that way all the way down the list, and the rule nearly always buys, and what it buys is nearly always in the top ten. Better than ninety eight times in a hundred, and that is the promise. So here is the whole strategy, in four lines. Look at the first thirty seven houses and buy nothing. Set the bar at the best of them. Then buy the first house that clears it. And as the list runs out, let the bar come down, one place at a time, so you never reach the end with nothing. That is the whole of it. You cannot know which house is the best. But you can spend a third of your search learning what good looks like, and then have the nerve to stop.