# Combinatorics: interview strategy problem (secretary problem)

This is a probability problem.

Suppose we have n applicants for a job with the following interviewing process:

• after interview an applicant is rejected or accepted
• if accepted, process is over
• if no applicant was selected in the first n-1 interviews, the n-th one is chosen by default.

The problem is to answer some questions about the following hiring strategy:

• Reject the first r-1
• Accept the first one after r-1 with ranking better than the first r-1

Note that there is an absolute rank of all n applicants so there is a best applicant i.e. one with the best rank, but is unknown. We only know the relative ranks of the interviewed applicants.

We define $$P_n(r)$$ as the probability of accepting the absolute best ranked using the above strategy.

For example $$P_4(2)$$ if I am not wrong is 11/24. If we look at all the permutations of the absolute rank of all the applicants (4!).

1*** (6) best applicant is already rejected here

2*** (6) best applicant will definitely be taken here because nobody is better than the second best than the first best

31** (2) yes

32** (2) no

3412 (1) yes

3421 (1) no

41** (2) yes

42** (2) no

43** (2) no

In total 11/24.

First I have to show that $$P_{10}(3) = \frac{2}{10} (\frac{1}{2} + \frac{1}{3} + ... + \frac{1}{9} )$$, derive the probability of accepting the applicant with the absolute rank 1 among n applicants at the k-th interview then find a recursive formula of $$P_n(r)$$ in the form $$P_n(r)=A+BP_n(r+1)$$.

I have done some research on the problem and it seems it has a classical name "Secretary Problem".

$$P_n(r) = \sum_{k=0}^{n}P(applicant\ k\ is\ selected\ \cap applicant\ k\ is\ the\ best)$$ $$= \sum_{k=0}^{n}P(applicant\ k\ is\ selected\ |\ applicant\ k\ is\ the\ best)P(applicant\ k\ is\ the\ best)$$ $$= \sum_{k=r}^{n}P(best\ applicant\ is\ selected\ in\ the\ k^{th}\ interview )\frac{1}{n}$$ $$=\sum_{r}^{n}\frac{r-1}{i-1} \frac{1}{n}$$ This seems to answer my question for $$P_{10}(3)$$ and the recursive formula can also be derived from the explicit one.