# Thread: Explain the math behind the secretary problem?

1. ## Explain the math behind the secretary problem?

It's been a while since I took calculus. Could someone please elaborate on the steps leading to the optimal solution of the secretary problem
Secretary problem - Wikipedia, the free encyclopedia

In particular under "Deriving the Optimal Policy" it says P(r)=

n
∑ (1/n) * (r-1 / j-1)
j=r

How was this derived? (This is more of a question on probabilities)

This becomes
(r-1 / n) * ∑ (1 / j-1)
from j=r to n

And then P(r) =
x * ∫ (1/t) * dt
integrating t over x and 1.

How do you make these substitutions, and why is it between x and 1, is that the range of probability? (I need to understand where it says "using t for j / n and dt for 1 / n")

Thanks!

2. Originally Posted by anony
It's been a while since I took calculus. Could someone please elaborate on the steps leading to the optimal solution of the secretary problem
Secretary problem - Wikipedia, the free encyclopedia

In particular under "Deriving the Optimal Policy" it says P(r)=

n
∑ (1/n) * (r-1 / j-1)
j=r

How was this derived? (This is more of a question on probabilities)
The probability of any single event can be expressed as the multiple of each probability for all necessary conditions required for that event. For example, if you want to roll snake eyes, the probability of doing so is found by multiplying the probability of the two required conditions: rolling a one for the first die (P=1/6) and rolling a one for the second die (P=1/6). This multiple is (1/6)(1/6)=1/36. So, the probability of rolling snake eyes is 1/36.

The same sort of thing goes on here. But remember that this is a series, and so we're not looking for the total probability, but only the probability for each trial.

Let's say that r is the stopping number. In other words, you only start considering secretaries after you've interviewed at least r-1 secretaries. Let's also say that j-1 is the number of secretaries you've considered so far. That makes each secretary you interview the jth secretary.

Now that we've assigned the variables, let's ask ourselves, what is the probability that the secretary I'm interviewing--the jth secretary--is the most qualified? Well, there's only one best out of the n secretaries, so the probability of some random secretary being the best is:

$\frac{1}{n}$

That's our first condition. The other condition which must be satisfied is the probability of even considering this jth secretary. Remember, we're going to stop once we get to the best after r-1 secretaries. For us to have moved on to the jth secretary means that so far, the best secretary was one of those first r-1 secretaries, otherwise we wouldn't be considering the jth secretary. And the probability that the best so far was one of the first r-1 is:

$\frac{r-1}{j-1}$

So, since these are the only two conditions which need be met, we know that the probability of the jth secretary being the best is:

$\frac{r-1}{n(j-1)}$

Next we add up the probabilities for each trial. This is done by converting to a series:

$\sum_{j=r}^n\frac{r-1}{n(j-1)}$

I know I didn't explain that last step very well. Quite frankly, I'm not sure how to put it into words. Maybe Mr. Fantastic can help out with an explanation. Hopefully you can just see how it works, though.

This becomes
(r-1 / n) * ∑ (1 / j-1)
from j=r to n
This can be done because r and n are both constants, and we can pull out constants. j is a variable, however, so we must keep any term which includes a j inside the sigma summation.

And then P(r) =
x * ∫ (1/t) * dt
integrating t over x and 1.
I have no clue about that one. Mr. Fantastic?

3. Originally Posted by anony
It's been a while since I took calculus. Could someone please elaborate on the steps leading to the optimal solution of the secretary problem
Secretary problem - Wikipedia, the free encyclopedia

In particular under "Deriving the Optimal Policy" it says P(r)=

n
∑ (1/n) * (r-1 / j-1)
j=r

How was this derived? (This is more of a question on probabilities)
[snip]
Call B the best secretary of all the applicants.

The strategy is to reject the first r-1 applicants and then choose the first applicant better than the best rejected applicant.

First note that if B is among the first r-1 candidates then you're stuck with having to choose the nth applicant (why?) and it's all over.

If B is among the remaining n - r + 1 choices then obviously there's a chance of choosing B and that chance will depend on where B is among the remaining choices. To calculate the probability of choosing B, each possibility needs to be considered:

B is in the (r)th position: B is certain to be chosen. The probability that B is in the (r)th position is 1/n. Therefore the probability of success is 1/n.

B is in the (r+1)th position: If the applicant in the (r)th position is the best yet then this aplicant will get chosen and so B will not be chosen. Otherwise B is certain to be chosen. This means that B will get chosen if the best yet among the first r choices lies among the first r-1. The probability of this is (r-1)/(r). But B is needed in the (r+1)th position and the probability of this is 1/n. Therefore the probability of success is (r-1)/(r) 1/n.

B is in the (r+2)th position: If the applicant in the (r+1)th position is the best yet then this aplicant will get chosen and so B will not be chosen. Otherwise B is certain to be chosen. This means that B will get chosen if the best yet among the first r+1 choices lies among the first r-1. The probability of this is (r-1)/(r+1). But B is needed in the (r+2)th position and the probability of this is 1/n. Therefore the probability of success is (r-1)/(r+1) 1/n.

etc. etc.

B is in the (n)th position: If the applicant in the (n-1)th position is the best yet then this aplicant will get chosen and so B will not be chosen. Otherwise B is certain to be chosen. This means that B will get chosen if the best yet among the first n-1 choices lies among the first r-1. The probability of this is (r-1)/(n-1). But B is needed in the (n)th position and the probability of this is 1/n. Therefore the probability of success is (r-1)/(n-1) 1/n.

The total probability of success (choosing B) is got by adding all these probabilities up, which is the result you're given.

I'll continue later unless someone else does first.

4. Originally Posted by anony
[snip]
(r-1 / n) * ∑ (1 / j-1)
from j=r to n

And then P(r) =
x * ∫ (1/t) * dt
integrating t over x and 1.

How do you make these substitutions, and why is it between x and 1, is that the range of probability? (I need to understand where it says "using t for j / n and dt for 1 / n")

Thanks!
You have $\Pr(r) = \frac{r-1}{n} \sum_{j=r}^{n} \frac{1}{j-1} = \frac{r-1}{n} \left( \frac{1}{r-1} + \frac{1}{r} + \frac{1}{r+1} + .... + \frac{1}{n-1}\right)$.

If you draw a graph of $y = \frac{1}{u}$ and draw upper and lower rectangles over the appropriate partition it should be clear that

$\frac{1}{r} + \frac{1}{r+1} + \frac{1}{r+2} + .... + \frac{1}{n-1} < \int_{r-1}^{n} \frac{1}{u} \, du < \frac{1}{r-1} + \frac{1}{r} + \frac{1}{r+1} + .... + \frac{1}{n-1}$

$\Rightarrow \frac{r-1}{n} \left( \frac{1}{r} + \frac{1}{r+1} + \frac{1}{r+2} + .... + \frac{1}{n-1} \right) < \frac{r-1}{n} \int_{r-1}^{n} \frac{1}{u} \, du$

$< \frac{r-1}{n} \left( \frac{1}{r-1} + \frac{1}{r} + \frac{1}{r+1} + .... + \frac{1}{n-1} \right)$

Substitute $t = \frac{u}{n}$:

$\Rightarrow \frac{r-1}{n} \left( \frac{1}{r} + \frac{1}{r+1} + \frac{1}{r+2} + .... + \frac{1}{n-1} \right) < \frac{r-1}{n} \int_{\frac{r-1}{n}}^{1} \frac{1}{t} \, dt$

$< \frac{r-1}{n} \left( \frac{1}{r-1} + \frac{1}{r} + \frac{1}{r+1} + .... + \frac{1}{n-1} \right)$.

Therefore, for large n and therefore large enough r: $\Pr(r) \approx x \int_{x}^{1} \frac{1}{t} \, dt$.

where the substitution $x = \frac{r-1}{n}$ is made.

Note that r-1 is the number of applicants initially rejected under the strategy and n is the total number of applicants. x therefore gives the proportion of applicants intially rejected.

All that's left is to find the value of x that maximises Pr(r) in this limit of large n ......

5. Originally Posted by mr fantastic
You have $\Pr(r) = \frac{r-1}{n} \sum_{j=r}^{n} \frac{1}{j-1} = \frac{r-1}{n} \left( \frac{1}{r-1} + \frac{1}{r} + \frac{1}{r+1} + .... + \frac{1}{n-1}\right)$.

If you draw a graph of $y = \frac{1}{u}$ and draw upper and lower rectangles over the appropriate partition it should be clear that

$\frac{1}{r} + \frac{1}{r+1} + \frac{1}{r+2} + .... + \frac{1}{n-1} < \int_{r-1}^{n} \frac{1}{u} \, du < \frac{1}{r-1} + \frac{1}{r} + \frac{1}{r+1} + .... + \frac{1}{n-1}$

$\Rightarrow \frac{r-1}{n} \left( \frac{1}{r} + \frac{1}{r+1} + \frac{1}{r+2} + .... + \frac{1}{n-1} \right) < \frac{r-1}{n} \int_{r-1}^{n} \frac{1}{u} \, du$

$< \frac{r-1}{n} \left( \frac{1}{r-1} + \frac{1}{r} + \frac{1}{r+1} + .... + \frac{1}{n-1} \right)$

Substitute $t = \frac{u}{n}$:

$\Rightarrow \frac{r-1}{n} \left( \frac{1}{r} + \frac{1}{r+1} + \frac{1}{r+2} + .... + \frac{1}{n-1} \right) < \frac{r-1}{n} \int_{\frac{r-1}{n}}^{1} \frac{1}{t} \, dt$

$< \frac{r-1}{n} \left( \frac{1}{r-1} + \frac{1}{r} + \frac{1}{r+1} + .... + \frac{1}{n-1} \right)$.

Therefore, for large n and therefore large enough r: $\Pr(r) \approx x \int_{x}^{1} \frac{1}{t} \, dt$.

where the substitution $x = \frac{r-1}{n}$ is made.

Note that r-1 is the number of applicants initially rejected under the strategy and n is the total number of applicants. x therefore gives the proportion of applicants intially rejected.

All that's left is to find the value of x that maximises Pr(r) in this limit of large n ......
But I prefer the following analysis for large n and r:

$\Pr(r) = \frac{r-1}{n} \left[ H_{n-1} - H_{r-2}\right]$

where $H_k = \sum_{i=1}^k \frac{1}{i}$ is a harmonic number

$\approx \frac{r-1}{n} \left[ (\ln (n-1) + \gamma ) - (\ln (r-2) + \gamma ) \right]$

$= \frac{r-1}{n} \left[ \ln (n-1) - \ln (r-2) \right]$

$= \frac{r-1}{n} \, \ln \left( \frac{n-1}{r-2} \right)$.