Solution to the optimal stopping problem

Share this page

Solution to the optimal stopping problem

September 1997

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:

(M-1)/(K-1)

So the overall chance of achieving your aim of finding the best potential partner this time is:

(M-1)/(N*(K-1))
Diagram

But K can take any of the values in the range from M to N, so we can write:

P(M,N) = Sum(K=M..N,(M-1)/(N*(K-1))) = ((M-1)/N)*Sum(K=M..N,1/(K-1)

The best value of M will be the one which satisfies:

P(M-1,N) < P(M,N) > P(M+1,N)

(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.)

1/M+1/(M+1)+...+1/(N-1) < 1 < 1/(M-1)+1/M+...+1/(N-1)

We can use these inequalities to find M for any N. Try it! Fill in the blanks below:

1/M + 1/(M+1)+...+1/(N-1) < 1 < 1/(M-1)+1/M+...+1/(N-1) and table N/M for values of N from 3 to 20

[Answers]

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:

Sum(K=1..L,1/K) = ln(L)+C

Using this equation we can calculate an approximation for P(M,N) as follows:

P(M,N) =~ (M-1)/(N-1)*ln((N-1)/(M-2))

For big N, we can make it even more simple:

P(M,N) =~ (M/N)ln(N/M)

In order to find the best value of M we have to apply the approximation to the conditions that we derived before:

ln(N/M) =~ 1, M/N ~= 1/e

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:

Solution table

[Back to questions]

Permalink
Comment

Many thanks for explaining why, after 45* years of dating, I still can't find a lasting match. With your permission I'd like to copy the article, enlarge the raw math sections, mount and frame it. There's a perfect spot on the wall next to my curio cabinet filled with souvenirs from a lifetime of dating duds.

*First date at age 18. Am 63 yrs old now. Never been married, never cohabitated. Normal, pleasant, sensible, good career, well traveled, intelligent, average looks, many interests but not manic about any of them (eg no collections, no cats running wild around the house). Sort of the reliable older sister type but not stodgy.

Permalink
Comment

think there is a typo in the formula #5: P(M-1,N) < P(M,N) < P(M+1,N), should have been P(M-1,N) < P(M,N) & P(M,N) > P(M+1,N)

Permalink In reply to by nil (not verified)
Comment

Ah! I did wonder.