Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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. –  André Nicolas Nov 5 '12 at 3:01
    
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; –  user1782677 Nov 5 '12 at 3:04
    
The secretary algorithm always hires one candidate; could you describe (in the body of your question) the precise algorithm that you are dealing with? –  Benjamin Dickman Nov 5 '12 at 3:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.