1
$\begingroup$

Suppose I have 1,000 independent random values with a uniform distribution $[+1, -1]$. Now suppose I take the discrete Fourier transform of this data. What the heck is the probability distribution of the resulting Fourier coefficients?

(I'm guessing it's either uniformly distributed again, or else some manner of exotic distribution which converges to a normal distribution if the number of samples is high enough...)


Edit:

Each coefficient produced by the Fourier transform is the weighted sum of the input samples.

It appears that if $x$ and $y$ are both random variables, then the probability distribution of $x+y$ is equal to the convolution of the probability distribution for $x$ and the probability distribution for $y$. [Obviously, this applies iff $x$ and $y$ are independent.] I think I read that right, anyway!

If we were just summing $N$ I.I.D. variables, the result would be a normal distribution. But because it's a weighted sum, each weighted variable has a different [uniform] distribution. So... that means the answer is... uh...??

$\endgroup$
  • $\begingroup$ May I ask discrete Fourier transform of what? So you have a vector $(a_1, ..., a_{1000}) \in [-1,1]^{1000}$ and you take the discrete Fourier transform of this vector? Or you bin the data, and take the discrete Fourier transform of the binned data? $\endgroup$ – Fabian Apr 25 '12 at 16:59
  • $\begingroup$ Just for the sake of curiosity, I tested in matlab what I interpreted to be the question: N=1e5;a=-1+2*rand(N,1);f=real(fftshift(fft(a)));histfit(f,50); and got what very much looks like a normal distribution (same for the the imaginary part) which, I suppose, is what the question is about. Could this somehow be related to the Box-Muller transform? $\endgroup$ – tibL Apr 25 '12 at 17:37
  • $\begingroup$ It does seem from Box-Muller that you'd be computing a weighted combination of normal components, and so the result ought to be normal. $\endgroup$ – ely Apr 25 '12 at 22:29
2
$\begingroup$

The complex Fourier coefficients of a random series form a 2-D normal distribution in the complex plane (a Gaussian rotated around zero). When taking the magnitude of the complex spectrum, at each magnitude $r$ (the distance from the origin) the probability density will be $2 \pi r dr$, multiplied by the Gaussian, which gives (up to some constants) $r*\exp(-r^2)$. Incidentally, this does not depend on the shape of the original random distribution (from the central limit theorem, I guess). I tried in Matlab randn(...) (normally distributed), rand(...) (uniformly distributed) or rand(...)>.5 (zeros and ones only). Magic!

$\endgroup$
  • $\begingroup$ Do you have a suggestion how to see your observations not only in a MATLAB simulation but also in mathematical equations? So, do you have an idea how to proof this? $\endgroup$ – zimmerrol Jul 28 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.