Probability and Expected Value DP

DP where the value is a probability or an expectation. The mechanics are ordinary DP; the difficulty is setting up the recurrence correctly.

Linearity of expectation — the most useful tool in the subject

$E [X + Y] = E [X] + E [Y]$

regardless of dependence. This lets you decompose a complicated random quantity into indicator variables and sum their probabilities:

$E [# events] = \sum_{i} Pr [event i] .$

Many “expected value” problems that look like they need a DP over configurations collapse to a sum of per-element probabilities. Always try this first.

Example. Expected number of fixed points in a random permutation: each element is fixed with probability $1/ n$ , so the answer is $n \cdot \frac{1}{n} = 1$ — no DP at all.

Forward vs backward DP

Forward (probability). dp[s] = probability of reaching state $s$ . Push probability outward:

dp[start] = 1.0;
for (state s in topological order)
    for (auto [t, p] : transitions(s)) dp[t] += dp[s] * p;

Backward (expectation). dp[s] = expected value from $s$ onward. Pull from successors:

$d p [s] = \sum_{t} p_{s t} (cost (s, t) + d p [t]) .$

// process states in reverse topological order
for (state s in reverse order)
    for (auto [t, p, c] : transitions(s)) dp[s] += p * (c + dp[t]);

Expectation DPs are almost always backward, with the terminal states as base cases. Getting the direction wrong is the most common structural error.

Self-loops — the algebra step

When a state can transition to itself, the recurrence is implicit:

$E = p E + (1 - p) X ⟹ E = X + \frac{p}{1 - p} X or, solving directly, E = \frac{( 1 - p ) X}{1 - p} .$

Concretely, for $E = 1 + p \cdot E + (1 - p) \cdot E^{'}$ (a step that with probability $p$ leaves you where you were):

$E = \frac{1 + ( 1 - p ) E ^{'}}{1 - p} .$

Always isolate $E$ algebraically rather than iterating — iteration converges slowly and accumulates error.

Cyclic dependencies — Gaussian elimination

If states depend on each other in a cycle that cannot be ordered, you have a linear system:

$E_{i} = \sum_{j} p_{ij} E_{j} + c_{i} .$

Solve with Gaussian elimination in $O (n^{3})$ . This is how random-walk-on-a-graph problems are solved when the walk can revisit states. For $n \leq 300$ or so it is entirely practical.

Special structure often helps: on a line or a tree, the system is tridiagonal or hierarchical and solvable in $O (n)$ .

Classic results

Problem	Answer
Expected rolls to see all $n$ faces (coupon collector)	$n H_{n} \approx n ln n$
Expected trials until success, probability $p$	$1/ p$
Expected number of comparisons in quicksort	$2 n ln n$
Expected length of the longest run of heads in $n$ flips	$\approx lo g_{2} n$
Expected number of inversions in a random permutation	$(2 n) /2$
Expected number of cycles in a random permutation	$H_{n}$
Random walk on a line, absorbing at 0 and $N$ , starting at $i$	reaches $N$ with probability $i / N$ ; expected time $i (N - i)$
Birthday paradox	collision after $\approx 1.18 n$ draws

Numerical care

Prefer long double for chained multiplications of probabilities.
Work in log space when probabilities get very small (products become sums).
Modular probabilities. Many problems ask for the answer mod $998244353$ : represent $p / q$ as $p \cdot q^{- 1}$ and use modular inverses throughout. This is exact and avoids all precision questions — check the statement, because it is now the more common convention.
Iterating to convergence (e.g. 100 000 rounds of a value iteration) is a legitimate technique for problems with a self-loop structure and a specified precision, but the algebraic solution is better when available.

Recognising the shape

“Expected number of X” → linearity of expectation, sum of indicators.
“Expected time until Y” → backward DP, watch for self-loops.
“Probability that Z happens” → forward DP over states.
“Both players play optimally and there is randomness” → game DP with expectation at chance nodes.

whoashish's cp notes

Directory