# 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 *X _{i}* be the indicator random variable associated with the event in which the

*i*th 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*(*c _{h}* ln

*n*).