1
$\begingroup$

Secretary problem's equation

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 ?

$\endgroup$
6
  • 1
    $\begingroup$ If you read the text accompanying the formula you copied from the Wikipedia article, you will find that $r$ is not the number of rejected applicants: "the interviewer rejects the first $r-1$ applicants". $\endgroup$
    – bof
    Nov 11, 2018 at 0:39
  • 1
    $\begingroup$ "The sum is not defined for $r = 1$, but in this case the only feasible policy is to select the first applicant, and hence $P(1) = 1/n.$" $\endgroup$
    – user459879
    Nov 11, 2018 at 0:42
  • $\begingroup$ We don't choose from the best ones in the rejection list, they have a given rank from the start. $\endgroup$
    – user459879
    Nov 11, 2018 at 0:54
  • $\begingroup$ You cannot reject the first $-1$ applicants. If you don't want to reject anyone, you simply let $r=1$, such that $r-1=0$. $\endgroup$
    – user459879
    Nov 11, 2018 at 0:56
  • 1
    $\begingroup$ No you can't because $r = 1$ implies that we divide $1/(i - 1)$ with $i = r$. So $r$ have to be greater or equal than $2$ $\endgroup$
    – Milow
    Nov 11, 2018 at 11:56

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

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.