Convolution of Bernouli trials with homogenous probability mass function

Question

I'm trying to learn the basics behind the "normal distribution" curve. And decided I should learn to understand basics of convolutions. A very basic example would be the convolution of Bernouli trials that all have the same value for "p". This should be equivalent to the Binomial distribution. I was thinking it would help me understand how to get from point A to point B via using a convolution. Could someone show me the steps for doing a convolution of "n" Bernouli trials that all have the same value for "p", and how it ends up as including the Binomial coefficient or choose function?

Answer 1

Let $X_i$ be i.i.d. $\mathsf{Ber}(p)$ random variables and define $S_n=\sum_{i=1}^n X_i$. For $n=1$ we have $$ \mathbb P(S_1 = k) = \binom 1k p^k(1-p)^{1-k}. $$ Assume now that $\mathbb P(S_n=k)=\binom nk p^k(1-p)^{n-k}$ for some $n\geqslant 1$. Then \begin{align} \mathbb P(S_{n+1}=k) &= \mathbb P(S_{n+1}=k,X_{n+1}=0) + \mathbb P(S_{n+1}=k,X_{n+1}=1)\\ &= \mathbb P(S_n=k)\mathbb P(X_{n+1}=0) + \mathbb P(S_n=k-1)\mathbb P(X_{n+1}=1)\\ &= \binom nk p^k(1-p)^{n-k} + \binom n{k-1} p^k(1-p)^{n-k}\\ &= \left(\binom nk+ \binom n{k-1} \right)p^k(1-p)^{n-k}\\ &= \binom {n+1}k p^k(1-p)^{n-k}. \end{align}

I'm not sure how this relates to the normal distribution however, unless you are thinking of the where (when$np$ and $np(1-p)$ are large) for a normally distributed random variable $Y$ with mean $np$ and variance $1-p$ we have the approximation $$ \mathbb P(S_n\leqslant x) \approx \mathbb P(Y\leqslant x+1/2). $$

Answer 2

Let $X$ and $Y$ be two independent $\text{Bern}(p)$ random variables and let $Z=X+Y$.

$P(Z=z) = P(X+Y=z) = \sum_x P(X+Y=z|X=x)P(X=x)$ (law of total probability)

implying

$P(Z=z) = \sum_x P(Y=z-x)P(X=x) = \sum_x f(z-x)f(x)$, where $f(\cdot)$ is the probability density function of a $\text{Bern}(p)$ random variable.

Proving the

Now let's consider the definition of convolution. Let $g(z)$ denote the convolution of the function $f(\cdot)$ with itself. By definition:

$g(z) = \sum_x f(x) f(z-x)$

You can see the similarity between the definition of convolution and the probability density of $Z=X+Y$, computed as $P(Z=z)$ above.

You can extend this exercise from 2 variables to 3 and so, and more formally prove it with mathematical induction.

To relate the above to the normal distribution (via the Central Limit Theorem), you will have to think in terms of moment generating functions and how the MGF of a sum of random variables is actually the product of their individual MGFs (It's equivalent to convolution in time domain being equivalent to multiplication in frequency domain, in case you are familiar with Fourier analysis)