A sequence of n job candidates is prepared to interview for a job. We would like to hire the best candidate, but we have no information to distinguish the candidates before we interview them. We assume that the best candidate is equally likely to be each of the n candidates in the sequence before the interviews start. After the interviews start, we are able to rank those candidates we have seen, but we have no information about where the remaining candidates rank relative to those we have seen. After each interview, it is required that either we hire the current candidate immediately and stop the interviews, or we must let the current candidate go and we never can call them back. We choose to interview as follows: We select a number 0 ≤ r < n and we interview the first r candidates without any intention of hiring them. Starting with the next candidate r + 1, we continue interviewing until the current candidate is the best we have seen so far. We then stop and hire the current candidate. If none of the candidates from r + 1 to n is the best, we just hire candidate n. We would like to compute the probability that we hire the best candidate and we would like to choose r to make this probability as large as possible. Let A be the event that we hire the best candidate, and let Bi be the event that the best candidate is in position i in the sequence of interviews.
a. Let i >r. Find the probability that the candidate who is relatively the best among the first i interviewed appears in the first r interviews.
b. Prove that Pr(A|Bi) = 0 for i ≤ r and Pr(A|Bi) = r/(i − 1) for i > r.
c. For fixed r, let pr be the probability of A using that value of r. Prove that pr
d. Let qr = pr − pr−1 for r = 1, . . . , n − 1, and prove that qr is a strictly decreasing function of r.
e. Show that a value of r that maximizes pr is the last r such that qr > 0. (Write pr = p0 + q1 + . . . + qr for r > 0.)
f. For n = 10, find the value of r that maximizes pr, and find the corresponding pr value.