Season 11 Episode 10

In this episode, Charles and James explore a problem where you must choose the best possible dorm room without being allowed to go back to one you've previously seen.

Watch on YouTube

Further Reading

Secretary Problem

Charles was inspired by this Veritasium video from a couple of years ago about the number 37; Why is this number everywhere? | Veritasium | YouTube

Ria Symonds did some similar mathematics on Numberphile back in 2014 with a bit of a different theme!  Mathematical Way to Choose a Toilet | Numberphile | YouTube

This problem is also in Hannah Fry’s Mathematics of Love. TED talk here; The mathematics of love | Hannah Fry | TED | YouTube or read the write-up or get the book.

Sums and integrals

I’d like to try and give more information about the step where Charlies approximated a sum with an integral.

To start with, let’s think about the sum of the reciprocals of the first \(n\) numbers;

$$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n-1}+\frac{1}{n}.$$

Perhaps you’ve seen this sum before as an example of a sum where each new term that’s added is smaller and smaller, but where the sum overall steadily gets larger without bound (it does not tend to any finite value; if you have enough terms you can make it as large as you like). This is sometimes shown to people just after they’ve seen a geometric series, in case you think that “terms getting smaller = this sum will tend a finite value". That’s not true, and we can prove it with the sum above.

Here's a proof that the sum gets as large as you like. Choose a number \(k\), as large as you like, and set \(n=2^{2k}\), which will be a really huge number. Then the sum can be bracketed like this

$$1 + \left( \frac{1}{2}\right) + \left( \frac{1}{3}+\frac{1}{4}\right) + \left( \frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}\right)+\dots + \left(\dots+ \frac{1}{2^{2k}}\right)$$

After the first 1, each bracket contains twice as many terms as the one before, but the value of each bracket is greater than or equal to \(\frac{1}{2}\). There are \(2k\) such brackets, so this sum overall is greater than \(k\).

You can set \(k\) as large as you like, and if you’re patient enough, then the sum will eventually be larger than \(k\).

Even if you’ve seen that fact before, you might not have seen a way to approximate or bound the value. Here's the idea; we’ll look for somewhere else in mathematics where that sum appears.

This image shows the function \(y=1/x\) and some rectangles between \(x=1\) and \(x=n+1\), with \(n=7\) as an example. Each rectangle is bounded between two integers on the \(x\)-axis, and the height of the rectangle is given by the value of the function on the lower integer (the left side). Since the curve is decreasing, each rectangle is above the curve over the range of that rectangle, and so the area of the rectangle is larger than the area under the curve.

There’s a fact from A-level Mathematics that lets you work out the area under the curve \(y=1/x\) from \(1\) to \(n+1\). Perhaps surprisingly, it’s \(\ln(n+1)\) where \(\ln(x)\) is the natural logarithm, the solution \(y\) to the equation \(x=e^y\) for a given positive value of \(x\).

The logarithm of \(n+1\) grows with \(n\) without bound, so this is another proof that the sum grows without bound. For the livestream, we said that the value of the sum is approximately the value of the area under the curve, but we can do better than that!

Let’s modify the curve to get an overestimate for the sum instead of an underestimate. Ignoring the initial \(\frac{1}{1}\) for a moment, we can consider the curve \(y=\frac{1}{x-1}\) between \(x=2\) and \(x=n+1\). The rectangles now meet the curve on the “other” corner (the right side).

Another little bit of integration shows that \(\frac{1}{1}+\frac{1}{2}+\dots+\frac{1}{n} < 1+\ln(n)\).

So this logarithm approximation is actually quite good; we can bound the sum below by a logarithm, and also bound the sum above by a logarithm.

There’s a name for the difference between the sum and the natural logarithm; that’s the Euler–Mascheroni constant.

This comparison between a sum and an integral is called the integral test. You can read more about it online here, and it’s generally covered in University-level courses on Analysis as part of a Mathematics degree.

Secretary problem

Just to run through the key steps of the calculation that Charles showed us in the episode

• Suppose that your strategy with \(N\) rooms is to look at the first \(S\) of them, and then take the next one that’s better than all of the first \(S\)
• Then for any value of \(S\), there are lots of ways to win (get the best room); you might see it straight away, or it might be nearer the end.
• For any value of \(S\), we can sum up the probabilities for the different ways to win
• We want to choose the value of \(S\) that maximises this sum. There are various techniques to do this, but one (approximate) method is to replace the sum with an integral, replace the discrete values of \(S\) with a continuous variable, and use calculus to differentiate the function and find the maximum value.

The approximations matter. Our final answer “Set \(S=N/e\) and look at the first \(S\) rooms, and then take the next one that’s better than those” isn’t even guaranteed to be the best value of \(S\). For one thing, that’s not a whole number. And rounding it up or down or to the nearest whole number isn’t guaranteed to give you the best possible value. For small values of \(N\) the approximation is quite crude. And for large values of \(N\), there are so many integer values near \(N/e\) that it’s plausible that any one of them could give the literal maximum.

This caught me out in a Numberphile video; I presented a problem (also involving the number \(e\), as it happens) and confidently asserted that the optimal solution would be the integer closest to my approximation. The YouTube comments were quick to point out the error!