How to compute the pdf of a sum of iid random variable using discrete Fourier transform?

524 Views Asked by At

Suppose there are $n$ i.i.d random variables $X_1, X_2, ..., X_n$ sampled from the distribution $p(X)$. We can compute the characteristic function of $X$ by \begin{equation} f(t) = \mathbb{E}[e^{i t X}]. \end{equation} Therefore, the characteristic function of $S = \sum_{i=1}^{N}{X_i}$ is just $f(t)^{N}$. In the sequel, we can recover the pdf of $S$ by computing the inverse Fourier transform. \begin{equation} \Pr[S = s] = \int_{t} f(t) e^{- i s t } dt. \end{equation}

The question is whether the above process can be simulated numerically using discrete Fourier transform. Given $p(X)$ as input, is it possible to output the $p(S)$ in the form of a histogram?

1

There are 1 best solutions below

0
On

If the random variables $X_1,\dots,X_n$ take values on a domain of finite size (i.e., have finite support), then yes, you can use a discrete Fourier transform.

For instance, suppose each $X_i$ is an integer in the range $[0,k]$. Then $S$ is in the range $[0,Nk]$, so you can do a discrete Fourier transform on any range of integers that includes $[0,Nk]$. For instance, you can round up to a power of two, and then compute a discrete Fourier transform over the domain $[0,2^\ell-1]$.

In this situation, everything works as in the continuous case, and gives you an efficient way to compute the probability distribution of $S$ from the probability distribution of $X_i$.