Linearity of expectation

The expectation of a sum is the sum of the expectations — always, whether or not the terms are independent. Almost every hard counting-flavoured probability question in a quant interview becomes easy the moment you write the quantity as a sum of indicators and apply this.

Equation 3.1

The statement

For any random variables $X_1,\dots,X_n$ on the same probability space, and any constants $a_i$ :

\mathbb{E}\!\left[\sum_{i=1}^{n} X_i\right] = \sum_{i=1}^{n} \mathbb{E}[X_i]

$X_i$: Any random variable. No independence assumption.
$\mathbb{E}[X_i]$: The expectation of the $i$ -th term, computed on its own.

Equation 3.2

With constants

\mathbb{E}\!\left[\sum_i a_i X_i + b\right] = \sum_i a_i\,\mathbb{E}[X_i] + b

Why independence is irrelevant here. Expectation is an integral, and integration is linear. $\mathbb{E}[X+Y]$ sums $x+y$ over the joint distribution; splitting that sum into an $x$ part and a $y$ part only needs each marginal, never how they move together. Dependence changes *where the mass sits jointly*, not the marginal averages. This is exactly why variance behaves differently: $\operatorname{Var}(X+Y)$ carries a covariance term, because squaring mixes the two variables together.

Identity	Needs independence?
$\mathbb{E}[X+Y] = \mathbb{E}[X] + \mathbb{E}[Y]$	No — always true
$\mathbb{E}[XY] = \mathbb{E}[X]\,\mathbb{E}[Y]$	Yes (uncorrelated suffices)
$\operatorname{Var}(X+Y) = \operatorname{Var}(X) + \operatorname{Var}(Y)$	Yes (uncorrelated suffices)
$\mathbb{E}[g(X)] = g(\mathbb{E}[X])$	Never true in general — see Jensen

Table 3.3 · What does and does not need independence.

Proposition 3.4

The indicator method

To find the expected number of things with some property, define $I_k = 1$ when the $k$ -th thing has the property and $0$ otherwise. Then the count is $N = \sum_k I_k$ , and because $\mathbb{E}[I_k] = \Pr(A_k)$ where $A_k$ is the event that item $k$ has the property, you get $\mathbb{E}[N] = \sum_k \Pr(A_k)$ . You never need the distribution of $N$ .

Holds when

The property must be checkable for each item separately.
The items may overlap, interact or be strongly dependent — it does not matter.

Derivation 3.5

Why an indicator’s expectation is a probability

$I_k = \begin{cases} 1 & \text{if the event } A_k \text{ occurs} \\ 0 & \text{otherwise} \end{cases}$
$\mathbb{E}[I_k] = 1\cdot\Pr(A_k) + 0\cdot\Pr(A_k^{c})$
Expectation of a two-valued variable, straight from the definition.

\mathbb{E}[I_k] = \Pr(A_k)

Example 3.6

The tournament question

A single-elimination tournament starts with $n$ equally skilled teams. Each round pairs the surviving teams at random, with a random bye when the count is odd. Two particular teams, A and B, are in the draw. What is the probability they play each other at some point? (Five Rings.)

Show the worked solutionHide the worked solution

Worked solution

Formula $\Pr(\text{A plays B}) = \mathbb{E}[\#\text{games between A and B}] = \sum_{g} \Pr(\text{game } g \text{ is A vs B})$
Substitute $= (n-1) \times \binom{n}{2}^{-1}$
Solve $\text{A and B can meet at most once, so } \#\text{games} \in \{0,1\}$ An indicator. Its expectation is therefore exactly the probability we want.
$\text{A tournament with } n \text{ teams plays exactly } n-1 \text{ games}$ Every game eliminates exactly one team, and all but the winner are eliminated.
$\Pr(\text{a given game is A vs B}) = \binom{n}{2}^{-1} = \frac{2}{n(n-1)}$ By symmetry every unordered pair is equally likely to be the one playing.
$\Pr = (n-1)\cdot\frac{2}{n(n-1)}$
Answer $\Pr(\text{A plays B}) = \frac{2}{n}$

Sanity check. With $n = 2$ the answer is $1$ : they must play. With $n = 8$ it is $1/4$ , matching the casework answer of $2/8$ .