Linearity of Expectation is the habit of adding expected contributions even when events are dependent. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.
The expected value of a sum equals the sum of expected values — even when the parts depend on each other.
Why It Works
1
Write the total as a sum of simpler random pieces $X = X_1 + \cdots + X_n$ (often $0/1$ indicators).
2
Expectation is a weighted sum over outcomes, and sums can be rearranged, so $E[X_1 + X_2] = E[X_1] + E[X_2]$ always holds.
3
Crucially this needs NO independence — the $X_i$ may overlap or interact, yet the identity still holds.
4
So compute each easy $E[X_i]$ separately and add, sidestepping the joint distribution entirely.
Worked Examples
Example 1
Five people randomly grab one hat each from their $5$ hats. What is the expected number of people who get their own hat?
1
Let $X_i = 1$ if person $i$ gets their own hat, else $0$. The total matches is $X = X_1 + X_2 + X_3 + X_4 + X_5$.
2
Person $i$ is equally likely to receive any of the $5$ hats, so $E[X_i] = P(X_i = 1) = \tfrac{1}{5}$.
3
By linearity (the matches are dependent, but that does not matter): $E[X] = 5 \cdot \tfrac{1}{5} = 1$.
Answer:
$1$
Warm-up
A fair coin is flipped $20$ times. What is the expected number of times a head is immediately followed by a tail (the pattern $HT$ in adjacent positions)?
1
There are $19$ adjacent positions $(i, i+1)$ for $i = 1, \ldots, 19$. Let $X_i = 1$ if positions $i, i+1$ read $HT$.
2
Each adjacent pair is $HT$ with probability $\tfrac{1}{2} \cdot \tfrac{1}{2} = \tfrac{1}{4}$, so $E[X_i] = \tfrac{1}{4}$.
3
The total is $X = \sum_{i=1}^{19} X_i$; by linearity (overlapping pairs are dependent, but that is fine) $E[X] = 19 \cdot \tfrac{1}{4}$.
4
Compute: $\tfrac{19}{4} = 4.75$.
Answer:
$\dfrac{19}{4}$
Contest level
Numbers $1, 2, \ldots, 100$ are arranged in a random order around a circle. What is the expected number of adjacent pairs whose two numbers differ by exactly $1$ (e.g. $k$ next to $k+1$)?
1
The consecutive value-pairs are $\{1,2\}, \{2,3\}, \ldots, \{99, 100\}$ — there are $99$ of them. Let $X_j = 1$ if pair $j$ sits in adjacent circle positions.
2
Fix a pair, say $\{k, k+1\}$. In a random circular arrangement of $100$ items, two specified items are adjacent with probability $\tfrac{2}{99}$ (each item has $2$ neighbors out of $99$ other positions).
3
So $E[X_j] = \tfrac{2}{99}$ for each of the $99$ pairs.
4
By linearity: $E\left[\sum_{j=1}^{99} X_j\right] = 99 \cdot \tfrac{2}{99} = 2$.
Answer:
$2$
Olympiad / Challenge
Each of $n$ people independently flips a fair coin. Everyone who flipped heads gives $\$1$ to the player on their left (around a circle). What is the expected number of people who end up with a net gain of $0$ dollars (received as much as they gave)?
1
Person $i$ gives $\$1$ iff they flip heads (their own flip $H_i$) and receives $\$1$ iff the person to their right flips heads (flip $H_{i-1}$). Their net is $0$ exactly when $H_i = H_{i-1}$ (both heads or both tails).
2
Let $X_i = 1$ if person $i$ nets $0$. Since the two relevant flips are independent fair coins, $P(H_i = H_{i-1}) = P(HH) + P(TT) = \tfrac{1}{4} + \tfrac{1}{4} = \tfrac{1}{2}$.
3
So $E[X_i] = \tfrac{1}{2}$ for each of the $n$ people, regardless of the dependence between neighbors.
4
By linearity: $E\left[\sum_{i=1}^{n} X_i\right] = n \cdot \tfrac{1}{2} = \tfrac{n}{2}$.
Answer:
$\dfrac{n}{2}$
Going Deeper
Linearity is the single most powerful counting-by-expectation tool because it holds with NO independence assumption: write the quantity of interest as a sum of indicators $X = \sum_i \mathbf{1}_{A_i}$, and then $E[X] = \sum_i P(A_i)$ even when the events overlap wildly. It is how one proves the expected number of fixed points of a random permutation is exactly $1$ for every $n$.
It appears whenever a problem asks for the 'expected number of' something — matches, inversions, records, adjacent pairs, empty boxes, distinct values — and it converts a hopeless joint-distribution computation into a sum of one-event probabilities. On AIME it frequently turns a problem that looks like it needs the full distribution into a two-line calculation.
Pitfall: linearity holds for the expectation of a SUM, not for products or nonlinear functions — $E[XY] \ne E[X]E[Y]$ unless $X, Y$ are independent, and $E[X^2] \ne (E[X])^2$. Also, $P(A_i)$ must be the probability of the event in the FULL random model; computing it inside a wrongly-conditioned subspace is the usual error.
Spot the Signal
Look for problems where the key step is adding expected contributions even when events are dependent.
You can describe the hard part as adding expected contributions even when events are dependent, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.
Learn the Move
Start by identify the counting object that calls for linearity of expectation, then rewrite the givens around it.
Name the relation that makes Linearity of Expectation legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.
Avoid These Traps
Do not use Linearity of Expectation just because the surface looks familiar; verify the required condition first.
Applying Linearity of Expectation because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.
MathGrit Coach Note
Let linearity of expectation reveal the counting structure; then compute only what remains.
Try it on:
Practice a contest problem where the key step is adding expected contributions even when events are dependent.