Math Core

"Find the expected number of..." questions can look impossible: the full probability distribution may be a nightmare. Linearity of expectation lets you skip the distribution entirely. You break the count into tiny yes-or-no pieces, find the probability of each piece, and add.

The key fact

The expected value of a random quantity $X$ is its long-run average, $E[X] = \sum x \cdot P(X = x)$ . The most useful property of expectation is that it adds.

Linearity of expectation

For any random quantities $X_1, X_2, \dots, X_n$ ,

$E[X_1 + X_2 + \dots + X_n] = E[X_1] + E[X_2] + \dots + E[X_n].$

This is true even when the $X_i$ depend on each other. No independence is needed.

Indicator variables

To find the expected number of times something happens, write the count as a sum of indicators. An indicator $I$ is $1$ if some event happens and $0$ if not, so $E[I] = P(\text{event})$ .

Definition

Indicator method

If $X$ counts how many of the events $B_1, \dots, B_n$ occur, write $X = I_1 + \dots + I_n$ , where $I_j = 1$ exactly when $B_j$ occurs. Then

$E[X] = P(B_1) + P(B_2) + \dots + P(B_n).$

For example, in a random permutation of $1, 2, \dots, n$ , let $I_j = 1$ if $j$ is in position $j$ . Each $P(I_j = 1) = \dfrac{1}{n}$ , so the expected number of fixed points is $n \cdot \dfrac{1}{n} = 1$ , for every $n$ . The events " $1$ is fixed" and " $2$ is fixed" are not independent, and it doesn't matter.

Common choices of indicator:

one per position (is position $j$ special?),
one per pair of positions or objects (is this pair adjacent, matching, inverted?),
one per object (does this object appear, get picked, come before something?).

Waiting times

The expected number of trials until an event of probability $p$ first happens is $\dfrac{1}{p}$ . Combine this with linearity to handle multi-stage waiting. To collect all $n$ faces of a fair $n$ -sided die, split the wait into stages: after you have seen $k$ faces, a new face appears with probability $\dfrac{n - k}{n}$ , so that stage lasts $\dfrac{n}{n - k}$ rolls on average. Adding,

$E = n\left(\frac{1}{n} + \frac{1}{n - 1} + \dots + \frac{1}{1}\right).$

Common mistake

Linearity works for sums, not products or maxima. $E[XY]$ is not $E[X]E[Y]$ unless $X$ and $Y$ are independent, and $E[\max(X, Y)]$ is not $\max(E[X], E[Y])$ . If the question asks for the expected value of a maximum or minimum, look for a way to write it as a sum of indicators first.

Worked example: Mixed neighbors

Five men and five women sit at random around a round table. Find the expected number of pairs of neighbors consisting of one man and one woman, written as $\dfrac{m}{n}$ in lowest terms; give $m + n$ .

There are $10$ neighboring pairs of seats. For a given pair, the probability that the two seats hold one man and one woman is $2 \cdot \dfrac{5}{10} \cdot \dfrac{5}{9} = \dfrac{5}{9}$ . So the expectation is $10 \cdot \dfrac{5}{9} = \dfrac{50}{9}$ , and $m + n = 59$ .

Worked example: The smallest element

A $4$ -element subset of $\{1, 2, \dots, 20\}$ is chosen at random. Find the expected value of its smallest element.

Write the minimum as a sum of indicators: $\min = \sum_{j \ge 1} I_j$ , where $I_j = 1$ if $\min \ge j$ . Then

$E[\min] = \sum_{j=1}^{17} P(\min \ge j) = \sum_{j=1}^{17} \frac{\binom{21 - j}{4}}{\binom{20}{4}} = \frac{\binom{21}{5}}{\binom{20}{4}} = \frac{21}{5}$

by the hockey stick identity. In general the expected minimum of a random $k$ -subset of $\{1, \dots, n\}$ is $\dfrac{n + 1}{k + 1}$ .

Worked example: Distinct faces

Six fair dice are rolled. What is the expected number of different values that appear?

Let $I_v = 1$ if value $v$ appears at least once. $P(I_v = 1) = 1 - \left(\dfrac{5}{6}\right)^6$ . So the expectation is $6\left(1 - \dfrac{15625}{46656}\right) = \dfrac{31031}{7776} \approx 3.99$ .

Tip

When you're stuck, ask "what is the smallest yes-or-no event whose count is my answer?" If each event has an easy probability, you're done.

Practice

Practice 1

A random permutation $a_1, a_2, \dots, a_{10}$ of $1, 2, \dots, 10$ is chosen. The expected number of indices $i$ with $1 \le i \le 9$ and $a_i > a_{i+1}$ is $\dfrac{m}{n}$ in lowest terms. Find $m + n$ .