N-Fold Convolution for IID Sums

Why Repeated Convolution Matters

A convolution describes how the possible values of two independent random variables combine. When a sum contains \(n\) independent variables with the same distribution, the same operation can be applied repeatedly: first to two variables, then to their sum and a third variable, and so on. This gives a direct way to calculate the entire distribution of a fixed-size IID sum.

The recursion is useful even when no familiar named distribution describes the answer. It also makes the role of the common law explicit: each new variable contributes the same probability mass function or density at every step. The formulas below treat discrete and absolutely continuous variables separately, using \(p\) for a probability mass function and \(f\) for a density.

Definition: \(X_1,\ldots,X_n\) are independent and identically distributed (IID) if they are mutually independent and each has the same distribution. Write \(S_n=X_1+\cdots+X_n\). The \(n\)-fold convolution of their common law is the distribution of \(S_n\), obtained by starting with the common law and recursively convolving with it.

The Recursive Formulas

In the discrete case, suppose each \(X_i\) takes values in a countable set and has probability mass function \(p(x)=P(X_i=x)\). Write \(p_n(s)=P(S_n=s)\), with \(p_1=p\). Independence gives the recurrence

p_{n+1}(s)=\sum_x p_n(s-x)\,p(x).

The sum is over the values \(x\) that \(X_{n+1}\) can take; terms with impossible values of \(S_n=s-x\) are zero. When the variables take integer values, this is conventionally written as a sum over all integers \(x\). In particular, \(p_2(s)=\sum_x p(s-x)p(x)\). Applying the same operation repeatedly gives \(p_n\).

Theorem: If \(X_1,X_2,\ldots\) are IID discrete random variables with mass function \(p\), then \(p_1=p\) and, for every \(n\geq1\), \(p_{n+1}(s)=\sum_x p_n(s-x)p(x)\). Thus the mass function of \(S_n\) is the recursively defined \(n\)-fold convolution of \(p\).

Proof. The sum \(S_n\), being a function of \(X_1,\ldots,X_n\), is independent of \(X_{n+1}\). For each possible value \(x\) of \(X_{n+1}\), the event \(S_n+X_{n+1}=s\) requires \(S_n=s-x\). The possible values of \(X_{n+1}\) partition the relevant event, so the law of total probability and independence give

\begin{aligned} P(S_{n+1}=s) &=\sum_x P(S_n=s-x,\ X_{n+1}=x)\\ &=\sum_x P(S_n=s-x)P(X_{n+1}=x)\\ &=\sum_x p_n(s-x)p(x). \end{aligned}

For a countably infinite support, the terms are nonnegative, so this sum is well-defined. Since \(S_1=X_1\), its mass function is \(p_1=p\), completing the recursion. \(\square\)

For absolutely continuous variables, assume each \(X_i\) has density \(f\), and write \(f_n\) for the density of \(S_n\), with \(f_1=f\). The corresponding recurrence is

f_{n+1}(s)=\int_{-\infty}^{\infty} f_n(u)f(s-u)\,du.

The integrand pairs a possible partial sum \(u\) with the value \(s-u\) required from the next variable. This formula gives a density, so values that differ only on a set of Lebesgue measure zero represent the same distribution.

Theorem: If \(X_1,X_2,\ldots\) are IID absolutely continuous random variables with density \(f\), then \(S_n\) has a density \(f_n\) satisfying \(f_1=f\) and \(f_{n+1}(s)=\int_{-\infty}^{\infty} f_n(u)f(s-u)\,du\), for almost every \(s\).

Proof. As in the discrete case, \(S_n\) and \(X_{n+1}\) are independent. Their joint density is therefore \(f_n(u)f(x)\). For any Borel set \(A\), the probability that their sum lies in \(A\) is

P(S_{n+1}\in A) =\int_{\mathbb R}\int_{\mathbb R} \mathbf{1}_A(u+x)f_n(u)f(x)\,dx\,du.

The integrand is nonnegative, so Tonelli's theorem allows the order of integration to be changed. For each fixed \(u\), make the translation \(s=u+x\), which has \(dx=ds\). Then

\begin{aligned} P(S_{n+1}\in A) &=\int_{\mathbb R}\int_{\mathbb R} \mathbf{1}_A(s)f_n(u)f(s-u)\,du\,ds\\ &=\int_A \left(\int_{\mathbb R} f_n(u)f(s-u)\,du\right)ds. \end{aligned}

The inner function is nonnegative and measurable, and its integral over \(s\in\mathbb R\) is \(1\): Tonelli's theorem and translation invariance give \(\int f_n(u)\,du\int f(s-u)\,ds=1\). It is therefore a density of \(S_{n+1}\), proving the recurrence. The base case is \(f_1=f\). \(\square\)

Worked Discrete Example

Worked Example: Three Variables With a Three-Point Law

Let each \(X_i\) take values \(0,1,2\), with \(p(0)=1/2\), \(p(1)=1/3\), and \(p(2)=1/6\). Find the distribution of \(S_3=X_1+X_2+X_3\) by applying the recursion.

First convolve \(p\) with itself. The support of \(S_2\) is \(0,1,2,3,4\), and the recurrence gives

\begin{aligned} p_2(0)&=(1/2)(1/2)=1/4,\\ p_2(1)&=(1/2)(1/3)+(1/3)(1/2)=1/3,\\ p_2(2)&=(1/2)(1/6)+(1/3)(1/3)+(1/6)(1/2)=5/18,\\ p_2(3)&=(1/3)(1/6)+(1/6)(1/3)=1/9,\\ p_2(4)&=(1/6)(1/6)=1/36. \end{aligned}

For the second convolution, \(S_3\) ranges from \(0\) to \(6\). For example, \(p_3(2)=p_2(0)p(2)+p_2(1)p(1)+p_2(2)p(0)=1/24+1/9+5/36=7/24\). Applying the same recurrence at each possible sum gives

\begin{aligned} p_3(0)&=1/8, & p_3(1)&=1/4, & p_3(2)&=7/24,\\ p_3(3)&=11/54, & p_3(4)&=7/72, & p_3(5)&=1/36,\\ p_3(6)&=1/216. \end{aligned}

As a check, putting these probabilities over denominator \(216\) gives numerators \(27,54,63,44,21,6,1\). Their sum is \(216\), so the probabilities total \(1\). The support also runs from \(0\) to \(6\), as expected from adding three values between \(0\) and \(2\).

Worked Continuous Examples

Worked Example: Three Uniform Variables

Let \(X_1,X_2,X_3\) be IID uniform on \([0,1]\), so \(f(x)=1\) for \(0<x<1\) and \(0\) otherwise. First, for \(0<s<2\), the convolution integral for \(S_2\) is over \(u\) such that both \(u\) and \(s-u\) lie in \([0,1]\). Thus \(u\) ranges from \(\max(0,s-1)\) to \(\min(1,s)\), and

f_2(s)= \begin{cases} s,&0<s<1,\\ 2-s,&1\leq s<2,\\ 0,&\text{otherwise}. \end{cases}

For the next convolution, the integrand is \(f_2(u)\), restricted to \(s-1\leq u\leq s\) by the support of the last uniform variable. If \(0<s<1\), this gives \(f_3(s)=\int_0^s u\,du=s^2/2\). If \(1\leq s<2\), split the integral at \(u=1\):

\begin{aligned} f_3(s) &=\int_{s-1}^{1}u\,du+\int_{1}^{s}(2-u)\,du\\ &=-s^2+3s-\frac32. \end{aligned}

Each \(X_i\) has the same distribution as \(1-X_i\). Consequently \(S_3\) has the same distribution as \(3-S_3\), so its density on \(2<s<3\) is the reflection of the density on \(0<s<1\). The complete density, up to endpoint values, is

f_3(s)= \begin{cases} s^2/2,&0<s<1,\\ -s^2+3s-\frac32,&1\leq s<2,\\ (3-s)^2/2,&2\leq s<3,\\ 0,&\text{otherwise}. \end{cases}

For example, the middle expression is \(1/2\) at \(s=1\) and \(s=2\), matching the adjacent pieces there. The density is supported on \([0,3]\), the range of the sum.

Worked Example: Three Exponential Variables

Suppose each \(X_i\) has exponential density \(f(x)=2e^{-2x}\) for \(x>0\), and zero otherwise. For \(s>0\), the two-variable recurrence integrates from \(0\) to \(s\):

f_2(s)=\int_0^s 2e^{-2u}\,2e^{-2(s-u)}\,du =4s e^{-2s}.

Convolving once more gives

\begin{aligned} f_3(s) &=\int_0^s 4u e^{-2u}\,2e^{-2(s-u)}\,du\\ &=8e^{-2s}\int_0^s u\,du =4s^2e^{-2s},\qquad s>0. \end{aligned}

This is zero for \(s\leq0\). To check its total mass, integration by parts twice gives \(\int_0^\infty s^2e^{-2s}\,ds=1/4\), so \(\int_0^\infty 4s^2e^{-2s}\,ds=1\). The support and normalization are both consistent with a density for a sum of positive variables.

Using the Recursion Carefully

A practical calculation starts with the common law and applies the same recurrence one variable at a time. In the discrete case, list the possible sums at each stage and add the corresponding products of probabilities. In the continuous case, determine the integration region from the supports before evaluating the integral; this often reduces an integral over the whole real line to a finite interval. The result after \(n-1\) recursive steps is the distribution of \(S_n\).

The assumptions matter. Independence supplies the product in each recurrence; without it, the joint probabilities or joint density need not factor. Identical distribution means the same \(p\) or \(f\) is used at every step. For independent variables with different laws, successive convolutions still use the appropriate law at each step, but the repeated-\(p\) or repeated-\(f\) description no longer applies.

Common pitfall: Do not use \(f\) to denote a discrete probability mass function and then use the same symbol for a density. In the discrete recurrence, \(p(x)\) is a probability and the operation is a sum. In the continuous recurrence, \(f(x)\) is a density and the operation is an integral. Also, a convolution formula cannot be justified by identical distributions alone: independence is what makes the joint law factor into the product used in the derivation.

Key takeaway: For a fixed number \(n\) of IID variables, initialize with the common mass function \(p_1=p\) or density \(f_1=f\), then convolve with that same law recursively until reaching \(p_n\) or \(f_n\), the law of the sum.

Check Your Understanding

Answer each question by using the recursive formulas and their assumptions.

State the recurrence for \(p_{n+1}(s)\) when the IID variables are discrete.
Why does the continuous recurrence integrate \(f_n(u)f(s-u)\) over \(u\)?
If a discrete variable takes only the values \(0\) and \(1\), what are the smallest and largest possible values of the sum of five IID copies?
For the exponential example with rate \(2\), what integration limits arise when forming \(f_3(s)\) for \(s>0\), and why?
Which assumption allows the joint law of \(S_n\) and \(X_{n+1}\) to factor in the proof of each recurrence?