## Solution to the optimal stopping problem

Submitted by plusadmin on September 1, 1997The 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 *K*th 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.