Articles

Probability Generating Function Interview Questions: Random Sums and Waiting Counts

Practice probability generating function interviews with random-sum composition, count conventions, moment checks and a worked waiting-time model for two heads.

Probability generating function interview questions become manageable when you treat a PGF as a probability ledger whose exponents are counts. Multiplication handles independent sums; composition handles an independent random number of identically distributed summands. Derivatives recover moments, but the second derivative gives a factorial moment, not the variance.

This guide uses a small random-batch example and a two-state waiting model to show where those shortcuts work and where they fail.

Evidence boundary: primary university notes support the mathematical properties cited here. The batch distribution, dependence counterexample and waiting-state derivation are original worked preparation.

Define the count and read its coefficients

Primary definition: for a nonnegative integer-valued random variable X, its PGF is G_X(z) = E[z^X] = sum P(X=k)*z^k. The coefficient of z^k is the probability of count k. Durham Probability II

Suppose a batch contributes either zero or two items, each with probability one half. Its PGF is G_X(z) = (1+z²)/2. The missing linear term means P(X=1)=0; it does not mean a missing observation. The constant term is the probability of zero.

Evaluate at one to check normalization: G_X(1)=1. Evaluate at zero to recover P(X=0)=1/2. The constant term is retained in this evaluation, including the usual power-series convention for the zero exponent.

Do not silently use an ordinary PGF for a signed profit or a continuous measurement. You may need a shifted integer count, a Laurent series, or a different transform. Explain the support before choosing the tool. A dollar amount and the number of successful events are different random variables even if the story contains both.

Also distinguish the PGF variable z from a random outcome. It is an algebraic argument that helps package probabilities. Setting z to a convenient number is meaningful only when the expectation or series converges there.

Recover mean and variance without confusing derivatives

Primary moment identities: when the relevant moments are finite, the first derivative at one gives E[X], and the second gives E[X(X-1)]. Consequently, Var(X)=G''(1)+G'(1)-G'(1)². For an infinite-support count, approach the boundary carefully rather than assuming all derivatives are finite. Cambridge generating-function notes

For our batch variable, G'(z)=z and G''(z)=1. Thus the mean is 1, the second ordinary moment is 1+1=2, and the variance is 2-1²=1. Direct enumeration gives the same result: half the mass at zero and half at two.

The missing correction term matters. Calling G''(1) the variance happens to produce 1 in this particular example, but only by coincidence. Change X to a constant two: its PGF is z², its second derivative at one is 2, and its variance is zero.

Derivatives at zero answer coefficient questions: P(X=k)=G^(k)(0)/k!. They are not interchangeable with derivatives at one. In an interview, state which question you are answering before doing the differentiation.

Explain why independent sums multiply

Primary property: independent nonnegative integer counts have a sum PGF equal to the product of their individual PGFs. Independence is the step that allows the expectation of a product to factor. Durham convolution property

For two independent copies of our batch variable, square (1+z²)/2. The result is 1/4 + z²/2 + z⁴/4. There are four equally likely ordered batch outcomes: (0,0), (0,2), (2,0) and (2,2). The middle two outcomes share a total, which explains the coefficient one half.

Now let the second batch always equal the first. Each marginal PGF is unchanged, but their sum is zero or four with equal probability. Its PGF is (1+z⁴)/2, with no mass at two. The product of marginal PGFs would invent outcomes the joint process cannot produce.

This contrast is a useful follow-up to linearity of expectation. Both sums have mean 2, but their distributions and variances differ. You can calculate a sum's mean without independence; you cannot generally multiply its marginal PGFs without it.

Derive a random sum by conditioning on its count

Let N be the number of batches, independent of all batch sizes. In our original example, N is zero with probability one half, one with probability one quarter, and two with probability one quarter. Every batch size is an independent copy of X above. Define S = X_1 + ... + X_N, with an empty sum equal to zero.

The count PGF is G_N(u)=1/2+u/4+u²/4. Conditional on N=n, the total has PGF G_X(z)^n. Averaging those conditional functions gives G_S(z)=G_N(G_X(z)). The count function is outside; the batch function goes inside. Duke random-sum exercise

Substitution yields G_S(z)=11/16+z²/4+z⁴/16. Reconstruct it from the count cases rather than trusting substitution alone:

Number of batches	Contributions to total probabilities
N=0, probability 1/2	Add 1/2 to total zero.
N=1, probability 1/4	Add 1/8 each to totals zero and two.
N=2, probability 1/4	Add 1/16, 1/8 and 1/16 to totals zero, two and four.

Therefore totals zero, two and four have probabilities 11/16, 4/16 and 1/16. They sum to one and respect the even-valued support. Our local exact-fraction fixture independently enumerates the ordered outcomes and reproduces the polynomial coefficients.

The mean total is 3/4. Directly, it is 2*(4/16)+4*(1/16). The second moment is 4*(4/16)+16*(1/16)=2; variance is 2-(3/4)²=23/16. This is a complete distribution check, not a simulation estimate.

What breaks if the count depends on the summands?

Retain independent batch variables with values zero or two, but now set N=1 when the first batch is two and N=0 when it is zero. N's marginal distribution is an equal-probability zero/one count. However, knowing N=1 tells you the first batch is two.

The actual total is zero or two with probability one half each. Composing the marginal functions would instead give 3/4+z²/4. That false answer predicts a mean of one half instead of the actual mean one.

The failure is not that the PGF representation stopped working. The conditional law of the selected summand changed, so the step E[z^S | N=n]=G_X(z)^n was invalid. Write the conditional law you actually have and average that instead.

A count determined by stopping after a qualifying outcome is a similar warning. Do not call a random sum “compound” and assume an independently sampled count when the same observations determine when sampling ends.

Does geometric count failures or total trials?

Assume independent Bernoulli trials with success probability p, where p is positive and no greater than one, and write q=1-p. If F counts failures before the first success, its probabilities are P(F=k)=q^k*p for k starting at zero. Summing the series gives G_F(z)=p/(1-qz).

If T counts total trials including that success, then T=F+1 and G_T(z)=z*G_F(z). For a fair coin, P(F=0)=1/2 but P(T=0)=0; their means are 1 and 2 respectively.

These are original checks of the counting convention, using the geometric-series construction explained in the Cambridge notes. Neither formula should be memorized without its starting index. At p=1, F is identically zero and T identically one, which makes a useful boundary check.

A shift multiplies the PGF by z; doubling a count replaces z with z². Confusing those operations makes the support wrong even if the function still evaluates to one at z=1.

Build a waiting model for two consecutive Heads

Waiting for HH is not the same as adding two independent waits for Heads. A tail after the first head destroys the partial match. Our original fair-coin model tracks state 0, with no current matching suffix, and state 1, with one trailing head. Completion is absorbing.

Let F0(z) and F1(z) describe additional tosses until completion from the two transient states. One more toss costs a factor z. From state 0, tails stays in state 0 and heads moves to state 1. From state 1, tails resets to state 0 and heads finishes.

Starting state	First-step equation
No trailing head	`F0 = z*(F0/2 + F1/2)`
One trailing head	`F1 = z*(F0/2 + 1/2)`

The completion term is one because zero further tosses remain after the finishing head. Solving gives F0(z)=z²/(4-2z-z²). It has no constant or linear term, as HH cannot appear before two tosses. At z=1 it equals one; its derivative there is 6.

The first-hit probabilities for two, three and four tosses are 1/4, 1/8 and 1/8. For four tosses, the qualifying prefixes are TTHH and HTHH; a prefix containing HH earlier does not count again. Our fixture enumerates every prefix through length 12 and checks these probabilities against the generating-function recurrence.

Do not confuse this PGF with the generating function of the survival probabilities P(T>n). The coefficients answer different questions. A finite truncation of either series is also not a new normalized waiting distribution unless you explicitly condition or assign the remaining tail.

Check a proposed answer before presenting it

First inspect possible exponents, zero-count mass and coefficient signs. Then check normalization, one independently computed probability and a moment when it exists. For a random sum, state independence between N and the summands separately from independence among summands.

For a waiting problem, explain why the state stores enough history. A state that forgets a relevant suffix can produce internally tidy algebra for the wrong process. With longer or competing patterns, add the suffix states needed after each outcome; do not restart blindly after every mismatch.

Finally, keep finite-horizon computation and infinite-horizon claims separate. Durham's notes discuss the boundary mass as the probability of a finite count. A formal count generating series can be defective when noncompletion has positive probability. Check termination before interpreting its derivative as an unconditional finite mean.

Five related questions to rehearse

The random-batch and HH derivations above are original. These verified prompts offer direct applications or carefully stated extensions.

Practice question	PGF practice focus
Compute extinction probability in a branching process	Write the offspring PGF and distinguish two-generation extinction from eventual extinction.
Solve quick probability questions	Reconstruct dice-sum coefficients by convolution.
Prove Equal Probability Impossible with Relabeled Dice Faces	Express face multiplicities as polynomial coefficients before attempting the proof.
Solve Exact Probability and Expected-Value Exercises	Extend suffix states to the prompt's competing coin patterns.
Expected Number of Runs in Coin Tosses	Separate an indicator-based mean from a full dependent count distribution.

Start with the branching-process exercise, then explain precisely which random count supplies the outside function in a composition.