As in the title.
I'm not sure where to start here. My guess is that in expectation at least a constant fraction are non zero, and as a result there would exist some "large" coefs. and some "small" coefs..
Any further intuition would be appreciated.
Thanks.
Here's one way of attacking the problem.
Any boolean function $f: [2]^n \rightarrow [2]$ can be written as
\begin{equation} f(\alpha) = \sum_{\beta \in [2]^n} \chi_{\beta}\delta_{\beta} (\alpha) \end{equation} where $\chi_{\beta} \in [2]$ and $\delta_{\beta}$ is defined as \begin{equation} \delta_{\beta} (\alpha) = \begin{cases} 1 & \text{if } \alpha = \beta \\ 0 & \text{o.w.} \end{cases}. \end{equation} Choosing an $f$ at random is equivalent to independently and identically giving each $\chi_{\beta}$ the probability $p(\chi_{\beta} = i ) = 1/2$; i.e. each $\chi_{\beta}$ is an uniformly random i.i.d. binary random variable and $f$ is the sum of these random variables. The Fourier transform of this function is \begin{equation} \widehat{f} (\gamma) = \frac{1}{2^n}\sum_{\alpha \in [2]^n} f(\alpha)e^{ \left\langle \gamma , \alpha \right\rangle \pi i} \end{equation} where $ \left\langle \gamma , \alpha \right\rangle $ is the dot product in $\mathbb{F}^n_2$. However, plugging in our previous definition/identity for $f$ we have that \begin{equation} \widehat{f} (\gamma) = \frac{1}{2^n}\sum_{\alpha \in [2]^n} \sum_{\beta \in [2]^n} \chi_{\beta}\delta_{\beta} (\alpha)e^{ \left\langle \gamma , \alpha \right\rangle \pi i} = \frac{1}{2^n}\sum_{\alpha \in [2]^n} \chi_{\alpha} e^{ \left\langle \gamma , \alpha \right\rangle \pi i}; \end{equation} therefore the expected value of $\widehat{f}$ can be written as \begin{equation} \mathbb{E}[\widehat{f} ] = \frac{1}{2^n} \sum_{\gamma \in [2]^n} \widehat{f}(\gamma) = \frac{1}{2^n} \sum_{\gamma \in [2]^n} \left(\frac{1}{2^n}\sum_{\alpha \in [2]^n} \chi_{\alpha} e^{ \left\langle \gamma , \alpha \right\rangle \pi i}\right) \end{equation} \begin{equation} = \frac{1}{2^n} \sum_{\alpha \in [2]^n} \chi_{\alpha} \left(\frac{1}{2^n}\sum_{\gamma \in [2]^n} e^{ \left\langle \gamma , \alpha \right\rangle \pi i}\right) ; \end{equation} which we can simplify that as \begin{equation} \mathbb{E}[\widehat{f} ] = \sum_{\alpha \in [2]^n} \frac{\chi_{\alpha} }{2^n} \mathbb{E}[ e^{ \left\langle \gamma , \alpha \right\rangle \pi i}] ; \end{equation} so that we can consider the subproblem $ \mathbb{E}[ e^{ \left\langle \gamma , \alpha \right\rangle \pi i}] $ instead.
Now we use the following fact from combinatorics
Lemma $\mathcal{E}$=(The number of binary strings with even number of ones) = (The number of binary strings with odd number of ones)=$\mathcal{O}$
(Proof): Binary strings in $[2]^m$ are in 1-to-1 correspondence with subsets of $[m]$; but by the binomial theorem $(1-1)^m = \sum_{k} \binom{m}{k}(-1)^{k} = \mathcal{E} - \mathcal{O} = 0 $. QED
Therefore we have the following (if $\alpha \neq 0^n$)
Corrollary $e^{ \left\langle \gamma , \alpha \right\rangle \pi i}$ is equal to 1 as often as it is equal to -1; i.e. $ \mathbb{E}[ e^{ \left\langle \gamma , \alpha \right\rangle \pi i}] = 0 $
(Proof): If the support of the string $\alpha$ has $m$ 1's then we can break up the sum by the substrings on the support. In particular there are $[2]^{n-m}$ possible strings that are equal on the $[2]^m$ different strings on the support, then apply the previous lemma. QED
We, therefore, have that $ \mathbb{E}[\widehat{f} ] = \sum_{\alpha \in [2]^n} \frac{\chi_{\alpha} }{2^n} \mathbb{E}[ e^{ \left\langle \gamma , \alpha \right\rangle \pi i}] = 2^{-n}\chi_0 $ for any fixed $f$. Therefore $\mathbb{E}_{\chi}[\mathbb{E}_{\gamma }[\widehat{f} ]]=2^{-(n+1)}$ for a random $f$ or more simply put we have that:
For a random $f$ we have that the mean value of $\mathbb{E}[\widehat{f} ]$ is equal to $2^{-(n+1)}$.
If we wanted a more precise answer we could have gone an alternate route:
What is $p(\widehat{f} (\gamma)= i )$?
We can split this up into two sets like in the proof of the lemma; i.e.
\begin{equation} \frac{1}{2^n}\sum_{\alpha \in [2]}\chi_{\alpha}e^{ \left\langle \gamma , \alpha \right\rangle \pi i} = \frac{1}{2^n}\sum_{\alpha \in \mathcal{E} }\chi_{\alpha} - \frac{1}{2^n}\sum_{\alpha \in \mathcal{O} }\chi_{\alpha} \end{equation}
But the $\chi_{\alpha}$ are i.i.d. and therefore this looks just like a random walk that is normalized by $2^{n}$.
The $\widehat{f} $ follows the binomial distribution of the form
\begin{equation} p\left(\widehat{f} (\gamma)= \frac{i}{2^{n-1}} \right) = \binom{2^n}{2^{n-1}+i}\frac{1}{2^n} \end{equation} if $\gamma \neq 0^n$; i.e. the distribution on $\widehat{f} $ looks like what would happen if you took a binomial distribution on $[2^n]$ and shited it to the left by $2^{n-1}$ and then divided by $2^{n}$.
