The hat problem

At a party, 10 guests toss their hats into a pile. Each guest then picks a hat at random.

What do you think?

On average, how many guests get their own hat back?

This seems impossibly hard — the assignments are all tangled up with dependencies. But with indicator variables, it becomes a one-line calculation.

What is an indicator variable?

Indicator Random Variable

For any event $A$ , the indicator variable $I_A$ is: $I_A = \begin{cases} 1 & \text{if } A \text{ occurs} \\ 0 & \text{if } A \text{ does not occur} \end{cases}$

Its expected value is simply the probability: $E[I_A] = P(A)$ .

The core property of indicator variables: $E[I_A] = 1 \cdot P(A) + 0 \cdot P(A^c) = P(A)$ . Expectation equals probability!

The indicator trick

Here's the strategy for "how many of these things happen?" problems:

Define indicators: For each item $i$ , let $I_i = 1$ if the event of interest happens for item $i$
Write the total: $X = I_1 + I_2 + \cdots + I_n$
Apply linearity: $E[X] = E[I_1] + E[I_2] + \cdots + E[I_n]$ (see linearity of expectation)
Compute each $E[I_i]$ : This is just $P(\text{event happens for item } i)$

You never need to worry about dependence between the indicators. Linearity handles that automatically.

Solving the hat problem

Let $I_i = 1$ if person $i$ gets their own hat.

Step 1: $X = I_1 + I_2 + \cdots + I_n$ = total matches

Step 2: $E[I_i] = P(\text{person } i \text{ gets own hat}) = \frac{1}{n}$

(Out of $n$ hats, exactly 1 is theirs.)

Step 3: $E[X] = \sum_{i=1}^n E[I_i] = n \cdot \frac{1}{n} = 1$

Hat Match Simulator

Number of people

Trials

Avg matches

0.000

E[matches]

1.000

The indicators $I_1, I_2, \ldots, I_n$ are not independent! If Alice got her own hat, it changes the odds for everyone else. But linearity of expectation doesn't care about dependence.

More examples

Fixed points in a random shuffle

Shuffle a deck of 52 cards. How many cards end up in their original position?

What do you think?

Expected number of cards in their original position?

Enter a whole number

Coupon collector (how many needed?)

A cereal box contains 1 of 5 toy types, equally likely. You want all 5.

When you have $k$ types, the probability the next box gives a new type is $(5-k)/5$ .

The expected boxes needed for the next new type = $\frac{5}{5-k}$ .

$E[\text{total boxes}] = \Large\frac{5}{5} + \frac{5}{4} + \frac{5}{3} + \frac{5}{2} + \frac{5}{1} \normalsize= 1 + 1.25 + 1.67 + 2.5 + 5 = 11.42$

With 6 toy types, what's the expected number of boxes needed? (Give to 2 decimal places) (decimal to 2 places, e.g. 5.23)

Simulate the coupon collector problem and see the indicator decomposition in action:

Coupon Collector Simulator

Number of coupon types

Trials

Avg draws

0.0

E[T] = nHₙ

14.7

Min draws

—

Why E[T] = nHₙ — the indicator trick

Phase	New types left	P(new)	E[draws]
1→1	6/6	1.00	1.00
2→2	5/6	0.83	1.20
3→3	4/6	0.67	1.50
4→4	3/6	0.50	2.00
5→5	2/6	0.33	3.00
6→6	1/6	0.17	6.00
Total E[T] = sum			14.70

Expected inversions in a random permutation

Shuffle numbers 1 through $n$ . An inversion is a pair $(i,j)$ where $i < j$ but the value at position $i$ is greater than the value at position $j$ .

Let $I_{ij} = 1$ if positions $i$ and $j$ form an inversion. For any pair, $P(I_{ij} = 1) = 1/2$ (one of the two orderings is equally likely).

$E[\text{inversions}] = \Large\binom{n}{2} \cdot \frac{1}{2} = \frac{n(n-1)}{4}$

For n = 10, expected inversions? (decimal, e.g. 0.42)

When to use indicator variables

The indicator trick is perfect when you're asked:

"How many…" things satisfy a condition?
"What fraction…" of items have a property?
"Expected number…" of successes?

The pattern:

Identify the individual items
Define $I_i$ for each
Use linearity: $E[\sum I_i] = \sum P(\text{event}_i)$

If you find yourself thinking "but the events are dependent!" — that's exactly when indicators shine. Independence is not required.

Summary

Concept	Formula
Indicator variable	$I_A = 1$ if $A$ occurs, $0$ otherwise
Expectation of indicator	$E[I_A] = P(A)$
Expected count	$E\left[\sum I_i\right] = \sum P(A_i)$
Key insight	Dependence between indicators doesn't matter

The indicator method: Decompose a complex count into a sum of binary questions. Each binary question is easy. Linearity adds them up for free.

Test your understanding

100 people in a room. Expected number sharing YOUR birthday? (decimal to 3 places, e.g. 0.456)

Shuffle 10 cards. Expected fixed points? (whole number)

Roll a die 6 times. Expected number of distinct values? (to 2 decimal places) (decimal to 2 places, e.g. 0.53)

What's next

Next we'll meet the geometric distribution — the waiting-time distribution for "how long until the first success?"