How Do We Find the Convolution of Sequences?
Convolutions are important in probability, but can be a little confusing.
We consider two sequences. The first is the sequence of odd numbers:
$$1, 3, 5, 7, \dots$$
Let the $n$th term of this sequence be $p_n$, where we start from $n=0$, and $p_n=2n+1$.
The second is the sequence of positive powers of $2$:
$$2,4,8,16, \dots $$
Let the $n$th term of this sequence be $q_n$, where we start from $n=0$, and $q_n=2^{n+1}$.
Now, the convolution of these two sequences is a new sequence, with $n$th term equal to $c_n$, produced from these two initial sequences – but not by just multiplying $p_n$ and $q_n$.
Rather, we use the following formula:
$$c_n = p_0 q_n + p_1 q_{n-1} + p_2 q_{n-2} + \dots + p_n q_0$$
So, $c_n$ is the sum of $n+1$ terms, each of which is a product of two terms, one from each original sequence, whose indices sum to $n$.
For our example, then, we calculate the first four terms of this convolution sequence as follows:
| $n$ | $p_n$ | $q_n$ | $c_n$ |
|---|---|---|---|
| $0$ | $1$ | $2$ | $1 \times 2 = 2$ |
| $1$ | $3$ | $4$ | $1 \times 4 + 2 \times 3 = 10$ |
| $2$ | $5$ | $8$ | $1 \times 8 + 3 \times 4 + 5 \times 2 = 30$ |
| $3$ | $7$ | $16$ | $1 \times 16 + 3 \times 8 + 5 \times 4 + 7 \times 2 = 74$ |
Note that to find $c_n$ we need to reference all the rows up to the current one (but no later rows).