Indicator Random Variables
The left side of the above equation is the expectation of the sum of n random variables. By Lemma 5.1, we can easily compute the expectation of each of the random variables. By equation (C.20)-linearity of expectation-it is easy to compute the expectation of the sum: it equals the sum of the expectations of the n random variables. Linearity of expectation makes the use of indicator random variables a powerful analytical technique; it applies even when there is dependence among the random variables. We now can easily compute the expected number of heads:
Analysis of the hiring problem using indicator random variables: Returning to the hiring problem, we now wish to compute the expected number of times that we hire a new office assistant. In order to use a probabilistic analysis, we assume that the candidates arrive in a random order, as discussed in the previous section. Let X is the random variable whose value equals the number of times we hire a new office assistant.
but this calculation would be cumbersome. We shall instead use indicator random variables to greatly simplify the calculation. To use indicator random variables, instead of computing E[X] by defining one variable associated with the number of times we hire a new office assistant, we define n variables related to whether or not each particular candidate is hired. In particular, we let Xi be the indicator random variable associated with the event in which the ith candidate is hired. Thus,
By Lemma 5.1, we have that
E[Xi] = Pr {candidate i is hired},
and we must therefore compute the probability that lines 5-6 of HIRE-ASSISTANT are executed.
Candidate i is hired, in line 5, exactly when candidate i is better than each of candidates 1 through i - 1. Because we have assumed that the candidates arrive in a random order, the first i candidates have appeared in a random order. Any one of these first i candidates is equally likely to be the best-qualified so far. Candidate i has a probability of 1/i of being better qualified than candidates 1 through i - 1 and thus a probability of 1/i of being hired. By Lemma 5.1, we conclude that
Now we can compute E[X]:
Even though we interview n people, we only actually hire approximately ln n of them, on average. We summarize this result in the following lemma.
Lemma 5.2
Assuming that the candidates are presented in a random order, algorithm HIRE-ASSISTANT has a total hiring cost of O(ch ln n).