Job candidates C1, C2,... are interviewed one by one, and the interviewer compares them

Chapter 4, Problem 53

(choose chapter or problem)

Job candidates C1, C2,... are interviewed one by one, and the interviewer compares them and keeps an updated list of rankings (if n candidates have been interviewed so far, this is a list of the n candidates, from best to worst). Assume that there is no limit on the number of candidates available, that for any n the candidates C1, C2,...,Cn are equally likely to arrive in any order, and that there are no ties in the rankings given by the interview. Let X be the index of the first candidate to come along who ranks as better than the very first candidate C1 (so CX is better than C1, but the candidates after 1 but prior to X (if any) are worse than C1. For example, if C2 and C3 are worse than C1 but C4 is better than C1, then X = 4. All 4! orderings of the first 4 candidates are equally likely, so it could have happened that the first candidate was the best out of the first 4 candidates, in which case X > 4. What is E(X) (which is a measure of how long, on average, the interviewer needs to wait to find someone better than the very first candidate)? Hint: Find P(X>n) by interpreting what X>n says about how C1 compares with other candidates, and then apply the result of Theorem 4.4.8.