The problem

I would like to understand the statistics of the discrete Fourier transform of a sequence of uncorrelated events $\{x_n\}$ each of which takes the value $\pm1$ with probability $1/2$. In other words, the probability distribution of the $n^\text{th}$ event is

$$P_{x_n}(x) = \frac{1}{2} \left( \delta(x - 1) + \delta(x + 1) \right) \, . $$

Note that the distribution does not depend on $n$. This stochastic process is called a Bernoilli process. The discrete Fourier transform of the sequence is

$$X_k \equiv \sum_{n=0}^{N-1} x_n e^{-i 2 \pi n k / N} \, .$$

What are the statistics of $X_k$?$^{[a]}$

My attempt

The $x_n$ values are random, so $X_k$ is also random; we want to analyze its statistics. We simplify the problem by first considering only the real part of $X_k$,

$$\Re X_k = \sum_{n=0}^{N-1} x_n \cos(2 \pi n k / N) \, . $$

Let $\xi_n \equiv x_n \cos(2\pi n k / N)$ so that

$$\Re X_k = \sum_{n=0}^{N-1} \xi_n \, .$$

The probability distribution of a sum of random variables is equal to the convolution of the distributions of the variables being summed, so

$$P_{\Re X_k} = \bigotimes_{n=0}^{N-1} P_{\xi_n} \tag{1}$$

where $\otimes$ means convolution and $P_{\xi_n}$ is the probability distribution of $\xi_n$ which is

\begin{align} P_{\xi_n}(\xi) &= \frac{1}{2 \cos(2 \pi n k / N)} \left( \delta \left( \frac{\xi}{\cos(2\pi n k / N)} - 1 \right) + \delta \left( \frac{\xi}{\cos(2\pi n k / N)} + 1 \right) \right) \\ &= \frac{1}{2 \cos(2 \pi n k / N)} \left( \delta \left( \xi - \cos(2\pi n k / N) \right) + \delta \left( \xi + \cos(2\pi n k / N) \right) \right) \, . \end{align}

Equation $(1)$ is difficult because it involves a convolution. We simplify by Fourier transforming because the Fourier transform of a convolution is the product of the Fourier transforms of the things being convolved. This turns Eq. $(1)$ into

$$\mathcal{F}(P_{\Re X_k})(\nu) = \prod_{n=0}^{N-1} \left( \frac{1}{2 \cos(2\pi n k / N)}\right) \left( e^{-i 2 \pi \nu \cos(2 \pi n k / N)} + e^{i 2 \pi \nu \cos(2 \pi n k / N)} \right) \, . $$

How can we proceed? In principle I'd like to evaluate the product and then inverse Fourier transform to arrive at the distribution for $\Re X_k$. This strategy works quite easily in the case that $x_n$ is Gaussian distributed (the product is trivial in that case) but here we've run into a product which, so far, I do not know how to evaluate.

$[a]$: Because the events are independent I'm reasonably sure that the spectral density ought to be independent of frequency, but I'd like to see the full statistics of $X_k$.


Your Answer

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

Browse other questions tagged or ask your own question.