Linearity of expectation

Statement

Let \( (\Omega, \mathcal{F}, \mathbb{P}) \) be a probability space and let \( X, Y : \Omega \to \mathbb{R} \) be random variables defined on this same space, each integrable: \( \mathbb{E}\lvert X\rvert \lt \infty \) and \( \mathbb{E}\lvert Y\rvert \lt \infty \). Let \( a, b \in \mathbb{R} \) be (deterministic) constants. Then the random variable \( aX + bY \) is integrable, and \[ \mathbb{E}[aX + bY] \;=\; a\,\mathbb{E}[X] + b\,\mathbb{E}[Y]. \] No independence, uncorrelatedness, or any other relationship between \( X \) and \( Y \) is assumed. By induction the identity extends to any finite collection: if \( X_1, \dots, X_n \) are integrable and \( a_1, \dots, a_n \in \mathbb{R} \), then \( \mathbb{E}\left[\sum_{i=1}^n a_i X_i\right] = \sum_{i=1}^n a_i\,\mathbb{E}[X_i] \).

Why it matters

Linearity of expectation is the single most-used computational fact in probability. Its power lies precisely in the hypothesis it does not make: the summands may be dependent in arbitrarily vicious ways, yet the expectation of the sum splits cleanly. This is what makes the indicator method work — decompose a complicated count \( N \) as a sum of indicator variables \( \mathbf{1}_{A_i} \), and compute \( \mathbb{E}[N] = \sum_i \mathbb{P}(A_i) \) even when the events \( A_i \) overlap heavily.

Structurally, the theorem says that \( \mathbb{E} \) is a linear functional on the vector space \( L^1(\Omega, \mathcal{F}, \mathbb{P}) \). Together with positivity (\( X \ge 0 \Rightarrow \mathbb{E}[X] \ge 0 \)) and normalisation (\( \mathbb{E}[1] = 1 \)), this triple of properties essentially characterises expectation, and underlies the first-moment method of the probabilistic method, derandomisation by conditional expectations, and the whole analytic theory of \( L^p \) spaces.

Hypotheses

Proof

All expectations are Lebesgue integrals with respect to \( \mathbb{P} \): for \( Z \ge 0 \), \( \mathbb{E}[Z] := \int_\Omega Z \, d\mathbb{P} = \sup\{ \int s \, d\mathbb{P} : 0 \le s \le Z, \ s \text{ simple} \} \), and for integrable \( Z \), \( \mathbb{E}[Z] := \mathbb{E}[Z^+] - \mathbb{E}[Z^-] \) where \( Z^+ = \max(Z, 0) \), \( Z^- = \max(-Z, 0) \). We use one external lemma, proved in the integration unit:

Lemma (additivity and positive homogeneity for non-negative functions). If \( f, g : \Omega \to [0, \infty] \) are measurable and \( c \ge 0 \), then \( \int (f + g)\, d\mathbb{P} = \int f \, d\mathbb{P} + \int g \, d\mathbb{P} \) and \( \int c f \, d\mathbb{P} = c \int f \, d\mathbb{P} \). (Proof: approximate \( f, g \) from below by increasing sequences of simple functions \( s_n \uparrow f \), \( t_n \uparrow g \); additivity is elementary for simple functions; pass to the limit by the Monotone Convergence Theorem.)

Result

Corollaries & converses

• Indicator / first-moment identity. If \( N = \sum_{i=1}^n \mathbf{1}_{A_i} \) counts how many of the events \( A_1, \dots, A_n \) occur, then \( \mathbb{E}[N] = \sum_{i=1}^n \mathbb{P}(A_i) \), regardless of how the events intersect.
• Binomial mean without combinatorics. \( X \sim \mathrm{Bin}(n, p) \) is a sum of \( n \) Bernoulli\( (p) \) indicators, so \( \mathbb{E}[X] = np \) — no binomial-theorem manipulation of \( \sum k \binom{n}{k} p^k (1-p)^{n-k} \) needed.
• Monotonicity. If \( X \le Y \) a.s. and both are integrable, then \( Y - X \ge 0 \) gives \( \mathbb{E}[Y] - \mathbb{E}[X] = \mathbb{E}[Y - X] \ge 0 \): linearity plus positivity yields order-preservation.
• First-moment method. If \( N \) takes values in \( \mathbb{N} \cup \{0\} \) and \( \mathbb{E}[N] \lt 1 \), then \( \mathbb{P}(N = 0) \gt 0 \); if \( \mathbb{E}[N] \gt 0 \), then \( \mathbb{P}(N \ge 1) \gt 0 \). The engine of the probabilistic method.
• Centring. \( \mathbb{E}[X - \mathbb{E}[X]] = 0 \), which legitimises every variance and covariance computation, e.g. \( \mathrm{Var}(X) = \mathbb{E}[X^2] - (\mathbb{E}[X])^2 \).
• No converse content about dependence. \( \mathbb{E}[X + Y] = \mathbb{E}[X] + \mathbb{E}[Y] \) holds for all integrable pairs, so it carries zero information about the joint law. In particular multiplicativity does not follow: with \( Y = X \) uniform on \( \{-1, +1\} \), \( \mathbb{E}[XY] = 1 \neq 0 = \mathbb{E}[X]\mathbb{E}[Y] \). Multiplicativity requires uncorrelatedness (e.g. via independence) and is a genuinely stronger hypothesis.
• Characterisation direction. Conversely, a positive linear functional \( \varphi \) on bounded random variables with \( \varphi(1) = 1 \) and suitable continuity along monotone limits is expectation with respect to a (countably additive) probability measure — a probabilistic reading of the Riesz–Daniell representation theorem. Linearity is thus not merely a property of \( \mathbb{E} \); with positivity and normalisation it essentially is \( \mathbb{E} \).

Fails without

Common errors

• The phantom independence hypothesis. Inserting "assume \( X, Y \) independent" before using linearity. Harmless logically, but it signals a misunderstanding and throws away the theorem's entire point — and in exam problems the intended indicators are almost always dependent (fixed points of a permutation, birthday pairs, occupied boxes).
• Product leakage. Writing \( \mathbb{E}[XY] = \mathbb{E}[X]\,\mathbb{E}[Y] \) "by linearity". Multiplicativity is a consequence of independence (or uncorrelatedness by definition), never of linearity.
• Ratio and reciprocal fallacies. \( \mathbb{E}[X/Y] \neq \mathbb{E}[X]/\mathbb{E}[Y] \) and \( \mathbb{E}[1/X] \neq 1/\mathbb{E}[X] \) in general (Jensen: for positive non-degenerate \( X \), \( \mathbb{E}[1/X] \gt 1/\mathbb{E}[X] \)).
• Unlicensed infinite swaps. Exchanging \( \mathbb{E} \) with \( \sum_{n=1}^\infty \) or \( \lim_{n \to \infty} \) with no justification. The telescoping example above and the St Petersburg game both live in this gap; cite MCT, DCT, or Fubini–Tonelli explicitly.
• Random coefficients. Writing \( \mathbb{E}[AX] = A\,\mathbb{E}[X] \) or \( = \mathbb{E}[A]\mathbb{E}[X] \) when \( A \) is random. The first is a type error (left side is a number, right side a random variable); the second needs independence. The correct conditional version, \( \mathbb{E}[AX \mid \mathcal{G}] = A\,\mathbb{E}[X \mid \mathcal{G}] \) for \( \mathcal{G} \)-measurable bounded \( A \), is "taking out what is known" — a later theorem with its own proof.
• Forgetting to check integrability of the sum. Quoting the identity when one of \( \mathbb{E}[X], \mathbb{E}[Y] \) is infinite or undefined. The extended identity does hold when both are non-negative (values in \( [0, \infty] \), by the Lemma alone), but the signed case genuinely needs \( L^1 \).

Discussion

Why does dependence not matter? Because linearity is a pointwise phenomenon: the identity \( (aX + bY)(\omega) = aX(\omega) + bY(\omega) \) holds sample point by sample point, and integration — a limit of weighted sums — respects finite pointwise linear structure. Dependence is a statement about the joint law of \( (X, Y) \), i.e. about how mass is arranged on \( \mathbb{R}^2 \); but the marginal integrals \( \int X \, d\mathbb{P} \) and \( \int Y \, d\mathbb{P} \) never interrogate that arrangement. Contrast \( \mathbb{E}[XY] = \int uv \, d\mu_{(X,Y)}(u,v) \), which integrates against the joint law and therefore does feel dependence.

Historically, linearity predates any formal definition of expectation. Huygens's De ratiociniis in ludo aleae (1657) computes values of compound games by exactly this decomposition, and de Moivre and Laplace used the additivity of expected values of dependent quantities freely — the expected number of matches in the jeu de rencontre (Montmort, 1708) is the fixed-point computation in the first worked example below. What the Kolmogorov axiomatisation (1933) added was a definition of \( \mathbb{E} \) as a Lebesgue integral under which the classical manipulations become theorems, with the Monotone Convergence Theorem carrying the load at exactly one point (the Lemma).

The modern resonance of the theorem is the probabilistic method (Erdős, from 1947 on): to prove a combinatorial object exists, show a random candidate has the desired property with positive probability, and the workhorse for that is the first-moment method — compute \( \mathbb{E}[N] \) by linearity over dependent indicators, then conclude \( \mathbb{P}(N \ge 1) \gt 0 \) or \( \mathbb{P}(N = 0) \gt 0 \). Its algorithmic shadow, derandomisation by conditional expectations, again leans on linearity to evaluate the conditional means cheaply.

Functional-analytically, the theorem states that \( \mathbb{E} : L^1(\Omega, \mathcal{F}, \mathbb{P}) \to \mathbb{R} \) is a linear functional; positivity plus \( \mathbb{E}[1] = 1 \) forces \( \lvert \mathbb{E}[X] \rvert \le \mathbb{E}\lvert X \rvert = \lVert X \rVert_1 \), so it is bounded of norm \( 1 \) — the prototype of a state in operator-algebraic probability. The Daniell–Stone and Riesz representation theorems run the logic backwards: a positive, normalised linear functional with monotone continuity on a suitable function lattice arises from integration against a unique probability measure. In noncommutative probability one defines expectation as a positive linear functional \( \varphi \) on a \( C^\ast \)-algebra with \( \varphi(1) = 1 \); linearity is promoted from theorem to axiom. The same pointwise argument also gives linearity of conditional expectation \( \mathbb{E}[\,\cdot \mid \mathcal{G}\,] \), a.s., once that object is constructed.

Common misconceptions. Linearity does not say expectation commutes with everything: \( \mathbb{E}[g(X)] \neq g(\mathbb{E}[X]) \) for nonlinear \( g \) (Jensen's inequality quantifies the failure for convex \( g \)). It does not require identical distributions, finite variance, boundedness, or countable state spaces — integrability alone. And it is not "approximately true" for infinite sums by default: the interchange there is a convergence theorem, not a formality.

Worked examples

Example 1 (fixed points of a random permutation). Let \( \pi \) be a uniformly random permutation of \( \{1, \dots, n\} \) and let \( F = \#\{k : \pi(k) = k\} \) be the number of fixed points. Find \( \mathbb{E}[F] \).

Example 2 (birthday collisions). \( n \) people have birthdays independent and uniform on \( m \) days. Let \( C \) be the number of pairs of people sharing a birthday. Find \( \mathbb{E}[C] \), and evaluate it for \( n = 23 \), \( m = 365 \).

Problems

1. Let \( X \sim \mathrm{Bin}(n, p) \). Using linearity (not the probability mass function), show \( \mathbb{E}[X] = np \). Then compute \( \mathbb{E}[X(X-1)] \) is not \( np(np - 1) \) in general: explain which step would be illegal.
   Solution

   By definition of the binomial, \( X \) has the law of \( \sum_{k=1}^n I_k \) with \( I_1, \dots, I_n \) independent Bernoulli\( (p) \). Each \( I_k \) is bounded, hence integrable, with \( \mathbb{E}[I_k] = 1 \cdot p + 0 \cdot (1-p) = p \). By linearity, \( \mathbb{E}[X] = \sum_{k=1}^n \mathbb{E}[I_k] = np \). (Independence was never used.) For the second part: \( X(X-1) = X^2 - X \), and linearity legally gives \( \mathbb{E}[X(X-1)] = \mathbb{E}[X^2] - \mathbb{E}[X] \); the illegal move would be replacing \( \mathbb{E}[X^2] \) by \( (\mathbb{E}[X])^2 \) — expectation does not commute with the nonlinear map \( x \mapsto x^2 \). Correctly: \( X(X-1) = \sum_{j \neq k} I_j I_k \) (the diagonal terms vanish since \( I_k^2 = I_k \)), and by linearity plus independence of distinct indicators, \( \mathbb{E}[X(X-1)] = n(n-1)p^2 \), which differs from \( np(np-1) \) unless \( p \in \{0, 1\} \) or degenerate cases.
2. Let \( X_1, \dots, X_n \) be i.i.d. with a continuous distribution. Say index \( k \) is a record if \( X_k \gt X_j \) for all \( j \lt k \) (index \( 1 \) is always a record). Show that the expected number of records is the harmonic number \( H_n = \sum_{k=1}^n \frac{1}{k} \).
   Solution

   Let \( R_k = \mathbf{1}_{\{X_k \text{ is a record}\}} \) and \( R = \sum_{k=1}^n R_k \). Continuity of the common distribution makes ties null events, so among \( X_1, \dots, X_k \) there is a.s. a unique maximum, and by exchangeability of the i.i.d. sample every one of the \( k \) positions is equally likely to hold it. Hence \( \mathbb{E}[R_k] = \mathbb{P}(X_k = \max_{j \le k} X_j) = \frac{1}{k} \). The indicators are dependent (a record at \( k \) makes an early record at \( k+1 \) statistically relevant — in fact here they happen to be independent, but we never need that). By linearity, \( \mathbb{E}[R] = \sum_{k=1}^n \frac{1}{k} = H_n \approx \ln n + \gamma \). Records are logarithmically rare.
3. \( r \) balls are thrown independently and uniformly into \( n \) boxes. Let \( V \) be the number of empty boxes. Compute \( \mathbb{E}[V] \), and find its limit when \( r = cn \) with \( c \gt 0 \) fixed and \( n \to \infty \), normalised by \( n \).
   Solution

   Let \( V_i = \mathbf{1}_{\{\text{box } i \text{ empty}\}} \), so \( V = \sum_{i=1}^n V_i \). Box \( i \) is empty iff all \( r \) independent balls avoid it: \( \mathbb{E}[V_i] = \left(1 - \frac{1}{n}\right)^r \). The \( V_i \) are dependent (two boxes cannot both be avoided as easily as one), but linearity gives \[ \mathbb{E}[V] = n\left(1 - \frac{1}{n}\right)^r . \] With \( r = cn \): \( \frac{\mathbb{E}[V]}{n} = \left(1 - \frac{1}{n}\right)^{cn} = \exp\left(cn \ln\left(1 - \frac{1}{n}\right)\right) \to e^{-c} \) as \( n \to \infty \), since \( n \ln(1 - \frac{1}{n}) \to -1 \). So a fraction \( e^{-c} \) of boxes is empty on average — the Poisson\( (c) \) occupancy heuristic made exact at the level of means.
4. Let \( \pi \) be a uniformly random permutation of \( \{1, \dots, n\} \) and let \( K \) be its number of cycles. Show \( \mathbb{E}[K] = H_n = \sum_{k=1}^n \frac{1}{k} \). Hint: write \( K = \sum_{i=1}^n \frac{1}{L_i} \), where \( L_i \) is the length of the cycle containing \( i \), and first prove \( \mathbb{P}(L_i = k) = \frac{1}{n} \) for each \( k = 1, \dots, n \).
   Solution

   Each cycle of length \( \ell \) contains \( \ell \) elements, each contributing \( \frac{1}{\ell} \) to \( \sum_i \frac{1}{L_i} \); so the cycle contributes exactly \( 1 \) and \( K = \sum_{i=1}^n \frac{1}{L_i} \) holds surely. Next fix \( i \) and \( k \); count permutations in which \( i \) lies on a \( k \)-cycle: choose the other \( k - 1 \) elements of the cycle in \( \binom{n-1}{k-1} \) ways, arrange the cycle in \( (k-1)! \) ways, permute the rest in \( (n-k)! \) ways, giving \( \binom{n-1}{k-1}(k-1)!\,(n-k)! = (n-1)! \) permutations — independent of \( k \). Hence \( \mathbb{P}(L_i = k) = \frac{(n-1)!}{n!} = \frac{1}{n} \): the cycle length through a fixed point is uniform on \( \{1, \dots, n\} \). Therefore \( \mathbb{E}\left[\frac{1}{L_i}\right] = \sum_{k=1}^n \frac{1}{k} \cdot \frac{1}{n} = \frac{H_n}{n} \) (this is the law-of-the-unconscious-statistician evaluation of \( \mathbb{E}[g(L_i)] \) for \( g(k) = \frac 1k \)). Finally, by linearity over the \( n \) (strongly dependent — elements share cycles) summands, \( \mathbb{E}[K] = \sum_{i=1}^n \frac{H_n}{n} = H_n \). A uniform permutation of \( n \) letters has about \( \ln n \) cycles on average.
5. (Countable extension.) Let \( X_1, X_2, \dots \) be random variables on a common probability space with \( \sum_{n=1}^\infty \mathbb{E}\lvert X_n \rvert \lt \infty \). Prove that \( \sum_{n=1}^\infty X_n \) converges absolutely almost surely, is integrable, and \[ \mathbb{E}\left[\sum_{n=1}^\infty X_n\right] = \sum_{n=1}^\infty \mathbb{E}[X_n]. \] Point to the exact place where the hypothesis excludes the telescoping counterexample from the "Fails without" section.
   Solution

   Set \( Y = \sum_{n=1}^\infty \lvert X_n \rvert \), a measurable \( [0, \infty] \)-valued function (an increasing limit of measurable partial sums). By the Monotone Convergence Theorem applied to the partial sums \( \sum_{n=1}^N \lvert X_n \rvert \uparrow Y \), together with finite linearity (T-036) at each \( N \), \[ \mathbb{E}[Y] = \lim_{N \to \infty} \sum_{n=1}^N \mathbb{E}\lvert X_n\rvert = \sum_{n=1}^\infty \mathbb{E}\lvert X_n \rvert \lt \infty. \] (This is Tonelli's theorem for counting measure \( \times \) \( \mathbb{P} \).) Since \( \mathbb{E}[Y] \lt \infty \), we have \( Y \lt \infty \) a.s., i.e. \( \sum_n X_n(\omega) \) converges absolutely for a.e. \( \omega \); define \( S = \sum_{n=1}^\infty X_n \) there (and \( 0 \) on the null set). Then \( \lvert S \rvert \le Y \) gives \( S \in L^1 \). The partial sums \( S_N = \sum_{n=1}^N X_n \) satisfy \( S_N \to S \) a.s. and \( \lvert S_N \rvert \le Y \) with \( Y \) integrable, so the Dominated Convergence Theorem yields \( \mathbb{E}[S_N] \to \mathbb{E}[S] \). But \( \mathbb{E}[S_N] = \sum_{n=1}^N \mathbb{E}[X_n] \) by finite linearity, and the right-hand series converges absolutely, so \( \mathbb{E}[S] = \sum_{n=1}^\infty \mathbb{E}[X_n] \). In the telescoping counterexample, compute \( \mathbb{E}\lvert X_n \rvert \) directly: on \( \left(0, \frac{1}{n+1}\right) \) we have \( X_n = n - (n+1) = -1 \); on \( \left[\frac{1}{n+1}, \frac{1}{n}\right) \) we have \( X_n = n \); elsewhere \( X_n = 0 \). So \( \mathbb{E}\lvert X_n \rvert = 1 \cdot \frac{1}{n+1} + n\left(\frac{1}{n} - \frac{1}{n+1}\right) = \frac{1}{n+1} + \frac{1}{n+1} = \frac{2}{n+1} \), and \( \sum_n \frac{2}{n+1} = \infty \): the hypothesis \( \sum_n \mathbb{E}\lvert X_n \rvert \lt \infty \) fails, exactly as it must.