Solution to the optimal stopping problem
The probability of choosing the best partner when you look at M-1 out of N potential partners before starting to choose one will depend on M and N. We write P(M,N) to be the probability.
For any value of N, this probability increases as M does, up to a largest value, and then falls again. P(1,N) and P(N,N) will always be 1/N because these two strategies, picking the first or last potential partner respectively, leave you no choice: it's just like picking one at random. Our aim is to find when P(M,N) is largest.
Suppose that you have collected the information from M-1 potential partners and are considering the Kth in sequence.
Since the potential partners come along in a random order, the chance that this one is the best is 1/N. But you only consider this potential partner if the highest ranking potential partner that you've seen so far was among the first M-1 of the K-1 that you have rejected (otherwise you wouldn't be looking at this potential partner at all). This happens with the following probability:
So the overall chance of achieving your aim of finding the best potential partner this time is:
But K can take any of the values in the range from M to N, so we can write:
The best value of M will be the one which satisfies:
(If you want to be very awkward, you could ask what happens if there are two "best" values of M, with one of those strict inequality signs replaced by a partial inequality. It turns out that the only time when equality is possible is when N=2, which is not very interesting anyway.)
We can use these inequalities to find M for any N. Try it! Fill in the blanks below:
The fraction of the potential partners that you see M/N is tending to a limit as N becomes large. There is a sum in the calculation of P(M,N) which appears in other situations in mathematics too:
Using this equation we can calculate an approximation for P(M,N) as follows:
For big N, we can make it even more simple:
In order to find the best value of M we have to apply the approximation to the conditions that we derived before:
1/e is about 0.368. This result can be expressed simply in the following "37%" rule:
37% rule
Look at a fraction 1/e of the potential partners before making your choice and you'll have a 1/e chance of finding the best one!
Further reading:
For more information see the article "Mathematics, marriage and finding somewhere to eat" elsewhere in this issue.
Answers to problems:
