Sums, convolution and generating functions

Two uncertainties, added up

Take two independent random variables, X and Y, and form their sum S=X+Y. Each has its own distribution. If X is the time a first server takes and Y the time a second takes, then S is the total time. If X is the error of one sensor and Y the error of another, S is the combined error. The sum is a new random variable, so it has a new distribution, and we want to compute it from the two inputs. Independence is what makes this tractable: it lets us multiply probabilities of the pieces.

The simplest case makes the shape of the answer obvious. Roll two fair dice and ask for the chance that the total is seven. There are six equally likely pairs, (1,6),(2,5),(3,4),(4,3),(5,2),(6,1), out of thirty-six possibilities, so the probability is 6/36=1/6. The count six is not an accident: it is the number of ways to split seven into one value for the first die and one for the second. To get the probability of any total s, count the pairs (t,s-t) with both coordinates in $\{1,\dots,6\}$ and divide by thirty-six. Probability of a sum is a sum over the ways the summands could have combined.

Push that counting idea to a continuum. If X has density f and Y has density g, the probability that $t\le X\le t+dt$ is $f(t)\,dt$, and the probability that $s\le X+Y\le s+ds$ given X=t is $g(s-t)\,ds$. Multiply and integrate over every possible t, and the density of the sum appears. That integral is the convolution of f and g. It is the exact analogue of the dice count, with the sum over the six values replaced by an integral over a continuum of values.

Two facts make this more than a formula. First, convolution is a smoothing operation: it tends to smear sharp features and produce something more bell-like than either input. That is a hint of the central limit theorem. Second, some families keep their shape under convolution — a Gaussian plus a Gaussian is a Gaussian, a Poisson plus a Poisson is a Poisson, a Cauchy plus a Cauchy is a Cauchy. These are the stable families, and knowing them saves enormous amounts of computation. This part builds the convolution picture, then the transform that turns it into multiplication, then the stability story that explains why the Gaussian is unavoidable.

Reflect, slide, and measure the overlap

For independent discrete variables the rule is a sum. If X and Y are independent with pmfs p and q, then the event X+Y=s is the disjoint union of the events $X=t,\;Y=s-t$ over all t, and independence lets the joint probability factor. The pmf of the sum is therefore $(p*q)(s)=\sum_t p(t)\,q(s-t)$. For the two dice, p and q are both the flat distribution on $\{1,\dots,6\}$, and the sum runs over the six values that keep both arguments in range — exactly the count we did by hand.

For densities the same argument with probabilities of small intervals gives the convolution integral. Read it geometrically and it becomes a picture: take the graph of g, flip it about the vertical axis to get g(-t), then slide it right by s to get g(s-t). Multiplying by f(t) and integrating accumulates the area where the two graphs overlap. As s sweeps across the line, that overlap area traces out the density of the sum. Nothing is being sampled, nothing is being approximated — the overlap is the answer.

Try it on two uniforms. Let X and Y each be uniform on [0,1]. When s is small the sliding rectangle overlaps the fixed one only partly, and the overlap grows linearly; when s passes one half the overlap starts shrinking. The result is the tent-shaped triangular density on [0,2], rising then falling, not flat at all. Two flat distributions convolved once already produce a peak. Convolve a third uniform and the corners round off; keep going and the shape marches steadily toward a Gaussian. That is convolution the smoothing machine at work.

The demo below makes the mechanics visible. The top panel shows the fixed density f(t) and the reflected, shifted density g(s-t), with their product shaded — that shaded area is (f*g)(s) for the current position of the slider. The bottom panel accumulates those areas into the full convolution curve, marks the current value, and overlays a histogram of sums drawn from the two distributions with a fixed seed. Switch between normal, uniform and exponential pairs to see how differently two of the same family combine.

Convolution is commutative and associative, and both facts matter. Commutative because X+Y and Y+X have the same distribution; associative because the sum of three variables can be grouped however you like, so the distribution of X+Y+Z is the convolution of any one of them with the convolution of the other two. It also distributes over mixing: if X is a mixture of two components, each component convolves separately and the results mix with the same weights. Convolution is linear in each argument, which is the reason the transform in the next section can exist at all.

Turn the integral into a product

Convolution integrals are rarely doable in closed form, and iterating them for many summands is hopeless. The way out is a change of viewpoint: instead of working with the density, attach to each variable a function that carries the same information but behaves well under addition. The moment-generating function does exactly that. For a random variable X and a real parameter t near zero, it is the expectation $M_X(t)=\mathbb{E}[e^{tX}]$. For a discrete variable this is the sum $\sum_k e^{tk}p(k)$; for a continuous one it is $\int e^{tx}f(x)\,dx$. Either way it is a weighted average of exponentials, and it exists whenever that average is finite.

The product rule is the whole point, and the proof is one line. Because e^{t(X+Y)}=e^{tX}e^{tY}, and because the expectation of a product factors when the variables are independent, $\mathbb{E}[e^{t(X+Y)}]=\mathbb{E}[e^{tX}]\,\mathbb{E}[e^{tY}]$. The convolution of densities corresponds exactly to the product of these functions. Repeating for n independent summands gives $M_{X_1+\cdots+X_n}(t)=M_{X_1}(t)\cdots M_{X_n}(t)$, so the distribution of a long sum is encoded in the n-th power of a single function. That is the computation the law of large numbers and the central limit theorem are built on.

The name is deserved: differentiating under the expectation gives $M_X'(0)=\mathbb{E}[X]$, $M_X''(0)=\mathbb{E}[X^2]$, and in general the k-th derivative at zero is the k-th moment. So the mgf is a moment factory, and its Taylor coefficients are the moments of the distribution. If the mgf is finite in an open interval around zero it also determines the distribution uniquely, which is what licenses the standard proof of the CLT: show the mgf of a standardised sum converges to e^{t^2/2}, and conclude the distributions converge to the standard normal.

One caveat has better manners than it first appears. The mgf need not exist: for a Cauchy variable, $\mathbb{E}[e^{tX}]$ is infinite for every $t\ne0$ because the tails decay only like 1/x^2. The characteristic function repairs this. Replace the real parameter by an imaginary one, $\varphi_X(t)=\mathbb{E}[e^{itX}]=\mathbb{E}[\cos(tX)]+i\,\mathbb{E}[\sin(tX)]$, and the integrand has modulus one, so the integral always converges. The characteristic function obeys the same product rule and determines the distribution just as well. It is the universal tool; the mgf is the convenient special case that works for the light-tailed families you meet most often.

The panel below compares four pairs. Click a pair to see the mgf of a single variable, the product of the two identical mgfs, and the mgf computed numerically from the distribution of the sum; the product and the sum agree curve for curve. The small second plot shows what that sum actually looks like. Normal stays normal, Poisson stays Poisson, the sum of two uniforms turns into a triangle, and for Cauchy the panel switches to the characteristic function because the mgf does not exist at all.

Notice how little the product rule cares about the shape of the density. It works for discrete and continuous variables at once, for finite and infinite supports, for any two independent pieces. That universality is why generating functions are the standard language for sums. When you later meet probability-generating functions, cumulants, or the log of the mgf — the cumulant-generating function, which turns the product into a sum — you are meeting the same idea in different clothes.

Families that survive addition, and the one that breaks averaging

Apply the product rule to two independent Gaussians, $X\sim N(\mu_1,\sigma_1^2)$ and $Y\sim N(\mu_2,\sigma_2^2)$. The mgf of a Gaussian is $M_X(t)=\exp(\mu_1 t+\tfrac12\sigma_1^2t^2)$; multiply the two and the exponents add, giving exactly the mgf of a normal with mean $\mu_1+\mu_2$ and variance $\sigma_1^2+\sigma_2^2$. So the sum of independent Gaussians is Gaussian. Variances add, means add, and the family is closed under addition — this is what people mean when they call the Gaussian stable.

Stability is not unique to the Gaussian. A Poisson with rate $\lambda_1$ plus an independent Poisson with rate $\lambda_2$ is Poisson with rate $\lambda_1+\lambda_2$: the mgfs are $e^{\lambda_1(e^t-1)}$ and $e^{\lambda_2(e^t-1)}$, and their product is the mgf of the sum. Gammas with a common scale add their shape parameters. Bernoulli trials accumulate into a binomial. Each of these is a family that survives summation, which is why the family names line up so neatly with the operations that generate them. The continuous families and their mgfs are collected in the continuous families part, and the discrete ones in the discrete families part.

The Cauchy is stable too, and that is precisely the problem. If X and Y are independent Cauchy variables with the same location x_0 and scales $\gamma_1$ and $\gamma_2$, then X+Y is Cauchy with location 2x_0 and scale $\gamma_1+\gamma_2$. You can see it from the characteristic function, $\varphi_X(t)=e^{ix_0t-\gamma|t|}$, which multiplies into the same form with the scales added. So a Cauchy plus a Cauchy stays Cauchy, and the average of n independent Cauchy variables is again Cauchy with the same scale — averaging does not concentrate it at all.

That failure has a signature you can feel in the demo. The Gaussian's tails decay like e^{-x^2/2}, so extreme values are so unlikely that the sample mean is pinned down with error shrinking like $1/\sqrt n$. The Cauchy's tails decay like 1/x^2, far too slowly for the mean to exist: the integral defining $\mathbb{E}[X]$ diverges, and with it every variance-based argument. One enormous observation can land at any moment and drag an average of thousands of samples with it. The sample mean wanders forever; it never settles, and the law of large numbers simply has nothing to say. This is the cleanest illustration that the central limit theorem's conclusion is not universal — it needs finite variance. Part 18 tells the positive side of that story, and the heavy-tail part takes the failure apart in detail.

So the Gaussian occupies a special seat: it is stable, it is the fixed point toward which convolution of light-tailed densities drifts, and it is the distribution that the mgf route singles out when the number of terms grows. The uniform family illustrates the drift in miniature — one uniform is flat, two give a triangle, three give a smooth bump, and after a dozen the profile is indistinguishable from a Gaussian. Convolution is a machine that forgets the initial shape and remembers only the mean and variance.

Sums under everything

Every formula in one place

Where to go deeper

• William Feller, An Introduction to Probability Theory and Its Applications, Vol. II, chapter VI — the classical treatment of convolutions, generating functions and the stable laws.
• David Williams, Probability with Martingales, chapters 5 and 7 — mgfs and characteristic functions done carefully, including the inversion theorem.
• Geoffrey Grimmett and David Stirzaker, Probability and Random Processes, chapter 5 — sums of random variables with a good stock of worked examples.
• Rick Durrett, Probability: Theory and Examples, chapter 2 — the mgf proof of the central limit theorem and the role of finite variance.
• Grant Sanderson, "But what is a convolution?", 3Blue1Brown — the sliding-overlap picture animated, in the context of signal processing.