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]

Reply

  • Web page addresses and e-mail addresses turn into links automatically.
  • Allowed HTML tags: <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Lines and paragraphs break automatically.

More information about formatting options

To prevent automated spam submissions leave this field empty.
By submitting this form, you accept the Mollom privacy policy.