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.

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

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.}
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.

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

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.

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.

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

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.

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.

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

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.

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

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.

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.

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 by the Chinese-restaurant process: insert elements one at a time, each either sitting after some existing element or starting a new cycle. Element kk (the kk-th inserted) closes a new cycle exactly when it is the one that “points back to the start,” which happens with probability 1k\tfrac1k among its kk equally likely choices. So the number of cycles 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.

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.

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.