Expected Value, Linearity & Advanced Probability

Study Sheet

Expected Value, Linearity & Advanced Probability

Competition counting & probability, Unit 9

Expected Value (Definition)

Concept
The expected value of a random variable

A random variable XX assigns a number to each outcome of a random experiment. Its expected value (or mean) is the probability-weighted average of the values XX can take:

E[X]=∑xx P(X=x),E[X]=\sum_{x} x\,P(X=x),

summing over every value xx in the range of XX. Think of E[X]E[X] as the long-run average of XX over many independent repetitions.

Expectation is linear under scaling and shifting: for constants a,ba,b,

E[aX+b]=a E[X]+b.E[aX+b]=a\,E[X]+b.

Expected value is the probability-weighted average of outcomes, and its superpower is linearity: E[X+Y]=E[X]+E[Y]E[X + Y] = E[X] + E[Y] always, even when XX and YY depend on each other. Indicator variables turn counting questions into expected values; geometric waiting times have expectation 1p\tfrac1p; and the expected value of a game decides whether it is worth playing.

The weights P(X=x)P(X=x) are nonnegative and sum to 11, so E[X]E[X] is a genuine weighted average and always lies between the smallest and largest possible values of XX.

Example
A weighted average of payoffs
01/2$03/6$12/6$2$31/6payoffmean 5/6
Put the probabilities on a seesaw at the payoffs; it balances at the mean, $56\$\tfrac56.

A game pays $33 if a fair die shows a 66, pays $11 if it shows a 44 or 55, and pays nothing otherwise. What is the expected payoff?

Solution. The payoff XX takes value 33 with probability 16\tfrac16, value 11 with probability 26\tfrac26, and value 00 with probability 36\tfrac36:

E[X]=3⋅16+1⋅26+0⋅36=36+26=56 dollars.E[X]=3\cdot\tfrac16+1\cdot\tfrac26+0\cdot\tfrac36=\tfrac{3}{6}+\tfrac{2}{6}=\tfrac{5}{6}\text{ dollars.}
Side note
Where it goes wrong

Believing linearity requires independence. It does not — that is the whole point. Independence is needed for E[XY]=E[X]E[Y]E[XY] = E[X]E[Y] and for adding variances, not for adding expectations.

Example
Expected value of a single die

A fair six-sided die is rolled. Then

E[X]=16(1+2+3+4+5+6)=216=72=3.5.E[X]=\tfrac16(1+2+3+4+5+6)=\tfrac{21}{6}=\tfrac{7}{2}=3.5.

Note 3.53.5 is not a possible outcome — the mean need not be attainable.

Tip

Tip. To build E[X]E[X] from scratch, list the distinct values, attach a probability to each, check the probabilities sum to 11, then take the dot product “value ×\times probability.” A missing or extra probability is the most common error.

Try it
Quick check

A fair six-sided die is rolled. What is the expected value of the number showing?

Work it on paper before revealing the answer.

Show the answer

Answer: Method: definition E[X]=∑x P(X=x)E[X]=\sum x\,P(X=x). Each face 1,2,3,4,5,61,2,3,4,5,6 of a fair die appears with probability 16\tfrac16, so

E[X]=16(1+2+3+4+5+6)=16⋅21=72=3.5.E[X]=\tfrac16(1+2+3+4+5+6)=\tfrac16\cdot 21=\boxed{\dfrac{7}{2}=3.5}.

Linearity of Expectation

Concept
Expectation adds — always

For any random variables XX and YY defined on the same experiment,

E[X+Y]=E[X]+E[Y],E[X+Y]=E[X]+E[Y],

and more generally E ⁣[∑iXi]=∑iE[Xi]E\!\left[\sum_i X_i\right]=\sum_i E[X_i]. This holds even when the XiX_i are dependent — no independence is required. Combined with scaling,

E ⁣[∑iaiXi]=∑iai E[Xi].E\!\left[\sum_i a_i X_i\right]=\sum_i a_i\,E[X_i].

Linearity is the single most powerful tool in this unit. It lets you compute the mean of a complicated total by breaking it into simple pieces, computing each piece's mean separately, and adding — without ever finding the distribution of the total.

Example
Sum of two dice
06/3623456789101112sum of two diceE[S] = 7
The whole distribution, which linearity never needed: its balance point is 3.5+3.5=73.5 + 3.5 = 7.

Roll two fair dice; let SS be their sum. Working out the full distribution of SS (values 22 through 1212) is tedious. Instead let S=X1+X2S=X_1+X_2 where XiX_i is die ii. Each die has mean 3.53.5, so

E[S]=E[X1]+E[X2]=3.5+3.5=7.E[S]=E[X_1]+E[X_2]=3.5+3.5=7.

The dice need not even be independent for this to work.

Example
Ten coins

Flip 1010 fair coins and let HH count the heads. Write H=X1+⋯+X10H=X_1+\cdots+X_{10} where Xi=1X_i=1 if flip ii is heads and 00 otherwise. Each E[Xi]=12E[X_i]=\tfrac12, so E[H]=10⋅12=5E[H]=10\cdot\tfrac12=5.

Tip

Key insight. When you must find the expected value of a count or a total, do not chase its distribution. Split it into a sum of simpler variables and add their means. Dependence between the pieces is irrelevant to the sum of the expectations.

Try it
Quick check

A fair die is rolled 1212 times. What is the expected number of sixes?

Work it on paper before revealing the answer.

Show the answer

Answer: Let Xi=1X_i = 1 if roll ii is a six. Each E[Xi]=16E[X_i] = \tfrac16, and the number of sixes is X1+⋯+X12X_1 + \cdots + X_{12}, so by linearity the expected number is 12⋅16=212\cdot\tfrac16 = \boxed{2}.

Indicator Random Variables

Concept
Turning “how many” into a sum of 0/10/1 variables

An indicator 1A\mathbf{1}_{A} equals 11 if event AA happens and 00 otherwise. Its expectation is just the probability of the event:

E[1A]=1⋅P(A)+0⋅P(Ac)=P(A).E[\mathbf{1}_A]=1\cdot P(A)+0\cdot P(A^c)=P(A).

If XX counts how many of the events A1,…,AnA_1,\dots,A_n occur, then X=∑i=1n1AiX=\sum_{i=1}^n \mathbf{1}_{A_i}, and by linearity

E[X]=∑i=1nP(Ai).E[X]=\sum_{i=1}^n P(A_i).

This is the workhorse pattern: whenever a quantity counts occurrences (heads, matches, fixed points, adjacent pairs, successes), define one indicator per potential occurrence and add up the individual probabilities. The events may overlap or be highly dependent — it does not matter.

Example
Expected number of aces in a hand

Deal 55 cards from a standard 5252-card deck. Let AA be the number of aces. For position ii, let 1i\mathbf{1}_{i} indicate that the ii-th card dealt is an ace; by symmetry P(1i=1)=452=113P(\mathbf{1}_i=1)=\tfrac{4}{52}=\tfrac1{13}. Then

E[A]=∑i=15P(card i is an ace)=5⋅113=513.E[A]=\sum_{i=1}^{5}P(\text{card }i\text{ is an ace})=5\cdot\tfrac{1}{13}=\tfrac{5}{13}.

The cards are dependent (drawing without replacement), yet linearity still applies.

Example
Expected number of fixed points

Randomly permute 1,2,…,n1,2,\dots,n. Let FF count the fixed points (positions ii with ai=ia_i=i). Let 1i\mathbf{1}_i indicate ai=ia_i=i; then P(ai=i)=1nP(a_i=i)=\tfrac1n, so

E[F]=∑i=1n1n=n⋅1n=1.E[F]=\sum_{i=1}^{n}\tfrac{1}{n}=n\cdot\tfrac1n=1.

On average a random shuffle leaves exactly one element in place, for every nn.

Tip

Recipe. (1) Identify the count. (2) Write it as ∑1Ai\sum \mathbf{1}_{A_i}, one indicator per possible occurrence. (3) Find P(Ai)P(A_i) for a single ii (symmetry usually makes them all equal). (4) Add. This four-step recipe cracks a huge fraction of contest expectation problems.

Try it
Quick check

Three fair dice are rolled. What is the expected number of different faces that appear?

Work it on paper before revealing the answer.

Show the answer

Answer: One indicator per face: Yf=1Y_f = 1 if face ff appears on at least one die. By the complement, P(Yf=1)=1−(56)3=91216P(Y_f = 1) = 1 - \left(\tfrac56\right)^3 = \tfrac{91}{216}. Adding over the 66 faces,

E=6⋅91216=9136≈2.53.E = 6\cdot\frac{91}{216} = \frac{91}{36} \approx 2.53.

  9136\boxed{\tfrac{91}{36}}

Expected Value via States & Recursion

Concept
Conditioning on the first step

When a process repeats until something happens, set up an equation for the expected value by conditioning on the first step. Let EE be the expected number of steps to finish. After one step you either finish or land back in a known state; averaging over the possibilities gives a linear equation in EE that you solve.

For a process that, each step, succeeds with probability pp (and otherwise restarts identically):

E=1+(1−p) E  ⟹  E=1p.E=1+(1-p)\,E \;\Longrightarrow\; E=\tfrac{1}{p}.

With several states, write one equation per state and solve the system.

The template is always “E=(cost of one step)+∑(probability of each next state)×(expected cost from that state)E = (\text{cost of one step}) + \sum (\text{probability of each next state})\times(\text{expected cost from that state}).” Finished/absorbing states contribute expected cost 00.

Example
First heads

Flip a fair coin until the first heads. Let EE be the expected number of flips. One flip always happens; with probability 12\tfrac12 we are done, and with probability 12\tfrac12 we are back where we started:

E=1+12⋅0+12⋅E  ⟹  12E=1  ⟹  E=2.E=1+\tfrac12\cdot 0+\tfrac12\cdot E \;\Longrightarrow\; \tfrac12E=1 \;\Longrightarrow\; E=2.
Example
Two states: waiting for HH
startHHHH, 1/2H, 1/2T, 1/2T, 1/2a = 6b = 40
A tail from either state sends you back to the start; only two heads in a row reach the end.

Flip a fair coin until two heads occur in a row. Let aa be the expected additional flips from the start (or just after a tails) and bb the expected additional flips right after a single heads. Then

a=1+12a+12b,b=1+12a+12⋅0.\begin{aligned} a &= 1+\tfrac12 a+\tfrac12 b,\\ b &= 1+\tfrac12 a+\tfrac12\cdot 0. \end{aligned}

Substituting the second into the first gives a=1+12a+12(1+12a)a=1+\tfrac12 a+\tfrac12(1+\tfrac12 a), so a=32+34aa=\tfrac32+\tfrac34 a, giving 14a=32\tfrac14 a=\tfrac32 and a=6a=6.

Side note
Where it goes wrong

Forgetting the step you just took. Writing E=12⋅0+12EE = \tfrac12\cdot 0 + \tfrac12 E for the wait until the first head solves to E=0E = 0, which is absurd. The equation must charge for the flip that has already happened: E=1+12⋅0+12EE = 1 + \tfrac12\cdot 0 + \tfrac12 E, so E=2E = 2. Every first-step equation starts with the cost of one step.

Tip

Tip. Choose states so that the future depends only on the current state, not the full history. Then each state gets one equation. Absorbing (“done”) states have expected remaining cost 00 — they anchor the system.

Try it
Quick check

A fair coin is flipped until the pattern HTHT (a head immediately followed by a tail) appears. What is the expected number of flips?

Work it on paper before revealing the answer.

Show the answer

Answer: States: start (aa) and "last flip was HH" (bb). From the start, a head moves to bb and a tail keeps you at the start: a=1+12b+12aa = 1 + \tfrac12 b + \tfrac12 a. From bb, a tail finishes and a head keeps you in bb: b=1+12b+12⋅0b = 1 + \tfrac12 b + \tfrac12\cdot 0, so b=2b = 2. Then 12a=1+1\tfrac12 a = 1 + 1, a=4a = \boxed{4}. (Compare 66 for HHHH: after a failed HHHH attempt you fall back to the start, but in HTHT a second head is not a setback.)

Symmetry Arguments

Concept
Let symmetry do the counting

When outcomes are interchangeable, symmetry pins down probabilities and expectations with almost no computation. Two common forms:

  • Uniform position. In a random permutation, each element is equally likely to occupy any given position, so its expected position is the average position n+12\tfrac{n+1}{2}.
  • Equal-likelihood ordering. Among kk specific items in random order, each of the k!k! relative orders is equally likely; e.g. any one of them is first with probability 1k\tfrac1k.

Symmetry pairs beautifully with linearity: use symmetry to argue every indicator has the same probability, then multiply by the number of indicators.

Example
Position of the first ace
gap 1gap 2gap 3gap 4gap 54 aces cut the 48 other cards into 5 gapseach gap holds 48/5 = 9.6 on average
One shuffle; the gap sizes change from deal to deal, but no gap is favoured, so each averages 485\tfrac{48}{5}.

Shuffle a 5252-card deck. The 44 aces split the remaining 4848 cards into 55 gaps (before the first ace, between consecutive aces, after the last). By symmetry each of the 4848 non-aces is equally likely to fall in any gap, so each gap holds 485\tfrac{48}{5} non-aces on average. The first ace sits just after the first gap, so its expected position is

485+1=535=10.6.\tfrac{48}{5}+1=\tfrac{53}{5}=10.6.

More generally the first of kk special cards among nn has expected position n+1k+1\tfrac{n+1}{k+1}.

Example
Who comes first?

Three runners A,B,CA,B,C finish in a uniformly random order. By symmetry each is equally likely to be the fastest, so P(A finishes first)=13P(A\text{ finishes first})=\tfrac13. No casework needed.

Tip

Tip. Before computing, ask: “Are these objects interchangeable?” If relabeling them leaves the setup unchanged, they share the same probability or expected value. That observation often replaces pages of casework with a single fraction.

Try it
Quick check

A row of 1010 cards, 33 red and 77 black, is shuffled. What is the expected position of the first red card?

Work it on paper before revealing the answer.

Show the answer

Answer: The 33 red cards cut the 77 black ones into 44 gaps, and by symmetry each gap holds 74\tfrac74 black cards on average. The first red card comes right after the first gap, so its expected position is 74+1=114\tfrac74 + 1 = \boxed{\tfrac{11}{4}}, which matches n+1k+1=114\tfrac{n+1}{k+1} = \tfrac{11}{4}.

Waiting Times & the Geometric Distribution

Concept
Expected wait for a first success

Repeat independent trials, each succeeding with probability p>0p>0. Let NN be the number of trials up to and including the first success. Then NN has a geometric distribution:

P(N=k)=(1−p)k−1p(k=1,2,3,… ),E[N]=1p.P(N=k)=(1-p)^{k-1}p\quad(k=1,2,3,\dots),\qquad E[N]=\frac{1}{p}.

The mean wait is the reciprocal of the success probability: rarer events take proportionally longer. (The variance is 1−pp2\tfrac{1-p}{p^2}, rarely needed on contests.)

The formula E[N]=1/pE[N]=1/p follows instantly from the recursion E=1+(1−p)EE=1+(1-p)E of the previous section, so “waiting time” problems and “restart” recursions are two views of the same idea.

Example
Rolling for a six
01/6123456789101112roll on which the first six appears (the tail goes on past 12)mean 6
Each bar is 56\tfrac56 of the one before it; the most likely single value is 11, yet the mean is 66 because of the long tail.

Roll a fair die until a 66 appears. Each roll succeeds with p=16p=\tfrac16, so the expected number of rolls is

E[N]=11/6=6.E[N]=\frac{1}{1/6}=6.

Waiting for a 11 or a 22 instead has p=13p=\tfrac13, giving E[N]=3E[N]=3.

Example
Free throws

A player makes each free throw with probability 0.80.8. The expected number of attempts to record the first make is 10.8=54=1.25\tfrac{1}{0.8}=\tfrac{5}{4}=1.25.

Tip

Careful. E[N]=1/pE[N]=1/p counts the trial on which success occurs. If a problem asks for the expected number of failures before the first success, that is 1p−1=1−pp\tfrac1p-1=\tfrac{1-p}{p}. Read carefully which count is wanted.

Try it
Quick check

Two dice are rolled together, repeatedly, until they show doubles. What is the expected number of rolls?

Work it on paper before revealing the answer.

Show the answer

Answer: Doubles occur on 66 of the 3636 outcomes, so each roll succeeds with p=16p = \tfrac16, independently. The wait is geometric, with mean 1p=6\tfrac1p = \boxed{6} rolls.

Going Deeper: Where These Ideas Combine

Concept
Signature techniques of advanced expectation

The four moves below appear again and again in olympiad and AMC/AIME problems:

  • Linearity magic. To find the expected value of a total, never compute its distribution — decompose into indicators or simple pieces and add. This defeats problems whose totals are hopelessly complicated to distribute directly.
  • Expected fixed points =1=1. In any random permutation of nn objects, the expected number of elements left in place is exactly 11, independent of nn (each of the nn positions is a fixed point with probability 1n\tfrac1n).
  • Absorbing-chain expectations. Model a repeating process as a Markov chain with “done” (absorbing) states; write one linear equation per transient state by conditioning on the next step, then solve. Symmetric gambler's-ruin on {0,1,…,N}\{0,1,\dots,N\} started at kk lasts k(N−k)k(N-k) steps in expectation.
  • Coupon collector. To collect all nn distinct coupons, once you hold jj of them the chance a new draw is fresh is n−jn\tfrac{n-j}{n}, a geometric wait of nn−j\tfrac{n}{n-j}. Summing gives E=n(1+12+⋯+1n)=n HnE=n\left(1+\tfrac12+\cdots+\tfrac1n\right)=n\,H_n.
Example
Coupon collector for a die

Roll a fair die repeatedly until all six faces have appeared. Waiting for the first new face costs 11 roll; from jj distinct faces seen, the next new face has probability 6−j6\tfrac{6-j}{6}, so its expected wait is 66−j\tfrac{6}{6-j}. Summing over j=0,1,…,5j=0,1,\dots,5:

E=6(16+15+14+13+12+1)=6⋅4920=14710=14.7 rolls.E=6\left(\tfrac16+\tfrac15+\tfrac14+\tfrac13+\tfrac12+1\right)=6\cdot\tfrac{49}{20}=\tfrac{147}{10}=14.7\text{ rolls.}
Example
Absorbing chain on a triangle

A token starts at vertex AA of triangle ABCABC and each step moves to one of the other two vertices with equal probability. How many steps, on average, to first reach CC? Let a,ba,b be the expected steps from AA and BB. By the transition rules,

a=1+12b,b=1+12a.a=1+\tfrac12 b,\qquad b=1+\tfrac12 a.

By symmetry a=ba=b, so a=1+12aa=1+\tfrac12 a, giving a=2a=2 steps.

Tip

Big picture. Expectation problems reward the solver who refuses to find the whole distribution. Ask three questions: (1) Is this a count or total? Then split into indicators and add (E=∑P(Ai)E=\sum P(A_i)) — linearity ignores all dependence. (2) Does the process repeat or wander among states? Then condition on the first step and solve a linear system; a pure “restart” collapses to the geometric mean 1/p1/p. (3) Are the objects interchangeable? Then symmetry hands you the per-piece probability for free. Almost every advanced expectation problem is one of these three shapes in disguise — name the shape, and the computation shrinks to a few lines.

Try it
Quick check

A cereal brand puts one of 33 different toys, equally likely, in each box. What is the expected number of boxes you must buy to collect all three toys?

Work it on paper before revealing the answer.

Show the answer

Answer: The first box always gives a new toy: 11. With one toy, a new one comes with probability 23\tfrac23, an expected 32\tfrac32 boxes. With two, probability 13\tfrac13, expected 33 boxes. By linearity,

E=1+32+3=112=3(1+12+13).E = 1 + \tfrac32 + 3 = \tfrac{11}{2} = 3\left(1 + \tfrac12 + \tfrac13\right).

  112\boxed{\tfrac{11}{2}}

Linearity Masterclass: Records, Inversions & Cycles

Concept
One permutation, many statistics — all by indicators

A uniformly random permutation a1,a2,…,ana_1,a_2,\dots,a_n of {1,…,n}\{1,\dots,n\} hides a zoo of natural statistics. Linearity computes the mean of each one without independence:

  • Records (left-to-right maxima): position ii is a record if aia_i exceeds all earlier entries. Among the first ii values, each is equally likely to be the largest, so P(record at i)=1iP(\text{record at }i)=\tfrac1i.
  • Inversions: a pair i<ji<j is inverted if ai>aja_i>a_j. By symmetry each unordered pair is inverted with probability 12\tfrac12.
  • Fixed points: P(ai=i)=1nP(a_i=i)=\tfrac1n (already seen: mean =1=1).
  • Cycles: the expected number of cycles equals the harmonic number Hn=∑k=1n1kH_n=\sum_{k=1}^{n}\tfrac1k.

In every case, sum the per-object probabilities. The events are wildly dependent; linearity does not care.

The cycle count is the subtle one. Build the permutation's cycles one element at a time (the Chinese-restaurant process): element kk either starts a new cycle of its own, or is inserted directly after one of the k−1k-1 elements already placed, inside that element's cycle. That is kk choices, and each permutation of {1,…,n}\{1,\ldots,n\} comes from exactly one sequence of choices (there are 1⋅2⋯n=n!1\cdot 2\cdots n = n! sequences), so a uniformly random permutation makes each choice uniformly: element kk starts a new cycle with probability 1k\tfrac1k. The number of cycles is the number of elements that started one, so it is ∑k=1n1k\sum_{k=1}^n \mathbf{1}_k with E[1k]=1kE[\mathbf{1}_k]=\tfrac1k, giving E[#cycles]=HnE[\#\text{cycles}]=H_n.

Example
Expected records and inversions (AIME flavor)

Let RR count the left-to-right maxima and II the inversions of a random permutation of 1,…,n1,\dots,n.

Records. E[R]=∑i=1n1i=HnE[R]=\sum_{i=1}^n \tfrac1i = H_n. For n=10n=10, E[R]=1+12+⋯+110=73812520≈2.93E[R]=1+\tfrac12+\cdots+\tfrac1{10}=\tfrac{7381}{2520}\approx 2.93.

Inversions. There are (n2)\binom{n}{2} pairs, each inverted with probability 12\tfrac12:

E[I]=(n2)⋅12=n(n−1)4.E[I]=\binom{n}{2}\cdot\tfrac12=\frac{n(n-1)}{4}.

For n=10n=10 this is 10⋅94=904=22.5\tfrac{10\cdot 9}{4}=\tfrac{90}{4}=22.5. Notice records and cycles share the same mean HnH_n — not a coincidence, but a bijective fact (Foata's correspondence) that linearity reveals for free.

Tip

Key insight. A permutation statistic that is a sum over positions or pairs yields to indicators. The whole art is choosing the right “atom”: positions for records and fixed points, unordered pairs for inversions, insertion steps for cycles. Find the atom, find one probability, multiply or sum. The joint distribution never appears.

Try it
Quick check

What is the expected number of inversions in a random permutation of 1,2,…,61, 2, \ldots, 6?

Work it on paper before revealing the answer.

Show the answer

Answer: One indicator per pair of positions i<ji < j: there are (62)=15\binom62 = 15 pairs, and each is inverted with probability 12\tfrac12 (swapping the two values maps inverted to non-inverted). So E=15⋅12=152E = 15\cdot\tfrac12 = \boxed{\tfrac{15}{2}}.

Variance & the Second Moment

Concept
Measuring spread with Var(X)\mathrm{Var}(X)

The variance of XX measures how far XX typically strays from its mean μ=E[X]\mu=E[X]:

Var(X)=E[(X−μ)2]=E[X2]−(E[X])2.\mathrm{Var}(X)=E\big[(X-\mu)^2\big]=E[X^2]-\big(E[X]\big)^2 .

The second form (“mean of the square minus square of the mean”) is almost always the easier one to compute. Variance scales quadratically: Var(aX+b)=a2 Var(X)\mathrm{Var}(aX+b)=a^2\,\mathrm{Var}(X) — shifting by bb changes nothing, stretching by aa multiplies spread by a2a^2.

Unlike expectation, variance does NOT add in general. It adds only when the pieces are independent (or merely uncorrelated):

Var(X1+⋯+Xn)=∑iVar(Xi)if the Xi are independent.\mathrm{Var}(X_1+\cdots+X_n)=\sum_i \mathrm{Var}(X_i)\quad\text{if the }X_i\text{ are independent.}

For a single indicator 1A\mathbf{1}_A with p=P(A)p=P(A), we have E[1A2]=E[1A]=pE[\mathbf{1}_A^2]=E[\mathbf{1}_A]=p (since 02=0, 12=10^2=0,\,1^2=1), so

Var(1A)=p−p2=p(1−p).\mathrm{Var}(\mathbf{1}_A)=p-p^2=p(1-p).

This one fact powers the variance of every count built from independent indicators.

Example
Variance of a binomial count

Flip nn independent coins, each heads with probability pp; let H=∑i=1n1iH=\sum_{i=1}^n \mathbf{1}_i be the number of heads. The flips are independent, so variances add:

Var(H)=∑i=1nVar(1i)=∑i=1np(1−p)=np(1−p).\mathrm{Var}(H)=\sum_{i=1}^{n}\mathrm{Var}(\mathbf{1}_i)=\sum_{i=1}^n p(1-p)=np(1-p).

For n=100n=100 fair coins (p=12p=\tfrac12): E[H]=50E[H]=50 and Var(H)=100⋅12⋅12=25\mathrm{Var}(H)=100\cdot\tfrac12\cdot\tfrac12=25, so the standard deviation is 25=5\sqrt{25}=5. Typical outcomes cluster near 50±550\pm 5.

Example
Second moment of a single die

Let XX be a fair die roll. We found E[X]=72E[X]=\tfrac72. For the variance, compute the second moment:

E[X2]=16(12+22+⋯+62)=16⋅6⋅7⋅136=916.E[X^2]=\tfrac16(1^2+2^2+\cdots+6^2)=\tfrac16\cdot\tfrac{6\cdot 7\cdot 13}{6}=\tfrac{91}{6}.

Then

Var(X)=E[X2]−(E[X])2=916−494=182−14712=3512.\mathrm{Var}(X)=E[X^2]-\big(E[X]\big)^2=\tfrac{91}{6}-\tfrac{49}{4}=\tfrac{182-147}{12}=\tfrac{35}{12}.

The sum of two independent dice therefore has variance 2⋅3512=3562\cdot\tfrac{35}{12}=\tfrac{35}{6}, even though its mean 77 came from linearity without any independence.

Tip

Careful. Expectation always adds; variance adds only under independence. When indicators are dependent (drawing without replacement, fixed points of a permutation), you must include covariance terms: Var ⁣(∑Xi)=∑Var(Xi)+∑i≠jCov(Xi,Xj)\mathrm{Var}\!\left(\sum X_i\right)=\sum \mathrm{Var}(X_i)+\sum_{i\ne j}\mathrm{Cov}(X_i,X_j). If a problem asks for a variance and the pieces overlap, do not just add — the cross terms are where the points hide.

Conditional Expectation & the Tower Property

Concept
Averaging in stages

The conditional expectation E[X∣Y]E[X\mid Y] is the average of XX once the value of YY is known; it is itself a random variable (a function of YY). The tower property (law of total expectation) says you may average in two stages and recover the plain mean:

E[X]=E[E[X∣Y]]=∑yE[X∣Y=y] P(Y=y).E[X]=E\big[E[X\mid Y]\big]=\sum_{y}E[X\mid Y=y]\,P(Y=y).

Read it as: “condition on whatever you wish you knew, solve the easy conditional problem, then average over the thing you conditioned on.” This is exactly the engine behind first-step analysis — there YY is the outcome of the first step.

The tower property turns a hard unconditional expectation into a menu of easy conditional ones. Choosing the right YY (the first coin flip, the first move, the number of successes so far) is the whole game, and it directly generalizes the state-recursion method of Unit 8's Markov chains.

Example
A random number of dice (compound expectation)

Roll a fair die to get a number NN; then roll NN fair dice and let SS be their total. Find E[S]E[S].

Solution. Condition on NN. Given N=nN=n, the inner sum has mean E[S∣N=n]=n⋅72E[S\mid N=n]=n\cdot\tfrac72, so as a random variable E[S∣N]=72NE[S\mid N]=\tfrac72 N. By the tower property,

E[S]=E[72N]=72 E[N]=72⋅72=494=12.25.E[S]=E\big[\tfrac72 N\big]=\tfrac72\,E[N]=\tfrac72\cdot\tfrac72=\tfrac{49}{4}=12.25.

This is Wald's identity in miniature: the mean of a random-length sum of i.i.d. terms is (expected length)×\times(term mean).

Example
Expected hitting time on a path (first-step analysis)

A frog sits at position kk on {0,1,2,3,4}\{0,1,2,3,4\} and each second hops left or right with equal probability; positions 00 and 44 are absorbing. Let hkh_k be the expected time to get absorbed. Conditioning on the first hop (the tower property with Y=Y= first move),

hk=1+12hk−1+12hk+1,h0=h4=0.h_k=1+\tfrac12 h_{k-1}+\tfrac12 h_{k+1},\qquad h_0=h_4=0.

Solving the symmetric system gives hk=k(4−k)h_k=k(4-k): h1=h3=3h_1=h_3=3 and h2=4h_2=4. This is the general gambler's-ruin duration k(N−k)k(N-k) on {0,…,N}\{0,\dots,N\}, derived here purely by conditioning on the first step.

Tip

Recipe. To use the tower property: (1) pick a variable YY that, once known, makes XX easy to average; (2) write E[X∣Y=y]E[X\mid Y=y] for each yy; (3) average against P(Y=y)P(Y=y). When YY is “the first step,” this reproduces the one-equation-per-state method — conditional expectation and first-step analysis are the same tool wearing different hats.

Probability Generating Functions & the Tail-Sum Formula

Concept
Encoding a distribution in a single function

For a nonnegative integer-valued XX, its probability generating function (PGF) packs all the probabilities into one power series:

GX(s)=E[sX]=∑k≥0P(X=k) sk.G_X(s)=E\big[s^X\big]=\sum_{k\ge 0}P(X=k)\,s^k .

Three facts make PGFs powerful on contests:

  • Normalization: GX(1)=∑kP(X=k)=1G_X(1)=\sum_k P(X=k)=1.
  • Coefficients are probabilities: the coefficient of sks^k in GX(s)G_X(s) is exactly P(X=k)P(X=k), so extracting one coefficient answers a “what is the chance the total is kk” question with pure polynomial bookkeeping.
  • Sums multiply: if X,YX,Y are independent, then GX+Y(s)=GX(s) GY(s)G_{X+Y}(s)=G_X(s)\,G_Y(s). Convolving distributions becomes multiplying polynomials.

For the mean, the workhorse is the tail-sum formula: for a nonnegative integer variable,

E[X]=∑k≥1P(X≥k).E[X]=\sum_{k\ge 1}P(X\ge k).

It re-derives many waiting-time means in one line and is often the fastest route when the tail probabilities P(X≥k)P(X\ge k) are simpler than the point probabilities P(X=k)P(X=k).

Example
PGF of a sum, then a tail-sum shortcut

PGF part. A single die has PGF G(s)=16(s+s2+⋯+s6)G(s)=\tfrac16(s+s^2+\cdots+s^6). The sum SS of two independent dice therefore has GS(s)=G(s)2G_S(s)=G(s)^2; the coefficient of s7s^7 in G(s)2G(s)^2 is 636=16\tfrac{6}{36}=\tfrac16, recovering P(S=7)=16P(S=7)=\tfrac16 by polynomial multiplication rather than casework. And by linearity of expectation, E[S]=E[die 1]+E[die 2]=72+72=7E[S]=E[\text{die 1}]+E[\text{die 2}]=\tfrac72+\tfrac72=7 — no new machinery needed for the mean.

Tail-sum part. Roll a die until the first 66; let NN be the number of rolls. Then P(N≥k)=(56)k−1P(N\ge k)=\big(\tfrac56\big)^{k-1} (the first k−1k-1 rolls all miss). So

E[N]=∑k≥1P(N≥k)=∑k≥1(56)k−1=11−56=6,E[N]=\sum_{k\ge 1}P(N\ge k)=\sum_{k\ge 1}\Big(\tfrac56\Big)^{k-1}=\frac{1}{1-\tfrac56}=6,

recovering the geometric mean 1/p1/p with a single geometric series and no distribution-by-distribution bookkeeping.

Tip

Key insight. Reach for a PGF when a problem involves a sum of independent variables: multiply their PGFs and read the answer off a coefficient. Reach for linearity of expectation for means of sums. Reach for the tail-sum formula E[X]=∑k≥1P(X≥k)E[X]=\sum_{k\ge 1}P(X\ge k) when the “at least kk” probabilities are clean — it turns a mean into a single series and is the slickest derivation of most waiting-time expectations.

Why It Works

Linearity: E[X+Y]=∑ω(X(ω)+Y(ω))P(ω)=∑ωX(ω)P(ω)+∑ωY(ω)P(ω)=E[X]+E[Y]E[X + Y] = \sum_\omega(X(\omega) + Y(\omega))P(\omega) = \sum_\omega X(\omega)P(\omega) + \sum_\omega Y(\omega)P(\omega) = E[X] + E[Y] — the sum splits term by term with no assumption about how XX and YY relate. The expected number of fixed points of a random permutation is therefore n⋅1n=1n\cdot\tfrac1n = 1 by indicators, a computation that would be miserable through the distribution. The geometric wait 1p\tfrac1p comes from the first-step equation E=1+(1−p)EE = 1 + (1 - p)E.

Tip
Reading a proof

Do not read a proof the way you read a rule. Cover the last line, ask what the previous line forces, and only then uncover it. If a step feels like magic, that is the step to work by hand with a concrete number.

Formulas, Proofs & Tips

Tip
Expected value and linearity
E[X]=∑xiP(xi),E[X+Y]=E[X]+E[Y]E[X]=\sum x_i P(x_i),\qquad E[X+Y]=E[X]+E[Y]

What it means. The long-run average outcome; expectations add even when the variables interact.

Example. A fair die: E[X]=1+2+3+4+5+66=3.5E[X]=\tfrac{1+2+3+4+5+6}{6}=3.5.

Why it works. E[X]E[X] weights each outcome by how often it happens. Linearity holds because summing over the joint distribution can be regrouped one variable at a time — no independence is needed.

Tip. Linearity is the workhorse: break a complicated count into indicator variables (11 if an event happens, 00 if not) and add their expectations.