Linearity of Expectation, Even Without Independence

A hundred people check their coats at a party, and the coats are handed back in a completely random order. What's the expected number of people who get their own coat back? Nobody wants to compute the probability of "exactly $k$ matches" for every $k$ from 0 to 100 and average — that's a nightmare of derangement counting. Yet the answer is one line, exactly 1, regardless of whether there are 5 people or 5 million.

Try it before reading on: guess whether the answer depends on the number of people, then see if you can find the one-line argument.

The trap: trying to compute the full distribution

The instinct is to find $P(\text{exactly } k \text{ matches})$ for every $k$, using derangement formulas, then compute $\sum_k k \cdot P(k)$. That's real combinatorics, genuinely hard to do under time pressure, and completely unnecessary — because expectation of a sum doesn't care about the joint distribution of the pieces at all.

This is the single most useful sentence in interview probability because it lets you dodge every hard joint-distribution question by never asking about the joint distribution at all.

Worked example: the hat-check problem

Let $X_i$ be the indicator variable that equals 1 if person $i$ gets their own coat back, 0 otherwise, for $i=1,\dots,n$. The total number of matches is $X = X_1+\cdots+X_n$, and

$$E[X] = E[X_1]+\cdots+E[X_n] = \sum_{i=1}^n P(X_i=1).$$

In words: the expected total number of matches is just the sum, over each person, of the chance that particular person matches — and crucially this holds even though $X_1,\dots,X_n$ are heavily dependent (if person 1 gets their coat, that changes the odds for everyone else). Linearity doesn't care.

Each individual $P(X_i=1)$ is easy: with a uniformly random permutation of $n$ coats, person $i$'s coat lands in any of the $n$ positions with equal probability, so $P(X_i=1)=1/n$. Summing $n$ copies of $1/n$: $E[X] = n\times\frac1n = 1$. Exactly one match expected, for any $n$ — 5 people or 5 million, the answer never changes, which is the counterintuitive punchline that makes this a favourite interview question.

Worked example: the birthday-collision count, not just the probability

A room has 30 people. Instead of the classic "probability at least two share a birthday," ask the linearity-friendly version: what's the expected number of pairs who share a birthday? There are $\binom{30}{2}=435$ pairs. For any specific pair, the chance they share a birthday (ignoring leap years, 365 equally likely days) is $1/365$, because once the first person's birthday is fixed, the second matches it with probability $1/365$ regardless of everyone else.

$$E[\text{matching pairs}] = \binom{30}{2}\times\frac{1}{365} = 435 \times \frac{1}{365} \approx 1.19.$$

In words: sum, over all $\binom{30}{2}$ possible pairs, the (tiny, identical) probability that that specific pair matches. You'd expect just over one matching pair among 30 people — consistent with the well-known fact that the probability of at least one match at 30 people is already around 70%, since even a fractional expected count above 1 corresponds to a substantial chance of at least one occurring.

E[X] = E[X1] + E[X2] + ... + E[Xn] — each term computed alone, ignoring the rest

The transferable technique

Whenever a problem asks for an expected count of something — matches, fixed points, collisions, successes, inversions — resist counting all the ways it can happen and instead decompose the count into indicator variables for the smallest atomic event you can name, compute each one's probability using symmetry or a direct argument, and sum. This single habit turns some of the ugliest-looking combinatorics questions in an interview into two lines of arithmetic.