Symptom

You are analyzing a hash table. You want the expected number of buckets that end up empty. The bucket occupancies are all tangled together — one key landing in bucket 3 makes every other bucket slightly less likely to be chosen — and the dependencies look like they will make the sum intractable.

Or: you want the expected number of comparisons in quicksort, where whether element $i$ is compared to element $j$ depends intricately on which pivots were chosen before.

Or, the interview version: you shuffle $n$ letters into $n$ addressed envelopes at random. How many land in the right envelope? The events are dependent in an obvious way — if the first $n-1$ are correct, the last one must be too.

In every case the honest-looking approach is a nightmare of conditional probabilities. In every case the actual answer takes one line, and the reason is a theorem so mild-sounding that people underestimate it for years.

Statement

$E[X + Y] = E[X] + E[Y]$, for any random variables $X$ and $Y$ on the same probability space.

For random variables $X_1, \dots, X_n$ and constants $c_i$,

$$E\left[\sum_{i=1}^n c_i X_i\right] = \sum_{i=1}^n c_i\, E[X_i]$$

with no assumption of independence.

That last line is the whole post. The variables may be dependent in any way whatsoever — perfectly correlated, adversarially entangled, defined in terms of each other — and the identity still holds exactly. Nothing else in probability is this forgiving. $E[XY] = E[X]E[Y]$ needs independence. Variances add only when uncorrelated. Expectations just add.

Argument

Work from the definition. For a finite sample space $\Omega$ with outcomes $\omega$:

$$E[X + Y] = \sum_{\omega \in \Omega} P(\omega)\,\bigl(X(\omega) + Y(\omega)\bigr)$$

Split the sum, which is legal because it is a finite sum of real numbers:

$$= \sum_{\omega} P(\omega)X(\omega) + \sum_{\omega} P(\omega)Y(\omega) = E[X] + E[Y]$$

$\blacksquare$

That is the entire proof, and its triviality is the point worth dwelling on. Independence never appears because the argument never factors a joint probability — it sums over outcomes, where $X$ and $Y$ are just two numbers attached to the same $\omega$, and addition does not care where they came from. Every theorem that does require independence requires it because it multiplies.

The technique: indicator variables. The proof is trivial; the use is not, and the standard move is worth stating explicitly because it converts almost any counting question into a one-liner.

To count things, define an indicator $X_i = 1$ if event $i$ occurs and $0$ otherwise. Then $E[X_i] = P(\text{event } i)$, directly from the definition. Let $X = \sum X_i$ be the total count. By linearity,

$$E[X] = \sum_i P(\text{event } i)$$

You have replaced a hard question about a total with $n$ easy questions about individual events. That is the trick, in full, and it is the single most useful thing in randomized algorithm analysis.

Envelopes. Let $X_i = 1$ if letter $i$ lands in its own envelope. Then $P(X_i = 1) = 1/n$, because letter $i$ is equally likely to land anywhere. So

$$E[X] = \sum_{i=1}^n \frac{1}{n} = 1$$

Exactly one letter, on average, for every $n$. The dependencies that made the problem look hard were never consulted. Computing the full distribution here requires the derangement numbers and inclusion–exclusion; computing the mean takes one line.

Empty buckets. Throw $n$ keys into $n$ buckets. Let $X_j = 1$ if bucket $j$ is empty. Each key misses bucket $j$ with probability $1 - 1/n$, so $P(X_j = 1) = (1-1/n)^n \approx e^{-1}$. Hence

$$E[\#\text{empty}] = n\left(1 - \tfrac1n\right)^n \approx n/e \approx 0.368\,n$$

About 37% of buckets sit empty in a full table, which is the number behind load factor tuning everywhere.

Quicksort. Let $X_{ij} = 1$ if elements of rank $i$ and $j$ are ever compared. They are compared exactly when the first pivot chosen from the rank range $[i, j]$ is $i$ or $j$ itself — if any middle element is picked first, $i$ and $j$ are split apart and never meet. That range has $j - i + 1$ elements, so $P(X_{ij} = 1) = 2/(j-i+1)$. Then

$$E[\text{comparisons}] = \sum_{iThe famous constant, from one page, with no recurrence relation and no master theorem.

Averaging as an existence proof. The other half of this tool’s value, and the reason it sits in Part I: if $E[X] = c$, then some outcome has $X \ge c$ and some outcome has $X \le c$. A value cannot be strictly below its own average everywhere. So to prove something with property $P$ exists, compute an average and point at it — without constructing anything. That is the probabilistic method, and it is how you prove a graph with a large cut exists (pick a random cut; each edge is cut with probability $1/2$; so $E[\text{cut}] = m/2$; so some cut has at least $m/2$ edges). It is pigeonhole (T001) with the integrality relaxed.

That max-cut line is worth pausing on, because it is also a 2-approximation algorithm obtained for free. Max-cut is NP-hard, and yet assigning every vertex to a random side puts at least half the edges across the cut in expectation, which is within a factor of 2 of any optimum. Three sentences of expectation arithmetic produce a guarantee that no amount of local search could have justified on its own. A large part of the approximation-algorithms literature opens exactly this way: bound the expected value of a random solution, then argue the optimum cannot be much better.

Where independence would have been needed. For contrast, consider what you cannot do with linearity alone. In the bucket example the expected number of empty buckets is $n/e$, but if you want to say “with high probability, between 36% and 38% are empty,” linearity has nothing to offer — that claim is about the distribution’s concentration, and proving it requires bounding how the $X_j$ co-vary. This is the exact boundary where the free lunch stops, and T008 picks it up.

Forbids

This is a tool rather than an impossibility, so its “forbids” are the claims it rules out about averages:

An algorithm whose expected cost beats the sum of its parts’ expected costs. If a routine does $n$ operations each costing 3 in expectation, its expected cost is $3n$. Not less, whatever the correlations. Optimizations must reduce some $E[X_i]$; there is no interaction term to exploit.

“The average case is better than the average of the cases.” A common hand-wave in performance arguments and it is simply false.

Amortized bounds that ignore a step. Since expectations add, a step with positive expected cost cannot be absorbed by correlation with other steps.

Does not forbid

It does not require independence, and the mistake goes in the expensive direction. People routinely add a dependence assumption they cannot justify — or worse, abandon a clean analysis because they cannot justify it, and fall back on simulation. The envelope, bucket, and quicksort examples above are all heavily dependent, and all correct. If you are summing, you never need independence. Check what you are actually computing before you go looking for an independence argument.

It does not extend to products, maxima, or anything non-linear. $E[XY] \ne E[X]E[Y]$ without independence, and $E[\max(X,Y)] \ne \max(E[X], E[Y])$ even with it. This is the boundary people cross by accident: having internalized that expectation “just distributes,” they distribute it over a max in a latency analysis and conclude that the slowest of 100 independent replicas is about as slow as one of them. It is not, and that error is the entire content of tail latency. $E[1/X] \ne 1/E[X]$ likewise, which is why average throughput is not the reciprocal of average latency.

It does not tell you about concentration, and this is the misuse that reaches production. Expectation is one number and says nothing about spread. A hash table has an expected chain length of 1, and the expected maximum chain is $\Theta(\log n / \log\log n)$, which is what actually determines your p99. “The expected queue depth is 3” is compatible with the queue being empty 90% of the time and holding 30 items the rest. If you need a guarantee rather than an average, you need Chernoff or Hoeffding (T008), and reasoning about SLOs from a mean is how services get sized wrong.

It does not mean the expected value is a typical value. The expected number of correct envelopes is 1, and the most likely single outcome is 0. For a lottery, the expectation is dominated by outcomes that essentially never happen. Expectation is a center of mass, not a forecast.

Boundary

  • When you need more than the mean. Markov’s inequality gives $P(X \ge a) \le E[X]/a$ from the expectation alone, which is weak but free and needs no independence either. Chebyshev needs the variance. Chernoff and Hoeffding (T008) give exponentially strong tails but do require independence, and that is precisely where the free lunch ends.
  • Conditional expectation and derandomization. $E[X] = E[E[X \mid Y]]$ (the tower property) lets you fix random choices one at a time, always keeping the conditional expectation at least as good — turning a probabilistic existence proof into a deterministic algorithm. This is the method of conditional expectations, and it is how the max-cut argument above becomes real code.
  • Infinite sums need care. Linearity extends to countably infinite sums only under absolute convergence or non-negativity (monotone convergence). Finite sums, which is everything in algorithm analysis, are unconditional.
  • Second moments. When you need to know a random variable is usually near its mean and independence is unavailable, the second-moment method (Chebyshev plus a variance computation over pairwise-dependent terms) is the next tool, and pairwise independence is often all it needs — much weaker than full independence and often actually true.