linearity of expectation

Suppose a group of friends each order a meal, and you want the expected total bill. You do not need to know whether their orders are correlated — whether one person ordering dessert makes another more likely to. You can just add up each person's expected spend. Linearity of expectation is exactly this everyday move: the expected value of a sum is the sum of the expected values, no matter how the parts depend on each other.

Precisely: for any random variables X and Y, E[X + Y] = E[X] + E[Y], and more generally E[X1 + X2 + ... + Xn] = E[X1] + E[X2] + ... + E[Xn], plus E[cX] = c E[X] for a constant c. The astonishing part is that this needs no independence — it holds even when the variables are heavily entangled. The standard proof for a sum of two: average over outcomes, E[X+Y] = sum over outcomes of (X+Y) times its probability, then split the sum into the X-part and the Y-part. The power in algorithms comes from breaking a complicated count into a sum of tiny indicator variables, one per event, taking each one's easy expectation, and adding. For instance, the expected number of fixed points in a random permutation: let X_i be 1 if item i stays in place, so E[X_i] = 1/n; the total expected fixed points is sum from i=1 to n of 1/n = 1, even though the X_i are not independent.

This single tool quietly powers most randomized analysis: the expected number of comparisons in randomized quicksort, the expected number of hash collisions, the expected length of the longest run, all fall out by summing indicators. It matters because it sidesteps the hardest part of probability — dependence — entirely for the purpose of computing a mean. The honest caveat: linearity computes the average only; it says nothing about the variance or the chance of being far from the average. For that you still need a tail bound like Markov, Chebyshev, or Chernoff, which in turn often do need independence.