Counting & ProbabilityDifficulty 40-953 tagged problems

Indicator Variables

Indicator Variables is the habit of turning events into zero-one variables so expectation and counting become additive. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

$$\mathbf{1}_A = \begin{cases} 1 & \text{if } A \text{ occurs} \\ 0 & \text{otherwise} \end{cases}, \qquad E[\mathbf{1}_A] = P(A)$$

Attach a $0/1$ variable to each event so that summing the variables counts how many events occur, and its expectation is just the probability.

Why It Works

1
Define $\mathbf{1}_A = 1$ exactly when event $A$ happens and $0$ otherwise.
2
Its expectation is $E[\mathbf{1}_A] = 1 \cdot P(A) + 0 \cdot P(A^c) = P(A)$.
3
If you want the total number of events that occur, write it as $X = \sum_A \mathbf{1}_A$.
4
By linearity of expectation, $E[X] = \sum_A P(A)$ — no independence needed — turning a hard count into a sum of simple probabilities.

Worked Examples

Example 1

A random permutation of $1, 2, \ldots, 5$ is chosen. What is the expected number of fixed points (positions $i$ with value $i$)?

1
Let $\mathbf{1}_i = 1$ if position $i$ holds the value $i$. The number of fixed points is $X = \mathbf{1}_1 + \cdots + \mathbf{1}_5$.
2
Position $i$ holds value $i$ with probability $\tfrac{1}{5}$, so $E[\mathbf{1}_i] = \tfrac{1}{5}$.
3
By linearity: $E[X] = 5 \cdot \tfrac{1}{5} = 1$.

Answer:

$1$

Warm-up

A fair die is rolled $30$ times. What is the expected number of rolls that show a prime number ($2$, $3$, or $5$)?

1
Let $\mathbf{1}_i = 1$ if roll $i$ shows a prime. The count of prime rolls is $X = \sum_{i=1}^{30}\mathbf{1}_i$.
2
A single roll is prime ($2$, $3$, or $5$) with probability $\tfrac{3}{6} = \tfrac{1}{2}$, so $E[\mathbf{1}_i] = \tfrac{1}{2}$.
3
By linearity: $E[X] = 30 \cdot \tfrac{1}{2} = 15$.

Answer:

$15$

Contest level

$50$ distinct balls are dropped independently and uniformly into $50$ distinct boxes. What is the expected number of EMPTY boxes?

1
Let $\mathbf{1}_j = 1$ if box $j$ is empty. The number of empty boxes is $X = \sum_{j=1}^{50}\mathbf{1}_j$.
2
Box $j$ is empty iff all $50$ balls miss it; each ball misses with probability $\tfrac{49}{50}$, so $P(\text{box } j \text{ empty}) = \left(\tfrac{49}{50}\right)^{50}$.
3
By linearity (the box-occupancies are dependent, but linearity ignores that): $E[X] = 50\left(\tfrac{49}{50}\right)^{50}$.
4
Numerically $\left(\tfrac{49}{50}\right)^{50} \approx e^{-1} \approx 0.3642$, so $E[X] \approx 50 \cdot 0.3642 \approx 18.2$.

Answer:

$50\left(\dfrac{49}{50}\right)^{50} \approx 18.2$

Olympiad / Challenge

A random permutation of $1, 2, \ldots, n$ is written in a row. An index $i$ is a 'descent' if the value at position $i$ is greater than the value at position $i+1$. What is the expected number of descents?

1
There are $n - 1$ adjacent index-pairs. Let $\mathbf{1}_i = 1$ if position $i$ is a descent, so $X = \sum_{i=1}^{n-1}\mathbf{1}_i$.
2
For a uniformly random permutation, the two values in positions $i$ and $i+1$ are equally likely to be in either relative order, so $P(\text{descent at } i) = \tfrac{1}{2}$ and $E[\mathbf{1}_i] = \tfrac{1}{2}$.
3
Adjacent indicators are NOT independent (consecutive pairs share an entry), but linearity of expectation needs no independence: $E\big[\sum_i \mathbf{1}_i\big] = \sum_i E[\mathbf{1}_i]$ holds however the pairs overlap — that is exactly its power.
4
By linearity: $E[X] = (n - 1) \cdot \tfrac{1}{2} = \tfrac{n-1}{2}$.

Answer:

$\dfrac{n-1}{2}$

Going Deeper

Indicators are the bridge from counting to expectation: any 'number of events that occur' is a sum of indicators, and $E[\mathbf{1}_A] = P(A)$ turns it into a sum of probabilities via linearity — no joint distribution required. The same decomposition computes second moments: $\operatorname{Var}(X) = \sum_i \operatorname{Var}(\mathbf{1}_i) + \sum_{i \ne j}\operatorname{Cov}(\mathbf{1}_i, \mathbf{1}_j)$, where covariances DO need the joint behavior.
This is the standard attack for 'expected number of fixed points / descents / empty boxes / matching pairs / records' problems, and it powers probabilistic existence proofs (if $E[X] < 1$ for a count of bad configurations, some outcome has $X = 0$). On AIME, recognizing 'expected number of' as a sum of indicators is often the entire solution.
Pitfall: linearity lets you ADD the $P(A_i)$ for the expected COUNT, but you cannot multiply them or assume independence — that only matters for variance, not the mean. The other slip is mis-stating $P(A_i)$: it is the probability event $i$ occurs in the full model, which by symmetry is usually easy, but a wrong conditioning silently breaks the sum.

Spot the Signal

Look for problems where the key step is turning events into zero-one variables so expectation and counting become additive.
You can describe the hard part as turning events into zero-one variables so expectation and counting become additive, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the counting object that calls for indicator variables, then rewrite the givens around it.
Name the relation that makes Indicator Variables legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Indicator Variables just because the surface looks familiar; verify the required condition first.
Applying Indicator Variables because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let indicator variables reveal the counting structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is turning events into zero-one variables so expectation and counting become additive.

Back to techniques

Counting & ProbabilityDifficulty 40-953 tagged problems

Indicator Variables

Practice this technique Match my level

The Key Result

$$\mathbf{1}_A = \begin{cases} 1 & \text{if } A \text{ occurs} \\ 0 & \text{otherwise} \end{cases}, \qquad E[\mathbf{1}_A] = P(A)$$

Attach a $0/1$ variable to each event so that summing the variables counts how many events occur, and its expectation is just the probability.

Why It Works

1
Define $\mathbf{1}_A = 1$ exactly when event $A$ happens and $0$ otherwise.
2
Its expectation is $E[\mathbf{1}_A] = 1 \cdot P(A) + 0 \cdot P(A^c) = P(A)$.
3
If you want the total number of events that occur, write it as $X = \sum_A \mathbf{1}_A$.
4
By linearity of expectation, $E[X] = \sum_A P(A)$ — no independence needed — turning a hard count into a sum of simple probabilities.

Worked Examples

Example 1

A random permutation of $1, 2, \ldots, 5$ is chosen. What is the expected number of fixed points (positions $i$ with value $i$)?

1
Let $\mathbf{1}_i = 1$ if position $i$ holds the value $i$. The number of fixed points is $X = \mathbf{1}_1 + \cdots + \mathbf{1}_5$.
2
Position $i$ holds value $i$ with probability $\tfrac{1}{5}$, so $E[\mathbf{1}_i] = \tfrac{1}{5}$.
3
By linearity: $E[X] = 5 \cdot \tfrac{1}{5} = 1$.

Answer:

$1$

Warm-up

A fair die is rolled $30$ times. What is the expected number of rolls that show a prime number ($2$, $3$, or $5$)?

1
Let $\mathbf{1}_i = 1$ if roll $i$ shows a prime. The count of prime rolls is $X = \sum_{i=1}^{30}\mathbf{1}_i$.
2
A single roll is prime ($2$, $3$, or $5$) with probability $\tfrac{3}{6} = \tfrac{1}{2}$, so $E[\mathbf{1}_i] = \tfrac{1}{2}$.
3
By linearity: $E[X] = 30 \cdot \tfrac{1}{2} = 15$.

Answer:

$15$

Contest level

$50$ distinct balls are dropped independently and uniformly into $50$ distinct boxes. What is the expected number of EMPTY boxes?

1
Let $\mathbf{1}_j = 1$ if box $j$ is empty. The number of empty boxes is $X = \sum_{j=1}^{50}\mathbf{1}_j$.
2
Box $j$ is empty iff all $50$ balls miss it; each ball misses with probability $\tfrac{49}{50}$, so $P(\text{box } j \text{ empty}) = \left(\tfrac{49}{50}\right)^{50}$.
3
By linearity (the box-occupancies are dependent, but linearity ignores that): $E[X] = 50\left(\tfrac{49}{50}\right)^{50}$.
4
Numerically $\left(\tfrac{49}{50}\right)^{50} \approx e^{-1} \approx 0.3642$, so $E[X] \approx 50 \cdot 0.3642 \approx 18.2$.

Answer:

$50\left(\dfrac{49}{50}\right)^{50} \approx 18.2$

Olympiad / Challenge

1
There are $n - 1$ adjacent index-pairs. Let $\mathbf{1}_i = 1$ if position $i$ is a descent, so $X = \sum_{i=1}^{n-1}\mathbf{1}_i$.
2
For a uniformly random permutation, the two values in positions $i$ and $i+1$ are equally likely to be in either relative order, so $P(\text{descent at } i) = \tfrac{1}{2}$ and $E[\mathbf{1}_i] = \tfrac{1}{2}$.
3
Adjacent indicators are NOT independent (consecutive pairs share an entry), but linearity of expectation needs no independence: $E\big[\sum_i \mathbf{1}_i\big] = \sum_i E[\mathbf{1}_i]$ holds however the pairs overlap — that is exactly its power.
4
By linearity: $E[X] = (n - 1) \cdot \tfrac{1}{2} = \tfrac{n-1}{2}$.

Answer:

$\dfrac{n-1}{2}$

Going Deeper

Indicators are the bridge from counting to expectation: any 'number of events that occur' is a sum of indicators, and $E[\mathbf{1}_A] = P(A)$ turns it into a sum of probabilities via linearity — no joint distribution required. The same decomposition computes second moments: $\operatorname{Var}(X) = \sum_i \operatorname{Var}(\mathbf{1}_i) + \sum_{i \ne j}\operatorname{Cov}(\mathbf{1}_i, \mathbf{1}_j)$, where covariances DO need the joint behavior.
This is the standard attack for 'expected number of fixed points / descents / empty boxes / matching pairs / records' problems, and it powers probabilistic existence proofs (if $E[X] < 1$ for a count of bad configurations, some outcome has $X = 0$). On AIME, recognizing 'expected number of' as a sum of indicators is often the entire solution.
Pitfall: linearity lets you ADD the $P(A_i)$ for the expected COUNT, but you cannot multiply them or assume independence — that only matters for variance, not the mean. The other slip is mis-stating $P(A_i)$: it is the probability event $i$ occurs in the full model, which by symmetry is usually easy, but a wrong conditioning silently breaks the sum.

Spot the Signal

Look for problems where the key step is turning events into zero-one variables so expectation and counting become additive.
You can describe the hard part as turning events into zero-one variables so expectation and counting become additive, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the counting object that calls for indicator variables, then rewrite the givens around it.
Name the relation that makes Indicator Variables legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Indicator Variables just because the surface looks familiar; verify the required condition first.
Applying Indicator Variables because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let indicator variables reveal the counting structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is turning events into zero-one variables so expectation and counting become additive.