Convolutions

Learning Objectives

Convolution is the fundamental operation for finding the distribution of sums of independent random variables. It appears everywhere in probability, signal processing, and deep learning. By the end of this section, you will master this essential tool.

1. Understand the convolution operation geometrically as a "flip-and-slide" integration that computes the PDF of $Z = X + Y$
2. Compute discrete convolutions for PMFs by summing products over all ways to achieve each sum
3. Evaluate continuous convolutions using the integral formula and understand when closed-form solutions exist
4. Use MGFs and characteristic functions to bypass integration entirely—transforming convolution into simple multiplication
5. Recognize common convolution results: normal + normal = normal, exponential + exponential = gamma, uniform + uniform = triangular
6. Connect to AI/ML applications: how convolution underlies CNNs, diffusion models, and the Central Limit Theorem

The Big Picture

"Convolution is the language of sums. When you add independent random variables, their probability distributions convolve."

Consider the fundamental question: if $X$ and $Y$ are independent random variables with known distributions, what is the distribution of their sum $Z = X + Y$?

This is exactly what convolution answers. The operation works by asking: "In how many ways can we get $Z = z$?" We must sum over all possible combinations where $X = x$ and $Y = z - x$.

The Core Insight

For each possible value $z$ of the sum:

1. Consider every possible value $x$ that $X$ could take
2. For each such $x$, $Y$ must equal $z - x$
3. Multiply the probabilities (or densities) of these events
4. Sum (or integrate) over all possible $x$ values

Historical Origins

Abraham de Moivre (1667-1754)

The roots of convolution trace to de Moivre's work on the binomial distribution. When he asked "what is the distribution of the sum of many Bernoulli trials?", he was implicitly performing discrete convolutions. His discovery that this approaches a bell curve was the first glimpse of the Central Limit Theorem.

Pierre-Simon Laplace (1749-1827)

Laplace formalized the convolution operation in his work on probability and celestial mechanics. He recognized that the "characteristic function" (what we now call the Laplace transform) converts convolution into multiplication—a crucial computational insight that remains central today.

Fourier and the Transform Revolution

Joseph Fourier's work on heat conduction led to the Fourier transform, which has the remarkable property that convolution in the "time domain" equals multiplication in the "frequency domain". This is the Convolution Theorem—the reason FFT (Fast Fourier Transform) makes convolution efficient.

Discrete Convolution

For discrete random variables with PMFs $p_X$ and $p_Y$, the PMF of $Z = X + Y$ is given by the discrete convolution:

This formula says: to find $P(Z = z)$, sum over all ways to partition$z$ into $x$ and $z - x$, multiplying the respective probabilities.

Example: Sum of Two Fair Dice

Consider rolling two fair dice $X, Y \sim \text{Uniform}\{1, 2, 3, 4, 5, 6\}$. The sum $Z = X + Y$ ranges from 2 to 12. For example:

Only terms where $7 - x \in \{1, ..., 6\}$ contribute:

There are 6 ways to roll 7: (1,6), (2,5), (3,4), (4,3), (5,2), (6,1). This is why 7 is the most likely sum!

Continuous Convolution

For continuous random variables with PDFs $f_X$ and $f_Y$, the PDF of $Z = X + Y$ is given by the convolution integral:

This is the continuous analog of the discrete sum. The notation $f * g$denotes the convolution of $f$ and $g$.

The "Flip and Slide" Interpretation

The convolution $(f * g)(z)$ can be visualized as:

1. Flip: Reflect $g(x)$ to get $g(-x)$
2. Shift: Slide the flipped function by $z$ to get $g(z - x)$
3. Multiply: Compute $f(x) \cdot g(z - x)$ at each $x$
4. Integrate: Sum up the product (area under the curve)

Example: Sum of Two Uniform(0, 1)

Let $X, Y \sim \text{Uniform}(0, 1)$. Both have PDF$f(x) = 1$ for $x \in [0, 1]$.

For $0 \leq z \leq 1$:

For $1 < z \leq 2$:

This gives a triangular distribution on $[0, 2]$ with peak at 1!

Interactive Visualization

The following visualization shows the convolution operation in action. Watch how the flipped second function slides across the first, with the integral of their product (purple shaded area) tracing out the convolution result.

Key Properties of Convolution

1. Commutativity

The order doesn't matter: $X + Y$ has the same distribution as $Y + X$.

2. Associativity

This allows us to convolve in any order, which is crucial for$X_1 + X_2 + ... + X_n$.

3. Identity Element

Convolving with the Dirac delta (a point mass at 0) returns the original function. This corresponds to adding a constant 0.

4. Shift Property

If $f(x)$ is shifted to $f(x - a)$, the convolution result shifts by $a$. This reflects that adding a constant shifts the sum distribution.

5. Scaling and Variance

MGF and Characteristic Functions

The most powerful technique for computing convolutions avoids integration entirely. Using moment generating functions (MGFs) or characteristic functions (CFs), convolution becomes simple multiplication.

The MGF Product Rule

For independent $X$ and $Y$:

This transforms the convolution integral into a product! To find the distribution of $X + Y$:

1. Compute $M_X(t)$ and $M_Y(t)$
2. Multiply them together
3. Recognize the resulting MGF (it uniquely determines the distribution)

Example: Sum of Exponentials

If $X_1, ..., X_n \sim \text{Exp}(\lambda)$ are independent:

This is the MGF of $\text{Gamma}(n, \lambda)$! We've proven the sum of $n$ exponentials is Gamma without computing any integrals.

The Characteristic Function Alternative

The MGF doesn't always exist (e.g., for Cauchy distributions). The characteristic function $\phi_X(t) = E[e^{itX}]$ always exists and satisfies:

Common Convolutions You Should Know

Some convolutions have beautiful closed-form solutions that appear repeatedly in statistics and machine learning. Memorizing these patterns will serve you well.

AI/ML Applications

1. Convolutional Neural Networks

The "convolution" in CNNs is mathematically similar but with key differences:

• Discrete: CNNs work with discrete pixel grids and kernel weights
• Multi-dimensional: 2D convolution for images, 3D for video
• Learnable kernels: The kernel weights are parameters optimized via backpropagation
• Cross-correlation: Many libraries actually implement cross-correlation (no kernel flip), calling it "convolution" by convention

2. Diffusion Models

Modern generative models like Stable Diffusion and DALL-E use diffusion processes that are fundamentally based on convolution:

• Forward process: Iteratively add Gaussian noise, which is convolution with Gaussian kernels
• Distribution evolution: The data distribution gets "blurred" by repeated convolutions until it becomes pure noise
• Reverse process: Learn to "deconvolve" (remove noise) step by step

3. Central Limit Theorem

The CLT can be understood through convolution: repeatedly convolving any distribution with itself produces a shape that approaches Gaussian. This is why:

• Sample means are approximately normal for large samples
• Measurement errors (sum of many small effects) are Gaussian
• Monte Carlo estimates have Gaussian-distributed errors

4. Noise in Neural Networks

Understanding noise combination via convolution helps analyze:

• Weight initialization: Xavier/He initialization ensures activation variances don't explode or vanish across layers
• Dropout noise: The multiplicative noise has specific distributional properties that affect training dynamics
• Gradient noise: Stochastic gradient noise aggregates across mini-batches following convolution rules

Python Implementation

Numerical Convolution

1import numpy as np
2from scipy.signal import convolve
3from scipy.stats import norm, uniform, expon
4import matplotlib.pyplot as plt
5
6def pdf_convolution(pdf1, pdf2, x_range, dx=0.01):
7    """
8    Compute convolution of two PDFs numerically.
9
10    The convolution (f * g)(z) = ∫ f(x) g(z - x) dx
11    gives the PDF of the sum Z = X + Y.
12    """
13    x = np.arange(x_range[0], x_range[1], dx)
14
15    # Evaluate PDFs on the grid
16    f = pdf1(x)
17    g = pdf2(x)
18
19    # Numerical convolution (scipy handles the flip)
20    conv = convolve(f, g, mode='same') * dx
21
22    return x, conv
23
24# Example 1: Sum of two Uniform(0, 1) → Triangular
25x, conv = pdf_convolution(
26    lambda x: uniform.pdf(x, 0, 1),
27    lambda x: uniform.pdf(x, 0, 1),
28    x_range=(-1, 3)
29)
30print("Sum of two Uniform(0,1) gives triangular distribution")
31
32# Example 2: Sum of two Gaussians
33# N(μ1, σ1²) + N(μ2, σ2²) = N(μ1+μ2, σ1²+σ2²)
34mu1, sigma1 = 0, 1
35mu2, sigma2 = 2, 0.5
36x, conv = pdf_convolution(
37    lambda x: norm.pdf(x, mu1, sigma1),
38    lambda x: norm.pdf(x, mu2, sigma2),
39    x_range=(-5, 10)
40)
41
42# Verify: result should be N(0+2, 1+0.25) = N(2, 1.25)
43theoretical = norm.pdf(x, mu1 + mu2, np.sqrt(sigma1**2 + sigma2**2))
44print(f"Max difference from theoretical: {np.max(np.abs(conv - theoretical)):.6f}")
45
46# Example 3: Sum of Exponentials → Gamma
47# Exp(λ) + Exp(λ) = Gamma(2, λ)
48lambda_param = 1.0
49x, conv = pdf_convolution(
50    lambda x: expon.pdf(x, scale=1/lambda_param),
51    lambda x: expon.pdf(x, scale=1/lambda_param),
52    x_range=(-1, 10)
53)
54print("Sum of two Exp(1) gives Gamma(2, 1)")

Using MGFs to Avoid Integration

1import numpy as np
2from scipy.stats import norm, expon, gamma
3
4def mgf_product_demonstration():
5    """
6    Demonstrate: MGF of sum = product of MGFs.
7    This transforms convolution into multiplication!
8
9    For X ~ Exp(λ): M_X(t) = λ/(λ-t) for t < λ
10    Sum of n Exp(λ): M_{X1+...+Xn}(t) = (λ/(λ-t))^n
11    This is the MGF of Gamma(n, λ)!
12    """
13    lambda_param = 2.0
14    n = 3  # Sum of 3 exponentials
15
16    # MGF of single exponential
17    def mgf_exp(t, lam):
18        return lam / (lam - t)
19
20    # MGF of sum = product of individual MGFs
21    def mgf_sum(t, lam, n):
22        return mgf_exp(t, lam) ** n
23
24    # Verify this equals MGF of Gamma(n, λ)
25    t_values = np.linspace(-0.5, 1.5, 100)
26
27    # Theoretical MGF of Gamma(n, λ)
28    def mgf_gamma(t, n, lam):
29        return (lam / (lam - t)) ** n
30
31    # They should match!
32    for t in [0, 0.5, 1.0]:
33        product_mgf = mgf_sum(t, lambda_param, n)
34        gamma_mgf = mgf_gamma(t, n, lambda_param)
35        print(f"t={t}: Product MGF={product_mgf:.4f}, Gamma MGF={gamma_mgf:.4f}")
36
37# Using characteristic functions for Cauchy (has no MGF!)
38def characteristic_function_example():
39    """
40    The Cauchy distribution has no MGF (no moments exist).
41    But it has a characteristic function: φ(t) = e^{iμt - γ|t|}
42
43    Sum of independent Cauchy(0, γ₁) + Cauchy(0, γ₂):
44    φ_{X+Y}(t) = φ_X(t) · φ_Y(t) = e^{-γ₁|t|} · e^{-γ₂|t|} = e^{-(γ₁+γ₂)|t|}
45
46    This is the CF of Cauchy(0, γ₁ + γ₂)!
47    """
48    gamma1, gamma2 = 1.0, 2.0
49
50    def cf_cauchy(t, gamma):
51        return np.exp(-gamma * np.abs(t))
52
53    t = 0.5
54    product = cf_cauchy(t, gamma1) * cf_cauchy(t, gamma2)
55    combined = cf_cauchy(t, gamma1 + gamma2)
56    print(f"\nCauchy CF product: {product:.4f}")
57    print(f"Cauchy({gamma1+gamma2}) CF: {combined:.4f}")
58    print("Cauchy is 'stable' under addition!")
59
60mgf_product_demonstration()
61characteristic_function_example()

Convolution in Diffusion Models

1import numpy as np
2import matplotlib.pyplot as plt
3
4def diffusion_as_convolution():
5    """
6    Diffusion models add Gaussian noise iteratively.
7    Each step is a convolution with a Gaussian kernel!
8
9    If X_t has distribution p_t, then:
10    X_{t+1} = X_t + √(β) · ε, where ε ~ N(0, 1)
11
12    This means: p_{t+1} = p_t * N(0, β)  (convolution!)
13
14    After many steps, any distribution converges to Gaussian.
15    This is the Central Limit Theorem in action.
16    """
17    np.random.seed(42)
18    n_samples = 10000
19    n_steps = 50
20    beta = 0.02  # Noise variance per step
21
22    # Start with a bimodal distribution (mixture of two Gaussians)
23    samples = np.concatenate([
24        np.random.normal(-2, 0.5, n_samples // 2),
25        np.random.normal(2, 0.5, n_samples // 2)
26    ])
27
28    # Track variance growth
29    variances = [np.var(samples)]
30
31    # Forward diffusion: repeatedly convolve with Gaussian
32    for t in range(n_steps):
33        # Each step adds independent Gaussian noise
34        noise = np.random.normal(0, np.sqrt(beta), n_samples)
35        samples = samples + noise
36        variances.append(np.var(samples))
37
38    print(f"Initial variance: {variances[0]:.3f}")
39    print(f"Final variance: {variances[-1]:.3f}")
40    print(f"Theoretical variance after {n_steps} steps: {variances[0] + n_steps * beta:.3f}")
41
42    # The distribution becomes more Gaussian with each convolution
43    # This is the forward process in diffusion models!
44    return samples, variances
45
46samples, variances = diffusion_as_convolution()
47
48# Convolution in CNNs vs Probability
49def cnn_vs_probability_convolution():
50    """
51    CNN 'convolution' is actually cross-correlation!
52
53    Probability: (f * g)(z) = ∫ f(x) g(z - x) dx  (flip g)
54    CNN:         (f ⋆ g)(z) = ∫ f(x) g(z + x) dx  (no flip)
55
56    For symmetric kernels, they're the same.
57    Libraries call it 'convolution' for historical reasons.
58    """
59    # Simple 1D example
60    signal = np.array([0, 1, 2, 3, 4, 3, 2, 1, 0], dtype=float)
61    kernel = np.array([1, 2, 1], dtype=float) / 4  # Symmetric kernel
62
63    # True convolution (flip kernel)
64    conv_result = np.convolve(signal, kernel, mode='same')
65
66    # Cross-correlation (no flip) - what CNNs actually do
67    corr_result = np.correlate(signal, kernel, mode='same')
68
69    # For symmetric kernel, they're identical!
70    print(f"Convolution result: {conv_result}")
71    print(f"Cross-correlation: {corr_result}")
72    print(f"Difference: {np.max(np.abs(conv_result - corr_result)):.10f}")
73
74cnn_vs_probability_convolution()

Common Pitfalls

Test Your Understanding

Summary

Convolution is the fundamental operation for finding distributions of sums of independent random variables. Here are the key takeaways:

Mathematical Formulas

Key Properties

• Commutative: $f * g = g * f$
• Associative: $(f * g) * h = f * (g * h)$
• Variance adds: $\text{Var}(X + Y) = \text{Var}(X) + \text{Var}(Y)$
• Means add: $E[X + Y] = E[X] + E[Y]$

Common Results to Memorize

• Normal + Normal = Normal (means and variances add)
• n Exponential(λ) = Gamma(n, λ)
• Uniform(0,1) + Uniform(0,1) = Triangular(0, 2)
• Poisson(λ₁) + Poisson(λ₂) = Poisson(λ₁ + λ₂)
• Cauchy is "stable": Cauchy + Cauchy = Cauchy

AI/ML Connections

• CNNs: Use the flip-and-slide operation (cross-correlation) to detect patterns
• Diffusion models: Forward process is repeated convolution with Gaussians
• Central Limit Theorem: Repeated convolution approaches Gaussian shape
• Noise modeling: Understanding how noise distributions combine