Expected Value Techniques

Linearity of expectation — always try this first

$\mathbb{E}\left[{\sum }_i{X}_i\right]={\sum }_i\mathbb{E}[X_i]$

regardless of dependence between the $X_i$. This is the most useful fact in probabilistic problem solving, because it lets you decompose a complicated random quantity into simple indicators.

$\mathbb{E}[\#\text{events}]={\sum }_i\mathrm{Pr}[\text{event }i].$

Worked examples

Question	Decomposition	Answer
Expected fixed points of a random permutation	$X_i=[\sigma (i)=i]$, each $\mathrm{Pr}=1/n$	$1$
Expected inversions	$X_{ij}=[\text{pair inverted}]$, $\mathrm{Pr}=1/2$	$\left(\genfrac{}{}{0ex}{}{n}{2}\right)/2$
Expected distinct values among $n$ uniform draws from $[1,m]$	$X_v=[\text{value }v\text{ appears}]$	$m\left(1-(1-\frac{1}{m}{)}^n\right)$
Expected length of the longest run	harder — linearity gives bounds, not the exact value
Expected number of records (“new maximum so far”)	$\mathrm{Pr}[a_i\text{ is a record}]=1/i$	$H_n$
Expected cycles in a random permutation	same as records	$H_n$
Expected edges in a random subgraph	$\mathrm{Pr}$ each edge survives	$p|E|$
Expected connected components	harder — needs more than linearity

The records result is a good one to remember: element $i$ is the maximum of the first $i$ with probability exactly $1/i$, by symmetry.

Indicator variables — the technique

1. Write the quantity as a sum of 0/1 indicators.
2. Compute $\mathrm{Pr}[\text{indicator}=1]$ for each, using symmetry wherever possible.
3. Add them up.

Step 2 is where symmetry does the work: “by symmetry, each of the $n$ positions is equally likely to be the maximum” replaces a calculation with an observation.

Contribution technique

The deterministic cousin, and just as useful. Instead of summing over configurations, sum over elements, counting how many configurations each contributes to:

${\sum }_{\text{configs}}f(\text{config})={\sum }_{\text{elements}}(\text{value})\times (\text{how many configs contain it}).$

Problem	Contribution
Sum of $\min$ over all subarrays	each element × the subarrays where it is the minimum (monotonic stack)
Sum of all pairwise tree distances	each edge × $s(n-s)$
Sum of $\gcd$ over all pairs	each $d$ × the number of pairs with that gcd
Sum over all subsets of the subset’s XOR	each bit, independently
Expected value of a max	$\mathbb{E}[\max ]={\sum }_t\mathrm{Pr}[\max >t]$

That last identity is the tail-sum formula: for a non-negative integer random variable,

$\mathbb{E}[X]={\sum }_{t\ge 1}\mathrm{Pr}[X\ge t].$

It converts “expected maximum” — which linearity cannot handle — into a sum of probabilities, which it can.

Conditional expectation

$\mathbb{E}[X]={\sum }_i\mathrm{Pr}[A_i]\mathbb{E}[X\mid A_i].$

Condition on the first step (giving a recurrence for expected time), or on a hidden variable (the value of the maximum, the position of a pivot).

The law of total expectation is what turns “expected number of steps” into the backward DP of Probability DP.

Classic results

Problem	Answer
Expected trials until success, probability $p$	$1/p$
Coupon collector	$n{H}_n\approx n\ln n$
Expected comparisons in randomized quicksort	$2n\ln n$
Expected depth of a random BST / treap	$2\ln n$
Expected height of a random BST	$4.311\ln n$
Random walk on $[0,N]$ from $i$: reach $N$ before 0	probability $i/N$; expected time $i(N-i)$
Expected maximum of $n$ uniform $[0,1]$	$\frac{n}{n+1}$
Expected minimum of $n$ uniform $[0,1]$	$\frac{1}{n+1}$
Expected number of local maxima in a random permutation	$\frac{n-2}{3}+\dots$ (interior positions have $\mathrm{Pr}=1/3$)
Birthday paradox	collision after $\approx 1.18\sqrt{n}$ draws

Modular expected values

Most contest problems now ask for the answer modulo $998244353$. Represent every probability $p/q$ as $p\cdot q^{-1}$ and work exactly — no floating point anywhere. This removes all precision concerns and is why “output $P\cdot Q^{-1}\mathrm{mod}998244353$” has become the standard phrasing.

Pitfalls

Three traps

1. $\mathbb{E}[XY]\ne \mathbb{E}[X]\mathbb{E}[Y]$ unless $X$ and $Y$ are independent. Linearity has no such requirement; products do.
2. $\mathbb{E}[1/X]\ne 1/\mathbb{E}[X]$. Ever.
3. $\mathbb{E}[\max (X,Y)]\ne \max (\mathbb{E}X,\mathbb{E}Y)$ — use the tail-sum formula instead.

See also: Probability · Probability DP · Randomized Algorithms