Expected Value & Recursive Probability

1. Introduction

Expected value is the single most useful number in contest probability. It is the long-run average of a random quantity, and its almost magical property — linearity of expectation — lets us compute averages of horrendously complicated random variables by breaking them into trivial pieces. Many AIME problems that look like they require summing over all configurations collapse to a one-line computation once you spot the right indicators.

The second pillar of this topic is recursion on states. When a random process unfolds step by step — a token moving on a board, a sequence of coin flips, a game continuing until someone wins — the expected outcome from a given state can be written in terms of the expected outcomes from the states it can move to. This produces a system of linear equations whose solution is the answer. The framework is that of Markov chains: processes where the future depends only on the present state, not on the path taken to reach it.

This article develops both pillars rigorously. We cover the definition and properties of expectation, indicator variables, conditional expectation and the law of total expectation, the first-step recursion, absorbing states, the gambler's ruin, and expected time to absorption. Throughout, we work hard contest problems in full, so that you can both set up the equations correctly and solve them cleanly under time pressure.

The two pillars in one sentence. Linearity of expectation answers "how many?" without independence; first-step recursion answers "how long?" or "what probability?" by writing one equation per state. Most AIME probability problems use one pillar or the other — rarely both in the same problem, but knowing both doubles your toolkit.

When to use which tool. If the question asks for an expected count (matches, edges, fixed points, successes), use indicators. If the question asks for expected time until an event or probability of reaching a target state, use Markov recursion. If the question asks for an expected maximum or sum of dependent rolls, consider tail sums or Wald's identity.

2. Core Concepts

2.1 Definition of Expected Value

For a discrete random variable $X$ taking value $x_i$ with probability $P(X = x_i)$, $E[X] = \sum_i x_i\, P(X = x_i).$ It is the probability-weighted average of the outcomes. For example, the expected value of a single fair six-sided die is $\frac{1+2+3+4+5+6}{6} = 3.5$.

2.2 Linearity of Expectation

For any random variables $X$ and $Y$ and constants $a, b$, $E[aX + bY] = a\,E[X] + b\,E[Y].$ Crucially, this holds whether or not $X$ and $Y$ are independent. This is what makes it so powerful: we can decompose a complicated count into a sum of simple indicator variables that may be highly dependent, and still add their expectations directly.

2.3 Indicator Variables

An indicator $I_A$ equals $1$ if event $A$ occurs and $0$ otherwise. Its expectation is simply the probability of the event: $E[I_A] = 1 \cdot P(A) + 0 \cdot P(A^c) = P(A).$ If a counting random variable can be written $X = I_{A_1} + I_{A_2} + \cdots + I_{A_n}$ (number of events that occur), then by linearity $E[X] = \sum_k P(A_k)$. This "indicator method" is the most common expectation technique on the AIME.

2.4 Conditional Expectation and the Law of Total Expectation

The law of total expectation (a.k.a. the tower rule) partitions the sample space by some first event or state: $E[X] = \sum_j E[X \mid B_j]\, P(B_j),$ where the events $B_j$ are disjoint and cover everything. Conditioning on the first step of a process is the special case that drives recursive analysis.

2.5 Markov Chains and States

A Markov chain is a process moving among states $s$, where from state $s$ it transitions to state $t$ with probability $p_{s\to t}$, and these probabilities do not depend on history. An absorbing state is one the process never leaves (e.g. "game over"). The two classic questions are: what is the probability of being absorbed at a particular absorbing state? and what is the expected number of steps until absorption?

2.6 The First-Step Recursion

Let $E_s$ denote the expected number of steps to reach an absorbing state, starting from state $s$. Conditioning on the first move, $E_s = 1 + \sum_t p_{s\to t}\, E_t,$ where absorbing states $a$ satisfy $E_a = 0$. The "$+1$" accounts for the step just taken. Similarly, for the probability $h_s$ of eventually being absorbed at a specific target, $h_s = \sum_t p_{s\to t}\, h_t,$ with $h = 1$ at the target absorbing state and $h = 0$ at the others. These boundary conditions anchor the linear systems.

2.7 Variance and When Linearity Is Not Enough

Variance is $\text{Var}(X) = E[X^2] - (E[X])^2$. Unlike expectation, variance is not linear: $\text{Var}(X + Y) \neq \text{Var}(X) + \text{Var}(Y)$ in general (unless $X, Y$ are independent). On the AIME, variance problems are rarer than expectation, but knowing $\text{Var}(X) = E[X^2] - E[X]^2$ lets you recover $E[X^2]$ when needed.

2.8 The Tail-Sum Formula for Nonnegative Integer Variables

If $X$ is a nonnegative integer-valued random variable, $E[X] = \sum_{k=1}^{\infty} P(X \ge k) = \sum_{k=0}^{\infty} P(X > k).$ This is invaluable for "expected maximum" and "expected count above threshold" problems without explicit probability mass functions.

2.9 Geometric and Negative Binomial Waiting Times

If each independent trial succeeds with probability $p$, the expected number of trials until the first success is $\frac{1}{p}$. More generally, the expected number of trials until the $r$-th success is $\frac{r}{p}$. These are the workhorses for "repeat until condition" problems.

2.10 Gambler's Ruin: Hitting Probabilities and Duration

On positions $0, 1, \ldots, N$ with each step $\pm 1$ with probability $\frac12$ (fair game), the probability of reaching $N$ before $0$ from position $k$ is $\frac{k}{N}$. The expected number of steps until absorption is $k(N - k)$. For biased walks with $p \neq \frac12$, the hitting probability involves ratios of geometric series.

2.11 Coupling and Symmetry Arguments

When states are symmetric under a transformation of the process, their expected values (or hitting probabilities) must be equal. Exploiting $E_1 = E_{N-1}$ in a symmetric walk cuts the system size in half. Coupling two processes to compare their expectations is an olympiad-level refinement of the same idea.

2.12 Expected Value of a Sum Over Random Sets

If $S$ is a random subset of $\{1, \ldots, n\}$ where each element is included independently with probability $p$, then $E[|S|] = np$ by indicators. More subtly, $E[\sum_{i \in S} f(i)] = \sum_{i=1}^n P(i \in S) f(i)$ — linearity decouples the random set from the summand.

2.13 Renewal and Regenerative Processes

A process regenerates when it returns to a starting state. The expected time between regenerations, plus the expected reward per cycle, gives the long-run average via renewal theory. On contests, the simple case is: expected total time $=$ (expected number of cycles) $\times$ (expected time per cycle).

2.14 Linearity for Products (Only with Independence)

$E[XY] = E[X]E[Y]$ only when $X$ and $Y$ are independent. For dependent variables, compute $E[XY]$ by conditioning or by direct summation. Confusing this with unconditional linearity is a top mistake.