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.


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.