How to mathematically choose the best Christmas gift
It’s almost Christmas time again and Santa has just finished getting gifts for everyone. Knowing about your proficiency in mathematics, Santa has decided to do something special for you. He has brought you 100 gifts, of which you can only keep one. However, you cannot simply examine the pool of all gifts and pick the best one. Santa will show you all the gifts one by one, and after seeing a gift, you must immediately decide if you want to keep that gift. If you reject it, he will move on to the next gift and you cannot go back to it. What strategy should you use to maximize the chances of picking the best gift? If you pick a gift too soon, the chances are high that you have not yet seen the best gift. But if you wait too long, it will probably have already passed. A useful strategy seems to be to always reject the first couple gifts to get an idea of the quality of the gifts Santa picked, and after that pick the first gift that is better than any of the ones you have seen before. But how should you figure out the optimal number of gifts you need to reject?
This problem is known as the ‘secretary’ problem, and it is usually framed as the problem a hiring manager faces when he needs to find the best secretary out of a selection of candidates. It is an example of a question in the field of optimal stopping theory, which deals with deciding the best time to take a particular action with the goal of maximizing an expected reward. Problems like this are ubiquitous in many areas of study, particularly in mathematical finance. As an example, there is the problem of trying to find the optimal time to exercise an American-style option, which in turn is necessary in order to price such options.
Let’s get back to Santa’s gift problem. Our strategy will be to reject the first n gifts, and then pick the first gift that is better than any gift we have seen before. We wish to find the value of n that maximizes our probability of picking the best gift.
Suppose that gift number k is the best gift. What is the probability that we will pick it? If k ≤ n, then we of course automatically reject it. Otherwise, suppose the best gift before gift k is gift number m. Then gift k gets picked precisely if m ≤ n (if not, that means that among gifts n+1 to k-1, there is a gift better than the first n, so that one gets picked instead of k). Since there are a total of k-1 possibilities for m, this means that the probability that gift k gets picked if it is the best one is n/(k-1).
Figure 1: In the first case gift k will not be picked, as gift m is already better than the first n. In the second case it will be picked, since no other gift before it is better than gift m, which occurs in the first n.
Since each gift has a 1/100 probability of being the best one, the probability that gift k is the best and is also picked is equal to 1/100 * n/(k-1). Adding this up over all k from n+1 to 100, we see that the total probability of picking the best gift is equal to
n/100 * (1/n + 1/(n+1) + … + 1/99)
To maximize this probability, we could try all values for n and see which gives the highest result. But we can make our life a little simpler if we approximate the probability by something that is easier to work with. We can visualize the above sum as follows: picture a bunch of adjacent rectangles with width 1 and height 1/k, going from k=n to 99. The sum is now the total area of these rectangles, which is roughly equal to the area under the curve y=1/x, from x=n to x=100.
Figure 2: We can approximate the sum by the area under this curve.
From calculus we know that this area is equal to ln(100) – ln(n) = -ln(n/100) (ln refers to the natural logarithm). Thus, our final probability can be estimated as -n/100 * ln(n/100). This function can now easily be maximized by setting its derivative equal to 0 and solving for n, which yields that the maximum occurs around n = 100/e ≈ 37.
Figure 3: Estimations of the probability versus their true values.
This suggests that we should reject the first 37 gifts Santa shows us, and then choose the first gift that is better than all the previous ones. If we calculate the true probabilities, it turns out that due to the error in our approximation the optimal cutoff is actually 36 gifts. With this strategy, we maximize our chances of picking the best gift, which now happens with a probability of about 37%. More generally if there are a total of M gifts, our calculation says that the maximal probability is around 1/e * 100% ≈ 36.79%, with an optimal cutoff of M/e gifts.
The solution to the secretary problem is relatively easy to derive, as we have just seen. Most problems in optimal stopping theory require more advanced tools, such as the theory of martingales and Markov processes. So, let’s hope that this Christmas, the best gift you get from Santa is a probability textbook!
References: Secretary problem - Wikipedia