# Secretary Problem - What is the solution for $n=3,4,5$?

I have been reading this page for a few days and still cannot understand the solution to the Secretary Problem. In particular, I cannot understand parts 2 and 4

It goes like this. Given the assumptions of the Secretary Problem, let $n$ be the number of candidates and let the "let $k$ go by" strategy be as follows:

We let $k-1$ candidates go by, and then select the first candidate who is better than all previous candidates. If the candidate exists, select her. Else, select the last candidate. $k$ can take the value of $\{ 1, 2, ... n\}$.

Given this strategy, we compute the probability of success $p_n(k)$, using "let $k$ go by" with $n$ candidates. Here is where my question comes in:

When $n=3$, we permuate $\{x_1,x_2,x_3\}$ (the smaller the number, the better the candidate) I understand why $p_3(1)=\frac 26$ and $p_3(3)=\frac 26$ because of the $6$ permutations, $x_1$ could come into the interview first in $2$ permutations. Similarly, $x_1$ could come into the interview last in $2$ permutations. However, why is it that $p_3(2)=\frac 36$? In fact, there is another confusing point. Formally, my questions are:

Is it true that by counting the permutations, we find out the numerator of $p_i(k)$ for $i=1, \cdots, n$? If so, then why is it that $\sum_i^n p_i(k) \neq 1$?

Also, how did the author arrive at the $\frac 36$ for $p_2(k)$?

This question, of course extends to the case where $n=4$ and $n=5$. Maybe consider $n=4$ and $n=5$ and someone could derive the expressions for $p_i(k)$:

$n=4$ \begin{matrix} k & 1 & 2 & 3 & 4 \\ p_4(k) & \frac {6}{24} & \frac {11}{24} & \frac {10}{24} & \frac {6}{24} \end{matrix}

$n=5$ \begin{matrix} k & 1 & 2 & 3 & 4 & 5\\ p_5(k) & \frac {24}{120} & \frac {50}{120} & \frac {52}{120} & \frac {42}{120} & \frac {24}{120} \end{matrix}

• $p_3(2)=\frac36$ because we'll pick $x_1$ if they come second, which can happen two ways, or we'll pick $x_1$ if all preceding candidates come in descending order of fitness for the position, which for three candidates can happen one way, $x_2,x_3,x_1$. So that's a total of 3 out of the 6 possible orderings of three candidates for which we'll make the optimal choice. – Arthur Skirvin May 26 '14 at 21:34
• I think I did a poor job of wording that. Let me try again. We'll pick $x_1$ if they come in position $k$ or later and all preceding candidates between position $k$ and the position of $x_1$ are both less fit than all candidates before position $k$ and less fit than their immediate predecessor. For the case with three candidates, this happens with orderings $\{x_3,x_1,x_2\},\{x_2,x_3,x_1\},\{x_2,x_1,x_3\}$ – Arthur Skirvin May 26 '14 at 21:49

It is indeed possible to find the numerator in $p_i(k)$ by counting the permutations, as outlined below. These don't sum to $1$ for $\sum_{k=1}^n p_i(k)$ because by changing the value of $k$ you are actually modifying your strategy, and there's no reason that the probabilities of success across different strategies should sum to $1$.

It's easiest to see why the author concluded that $p_3(2)=\frac36$ by looking at the possible orderings the three candidates could have taken: $$\begin{matrix} \text{Candidate order} & \text{Chosen candidate for k=2}\\ x_1,x_2,x_3 & x_3 \\ x_1,x_3,x_2 & x_2 \\ x_2,x_1,x_3 & x_1 \\ x_2,x_3,x_1 & x_1 \\ x_3,x_1,x_2 & x_1 \\ x_3,x_2,x_1 & x_2 \end{matrix}$$

Now it's plain to see that 3 of the 6 possible candidate orders resulted in the optimal choice of $x_1$. I know inspecting all cases might seem like a dissatisfying sort of an answer, so now I'll derive the general formula for $p_n(k)$, which will hopefully provide a little more insight.

From here on I'm going to refer to the candidates using numbers (so that $1$ represents the best candidate) since it's easier to get my head around ordering the numbers $1,...,n$ than ordering candidates $x_1,...,x_n$.

We observe that if candidate $2$ was in the first $k-1$ but candidate $1$ wasn't, then we'd be guaranteed to pick candidate $1$. So any ordering that has $2$ in the first $k-1$ positions but not $1$ will result in the optimal choice. The number of ways that candidate $2$ can be in the first $k-1$ without candidate $1$ being there is ${n-2\choose k-2}(k-1)!$. This is obtained by first choosing which $k-2$ candidates will be in the first $k-1$ with candidate $2$, then picking an order for them all to be in. After appropriately choosing and ordering the first $k-1$, we need to order the remaining $n-k+1$, which naturally is done by $(n-k+1)!$. Thus the total number of ways for candidate $2$ to be among the first $k-1$ candidates, but not candidate $1$ is

$$(k-1)!{n-2\choose k-2}(n-k+1)!$$

Again, all of these orderings result in the optimal choice.

Now we observe that if neither $1$ nor $2$ were in the first $k-1$ but $3$ was, we'd only make the optimal choice if $1$ came before $2$ in the next $n-k+1$ numbers. The number of ways for $3$ to be in the first $k-1$ but not $1$ or $2$ is $(k-1)!{n-3\choose k-2}$, while the number of ways for $1$ to come before $2$ in the next $n-k+1$ numbers is $(n-k+1)!\over2$, giving us $$(k-1)!{n-3\choose k-2}(n-k+1)!\over2$$ such orderings. And, as you might expect, the number of ways for $4$ to be in the first $k-1$ candidates, but not $1,2$, or $3$ and for $1$ to come before $2$ and $3$ in the next $n-k+1$ is

$$(k-1)!{n-4\choose k-2}(n-k+1)!\over 3$$

What we're doing is considering cases in which the best candidate in the first $k-1$ is $t$ and finding the number of orderings for each case that result in the optimal choice. If we do this for all candidates $t$, then we'll have considered every possible case and will then have the total number of orderings that result in the optimal choice.

Thus you end up with a general formula for $p_n(k)$:

$$p_n(k)=\cases{\frac{(n-1)!}{n!} &for k=1\\\ \frac1{n!}\sum_{j=1}^{n-1}(k-1)!{{n-j-1\choose k-2}(n-k+1)!\over j}&for k>1}$$

For $p_4(k)$ we get $$\begin{matrix} k & 1 & 2 & 3 & 4 \\ p_4(k) & \frac {6}{24} & \frac {11}{24} & \frac {10}{24} & \frac {6}{24} \end{matrix}$$

And for $p_5(k)$ we get $$\begin{matrix} k & 1 & 2 & 3 & 4 & 5\\ p_5(k) & \frac {24}{120} & \frac {50}{120} & \frac {52}{120} & \frac {42}{120} & \frac {24}{120} \end{matrix}$$

both of which match the known solutions written in your question above.

• This is honestly simple and clear. Now I can finally move on to prove the remaining of the problem. Thank you! You have indeed enlightened me. – bryanblackbee May 27 '14 at 6:23