# Distribution of random Fourier coefficients

Let $$f : \{0, 1\}^{n} \rightarrow \{-1, 1\}$$ be a Boolean function. Let the Fourier coefficients of this function be given by

$$\hat f(z) = \frac{1}{2^{n}} \sum_{x \in \{0, 1\}^{n}} f(x)(-1)^{x \cdot z}$$

for each $$z \in \{0, 1\}^{n}$$, where $$x \cdot z$$ is the bitwise inner product between $$x$$ and $$z$$. Let me choose a function uniformly at random from the set of all Boolean functions $$\{f : \{0, 1\}^{n} \rightarrow \{-1, 1\}\}.$$

What is the distribution that each Fourier coefficient $$\hat f(z)$$ is distributed as?

Each Fourier coefficient on its own is the average of $$2^n$$ independent uniformly random $$\pm1$$ variables. Its distribution is roughly normal with mean $$0$$ and variance $$2^{-n}$$.
• Why is the mean $1$ and variance $2^{-n}$? Oct 6 '20 at 19:35