Question

Exercise 14. Let bi,..., bn be distinct numbers, representing the quality of n people. Sup pose n people arrive to interview for a job, one at a time, in a random order. That is, every possible arrival order of these people is equally likely. We can think of an arrival ordering of the people as an ordered list of the form ai, . . . , an, where the list ai, . . . , an is a permutation of the numbers bi,..., bn Moreover, we interpret a as the rank of the first person to arrive, 02 as the rank of the second person to arrive, and so on. And all possible permutations of the numbers bi,... , bn are equally likely to occur. For each i E {1, ,n), upon interviewing the ith person, if ai > aj for all 1 j 〈 i, then the ith person is hired. That is, if the person currently being interviewed is better than the previous candidates, she w be hired. What is the expected number of hirings that will made? (Hint: let X Consider x, 1 if theih person to arrive is hired, and let X, otherwise.

Answer 1