“‘How do mathematicians find love in a world filled with logic and rationalism?’ I was recently asked.

‘Well, that’s easy’, I said. And this is what I told them.

The Problem Setting

The problem is mostly referred to as the Marriage Problem, sometimes also the Secretary Problem. Since, if anything at all, I would be looking for a man to spend my life with, let’s call it the Husband Problem.

We assume that there is a number of n guys that I could potentially date throughout my life. I know that this is a difficult assumption to make. How would I ever know how many other guys there would be down the lane if I didn’t keep rejecting guys until there was no one left?

Nonetheless, let’s assume we have a number of n candidates to choose from. The only problem here: Once I settle for someone, I have settled. That’s it. That’s the deal I’m getting and I will never know who I am missing out on.

We also assume that I cannot go back to someone I have previously rejected.

Furthermore, we assume that for any two guys, I can decide who is better (at least for me). We also assume that the candidates are uniformly distributed. Intuitively, that means that the probability of the best candidate being in a certain position is the same for all positions.

Of course, I want the best deal I can get. I want to find the guy that is the best out of the n guys that I could potentially marry. The question is: How do I know when to stop searching? What if I decide that I am not happy with someone but I realize that there might never be anyone better? What if I keep rejecting guys and in the end, I realize that I will have to live with a poor choice or no choice at all because there are no candidates left?

Well, that’s a different story. For now, we want to maximize our chances of finding the best one.

Let’s talk about math!

A Mathematical Approach: The Strategy

The way we formulated the problem includes that we are incredibly picky. That means we want the best candidate or no candidate at all. It also means that success is defined by having chosen the best candidate and failure is defined by having chosen any other candidate other than the best one.

This means that our goal is to maximize the probability of picking the best candidate. Failure means that we picked any other candidate (even the second-best one).

How do we maximize our chances of finding the optimal candidate? Here’s our strategy:

1. Look at the first k-1 candidates and reject all of them.
2. Choose the first candidate starting with candidate k that is better than all of the candidates previously seen.

Let’s look at an example to make this clearer and pretend there are 12 possible candidates (n=12). We now choose to set k=5. This means that we date the first 4 guys, we reject all of them and then we take the first one that is better than all of the first 4 guys.

What are the possible results here?

• Let’s say our optimal candidate is candidate number 2: Too bad, we keep rejecting everyone until we end up with candidate number 12.

• Our optimal candidate is candidate number 7: Great, we got the best deal possible by following this strategy and settled for candidate number 7!

How to choose k?

Choosing k is the hardest part. If we choose k too small that means we only get to look at very few candidates before making a choice. Let’s say we choose k=1. That means we pick the first guy that comes along. The chance that this candidate is the best is 1/n ( — remember how we said that the candidates are uniformly distributed?). Doesn’t seem like the smartest strategy, does it?

What if we choose a large k? For example, if we choose k=n. Well, then we’re always stuck with candidate n, no matter how good or bad this candidate is. Again, we end up with the optimal candidate with a probability of 1/n.

Intuitively, a good k lies somewhere in between 1 and n, and luckily, Math has all the answers for us.

Our goal is to find the optimal candidate. That means that we want to maximize the probability of finding the best candidate. To do this, we use the function ϕ(k) to describe this probability for a fixed n. We need to determine ϕ(k) for all admissible k and then pick the k for which this function takes the highest value.

How do we calculate ϕ(k)?

Let’s set n=5 and go through it step by step.

k=1:

If we set k=1, we end up with the first candidate. The probability that this is the best candidate is 1/5 and therefore, ϕ(1) = 1/5.

k=2:

If we set k=2, we look at the first candidate and reject him. We then start going through all of the other candidates.

• If candidate 2 is the best (with probability 1/5), he is also better than candidate 1 and in that case, we pick him with probability 1.
• If candidate 3 is the best (with probability 1/5), he is better than candidate 1, but with a chance of 1/2, we have already picked candidate 2. Therefore we only pick candidate 3 with a probability of 1/2.
• If candidate 4 is the best (with probability 1/5), he is better than all the previous ones, but with a chance of now 2/3, we have already settled for candidate 2 or 3. Therefore we pick candidate 4 with a probability of 1/3.
• If candidate 5 is the best (with probability 1/5), he is better than all the previous once, but with a chance of now 3/4, we have already settled for any of the candidates 2, 3 or 4. Therefore we pick candidate 5 with a probability of 1/4.

Thus, we can calculate ϕ(2) by

k=3,…n:

For k=3,…n, we do the same as we did for k=2.

This generalizes to

and for n=5, we get these probabilities for k. If we punch in the numbers for k=1,…5, this leads to the following table.

For k=3, ϕ(k) takes the highest value. That means that we are supposed to look at the first two candidates and then pick the first one that is better than candidates 1 and 2.

So for small n, we can either calculate this by hand or use a programming language of our choice to figure out which k is optimal.

For example, for n=12, we get the following table.

For k=5, we get the highest value. That means we should take a look at the first four candidates and then pick the first one that comes along and is better than those 4 candidates.

And for large n, we can check out the limit!

Finding the Optimal k for Large n

For large n, we can look at the limit of our above formula and use the Rieman approximation. We set x=k/n and ϕ(k) converges as follows.

This function ϕ(x) is differentiable and we can calculate the first derivative and set it to zero to find a local maximum.

Because of

this is, in fact, the maximum and now we know that for large n, we always choose k≈ 0.368 ⋅ n.

So if you have 100 candidates in your life, it’s optimal to look at the first approximately 36 candidates and then pick the first one that is better than all the ones you’ve seen before.

In case you’re wondering: Of course, there are other ways to define an optimal strategy. Especially if you are happy with a candidate that surpasses a certain threshold or if the second-best choice is not too bad either. But these strategies are not part of this story.

A note on the Naming of the Problem

In Literature, the problem is often referred to as the Marriage Problem. This is problematic though as one usually doesn’t know about the number of potential marriage partners in life before meeting them all.

That’s also the reason, why sometimes it is called the Secretary Problem. It is a little bit easier to know how many people have applied for a certain job than to know how many people would volunteer to spend the rest of their lives with someone. But then again, why would we not be able to first look at all job candidates before rejecting them?

That’s why my friends and I jokingly call it the Calendar Problem. It’s because they once gave me a calendar for my birthday where you had to rip off the pages to see the next page. There was no going back once you had ripped off a page. And we knew right from the start how many candidates there were (12!). I ended up using the above strategy. For three years, I had the September picture hanging up there on my wall. Some people might say, that’s stupid and “Wait, it’s a calendar, wouldn’t you wanna have the right month up?”.

Well, yes, but who needs the right month up if you can do the calculations in your head anyway? 

And lastly:

In case you’re wondering whether this is REALLY the way Mathematicians look for love: probably not. But if you’re a Mathematician like me and you’re ever looking to lose a guy in 10 minutes: This is your story to tell!”

By Maike Elisa for Towards Data Science