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}

  • $\begingroup$ $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. $\endgroup$ – Arthur Skirvin May 26 '14 at 21:34
  • 1
    $\begingroup$ 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\}$ $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – bryanblackbee May 27 '14 at 6:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.