# As Good as It Gets

## What are we going to learn?
In this course you will learn how to find a nice flat, land your dream job and even have a successful love life. In other words, we will explore everyday life situations involving results from a branch of mathematics called the optimal stopping theory. You will establish strategies to decide when to stop searching and settle on your choice --- using maths.

**Prerequisites:**
- Calculating simple probabilities.
- [Conditional probability](https://brilliant.org/wiki/conditional-probability/), [the law of total probability](https://brilliant.org/practice/conditional-probability-casework-calculations/) and [probability trees](https://brilliant.org/wiki/conditional-probability-distribution/).

We will also need a little bit of calculus:
- [Riemann sums](https://brilliant.org/wiki/riemann-sums/).
- [Derivative tests](https://brilliant.org/wiki/optimization-problems/).

However, you do not need these two concepts to understand the rest of the course, so definitely give it a go!

## Flat hunting
You are looking for a flat in London. An estate agent offers to show you three flats. The market in London moves very fast, so you will have to make up your mind and sign the contract on the spot, before your next viewing. Assuming that the agent picks the viewing order at random, you decide that it does not make sense to view all three flats but just accept the first one you are shown.

### Problem 1
*What is the probability that you get the best flat if you only view the first one?*
- $\frac{1}{2}$
- $\frac{1}{3}$
- $\frac{2}{3}$
- *It depends on the quality of the flats*

**Answer**
<details >
<summary>
</summary>

Each flat has equal chance of appearing first, so the first flat you see is the best of all three with probability $\frac{1}{3}$.
</details>

### Problem 2
*Would your chance of choosing the best option change if you decided upfront to pick the third flat?*
- *Yes, it would increase*
- *Yes, it would decrease*
- *No, it would not change*

**Answer**
<details >
<summary>
</summary>

Each flat has equal probability of appearing first, second or third, so you pick the best flat also with probability $\frac{1}{3}$.
</details>

Let's see if you can do better than that. If you just pick the first flat you see, you ignore the possible information you could get after viewing other properties. On the other hand, if you wanted to see all three flats to get the full picture, you would be stuck with the last one, since you cannot go back. The optimal strategy would be a compromise between choosing the first option (when you do not have any information) and waiting until the end (when it is too late for any decisions).
To maximise the probability of picking the best flat (based on your personal ranking), you should define a cut-off $k \in \{1,2,3\}$ and view the first $k-1$ flats just to gather information. Then you need to settle on the first flat better than all you have seen before (otherwise you certainly would not pick the very best one) or the last one, if all flats after the $(k-1)$-th one are worse than one from before. What should the cut-off point $k$ be?

### Problem 3
*If you use the optimal strategy with $k=2$, what is your chance of getting the best flat?*
- $\frac{1}{2}$
- $\frac{1}{3}$
- $\frac{2}{3}$
- $1$

**Hint**
<details >
<summary>
</summary>

*Imagine you are going to see flats $A$, $B$ and $C$ such that $A$ is the best, while $C$ the worst --- but you do not know their ranks in advance. List all possible orders of flat viewing and your choice for $k=2$.*

</details>

**Answer**
<details >
<summary>
</summary>

In the following table we list all possible viewing orders and the flat we end up picking if the cut-off point $k$ equals $2$.

| Viewing Order | Chosen Flat |
| ------------- | ----------- |
| A,B,C | C |
| A,C,B | B |
| B,A,C | **A** |
| B,C,A | **A** |
| C,A,B | **A** |
| C,B,A | B |

In this case you pick the best flat $A$ in three out of six cases, so the probability equals $\frac{1}{2}$. Notice that this chance is bigger than if you always picked the first flat (corresponding to $k=1$) or the last one (equivalent to $k=3$).
</details>

### Problem 4
*Another agency offers four flats instead of three. Which cut-off $k$ maximises your probability of choosing the best flat?*
- $k=1$
- $k=2$
- $k=3$
- $k=4$

**Answer**
<details >
<summary>
</summary>

Listing all 24 options, similarly to the previous problem, leads us to the conclusion that for $k=1$ you get the best flat in 6, for $k=2$ in 11, for $k=3$ in 10 and for $k=4$ in 6 cases out of 24. This means that you should choose the cut-off point $k=2$, i.e. always reject the first flat and pick the best one you see afterwards.
</details>

## Job interviews
In the previous problems we explored examples of the so-called **secretary problem**, known also as the sultan's dowry problem, the optimal dating problem or the googol game. We can formulate it as follows.

### The secretary problem
Brilliant needs to hire a maths content writer. After receiving $N$ applications, with $N$ being an integer, they interview candidates one by one, in no particular order. After each interview they are able to rank the candidate among the others met so far; in particular, they know who their current favourite is. The applicants are impatient, so the Brilliant team must decide if they want to hire the candidate immediately after the interview. How can they maximise the probability of hiring the very best applicant?

We have already seen that to maximise the probability of picking the best candidate (or a flat) one needs to define a cut-off $k \in \{2,3,\dots\}$; $k=1$ is equivalent to always choosing the first candidate. The Brilliant team should treat the first $k-1$ applicants like guinea pigs: interview them only to gain some information and reject regardless of their abilities. After that, they will choose the first candidate better than all seen so far, or the last one if they are unlucky.

### Problem 5
*What is the probability that a given candidate is the best?*

- $\frac{1}{2}$
- $\frac{1}{N}$
- $\frac{1}{N^2}$
- $\frac{N}{2}$

**Answer**
<details >
<summary>
</summary>

Candidates arrive in random order, so any candidate is the best with equal probability $\frac{1}{N}$.
</details>

### Problem 6
*The Brilliant team is interviewing the $i$th candidate. If she is the best one, what is the probability she will be picked?*
- $$ \begin{cases}
\frac{1}{k-1} & \text{if } i \leq k-1,\\
\frac{k-1}{i-1} & \text{if } i \geq k.
\end{cases}
$$
- $$ \begin{cases}
0 & \text{if } i \leq k-1,\\
1 & \text{if } i \geq k.
\end{cases}
$$
- $$ \begin{cases}
0 & \text{if } i \leq k-1,\\
\frac{k-1}{i-1} & \text{if } i \geq k.
\end{cases}
$$

**Hint**
<details >
<summary>
</summary>

*Consider the cases $i \leq k-1$ and $i \geq k$ separately.*

</details>

**Answer**
<details >
<summary>
</summary>

If $i \leq k-1$, according to the strategy our candidate must be rejected. If $i \geq k$, she will get the job if and only if the best of all previous $i-1$ applicants was among the first $k-1$ applicants; in other words, the second-best candidate was interviewed in the initial sample of $k-1$ candidates. Therefore, if the $i$th candidate is the best, she will be accepted with probability
$$
\begin{cases}
0 & \text{if } i \leq k-1,\\
\frac{k-1}{i-1} & \text{if } i \geq k.
\end{cases}
$$
</details>

To compute complicated probabilities we often split the event into [separate cases](https://brilliant.org/practice/conditional-probability-casework-calculations/?chapter=conditional-probability-2). These cases must be mutually exclusive and fill the whole sample space, which means that exactly one of them occurs. For example, if Brilliant receives only two applications, they will make one of four possible choices, illustrated in the right hand side of the [probability tree](https://brilliant.org/wiki/conditional-probability-distribution/) below. $B_1$ and $B_2$ correspond to the events that the first or second candidate is the best one, respectively. $BC$ denotes choosing, while $\overline{BC}$ not choosing the best candidate.


The best candidate will get the job in two cases:
- candidate 1 is chosen and candidate 1 is best ($BC \cap B_1$);
- candidate 2 is chosen and candidate 2 is best ($BC \cap B_2$).

In other words, we trace the red paths of the probability tree, multiplying the appropriate probabilities, and add these mutually exclusive (such that exactly one of them occurs) cases together:
$$
\mathbb{P}\left(BC\right)=\mathbb{P}\left(BC \cap B_1\right) + \mathbb{P}\left(BC \cap B_2\right) = \mathbb{P}\left(BC|B_1\right)\mathbb{P}\left(B_1\right)+\mathbb{P}\left(BC|B_2\right)\mathbb{P}\left(B_2\right).
$$
Of course we can generalise this method to any number of candidates.

### Problem 7
*By splitting the problem into mutually exclusive cases and using the previous results, compute the probability that the best candidate gets the job. Assume $k>1$.*

- $\frac{k-1}{N}\sum_{i=k}^N \frac{1}{i-1}$
- $\frac{k}{N}\sum_{i=k}^N \frac{1}{i}$
- $\frac{k-1}{N}\sum_{i=1}^N \frac{1}{i}$
- $\frac{k-1}{N}\sum_{i=1}^k \frac{1}{i}$

**Hint**
<details >
<summary>
</summary>

Similarly to the case of two applicants, we write the probability of the best candidate being chosen as
$$
\mathbb{P}\left(BC\right)=\sum_{i=1}^N \mathbb{P}\left(BC \cap B_i\right)= \mathbb{P}\left(BC|B_i\right)\mathbb{P}\left(B_i\right).
$$
And you already computed all the ingredients of this sum!
</details>

**Answer**
<details >
<summary>
</summary>

Recall that the probability that the $i$th candidate is best equals
$$
\mathbb{P}\left(B_i\right)=\frac{1}{N},
$$
while the probability that the best candidate gets the job if the $i$-th candidate is best
$$
\mathbb{P}\left(BC|B_i\right)=\begin{cases}
0 & \text{if } i \leq k-1,\\
\frac{k-1}{i-1} & \text{if } i \geq k.
\end{cases}
$$
We can just substitute these expressions to obtain
$$
\mathbb{P}\left(BC\right)=\sum_{i=1}^{k-1}0*\frac{1}{N}+\sum_{i=k}^{N}\frac{k-1}{i-1}*\frac{1}{N}=\frac{k-1}{N}\sum_{i=k}^N \frac{1}{i-1}.
$$
This result holds for $k>1$. If $k=1$, the Brilliant team always hires the very first interviewee, so they pick the best one with probability $\frac{1}{N}$.
</details>

Well done! You can now find the probability of choosing the best candidate for any cut-off point $k$.

## Dating

### Problem 8
*You finally asked that good looking maths enthusiast out --- and he said yes! After a successful evening in the cinema you both became hungry. You want to impress your date with the restaurant choice, but you do not know the neighbourhood very well. You decide to peek into restaurants you are passing by and mentally rank them. Of course you do not want to appear indecisive to your Prince Charming, so you never go back to the place you have just seen and you give yourself a limit of five restaurants: if you reach the fifth one, you are going to eat there, no matter what. Having studied maths to win the heart of your friend, you know that you should reject the first few restaurants. At which point should you allow yourself to sit at a table, i.e. what is the optimal cut-off $k$? Type your answer:*

**Answer**
<details >
<summary>
</summary>

You can use the expression for the probability of choosing the best candidate to compare the probabilities for different cut-off points $k$:
$\frac{24}{120}$, $\frac{50}{120}$, $\frac{52}{120}$, $\frac{42}{120}$ and $\frac{24}{120}$ for $k=1$, $k=2$, $k=3$, $k=4$ and $k=5$, respectively. The largest value is obtained for $k=3$, so you should reject the first $2$ restaurants and afterwards accept the first one better than all seen so far.
</details>

You found that for $N=3$ and $N=4$ the optimal cut-off is given by $k=2$, while for $N=5$ by $k=3$. Now we are ready to generalise the result for natural numbers $N>5$.

How does the expression for the probability of choosing the best candidate behave as a function of $k$? In the following figure we notice that for $N=100$ the chance of picking the best candidate initially grows until it reaches the maximum and starts decreasing. This maximum is exactly in the cut-off point $k$ which we want to compute.

Let's slightly rewrite the expression for the probability of choosing the best candidate:
$$
\mathbb{P}\left(\text{we pick candidate $i$ and $i$ is the best candidate}\right)=\frac{k-1}{N}\sum_{i=k}^N \frac{1}{N}\frac{N}{i-1}.
$$

If you are familiar with [Riemann sums](https://brilliant.org/wiki/riemann-sums/), you might spot that for large $N$ the sum in this equation approximates a definite integral of the function $f(t)=\frac{1}{t}$. The following [figure](https://www.math.ubc.ca/~pwalls/math-python/integration/riemann-sums/) shows $f(t)$ plotted between $\frac{k-1}{N}$ and $1$ for $N=10$ and $k=3$. The value of the integral
$$
\int_{\frac{k-1}{N}}^{1}\frac{1}{t} dt
$$
is the area between the curve and the X-axis.


While computing this area is not trivial, we can approximate it with areas of $N-k+1$ rectangles as shown in the figure.

The basis of each rectangle has length $\frac{1}{N}$, while the height equals to the value of $f(t)$ in the left endpoint of the subinterval. When we sum them up, we obtain
$$
\frac{1}{N}\left[\frac{1}{\frac{k-1}{N}}+\frac{1}{\frac{k}{N}}+\dots+\frac{1}{\frac{N-1}{N}}\right],
$$
so exactly the sum in our expression. If we make the subintervals very small, we approximate the integral very well. In particular,
$$
\lim_{N \to \infty} \sum_{i=k}^N \frac{1}{N}\frac{N}{i-1}= \int_{x}^1 \frac{1}{t}dt,
$$
where $x$ denotes $\frac{k-1}{N}$. Putting it all together, we learn that for large $N$
$$
\mathbb{P}\left(\text{best candidate chosen}\right) \approx x\int_{x}^1 \frac{1}{t}dt=-x\ln(x),
$$
where $x$ corresponds to the proportion of first candidates we must reject.

### Problem 9
*Use the formula for the probability of choosing the best candidate to find the optimal cut-off point $k$ for any natural $N$. Type your answer (2 significant digits).*

**Hint**
<details >
<summary>
</summary>

*How could you use the derivatives of a function to find its extrema?*
</details>

**Answer**
<details >
<summary>
</summary>

Let's denote the probability of choosing the best candidate by
$$
P(x):=-x\ln(x).
$$
Then its first derivative equals
$$
\frac{dP(x)}{dx}=-\ln(x)-1.
$$
We can find the extremum of this function by equating its first derivative to zero:
$$
\frac{dP(x)}{dx}=0 \iff x=\frac{1}{e} \approx 0.37.
$$
Because $x$ refers to the proportion of candidates, which must be positive, we check that
$$
\frac{d^2P(x)}{dx^2}=-\frac{1}{x}<0,
$$
so indeed we found the maximum of $P(x)$.
</details>

Congratulations! You established that to maximise your chance of finding the best candidate, you have to reject the first $37\%$ and then accept the first candidate better than all you have seen so far, or the last one if it does not happen. Of course $37\%$ of $N$ will not always be a natural number and, since the result is approximate, it does not matter if we round it up or down --- for larger $N$ the resulting probabilities will not differ significantly.

### Problem 10
*Your best friend envies you for your dating successes, so you suggest that she tries a dating app. She is a bit tight on money, so she opts for the free version, which allows her to see only 50 potential partners. Another downside of skimping on premium membership is that one can either accept a candidate or move on and never be shown his profile again. How many guys should she definitely pass on to maximise her probability of finding her second half?*
- $18$ or $19$
- $33$ or $34$
- $37$ or $38$
- $12$ or $13$

**Answer**
<details >
<summary>
</summary>

$50$ is a pretty big sample size, so we know that $k-1 \approx 0.37\cdot 50=18.5$, which can be rounded to $18$ or $19$, depending on our preferred method. So your friend should reject $18$ or $19$ first candidates. To get the precise number you would have to use the explicit formula, but in practice the approximation works very well.
</details>

### Problem 11
*If your friend follows this optimal strategy, how likely is she to meet the very best guy? Type your answer (2 significant digits).*

**Answer**
<details >
<summary>
</summary>

To compute this probability, we can use the function $P(x)$: $P(0.37)\approx 0.37$.
</details>

Notice that if we follow the optimal strategy the probability of choosing the best candidate always equals about $37\%$, regardless of $N$. Yes, it is the same number as the proportion of people we should reject. Why does it happen?

## Job interviews revisited
Let's go back to Brilliant looking for course writers. Imagine you sent your CV, together with $19$ other applicants. You know that a team of maths educators will employ the optimal strategy to hire the candidate. How can you maximise the chances of landing your dream job if you could choose your position in the interview order? Assume that you do not know how your qualifications compare to the rest of applicants: you are equally likely to be the best or the worst of all $20$ candidates.

### Problem 12
*If you are the $5$th interviewee, what is the probability that you get the job? Type your answer (2 significant digits).*
**Answer**
<details >
<summary>
</summary>

The optimal $k-1$ is approximately $0.37 \cdot 20$, so about 7. Since you are interviewing before the cut-off point, unfortunately Brilliant will have to reject you, no matter how qualified you are.
</details>

### Problem 13
*How likely is your success if you are $16$th in the interview order?*
- $0.05$
- $0.1$
- $0.03$
- $0.001$
**Answer**
<details >
<summary>
</summary>

Two things must happen in order for you to be hired:
- You have to be the best among the first $16$ candidates. This happens with probability $\frac{1}{16}$.
- The best of the first $15$ candidates must interview before the cut-off point, i.e. among the first $7$ people; otherwise this person would be hired before you even get the chance to talk to Brilliant. This happens with probability $\frac{7}{15}$.

Thus you get the job with probability
$$
\frac{1}{16}\cdot \frac{7}{15} \approx 0.03.
$$
Note that you would be better off if Brilliant were not so brilliant and picked the candidate completely at random: then you would get the job with probability $\frac{1}{20}=0.05$.
</details>

### Problem 14
*What is the probability that Brilliant hire you if your interview is scheduled last?*
- $0.21$
- $0.52$
- $0.37$
- $0.07$

**Hint**
<details >
<summary>
</summary>

The last person gets hired in two separate cases.
</details>

**Answer**
<details >
<summary>
</summary>

You will get the job if one of the following occurs.
- You are indeed the best candidate and the second best applicant was interviewed among the first $7$ people (before the cut-off). Similarly to the scenario in the previous question, this happens with probability $\frac{1}{20}\cdot\frac{7}{19}$.
- The best candidate was unlucky enough to meet the hiring team before the cut-off point. This happens with probability $\frac{7}{20}$.

Thus your chance of succeeding is
$$
\frac{1}{20}\cdot\frac{7}{19}+\frac{7}{20} \approx 0.37.
$$
</details>

### Problem 15
*If you could influence the interview order, which position should you aim for to maximise your chances of success? Type your answer.*
**Hint**
<details >
<summary>
</summary>

Based on previous questions, develop a general formula for the probability of being hired as a function of the interview position.
**Answer**
<details >
<summary>
</summary>

Reasoning as in previous questions, we can compute the probability of the $i$th candidate being hired in the following cases:
- If $i \leq k-1$, the candidate must be rejected, so $\mathbb{P}\left(\text{success}\right)=0$.
- If $k \leq i \leq N-1$, the candidate is the best so far with probability $\frac{1}{i}$ and the second-best applicant was interviewed before the cut-off point with probability $\frac{k-1}{i-1}$. Thus in this case $\mathbb{P}\left(\text{success}\right)=\frac{1}{i}\frac{k-1}{i-1}$.
- If $i=N$, the candidate is the best and the second best candidate was interviewed among the first $k-1$ people with probability $\frac{1}{N}\frac{k-1}{N-1}$ (similarly to the previous case). Alternatively, this candidate is hired if the very best candidate was interviewed before the cut-off point, which happens with probability $\frac{k-1}{N}$. Therefore $\mathbb{P}\left(\text{success}\right)=\frac{k-1}{N(N-1)}+\frac{k-1}{N}=\frac{k-1}{N-1}$.

Summing up, for the $i$th candidate
$$
\mathbb{P}\left(\text{success}\right)=
\begin{cases}
0 & \text{if } i \leq k-1,\\
\frac{k-1}{i(i-1)} & \text{if } k \leq i \leq N-1,\\
\frac{k-1}{N-1} & \text{if } i=N.
\end{cases}
$$
A quick look at this function will persuade you that the last indeed shall be first!

</details>

## Additional reading
Here you can learn more about the secretary problem:
- [https://www.math.upenn.edu/~ted/210F10/References/Secretary.pdf](https://www.math.upenn.edu/~ted/210F10/References/Secretary.pdf)
- [https://algorithmstoliveby.com/}{https://algorithmstoliveby.com/](https://algorithmstoliveby.com/}{https://algorithmstoliveby.com/)
- [https://www.youtube.com/watch?v=ZWib5olGbQ0](https://www.youtube.com/watch?v=ZWib5olGbQ0)
- [https://www.americanscientist.org/article/knowing-when-to-stop](https://www.americanscientist.org/article/knowing-when-to-stop)
- [https://www.jstor.org/stable/10.4169/college.math.j.43.1.076](https://www.jstor.org/stable/10.4169/college.math.j.43.1.076) (inspired the section "Job interviews revisited")