Linearity of Expectation Tricks

Medium4–5 hrsLinearityIndicator VariablesClever Counting

Overview

Linearity of expectation is magical. It says: to find E[sum of things], just add up E[each thing] — even if the things are wildly dependent. The indicator variable trick transforms 'expected count of X' into 'sum of probabilities of each X occurring'. This bypasses the need to know the full joint distribution. Once you see this technique, you use it everywhere.

How to Recognize

→Hard to enumerate all outcomes — too many cases
→Asked for expected count of something (matches, crossings, inversions)
→Problem has symmetric or exchangeable structure
→Each 'piece' of the answer is independent or symmetric

Step-by-Step Approach

1.Define indicator Iᵢ = 1 if event i occurs, 0 otherwise
2.E[total count] = E[ΣIᵢ] = ΣE[Iᵢ] = ΣP(event i occurs)
3.Each P(event i) is usually MUCH easier to compute than the full distribution
4.Use symmetry: if all events are exchangeable, E = n·P(one event occurs)

Key Formulas

E\left[\sum_i I_i\right] = \sum_i P(\text{event}_i)

— linearity of expectation

02Records in random permutation:

E[\text{records}] = H(n) = \sum_{k=1}^n \frac{1}{k} \approx \ln n

03Fixed points in random permutation:

E[\text{fixed points}] = 1

for any

n

04Inversions in random permutation:

E[\text{inversions}] = \frac{n(n-1)}{4}

Worked Examples

0Quick Example

Expected fixed points in random permutation of n: ΣP(position i maps to itself) = Σ 1/n = 1. Always 1, regardless of n!

Problem

A deck of 52 cards is shuffled randomly and placed next to an ordered reference deck. What is the expected number of positions where both decks have the same card?

Solution

Define Iᵢ = 1 if card i is in position i in the shuffled deck.

P(Iᵢ = 1) = P(card i is in position i) = 1/52 for every card.

By linearity: E[total matches] = Σ P(Iᵢ = 1) = 52 · (1/52) = 1.

Mind-blowing: it doesn't matter if n=1 or n=1,000,000. The answer is always 1.

This is the expected number of fixed points of a random permutation.

Answer

$E[\text{matches}] = 1$ regardless of deck size $n$ . The expected number of fixed points in any random permutation is always exactly 1.

Common Mistakes

!
Thinking linearity requires independence. E[X+Y] = E[X] + E[Y] ALWAYS — even if X and Y are perfectly correlated. Independence is NOT required.
!
Not defining indicators carefully. The event must be something that either happens or doesn't for each piece of the sum.
!
Trying to compute the full distribution when linearity would give the expected value directly and easily.

Practice Problems

Click "Show Answer" to reveal

Roll 10 fair dice. What is the expected number of 6s?

Hint: Indicator for each die. P(one die shows 6) = 1/6.

Randomly arrange n people in a line. What is the expected number of adjacent pairs where person A is taller than the adjacent person B (A is immediately to B's left)?

Hint: There are n−1 adjacent pairs. For each pair, by symmetry, P(left is taller) = 1/2.

A box has 10 balls: 4 red, 6 blue. Draw 3 without replacement. Expected number of red balls?

Hint: Each of the 3 draws: P(red) = 4/10 by symmetry.

Back to Study Plan

Direct EV Calculation Conditional Expectation & Tower Property