# Secretary Problem: The probability of hiring exactly $k$ times

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).

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.

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 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.

• 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? – Arman Malekzadeh Feb 14 at 16:36