In \(\textsc{Hire-Assistant}\), assuming that the candidates are presented in a random order, what is the probability that you hire exactly one time? What is the probability that you hire exactly \(n\) times?
To understand this problem, we need to think about when we hire candidates in the \(\textsc{Hire-Assistant}\) procedure. We hire a new candidate whenever they are better than all previously interviewed candidates.
Hiring Exactly Once
We hire exactly once when the very first candidate is the best of all \(n\) candidates. Think of it this way: if the best candidate shows up first, we hire them, and then every subsequent candidate will be worse, so we never hire again.
Since the candidates arrive in a random order, each of the \(n\) candidates has an equal probability of being in the first position. The probability that the best candidate is first is simply:
\[\Pr\{\text{hire exactly once}\} = \frac{1}{n}\]Hiring Exactly \(n\) Times
We hire exactly \(n\) times when every candidate we interview is better than all the ones before them. This only happens when the candidates arrive in strictly increasing order of quality (worst to best).
For candidates in random order, each of the \(n!\) possible permutations is equally likely. Only one permutation has the candidates in strictly increasing order. Therefore:
\[\Pr\{\text{hire exactly } n \text{ times}\} = \frac{1}{n!}\]