3
$\begingroup$

The secretary problem:

We want to hire a secretary for a company. The candidates arrive one by one (randomly). The first candidate is always hired since there is no better candidate at the time. When the second candidate arrives, we compare him/her to the current secretary. If he/she is better, we fire the previous secretary and hire the new candidate. The third candidate is also compared with the current secretary and hired in place of him/her is he/she is better. This way, we interview $n$ candidates to find the best among all of them.


The question:

What is the probability that hiring occurs $k\le n$ times? (Meaning that we change the secretary $k-1$ times to finally find the best person)


My try:

I worked with the arrangement of the numbers $1,\dots,n$ and assumed that there is a function $f:\mathbb N\to\mathbb N$ which gives the rank of each candidate (meaning that $f(k)=1$ iff $k$-th candidate is the best one among all). So, the question is reduced to finding all of the arrangements of $f(1), f(2), \dots, f(n)$ in which $f(1)$ comes first. (For instance, $f(1), f(5), f(2), \dots, f(n) $ can be a possible arrangement which means candidate $1$ has the best quality, the $5$-th candidate is the second best and so on).

For $k=1$, among all combinations ($n!$), there is only $(n-1)!$ in which $f(1)$ comes first. (So, $P\{\mbox{Hiring only one person}\}=\frac{(n-1)!}{n!}=\frac{1}{n}$)

For $k=2$, since always the first candidate is hired, we should have $f(1)=2$ (meaning that the first candidate should be the second-best one). So, in the combination of $f(i)$'s, we should choose some number in $\{2,3,\dots,n\}$ to be the best one ($n-1$) and for arranging other numbers, we will have $(n-2)!$ cases. (Overall cases equalling $(n-1)!$ ). So, we will have $P\{\mbox{Hiring twice}\}=\frac{1}{n}$ again!

Unfortunately, with a similar argument, I get the same number ($\frac{1}{n}$) for all $k\le n$ which is obviously wrong! I do not know why this happens and how I should count the cases correctly.


Note: There are similar questions like this which uses random indicator variables and this one in which $k=n-1$. But I do not want to use random indicator variable. Instead, I wish to solve the problem by counting rules (e.g., counting the number of cases in which hiring occurs $k$ times, and dividing it by the size of sample space).

$\endgroup$
1
$\begingroup$

I think the flaw in your reasoning is here:

For $k=2$, since always the first candidate is hired, we should have $f(1)=2$ (meaning that the first candidate should be the second-best one).

For $k=2$, let us say that $f(x_0) = 1$, we only need that for all $i$ with $2 \leq i < x_0$ we have $f(i) < f(1)$. This means that the first person can be the 5th best candidate, as long as only worse candidates come after him/her till we reach the best candidate.

Given this, you then need to, for each possible position of the best candidate ($2 \leq x_0 \leq n$), find what are the values possible at the first position and then find, for each, the total number of possible permutations.

ADDENDUM

Let $r_i$ be the rank of the candidate at position $i$.

As assumed above, let $x$ be the position of the rank $1$ candidate ($r_x = 1, 2\leq x\leq n$). Let $r_1$ rank of the candidate at position $1$.

We now know that the ranks of all the candidates at position $i$ such that $1<i<x$ are higher than $r_1$ to allow for only two selections, since $r_1$ is always selected and the next selection can only be at $r_x$. There needs to be, for any given $r_1$, $x-2$ such numbers at least to fit the space between position $1$ and $x$. This restricts the possible $r_1$ to $2\leq r_1\leq n-x+2$.

Now, we just need to find the possible permutations. Given any $x$ and $r_1=y$, we have precisely these many permutations possible: $$(x-2)!(n-x)!$$

Hence, to calculate overall number we sum for all possible $x$ and $y$: $$\sum\limits_{x=2}^{n}\sum\limits_{y=2}^{n-x+2}(x-2)!(n-x)! = \sum\limits_{x=2}^{n}(n-x+1)!(x-2)!$$ This needs to be divided by $n!$ to get the probability.

PS: I am not sure if this is the correct equation. You can try comparing the result of this to the alternative solutions, and I will be happy to know the result and modify if necessary.

$\endgroup$
  • $\begingroup$ Thanks for pointing out the flaw in my reasoning. But you actually did not answer the original question. How should I consider each possible position of the best candidate and so on? $\endgroup$ – Arman Malekzadeh Feb 14 at 16:36
  • $\begingroup$ @ArmanMalekzadeh Added $\endgroup$ – Satwik Pasani Feb 14 at 19:12

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.