Generating functions for random batches

What you will learn

Encode finite count laws as PGFs, derive random-sum composition by conditioning and recover mean and variance through factorial derivatives.

Prerequisites: Convolving finite distributions · Conditional forecasts and the tower · Variance and standard deviation

Encode an entire count law in one polynomial

A toy packet counter receives a random number N of batches. The count law is P(N=0)=1/4, P(N=1)=1/2 and P(N=2)=1/4. A batch independently delivers either zero packets or two packets, each with probability one half. Let B be that batch size and S the total number of packets delivered. Zero batches means S=0, with no additional draw required. These are stipulated population probabilities, not fitted frequencies, card draws without replacement or real trading forecasts. Assume N is independent of an indefinitely available sequence of mutually independent batch sizes with the stated common law. Only the first N sizes enter S.

For a nonnegative integer count X, its probability generating function is G_X(z)=E[z^X]. In our finite setting this is simply a polynomial: the coefficient of z^k is P(X=k). The symbol z marks a count; it is not a random outcome or a probability parameter to estimate. Write G(z)=(1+z²)/2 for one batch and H(u)=(1+2u+u²)/4 for the number of batches. Missing powers have coefficient zero. The constant term retains the probability of no delivery, so deleting it destroys information. Evaluate at one to check total mass, but remember that a polynomial summing to one may still encode the wrong experiment.

Distinguish a fixed sum from a random number of terms

With exactly n independent batches, exponents add and probabilities multiply, giving the PGF G(z)^n. With a random count, first condition on N=n and then average those polynomials with the count probabilities. Thus K(z)=E[G(z)^N]=H(G(z)). This is composition: the inner polynomial describes one batch and the outer polynomial describes how many independent copies are used. Reversing the order models a different experiment. Writing H(z)G(z) would instead describe adding one independent batch size to the batch count, which has incompatible counting meaning here.

In this example K(z)=[1+2G(z)+G(z)²]/4. The N=0 branch contributes a constant even when every positive batch delivers packets. G(z)² alone forces two batches and discards the zero- and one-batch branches. The earlier convolution lesson derives a fixed-sum PMF from joint cells. Here the new reasoning step is choosing between multiplication and substitution based on a random stopping count. Independence of N and the batch sequence is essential: if the decision to include a second batch depended on the first delivery, the conditional batch law could change and the same substitution would need a new justification.

Expand by branches and independently count the outcomes

Put every contribution over denominator sixteen. The zero-batch branch contributes 4. The one-batch branch contributes 4+4z². The two-batch branch contributes 1+2z²+z⁴. Their sum is K(z)=(9+6z²+z⁴)/16. Consequently P(S=0)=9/16, P(S=2)=6/16 and P(S=4)=1/16. The coefficient of z is zero, not an omitted unknown. Normalization gives (9+6+1)/16=1. The chance of any delivery is 7/16, whereas the mean packet count below is one; these are different quantities with different units.

An independent check uses four equally likely count tickets labelled 0,1,1,2 and two fair delivery bits, even when some bits go unused. This creates sixteen equally likely elementary cases. The zero ticket produces four zero totals. Each of the two one-batch tickets produces two zero totals and two totals of two. The two-batch ticket produces totals 0,2,2,4. Combining counts gives nine zeros, six twos and one four without expanding a polynomial. Drawing unused bits is a verification device that leaves the delivered count unchanged; it does not add batches. This explicit experiment checks both the coefficient arithmetic and the treatment of the empty sum.

Derivatives count ordered selections, not ordinary squares

For a finite polynomial K(z)=Σp_k z^k, termwise differentiation gives K′(1)=Σk p_k=E[S]. A second derivative gives K″(1)=Σk(k−1)p_k=E[S(S−1)]. The factor k(k−1) counts ordered choices of two distinct packets. It is a factorial moment, not E[S²]. Since S²=S(S−1)+S, the variance is K″(1)+K′(1)−K′(1)². No limits or convergence interchanges are needed for these finite polynomials. A learner unfamiliar with calculus can apply these coefficient weights directly; that operation is exactly what the derivative notation summarizes.

The example yields K′(1)=(2×6+4×1)/16=1 and K″(1)=(2×1×6+4×3×1)/16=24/16=3/2. Hence Var(S)=3/2+1−1=3/2. Directly, E[S²]=(4×6+16×1)/16=5/2; subtract the mean squared to recover 3/2. As another structural check, the chain rule gives K′(1)=H′(1)G′(1)=E[N]E[B]=1×1. The second derivative of the composition is H″(1)G′(1)²+H′(1)G″(1)=1/2+1=3/2. These checks target different errors, including confusing a factorial moment with a raw second moment.

Build and audit a composition rather than copy a formula

In the workshop, move one of four count tokens from one N category to another. This changes H while preserving its normalization. Choose whether a successful batch delivers one or two packets. Then choose the appropriate polynomial operation and route each of six branch expansion terms to its resulting power. A term records the batch count n, successful batch count j and its probability numerator over sixteen. Its destination is z raised to j times the successful batch size. Several terms can land on the same power and must be combined. Even a zero-mass term keeps its structural destination, so changing weights later does not silently change the meaning of the expression.

The candidate coefficient ledger reflects your routing, including explicit zeros. Audit its first derivative, second factorial moment and variance. Moving a token or changing batch size clears every route and audit entry. Try placing all tokens at N=0: the correct polynomial is one, the mean and both higher quantities are zero, and every active contribution is constant. Then reset and switch to one-packet batches; the coefficients become (9+6z+z²)/16, mean 1/2, factorial moment 1/8 and variance 3/8. Hints explain the operation and weighting rules; completion is visit-only reasoning feedback, separate from account progress. A successful audit verifies this finite model, not independence or parameter accuracy in an external dataset.

Hands-on: Compose a random batch polynomial

Change the count law, route branch expansion terms and audit factorial derivatives.

Common mistakes

• Using G² because the largest possible count is two.
• Adding PGFs to describe a sum instead of conditioning on the random count.
• Dropping the constant term or confusing a power with its coefficient.
• Calling K″(1) the raw second moment or the variance.
• Assuming independent batch draws after a count was selected using their outcomes.

Keep these ideas

• The coefficient of z^k records the probability of count k.
• Fixed independent sums multiply PGFs; independent random counts compose them.
• Keep the empty sum and combine equal powers.
• First derivatives give means; second derivatives give factorial moments.
• Recover variance with K″(1)+K′(1)−K′(1)² and verify through explicit cases.

Further reading

• Lancaster MATH332: Generating functions and their properties ↗

  Read definition 3.1.1, proposition 3.1.2 and its coefficient, derivative and independence proofs, and corollary 3.1.3. Original random-batch composition derived by finite conditioning; packet example and workshop are original. No source exercises or video review claimed. Checked 2026-10-24.