I found this equation on wikipedia to resolve the secretary problem. I understand it but I have a small problem.
Theoretically, if I would not want to reject any applicant, I should use $r = 0$ (edit : $r = 1$, because we reject the $r – 1$ applicants) and I would select the first applicant (because it is the best among the ones we didn't see in the rejection list) .
In this case, the probability that I choose the best applicant should be $\frac1 n$ (with $n$ the number of applicants). But in reality, the equation doesn't allow one to pick $r = 1$ because of the sum.
Is there a more generic equation to take in account this value of the number of reject applicants ?
Best Answer
Although there are many variations, the basic problem can be stated as follows:
There is a single position to fill. There are $n$ applicants for the position, and the value of $n$ is known.
The applicants, if seen altogether, can be ranked from best to worst unambiguously.
The applicants are interviewed sequentially in random order, with each order being equally likely.
Immediately after an interview, the interviewed applicant is either accepted or rejected, and the decision is irrevocable. The decision to accept or reject an applicant can be based only on the relative ranks of the applicants interviewed so far.
The objective of the general solution is to have the highest probability of selecting the best applicant of the whole group. This is the same as maximizing the expected payoff, with payoff defined to be one for the best applicant and zero otherwise.
Read the section on "deriving the optimal policy"and be sure to understand that $r$ is a random cutoff. We determine it based on best-practise and then we can just 'roll with it'
I quote:
The optimal policy for the problem is a stopping rule. Under it, the interviewer rejects the first $r − 1$ applicants (let applicant $M$ be the best applicant among these $r − 1$ applicants), and then selects the first subsequent applicant that is better than applicant $M$. It can be shown that the optimal strategy lies in this class of strategies.For an arbitrary cutoff $r$, the probability that the best applicant is selected gives rise to your formula.