Probability of Hiring the Best Candidate on the ith Trial

[Mogarrr]

Homework Statement

An employer is about to hire one new employee from a group of N candidates, whose future potential can be rated on a scale from 1 to N. The employer proceeds according to the following rules:
(a) Each candidate is seen in succession (in random order) and a decision is made whether to hire the candidate.
(b) Having rejected m-1 candidates (m>1), the employer can hire the mth candidate only if the mth candidate is better than the previous m-1.

Suppose a candidate is hired on the ith trial. What is the probability that the best candidate was hired.

Homework Equations

I have the solution, however I'm not entirely convinced that it's correct.

This is most easily seen by doing each possibility. Let P(i) = probability that the candidate is hired on the ith trial is best. then

P(1)=\frac 1N, P(2)=\frac 1{N-1}, ... , P(i)=\frac 1{N-i+1}, ... , P(N)=1.

The Attempt at a Solution

As a counterexample, suppose that there are 5 candidates, with an ordering of 'future potential' (a bit redundant eh) corresponding to an arbitrary number assignment, i.e. candidate number one has a future potential of one and so forth.

Now Suppose that a candidate is hired on the 2nd trial. We're assuming that each outcome is equally likely, as per (a). Thus we can use the standard method, P(E)= \frac {number of outcomes favorable to event E}{total number of possible outcomes}.

Here are the possibilities enumerated as ordered pairs: (1,2), (1,3), (2,3), (1,4), (2,4), (3,4), (1,5), (2,5), (3,5) and (4,5). Note that ordered pairs like (3,2) are not considered, as they would violate (b).

Now the number of total possible outcomes is 10, and the number favorable to the best candidate is 4. However, \frac 4{10} \neq \frac 14.

Am I right here? Please help.

 

[mfb]

What does "a candidate is hired on the 2nd trial" mean? The second invited candidate is hired if he is better than the first? What happens if he is not?

The best strategy to maximize the probability to hire the best candidate is to have a look at x candidates, then take the first one better than those x. If this is your goal, here is a hint: x is some fixed fraction of N.
This is not the best strategy for a realistic company, as taking the second-best is still better than taking no one.

 

[Ray Vickson]

Homework Statement

An employer is about to hire one new employee from a group of N candidates, whose future potential can be rated on a scale from 1 to N. The employer proceeds according to the following rules:
(a) Each candidate is seen in succession (in random order) and a decision is made whether to hire the candidate.
(b) Having rejected m-1 candidates (m>1), the employer can hire the mth candidate only if the mth candidate is better than the previous m-1.

Suppose a candidate is hired on the ith trial. What is the probability that the best candidate was hired.

Homework Equations

I have the solution, however I'm not entirely convinced that it's correct.

This is most easily seen by doing each possibility. Let P(i) = probability that the candidate is hired on the ith trial is best. then

P(1)=\frac 1N, P(2)=\frac 1{N-1}, ... , P(i)=\frac 1{N-i+1}, ... , P(N)=1.

The Attempt at a Solution

As a counterexample, suppose that there are 5 candidates, with an ordering of 'future potential' (a bit redundant eh) corresponding to an arbitrary number assignment, i.e. candidate number one has a future potential of one and so forth.

Now Suppose that a candidate is hired on the 2nd trial. We're assuming that each outcome is equally likely, as per (a). Thus we can use the standard method, P(E)= \frac {number of outcomes favorable to event E}{total number of possible outcomes}.

Here are the possibilities enumerated as ordered pairs: (1,2), (1,3), (2,3), (1,4), (2,4), (3,4), (1,5), (2,5), (3,5) and (4,5). Note that ordered pairs like (3,2) are not considered, as they would violate (b).

Now the number of total possible outcomes is 10, and the number favorable to the best candidate is 4. However, \frac 4{10} \neq \frac 14.

Am I right here? Please help.

There is something wrong with the problem description. If each candidate has a different rating (and all ratings are integers between 1 and N inclusive) then for sure, one of the candidates must have rating N, and so the employer just has to wait until that very best candidate is interviewed, then hire him/her. The best candidate will thus be hired with probability = 1. If the candidate ratings are not all different (but are still integers between 1 and N inclusive) then it is possible that nobody at all is hired. For example, it is possible that the first interviewee is the best of all N (although it has a rating < N). If that interviewee is rejected, then no others can be hired because none of them is better than the first one (and you say that a candidate can be hired only if it is better than all the previous ones interviewed).

 

[Mogarrr]

There is something wrong with the problem description.

I agree.

I found the problem in Statistical Inference Second Edition, which, unfortunately for me, will be the text used in my statistics class this fall.

 

[OlgaBorovikova]

I agree.

I found the problem in Statistical Inference Second Edition, which, unfortunately for me, will be the text used in my statistics class this fall.

Were you able to solve this problem?

 

[haruspex]

I don't see much of a problem with the description. It nowhere says a hiring will occur. The wording could be clearer in one respect. P(i) is the probability that the ith candidate is the best, given that the ith candidate is hired.
Wrt the attempted solution, please explain the ordered pair notation.

 

[Mogarrr]

I don't see much of a problem with the description. It nowhere says a hiring will occur. The wording could be clearer in one respect. P(i) is the probability that the ith candidate is the best, given that the ith candidate is hired.
Wrt the attempted solution, please explain the ordered pair notation.

Under the assumption that candidates have distinct 'future potential' rankings, I was looking specifically at the 2nd interview. I looked at outcomes as ordered pairs, (a,b), where a is the rank of the 1st candidate interviewed and b is the rank of the second candidate interviewed. I thought of rankings as the integers 1-5, with 1 being the lowest ranking and 5 being the best ranking.

Thus there are 5x5 - 5 possible ordered pairs as (a,a) cannot happen. The ordered pairs (1,2), (1,3) ... (4,5) are all outcomes where the 2nd candidate may be hired. I counted 4+3+2+1=10 outcomes. The pairs (1,5), (2,5), (3,5) and (4,5) are all outcomes where the best candidate is the 2nd being interviewed, and by rule (b) the best candidate may be hired.

Thus, the probability that the best candidate is hired on the 2nd trial is \frac 4{10} = \frac 25 \neq \frac 1{5-1}

So I'm still not so sure about the answer to this problem.

 

[Ray Vickson]

I don't see much of a problem with the description. It nowhere says a hiring will occur. The wording could be clearer in one respect. P(i) is the probability that the ith candidate is the best, given that the ith candidate is hired.
Wrt the attempted solution, please explain the ordered pair notation.

Part of the problem is that there is no mechanism for specifying when hiring will occur---only when it will not. So, if the employer is entitled to hire the third interviewee (because that person ranks higher than the first two), what governs whether or not that person gets hired? The way the problem is written, it seems optional on the part of the employer. If so, there is some other (random?) mechanism at work besides the random ordering of the candidate ranks, and surely the final hiring probability rank must be influenced by that mechanism.

 

[haruspex]

Part of the problem is that there is no mechanism for specifying when hiring will occur---only when it will not. So, if the employer is entitled to hire the third interviewee (because that person ranks higher than the first two), what governs whether or not that person gets hired? The way the problem is written, it seems optional on the part of the employer. If so, there is some other (random?) mechanism at work besides the random ordering of the candidate ranks, and surely the final hiring probability rank must be influenced by that mechanism.

No, that's not a problem either. The employer's strategy is irrelevant. The question is if the ith candidate is hired, what is the probability that she is the best? We know she must be the best of the first i, so it remains to ask what the probability is that the best of the N is in the first i.

There is one huge problem, though: the given answer is wrong, as Mogarrr has discovered.