1
$\begingroup$

So I have to figure out that in the case of the secretary problem(http://en.wikipedia.org/wiki/Secretary_problem) what is the probability that I hire exactly one applicant over the course of going through the whole algorithm, given that the applicants come in random order.

According to the algorithm, you automatically hire whoever is the current best. So if you wind up only hiring 1 person, then that means that the first person you interviewed had to be the very best out of all n choices.

So, is it fair to rethink of this question as "what is the probability that the best candidate is the first one you interview?" In which case, would the answer be (n-1)!/n! because there are n! total permutations but if you assume the best candidate is in slot 1, you can permute the other (n-1) as many ways as you want.

This sort of makes sense to me but it seems wrong at the same time and I can't quite pinpoint why.

  • 2
    Under the usual assumptions the best is equally likely to be in any of the positions, so the probability it is the first is $1/n$. But the classical solution of the secretary problem has us automatically reject roughly the first $n/e$ applicants. So the $1/n$ is not particularly relevant to the standard secretary problem.2012-11-05
  • 0
    I'm not familiar with the "standard" form of the algorithm, however the form I am using looks like this: 1 randomly permute the list of candidates; 2 best == 0; 3 for i D 1 to n; 4 interview candidate i; 5 if candidate i is better than candidate best; 6 best D i; 7 hire candidate i;2012-11-05
  • 0
    The secretary algorithm always hires one candidate; could you describe (in the body of your question) the precise algorithm that you are dealing with?2012-11-05

0 Answers 0