You are given a chance to marry one of N candidates, who will be presented to you one at a time. You must accept or reject the candidate on the spot, without the possibility of returning to a previously rejected one. What is the best strategy for selecting the best candidate? Assume that you can rate each candidate (i.e. the problem is to select the candidate with the highest rating, or score — hence the "dowry").
The most obvious strategy of picking the first one gives 1/100 chance of winning. It turns out we can do much better than that.
We will consider the following type of a strategy. Check out the first k candidates and remember the highest score among them. Then select, among the remaining candidates, the first candidate who beats that score. Let's calculate the probability of winning with that type of a strategy.
P( winning with the "pass first k" strategy on N candidates ) =| N | |
| å | P( winning by selecting m-th candidate ) = |
| m = k + 1 |
| N | |
| å | P( you choose the m-th candidate | the m-th candidate has the highest score ) · P( the m-th candidate has the highest score ) = |
| m = k + 1 |
| N | |
| å | P( the highest score that shows up before the m-th is among the first k ) · P( the m-th candidate has the highest score ) = |
| m = k + 1 |
| N | |
| å | ( k / ( m - 1 ) ) · ( 1 / N ) = |
| m = k + 1 |
| N | ||
| k/N | å | 1 / ( m - 1 ) |
| m = k + 1 |
Now that we have the formula for the probability of winning with a "pass first k" strategy, we can find the k that gives the highest probability:
You can also print the first 1000 cases. What is so remarkable about the result? The explanation of this remarkable behavior, as well as the significance of the number 0.3678794... , can be revealed using techniques from Calculus.