Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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...??

share|improve this question
    
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? –  Fabian Apr 25 '12 at 16:59
    
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? –  tibL Apr 25 '12 at 17:37
    
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. –  EMS Apr 25 '12 at 22:29

1 Answer 1

up vote 0 down vote accepted

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!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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