Solution: For n greater than or equal to 2, P(X > n) is the probability that none of C2, C3,..., Cn are better candidates than C1, i.e., the probability that the first candidate is the highest ranked out of the first n. Since any ordering of the first n candidates is equally likely, each of the first n is equally likely to be the highest ranked of the first n, so P(X > n) = 1/n. For n = 0 or n = 1, P(X > n) = 1 (note that it does not make sense to say the probability is 1/n when n = 0). Applying the result of the previous problem, E(X) = infinity. The series is the harmonic series, which diverges. How can the average waiting time to find someone better than the first candidate be infinite? In the real world, there are always only finitely many candidates so the expected waiting time is finite, just as in the St. Petersburg paradox there must in reality be an upper bound on the number of rounds. The harmonic series diverges very slowly, so even with millions of job candidates the average waiting time would not be very large.

Copyright © 2011 Stat 110 Harvard.
Website layout by former Stat110'er.