Massachusetts Institute of Technology Lecture 23 6.042J/18.062J: Mathematics for Computer Science 30 November 2000 Professors Nancy Lynch and Srinivas Devadas

Expectation

1 Expected Value

The main topic of this lecture is the expectation, or expected value, or mean of a random variable. These terms are all synonymous.

1.1 Definition

Fix a particular discrete sample space S and a probability function Pr.

Definition The expected value of a random variable R is denoted Ex(R) and defined as:

Ex(R) = ∑_{s∈S} R(s) · Pr(s)

The expected value of a random variable is also sometimes called the mean or average. Intuitively, the expected value is the average of all possible values of a random variable, where a value is weighted according to the probability that it is attained.

An equivalent definition:

Definition The expected value of random variable R is:

Ex(R) = ∑_{r∈range(R)} r · Pr(R = r)

These are equivalent, because the second definition can be obtained from the first by simply grouping the terms in the summation that have the same R value:

Ex(R) = ∑_{s∈S} R(s) · Pr(s)
= ∑_{r∈range(R)} ∑_{s|R(s)=r} R(s) · Pr(s)

= ∑_{r∈range(R)} ∑_{s|R(s)=r} r · Pr(s)

= ∑_{r∈range(R)} r ∑_{s|R(s)=r} Pr(s)

= ∑_{r∈range(R)} r Pr(R = r)

If the image of a random variable R is not countable, then the summation above becomes an integral. We will not deal with this in 6.042.

Note: In the previous lecture, a random variable was defined as a function R : S ↦ R. That is, the range of a random variable was defined to be the real numbers. In this lecture, we relax this definition and consider random variables over a more limited range. In particular, we often consider random variables R : S ↦ N.

1.2 Expected Value of One Die

Suppose we roll a fair, six-sided die. Let the random variable R be the number that comes up. We can compute the expected value of R directly from the definition of expected value. Using the second version of the definition:

Ex(R) = ∑_{i=1}^{6} i · Pr(R = i)
= \frac{1}{6} + \frac{2}{6} + \frac{3}{6} + \frac{4}{6} + \frac{5}{6} + \frac{6}{6}
= 3\frac{1}{2}

The average value thrown on a fair die is 3\frac{1}{2}.

1.3 Expected Value of an Indicator Variable

If I is the indicator random variable for event A, then we calculate Ex(I) using the second definition of expectation, as:

Ex(I) = 1 · Pr(I = 1) + 0 · Pr(I = 0)
= 1 · Pr(A) + 0 · Pr(¯(A))
= Pr(A)

That is, the expected value of the indicator random variable for an event is just the probability of that event.

1.4 Meaning of Expectation

The expected value of a random variable doesn’t say anything about what will happen on one trial. Rather, it gives information about what we “expect” to happen, “on the average”, over a large number of trials. In fact, in a large number of trials, the probability will be very high that the average outcome is very close to the expected value.

Example: In one die roll, we have no reason to expect an outcome near 3.5. But over many die rolls, outcomes will almost surely average to around 3.5.

By itself, the mean of a random variable doesn’t say too much about the distribution of values of the variable. Random variables with very different distributions can have the same mean:

Example: Consider a funny die with 3 sides of 1 and 3 sides of 6. The expected value is still 3.5.

1.5 The Median is Not the Mean

Expected value, average, and mean are the same thing, but median is entirely different. The median is defined below, but only to make the distinction clear.

Definition The median of a random variable R is the unique value r in the range of R such that:

Pr(R < r) ≤ \frac{1}{2}
and Pr(R > r) < \frac{1}{2}

(Sometimes the ≤ and < are swapped in the two conditions above.)

Example: For an ordinary die, the median of the value of the random variable R giving the value thrown is 4.

Example: The median and the mean can be very far apart. Consider a 2n-sided die, with n 0s and n 100s. The mean is 50, and the median is 100.

We will not discuss the median further in this lecture.

1.6 Modified Carnival Dice

Let’s look at a modified version of Carnival Dice. The player chooses a number from 1 to 6. He then throws three fair and mutually independent dice. He wins one dollar for each die that matches his number, and he loses one dollar if no die matches.

This is better than the original game where the player received one dollar if any die matched, and lost a dollar otherwise. At first glance the new game appears to be fair; after all, the player is now “justly compensated” if he rolls his number on more than one die. In fact, there is still another variant of Carnival Dice in which the payoff is $2.75 instead of $3 if all three dice match. In this case, the game appears fair except for the lost quarter in the rare case that all three dice match. This looks like a tiny, tolerable edge for the house.

Let’s check our intuition by computing the expected profit of the player in one round of the $3 variant of Carnival Dice. Let the random variable R be the amount of money won or lost by the player in a round. We can compute the expected value of R as follows:

Ex(R) = −1 · Pr(no dice match) + 1 · Pr(one die matches) +

2 · Pr(two dice match) + 3 · Pr(three dice match)

= −1 · (\frac{5}{6})^{3} + 1 · 3 (\frac{1}{6}) (\frac{5}{6})^{2} + 2 · 3 (\frac{1}{6})^{2} (\frac{5}{6}) + 3 · (\frac{1}{6})^{3}
= \frac{−125 + 75 + 30 + 3}{216}
= \frac{−17}{216}

Our intuition was wrong! Even with a $3 payoff for three matching dice, the player can expect to lose \frac{17}{216} of a dollar, or about 8 cents, in every round. This is still a horrible game for the player!

The $2.75 variant is deceptive. One is tempted to believe that a player is shortchanged only a quarter in the rare case that all three dice match. This is a tiny amount. In fact, though, the player loses this tiny amount in addition to the comparatively huge 8 cents per game!

2 A Shortcut for Computing Expectations

There is a nice, alternative way to compute the expected value of a random variable with range N.

2.1 The Method

Theorem 2.1 If R is a random variable with range N, then

Ex(R) = ∑_{i=0}^{∞} Pr(R > i)

Proof. We will begin with the right-hand expression and transform it into Ex(R).

∑_{i=0}^{∞} Pr(R > i) = Pr(R > 0) + Pr(R > 1) + Pr(R > 2) + …

= Pr(R = 1) + Pr(R = 2) + Pr(R = 3) + …

=Pr(R>0)

+ \underbrace{Pr(R = 2) + Pr(R = 3) + …}_{=Pr(R>1)}

+ \underbrace{Pr(R = 3) + …}_{=Pr(R>2)}

= Pr(R = 1) + 2 · Pr(R = 2) + 3 · Pr(R = 3) + …
= ∑_{i=0}^{∞} i · Pr(R = i)
= Ex(R)

In the first step, the summation is rewritten with the … notation. In the second step, we rewrite each term Pr(R > i) as a series; if R is greater than i, then it must be one of i + 1, i + 2, etc. (This is where we use the fact that the range of R is N.) Next, we sum all the resulting series, and then revert to Σ notation. The last summation is the definition of Ex(R).

We can now compute the expected value of a random variable R by summing terms of the form Pr(R > i) instead of terms of the form Pr(R = i). Sometimes this makes a problem easier, as we will see in the next section. Remember, though, that the theorem only holds if the range of R is N!

2.2 Mean Time to Failure

American astronaut David Wolf has just arrived on the Mir space station. Suppose that Mir’s main computer has probability p of failing every hour, and assume that failures occur independently. (A failure is not catastrophic; the Mir computer is constantly on the blink.) How long can David expect to wait until the main computer fails?

Let the random variable R be the number of hours until the first failure; more precisely, assuming that the hours are numbered 1, 2, 3, …, R is the number of the hour in which the first failure occurs.

We want to compute the expected value of R. Since the range of R is N, we can apply Theorem 2.1:

Ex(R) = ∑_{i=0}^{∞} Pr(R > i)

All that remains is to compute Pr(R > i), the probability that the first failure occurs sometime after hour i. We can compute this with the usual four-step method, though there is a twist!

Step 1: Find the Sample Space. We can regard the sample space as a set of infinite strings such as W W F W F F W . . .. A W in the i-th position means that the main computer is working during hour i. An F in the i-th position means that the computer is down during hour i.

Step 2: Define Events of Interest. We are concerned with the event that R > i. This event consists of all outcomes with no F in the first i positions.

Step 3: Compute Outcome Probabilities. We want to compute the probability of a particular outcome, say the probability of the sequence W W F W F F W . . .. There is a problem! The number of outcomes in this experiment is infinite and, in fact, uncountably infinite! We must skip computing the probability of an individual outcome and hope to compute the probability of the event R > i directly.

Step 4: Compute Event Probabilities. We want to compute Pr(R > i). There is no F in the first position of an outcome string with probability 1 − p, no F in the second position with probability 1 − p, etc. Since failures occur independently, we can multiply probabilities; the probability that there is no F in the first i positions is (1 − p)^{i}. Therefore, Pr(R > i) = (1 − p)^{i}.

Substituting this result into the formula for Ex(R) given above, we can find the mean time until the first failure of the main computer.

Ex(R) = ∑_{i=0}^{∞}(1 − p)^{i}
= 1 + (1 − p) + (1 − p)^{2} + (1 − p)^{3} + …
= \frac{1}{1 − (1 − p)}
= \frac{1}{p}

In the first step, we substitute our expression for Pr(R > i). Next, we rewrite the summation in the … notation. This makes clear that we have the sum of a geometric series. The third step is an application of our old formula for the sum of a geometric series, and the last step is simplification.

The expected hour when the main computer fails is \frac{1}{p}. For example, if the computer has a 1% chance of failing every hour, then we would expect the first failure to occur at the 100th hour, or in about four days. On the bright side, this means that David Wolf can expect 99 comfortable hours without a computer failure.

2.3 Waiting for a Baby Boy

A couple really wants to have a baby boy. There is a 50% chance that each child they have is a boy, and the genders of their children are mutually independent. If the couple insists on having children until they get a boy, then how many baby girls should they expect to have first?

This is really a variant of the previous problem. The question, “How many hours until the main computer fails?” is mathematically the same as the question, “How many children must the couple have until they get a boy?” In this case, a computer failure corresponds to having a boy, so we should set p = \frac{1}{2}. By the preceding analysis, the couple should expect a baby boy after having \frac{1}{p} = 2 children. Since the last of these will be the boy, they should expect just 1 baby girl.

This strategy may seem to be favoring boys, because the couple keeps trying until they have one. However, this effect is counterbalanced by the small possibility of a long sequence of girls.

Example: Suppose the couple has a \frac{3}{4} chance of having a girl instead of \frac{1}{2}. Then what is the expected number of children up to and including the first boy?

Let R be the number of children up to and including the first boy. Then Ex(R) = _{\frac{1}{\frac{1}{4}}} = 4. That is, the expected number of girls before the first boy is 3.

Exercise: What is the expected number of children needed to get both a girl and a boy?

3 An Expectation Paradox

Here is a game that reveals a strange property of expectations.

First, you think of a probability distribution function on the natural numbers. This distribution can be absolutely anything you like. For example, you might choose a uniform distribution on 1, 2, …, 6, giving something like a fair die. Or you might choose a binomial distribution on 0, 1, …, n. You can even give every natural number a non-zero probability, provided, of course, that the sum of all probabilities is 1.

Next, I pick a random number z according to whatever distribution you invent. Finally, you pick a random number y according to the same distribution. If your number is bigger than mine (y > z), then the game ends. Otherwise, if our numbers are equal or mine is bigger (y ≤ z), then you pick again, and keep picking until you get a value that is bigger than z. What is the expected number of picks that you must make?

Certainly, you always need at least one pick, so the expected number is greater than one. An answer like 2 or 3 sounds reasonable, though one might suspect that the answer depends on the distribution. The real answer is amazing: the expected number of picks that you need is always infinite, regardless of the distribution you choose!

This makes sense if you choose, say, the uniform distribution on 1, 2, …, 6. After all, there is a \frac{1}{6} chance that I will pick 6. In this case, you must pick forever— you can never beat me!

In general, what is the probability that you need more than one pick? There are two cases to consider. If our numbers are different, then by symmetry there is a \frac{1}{2} chance that mine is the larger, and you have to pick again. Otherwise, if our numbers are the same, then you always have to pick again. In either case, you need more than one pick with probability at least \frac{1}{2}.

What is the probability that you need more than two picks? Here is an erroneous argument. On the first pick, you beat me with probability about \frac{1}{2}. On the second pick, you beat me with probability about \frac{1}{2}. The probability that you fail to beat me on both picks is only \frac{1}{2} · \frac{1}{2} = \frac{1}{4}. Therefore, the probability that you need more than two picks is around \frac{1}{4}. The problem is that beating me on your first pick is not independent of beating me on your second pick; multiplying the probabilities of these two events is therefore invalid.

Here is a correct argument for the probability that you need more than two picks. Suppose I pick z and then you pick y_{1} and y_{2}. There are two cases. If there is a unique largest number among these three, then there is a \frac{1}{3} chance that my number z is it, and you must pick again. After all, the largest number is equally likely to be chosen first, second, or third, regardless of the distribution. Otherwise, two or three of the numbers are tied for largest. My number is as likely to be among the largest as either of yours, so there is a better than \frac{1}{3} chance that my number is as large as all of yours, and you must pick again. In both cases, you need more than two picks with probability at least \frac{1}{3}.

By the same argument, the probability that you need more than i picks is at least \frac{1}{i+1}. Suppose I pick z and you pick y_{1}, y_{2}, …, y_{i}. Again, there are two cases. If there is a unique largest number among our picks, then my number is as likely to be it as any one of yours; with probability \frac{1}{i+1} you must pick again. Otherwise, there are several numbers tied for largest. My number is as likely to be one of these as any of your numbers, so with probability greater than \frac{1}{i+1} you must pick again. In both cases, with probability at least \frac{1}{i+1}, you need more than i picks to beat me.

These arguments suggest that you should choose a distribution such that ties are very rare. For example, you might choose the uniform distribution on [1, 10^{100}]. In this case, the probability that you need more than i picks to beat me is very close to \frac{1}{i+1} for reasonable i. For example, the probability that you need more than 99 picks is almost exactly 1%. This sounds very promising for you; intuitively, you might expect to win within a reasonable number of picks on average!

Unfortunately for intuition, there is a simple proof that the expected number of picks that you need in order to beat me is infinite, regardless of the distribution.

Theorem 3.1 If the random variable T is the number picks you need to beat me, then Ex(T) = ∞.

Proof.

Ex(T) = ∑_{i=0}^{∞} Pr(T > i)

≥ ∑_{i=0}^{∞} \frac{1}{i + 1}
= ∞

In the first step, we express the expectation using Theorem 2.1. This is valid, since the range of T is N. In the second step, we use the observation from above that you need more than i picks with probability at least \frac{1}{i+1}. This gives an unbounded sum!

This phenomenon can cause all sorts of confusion. For example, suppose you have a communication network. Assume that a packet has a 1/i chance of being delayed by i or more steps. This sounds good; there is only a 1% chance of being delayed by 100 or more steps. But, by the argument above, the expected delay for a packet is actually infinite!

4 Linearity of Expectation

Expected values obey a really nice rule called linearity of expectation. This rule says that the expected value of a sum of random variables is the sum of the expected values of the variables.

4.1 The Rule

Theorem 4.1 (Linearity of Expectation) For any random variables R_{1} and R_{2},

Ex(R_{1} + R_{2}) = Ex(R_{1}) + Ex(R_{2})

In other words, expectation is a linear function. The same rule holds for more than two random variables:

Corollary 4.2 For any random variables R_{1}, R_{2}, …, R_{k},

Ex(R_{1} + R_{2} + … + R_{k}) = Ex(R_{1}) + Ex(R_{2}) + … + Ex(R_{k})

Given the theorem, we can prove the corollary by induction on k.

To prove the theorem, we use a basic result about set theory and probability:

Theorem 4.3 (Theorem of Total Probability) Let B_{1}, B_{2}, … be disjoint events such that the union is the entire sample space S. Then for all events A ⊆ S,

Pr(A) = ∑_{i} Pr(A ∩ B_{i})

Now we are ready to prove linearity of expectation.

Proof. We transform Ex(R_{1} + R_{2}) into Ex(R_{1}) + Ex(R_{2}) with a sequence of equalities. We start by writing out Ex(R_{1} + R_{2}) using the (second) definition of expectation. Then we split the sum over all values of R_{1} + R_{2} into two sums, one over values of R_{1} and the other over values of R_{2}.

Ex(R_{1} + R_{2}) = ∑_{x∈range(R_{1} + R_{2})} x · Pr(R_{1} + R_{2} = x)

= ∑_{x_{1}∈range(R_{1})} ∑_{x_{2}∈range(R_{2})}(x_{1} + x_{2}) Pr((R_{1} = x_{1}) ∩ (R_{2} = x_{2}))

Next, we split the summation into two parts. We then swap the the second pair of summation symbols, and continue by pulling out x_{1} in the first pair of summations and pulling out x_{2} in the second pair.

= ∑_{x_{1}} ∑_{x_{2}} x_{1} Pr((R_{1} = x_{1}) ∩ (R_{2} = x_{2})) + ∑_{x_{1}} ∑_{x_{2}} x_{2} Pr((R_{1} = x_{1}) ∩ (R_{2} = x_{2}))
= ∑_{x_{1}} ∑_{x_{2}} x_{1} Pr((R_{1} = x_{1}) ∩ (R_{2} = x_{2})) + ∑_{x_{2}} ∑_{x_{1}} x_{2} Pr((R_{1} = x_{1}) ∩ (R_{2} = x_{2}))
= ∑_{x_{1}} x_{1} ∑_{x_{2}} Pr((R_{1} = x_{1}) ∩ (R_{2} = x_{2})) + ∑_{x_{2}} x_{2} ∑_{x_{1}} Pr((R_{1} = x_{1}) ∩ (R_{2} = x_{2}))

Now we apply the Theorem of Total Probability to each pair of summations. For the first pair, event A in the theorem is the event R_{1} = x_{1}. The B_{i} events in the theorem correspond to events of the form R_{2} = x_{2}. The theorem is similarly applied to the second pair of summations.

= ∑_{x_{1}} x_{1} Pr(R_{1} = x_{1}) + ∑_{x_{2}} x_{2} Pr(R_{2} = x_{2})
= Ex(R_{1}) + Ex(R_{2})

In the final step, we substitute Ex(R_{1}) and Ex(R_{2}) in place of their definitions.

Here is an alternative proof based on the first definition of expectation, which sums over individual outcomes rather than values of the random variables.

Ex(R_{1} + R_{2}) = ∑_{s∈S}(R_{1} + R_{2})(s) Pr(s)
= ∑_{s∈S}(R_{1}(s) + R_{2}(s)) Pr(s)
= ∑_{s∈S} R_{1}(s) Pr(s) + ∑_{s∈S} R_{2}(s) Pr(s)
= Ex(R_{1}) + Ex(R_{2})

Here, the first equation uses the (first) definition of expectation. The second equation uses the definition of the sum of two random variables. The third equation reorganizes terms into two summations, and the fourth equation uses the definition of expectation twice more.

The best thing about linearity of expectation is that no independence is required. This is great, because dealing with independence is pain! On one hand, we often need to work with random variables that are not independent. And even if we believe that some random variables are independent, we know from the last lecture that proving independence requires a lot of work.

Another aspect of linearity:

Theorem 4.4 For any random variables R_{1} and R_{2}, and any real number a,

Ex(aR) = a Ex(R)

and

Ex(aR_{1} + bR_{2}) = a Ex(R_{1}) + b Ex(R_{2})

4.2 Expected Value of Two Dice

What is the expected value of the sum of two fair dice?

Let the random variable R_{1} be the number on the first die, and let R_{2} be the number on the second die. Earlier in this lecture, we showed that the expected value of one die is 3\frac{1}{2}. We can find the expected value of the sum using linearity of expectation:

Ex(R_{1} + R_{2}) = Ex(R_{1}) + Ex(R_{2})
= 3\frac{1}{2} + 3\frac{1}{2}
= 7

Notice that we did not have to assume that the two dice were independent. The expected sum of two dice is 7, even if they are glued together! (This is provided that gluing does not change weights to make the individual dice unfair.)

Proving that the expected sum is 7 with a tree diagram would be hard; there are 36 cases. And if we did not assume that the dice were independent, the job would be a nightmare!

4.3 The Hat-Check Problem

There is a dinner party where N men check their hats. The hats are mixed up during dinner, so that afterward each man receives a random hat. In particular, each man gets his own hat with probability \frac{1}{N}. What is the expected number of men who get their own hat?

Without linearity of expectation, this would be a very difficult question to answer. We might try the following. Let the random variable R be the number of men that get their own hat. We want to compute Ex(R). By the definition of expectation, we have:

Ex(R) = ∑_{k=0}^{∞} k · Pr(R = k)

Now we are in trouble, because evaluating Pr(R = k) is a mess and we then need to substitute this mess into a summation. Furthermore, to have any hope, we would need to fix the probability of each permutation of the hats. For example, we might assume that all permutations of hats are equally likely.

Now let’s try to use linearity of expectation. As before, let the random variable R be the number of men that get their own hat. The trick is to express R as a sum of indicator variables. In particular, let R_{i} be an indicator for the event that the i-th man gets his own hat. That is, R_{i} = 1 is the event that he gets his own hat, and R_{i} = 0 is the event that he gets the wrong hat. The number of men that get their own hat is the sum of these indicators:

R = R_{1} + R_{2} + … + R_{N}

These indicator variables are not mutually independent. For example, if N −1 men all get their own hats, then the last man is certain to receive his own hat. That is, if R_{1} = R_{2} = … = R_{N−1} = 1, then we know that R_{N} = 1. Therefore, R_{N} is not independent of the other indicator variables. But, since we plan to use linearity of expectation, we do not care whether the indicator variables are independent!

We can take the expected value of both sides of the equation above and apply linearity of expectation without worrying about independence:

Ex(R) = Ex(R_{1} + R_{2} + … + R_{N})
= Ex(R_{1}) + Ex(R_{2}) + … + Ex(R_{N})

All that remains is to compute the expected value of an indicator variable R_{i}. Applying the definition of expectation, we find that the expected value of an indicator variable R_{i} is just the probability that the indicator is 1.

Ex(R_{i}) = 1 · Pr(R_{i} = 1) + 0 · Pr(R_{i} = 0)
= Pr(R_{i} = 1)

(In general, the expected value of an indicator variable is always the probability that the indicator is 1.)

The quantity Pr(R_{i} = 1) is the probability that the i-th man gets his own hat, which is just \frac{1}{N}. We can now compute the expected number of men that get their own hat:

Ex(R) = Ex(R_{1}) + Ex(R_{2}) + … + Ex(R_{N})
= \frac{1}{N} + \frac{1}{N} + … + \frac{1}{N}
= 1

We should expect exactly 1 man to get the right hat!

Notice that we did not assume that all permutations of hats are equally likely or even that all permutations are possible. We only needed to know that each man received his own hat with probability \frac{1}{N}. This makes our solution very general, as the next example shows.

4.4 The Chinese Appetizer Problem

There are N people at a circular table in a Chinese restaurant. On the table, there are N different appetizers arranged on a big Lazy Susan. Each person starts munching on the appetizer directly in front of them. Then someone spins the Lazy Susan so that everyone is faced with a random appetizer. What is the expected number of people that end up with the appetizer that they had originally?

This is just a special case of the hat-check problem, with appetizers in place of hats. In the hat check problem, we assumed only that each man received his own hat with probability \frac{1}{N}; we made no assumptions about how the hats could be permuted. This problem is a special case, because we happen to know that appetizers are cyclically shifted relative to their initial position. (We assume that each cyclic shift is equally likely.) Our previous analysis still holds; the expected number of people that get their original appetizer is 1.

(Of course, the event that exactly one person gets his original appetizer never happens. Either everyone does or no one does. The name “expected value” can be misleading, since that value may never occur!)

4.5 Expected Number of Events that Occur

We can generalize the hat-check and appetizer problems even further. Suppose that we have a collection of events in a sample space. What is the expected number of events that occur? For example, A_{i} might be the event that the i-th man receives his own hat. The number of events that occur is then the number of men that receive their own hat. Linearity of expectation gives a general solution to this problem:

Theorem 4.5 Given any collection of events A_{1}, A_{2}, …, A_{N} ⊆ S, the expected number of these events that occur is

∑_{i=1}^{N} Pr(A_{i}).

The theorem says that the expected number of events that occur is the sum the probabilities of the events. For example, in the hat-check problem the probability of the event that the i-th man receives his hat is \frac{1}{N}. Since there are N such events, the theorem says that the expected number of men that receive their hat is N · \frac{1}{N} = 1. This matches our earlier result. No independence assumptions are needed.

Proof. Let the random variable R be the number of events that occur. Let R_{i} be an indicator variable for the event A_{i}; that is, R_{i}(w) = 1 if event A_{i} occurs in outcome w (i.e., if w ∈ A_{i}), and R_{i}(w) = 0 otherwise. Then R_{i} = 1 and A_{i} are the same event.

The number of events that occur is the sum of the indicator variables:

R = R_{1} + R_{2} + … + R_{N}

Taking the expected value of both sides, we find:

Ex(R) = Ex(∑_{i=1}^{n} R_{i})

= ∑_{i=1}^{n} Ex(R_{i})

= ∑_{i=1}^{n} Pr(R_{i} = 1)

= ∑_{i=1}^{n} Pr(A_{i})

The second equation follows by linearity of expectation. In the third step, we use the fact that the expectation of an indicator variable is the probability that the indicator is 1. The final step follows because R_{i} = 1 and A_{i} are the same event.

4.6 Flipping Fair Coins

Suppose that we flip N fair coins. What is the expected number that come up heads?

Let A_{i} be the event that coin i comes up heads. Since the coin is fair, Pr(A_{i}) = \frac{1}{2}. Since there are N coins in all, there are N such events. By the theorem in the last section, the expected number of events that occur (the number of coins that come up heads) is N · \frac{1}{2} = \frac{N}{2} .

Let’s try to solve the same problem the hard way. In this case, assume that the coins are fair. Let the random variable R be the number of heads. We want to compute the expected value of R.

Ex(R) = ∑_{i=0}^{N} i · Pr(R = i)

= ∑_{i=0}^{N} i\binom{N}{i}2^{−N}

The first equation follows from the definition of expectation. In the second step, we evaluate Pr(R = i). An outcome of tossing the N coins can be represented by a length N sequence of H’s and T ’s. An H in position i indicates that the i-th coin is heads, and a T indicates that the i-th coin is tails. The sample space consists of all 2^{N} such sequences. The outcomes are equiprobable, and so each has probability 2^{−N}. The number of outcomes with exactly i heads is the number of length N sequences with i H’s, which is \binom{N}{i}. Therefore, Pr(R = i) = \binom{N}{i}2^{−N}.

The answer from linearity expectation and from the hard way must be the same, so we can equate the two results to obtain a neat identity.

∑_{i=0}^{N} i\binom{N}{i}2^{−N} = \frac{N}{2}

∑_{i=0}^{N} i\binom{N}{i} = N2^{N−1}

Thus, we have a probabilistic proof of a combinatorial identity. In fact, we proved this identity by another method earlier in the term. Note that linearity of expectation solves the problem more easily and that the result is more general, since we do not need to assume that the coins are independent. The expected number of heads is \frac{N}{2} , even if some coins are glued together.

We can extend this reasoning to n tosses of a coin with probability p of a head, rather than probability \frac{1}{2}. If we do this, we get the generalized combinatorial identity:

∑_{i=0}^{N} i\binom{N}{i}p^{i}(1 − p)^{N−i} = Np

Here, the p^{i} factor gives the probabilities for the heads and the (1 − p)^{N−i} factor gives the probabilities for the tails. The right-hand side is the sum of N terms, each giving the probability of a particular A_{i}, which is p. The total is Np.

Example: Consider an ordinary die. Let A_{1} be the event that the value is odd, A_{2} the event that the value is 1, 2, or 3, and A_{3} the event that the value is 4, 5, or 6. These events are not mutually independent. However, the expected number of these events that occur is still obtainable by adding Pr(A_{1}) + Pr(A_{2}) + Pr(A_{3}), which yields \frac{3}{2}.

Question: What can we say about the product of expectations? E.g., can we say Ex(R_{1}R_{2}) = Ex(R_{1}) Ex(R_{2}) ?

Not in general. We’ll come back to this next time.