applets.

When to Stop Looking

← All apps

About When to Stop Looking

You're house hunting. The houses come up one at a time, in a random order. After each viewing you must make an offer or walk away, and a house you walk away from is gone for good. You can't score a house on its own, only say how it compares with the ones you've already seen. How do you give yourself the best chance of buying the very best one?

The viewings (left) lets you try it: 10, 20 or 50 houses. The card shows the house on view and where it stands among those you've seen; the strip under it lists them best first. When you buy, the diary shows every house's true rank (1 = the best), the one you bought, and what the 37% rule would have bought on the same houses. Keys: O make an offer, W walk away, N new search.

The market report (right) tests every look length at once on thousands of random searches. The line is the Expected chance (worked out exactly), the red dots are the simulation. You can aim for one of the top 2 or top 3 instead of the best, or charge a cost for every viewing.

THE 37% RULE

Look at the first n ÷ e houses (e = 2.718…, so about 37% of them) and turn them all down, whatever they're like. Then make an offer on the first house that's better than every one you've seen. If none is, you're left with the last house. As the number of houses grows, this finds the best one about 37% of the time (1 ÷ e = 0.368), and no rule does better: a striking result, since the chance of picking the best at random is 1 in n.

THE STORY

The puzzle reached a wide audience through Martin Gardner's Mathematical Games column in Scientific American in February 1960, as the "game of googol": someone writes numbers on slips of paper, you turn them over one at a time and must stop at the largest. Gardner credited it to John Fox and Gerald Marnie, who came up with it in 1958. Dennis Lindley gave one of the first published solutions in 1961, using dynamic programming, and Eugene Dynkin solved it with the theory of Markov stopping times in 1963. It has been told as the secretary problem, the marriage problem, the fussy suitor and the dowry problem; Thomas Ferguson's 1989 paper Who solved the secretary problem? traces how tangled the history is, back to a question of Arthur Cayley's in 1875.

A story often told with it: the astronomer Johannes Kepler, after his first wife died in 1611, is said to have weighed up eleven possible brides over about two years before marrying Susanna Reuttinger in 1613. It's a nice story, but treat the details as uncertain, and Kepler wasn't following a rule.

HOW IT WORKS

Turn down the first k houses and take the next one better than all of them. You end with the best house exactly when the best is at some place i after the look, and the best of the houses before it was inside the look (otherwise you'd have stopped at that one). The best is at place i with chance 1/n, and the best of the first i − 1 is among the first k with chance k/(i − 1), so the chance is k/n × (1/k + 1/(k+1) + … + 1/(n − 1)). For large n that is about x × ln(1/x) with x = k/n, which is largest at x = 1/e.

For the top 2 or 3 the same sum is used, with the chance that the house you stop at is among the top m (the best of the first i houses is in the top m unless all i miss the top m). This app keeps one look length for those goals; the best strategy for them uses more than one threshold, and needs an even shorter look. With a cost per viewing, the chart shows the chance of success less the expected cost of the viewings, which pulls the best look length earlier.

The simulation scores every look length on the same random searches: for a look of k, the rule stops at the first house after the look that beats every house before it, so one pass through a search answers all the look lengths together.

FURTHER WATCHING AND READING

THE VIEWINGS

One house at a time. No going back.
HOUSES
VIEWING 1 OF 20FOR SALE

SEEN SO FAR · BEST FIRST

THE DIARY · IN THE ORDER YOU SAW THEM

MARKET REPORT

How long should you look?

HOUSES
AIM FOR
COST PER VIEWING
SEARCHES
BEST LOOK · EXPECTED
THE 37% RULE
SIMULATED