Indicator Variables

An indicator variable (or indicator random variable) is a random variable that equals 1 when an event occurs and 0 otherwise: $$\mathbf{1}_A = \begin{cases} 1 & \text{if event } A \text{ occurs} \\ 0 & \text{otherwise} \end{cases}$$ The key insight: The expected value of an indicator is just the probability of the event: $E[\mathbf{1}_A] = P(A)$. Do you see why? It is $1 \cdot P(A) + 0 \cdot P(A^c) = P(A)$. Concrete example: How many fixed points does a random permutation of $n$ elements have on average? Define $X_i = \mathbf{1}\{\text{element } i \text{ is fixed}\}$. Then the total number of fixed points is $X = X_1 + X_2 + \cdots + X_n$. By linearity of expectation: $$E[X] = \sum_{i=1}^n E[X_i] = \sum_{i=1}^n \frac{1}{n} = 1$$ Observe that we never needed the $X_i$ to be independent — linearity of expectation works regardless. When to use: Whenever a problem asks "how many objects satisfy some property on average," decompose into indicators. This is the go-to technique for expected value problems involving counts — random permutations, hash collisions, coupon collector variants, and graph properties. Power move: For variance, note $\mathbf{1}_A^2 = \mathbf{1}_A$, so $\text{Var}(\mathbf{1}_A) = P(A)(1-P(A))$. For sums of indicators, you need covariance terms: $\text{Var}(\sum X_i) = \sum \text{Var}(X_i) + 2\sum_{i<j} \text{Cov}(X_i, X_j)$.