Tuesday, October 16, 2012

Convolve n Square Pulses to Gaussian

The other day, I was perusing Wikipedia, and stumbled upon the convolution page.
Intrigued by the convolution of 2 square pulses, which is a triangular function, I set about convolving a square pulse with itself several times and soon empirically observed that it seems to converge to a Gaussian shape, and fast.

The graph below shows the result of such convolutions for n from 0 (initial square pulse) to 9.

After only 3 convolutions the resulting function is visually indistinguishable from a Gaussian shape.

Below is short animation that gives a sense of how fast the repeated convolutions "spread" the square pulse into a quasi Gaussian curve.

I was a bit surprised, but after some conversations/investigations, it turns out to be a very direct application of the following 3 (a posteriori) basic propositions:

Let \(X_i\) for i a positive integer, a random variable with uniform distribution from -0.5 to 0.5.
All \(X_i\) being independent and identically distributed, the Central Limit Theorem states that for \(n\rightarrow \infty\) :
\[\sqrt{n}\left(\left(\frac{1}{n}\sum _{i=1}^n X_i\right)-\mu \right)\overset{\mathit{d}}{\rightarrow }\mathcal{N}\left(0,\sigma ^2\right)\]
where \(\mu\) and \(\sigma ^2\) are respectively the mean and the variance of of \(X_i\)

In this case \(\mu=0\) and and \(\sigma ^2=\frac{1}{12}\)
Then the convergence becomes :
\[\frac{1}{\sqrt{n}}\sum _{i=1}^n X_i\overset{\mathit{d}}{\rightarrow }\mathcal{N}\left(0,\sigma ^2\right)\]
where the left hand side is a random variable having the probability density function equal to the \((n-1)^{\text{th}}\) convolution of a square pulse with itself.

So it is no surprise, after all, that the convolution of a square pulse with itself converges to a Gaussian shape. Actually, it does not even have to be a square pulse for this observation to hold. Any probability density function with mean=0 would do.
But there is at least one specific additional result: For any n, the variance of the function obtained by n convolutions is constant and equal to its limit when \(n\rightarrow \infty\) :
\[\text{Variance}\left(\sum _{i=1}^n X_i\right)=n\sigma ^2\]

This was expected because the variance of the sum of any two \(X_i\) is the sum of their individual variances, as the 2 random variables are deemed independent, and is indeed observed as shown in the table below.

It is funny how this Gaussian shape acts as a "strange attractor" (personal use of the term) in this instance, as well as many phenomena in Nature. It seems to be due to the ubiquity of the Central Limit Theorem...

The Mathematica notebook used to create the pictures and animations is in this github repo.