Linearity of Expectation

This is the "Swiss Army Knife" of Olympiad probability. It allows you to calculate averages for complex systems without knowing the full distribution.

The Theorem

Theorem (Linearity of Expectation)

For any random variables

X

and

Y

(dependent or independent):

E [X + Y] = E [X] + E [Y]

Generally:

E [\sum c_{i} X_{i}] = \sum c_{i} E [X_{i}]

Indicator Variables

The most powerful way to use linearity is to break a count

X

into binary "indicator" variables.

X = I_{1} + I_{2} + \dots + I_{n}

where

I_{k} = 1

if event

k

happens, and

0

otherwise. Then

E [X] = \sum E [I_{k}] = \sum P (Event k happens)

Example (Hat Check Problem)

n

people drop their hats. The hats are returned randomly. What is the expected number of people who get their own hat back?

Proof. Let $X$ be the number of matches. Hard to find $P (X = k)$ . Use Indicators: Let $I_{j} = 1$ if person $j$ gets their own hat, $0$ otherwise. $X = I_{1} + \dots + I_{n}$ . $E [I_{j}] = P (Person j gets own hat) = \frac{1}{n}$ . By Linearity:

E [X] = j = 1 \sum n E [I_{j}] = j = 1 \sum n \frac{1}{n} = n \cdot \frac{1}{n} = 1

The answer is 1, regardless of

n

! ∎

Practice Problems

Exercise (Problem 1)

A deck of 52 cards is shuffled. What is the expected number of Aces in the top 5 cards?

Exercise (Problem 2)

Find the expected number of times "HH" appears in a sequence of

n

coin flips. (Hint: Let $I_{k}$ be the indicator that flips $k, k + 1$ are HH).

Exercise (Problem 3)

n

distinct balls are placed into

n

distinct bins randomly, what is the expected number of empty bins?