## Convolution Formula

### The Convolution Formula¶

Let $X$ and $Y$ be discrete random variables and let $S = X+Y$. We know that a good way to find the distribution of $S$ is to partition the event $\{ S = s\}$ according to values of $X$. That is,

$$P(S = s) ~ = ~ \sum_{\text{all }x} P(X = x, Y = s-x)$$

If $X$ and $Y$ are independent, this becomes the discrete convolution formula:

$$P(S = s) ~ = ~ \sum_{\text{all }x} P(X = x)P(Y = s-x)$$

This formula has a straightforward continuous analog. Let $X$ and $Y$ are continuous random variables with joint density $f$, and let $S = X+Y$. Then the density of $S$ is given by

$$f_S(s) ~ = ~ \int_{-\infty}^\infty f(x, s-x)dx$$

which becomes the convolution formula when $X$ and $Y$ are independent:

$$f_S(s) ~ = ~ \int_{-\infty}^\infty f_X(x)f_Y(s-x)dx$$

### Sum of Two IID Exponential Random Variables¶

Let $X$ and $Y$ be i.i.d. exponential $(\lambda)$ random variables and let $S = X+Y$. For the sum to be $s > 0$, neither $X$ nor $Y$ can exceed $s$. The convolution formula says that the density of $S$ is given by

\begin{align*} f_S(s) ~ &= ~ \int_0^s \lambda e^{-\lambda x} \lambda e^{-\lambda(s-x)} dx \\ \\ &= ~ \lambda^2 e^{-\lambda s} \int_0^s ds \\ \\ &=~ \lambda^2 s e^{-\lambda s} \end{align*}

That's the gamma $(2, \lambda)$ density, consistent with the claim made in the previous chapter about sums of independent gamma random variables.

Sometimes, the density of a sum can be found without the convolution formula.

### Sum of Two IID Uniform $(0, 1)$ Random Variables¶

Let $S = U_1 + U_2$ where the $U_i$'s are i.i.d. uniform on $(0, 1)$. The gold stripes in the graph below show the events $\{ S \in ds \}$ for various values of $S$. The joint density surface is flat. So the shape of the density of $S$ depends only on the lengths of the stripes, which rise linearly between $s = 0$ and $s = 1$ and then fall linearly between $s = 1$ and $s = 2$. So the joint density of $S$ is triangular. The height of the triangle is 1 since the area of the triangle has to be 1. At the other end of the difficulty scale, the integral in the convolution formula can sometimes be intractable. The rest of the chapter is about a way of describing distributions that is particularly well suited to distributions of sums.