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}$.