Back to course

Indicator Variables and Trick Expectations

Indicator variables
IA={1if A occurs0otherwiseE[IA]=P(A)I_A = \begin{cases} 1 & \text{if } A \text{ occurs} \\ 0 & \text{otherwise} \end{cases} \qquad E[I_A] = P(A)

A zero-one variable whose expectation is the probability of the event, which is what turns counting into summing.

The expectation of an indicator is the probability of the event. Combined with linearity of expectation, this becomes the most powerful technique in interview probability.

Why it is so strong

E[∑iXi]=∑iE[Xi]E\left[\sum_i X_i\right] = \sum_i E[X_i]

always, whether or not the XiX_i are independent.

That is unusual. Nearly every other result requires independence. Expectation's additivity does not, so you can decompose a horribly entangled problem into pieces, take expectations separately, and add, without ever thinking about how the pieces interact.

Key takeaway

Write the quantity as a sum of indicators, compute each probability separately, add. Dependence between the indicators is irrelevant, which is precisely why the method beats direct counting.

The rest of this lesson is for subscribers

Unlock every lesson in Advanced Topics in Probability and Statistics, and every other premium course.

Subscribe to continue

Test your knowledge

Questions are only available to subscribers.
Continue
NextInequalities: Chernoff, Hoeffding, and More

Keep reading Advanced Topics in Probability and Statistics

35 lessons in this course, and every other premium course, on one subscription.

Subscribe now
  • Every lesson in every course, with the worked examples and interactive simulators
  • Graded questions on every lesson, with explanations for the wrong answers as well as the right one
  • The trainers, timed assessments and brainteaser library that go with them