Convolution (Discrete Case)

Given two sequences a = [a₀, a₁, ..., aₘ] and b = [b₀, b₁, ..., bₙ], their convolution is the sequence c = a * b defined by:

c_{k} = \sum_{i + j = k} a_{i} \cdot b_{j}

This involves flipping one sequence, shifting, taking pairwise products, and summing.

Think of convolution as a weighted sum of values, where one sequence “slides” over another (see this video) .

Key Examples

▸ Probability

Adding independent random variables (e.g., two irregular dice): convolve their probability distributions to get the distribution of the sum (this video).
▸ Image Processing
Convolving an image with a small matrix (kernel) yields:
- Blurring (e.g., averaging neighboring pixels),
- Edge detection (using kernels with positive and negative weights).
  ▸ Moving Average
Convolving data with a kernel like [1/3, 1/3, 1/3] smooths out local fluctuations.
▸ Polynomial Multiplication
Coefficients of the product of two polynomials equal the convolution of their coefficient sequences.