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

CC BY-SA 4.0
2020-05-13T03:11:43.770Z
2020-05-13T03:44:24.363Z
2020-06-17T09:38:08.363Z
Pedro Juan Soto
<p>As in the title.</p>

<p>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..</p>

<p>Any further intuition would be appreciated.</p>

<p>Thanks.</p>

CC BY-SA 4.0
2020-05-12T18:29:08.520Z
Each Fourier coefficient will be roughly normal (with variance $1/2^n$), so you can get a sense of how they'll behave approximately.
Clement C.
CC BY-SA 4.0
2020-05-12T21:08:21.107Z
To add a little to Clement's answer: You're asking what's the Hadamard transform of a random Rademacher vector looks like. In such cases, you can safely simulate Rademacher random variables with Gaussians, and observe that the resulting vector essentially behaves like a random Gaussian.
Mahdi Cheraghchi
<boolean-functions><fourier-analysis>
A boolean function $f: \{0,1\}^n \rightarrow \{0,1\}$ is chosen at random from all $2^{2^n}$ such $f$. What do the Fourier coefficients look like?
zfkmz
# A boolean function $f: \{0,1\}^n \rightarrow \{0,1\}$ is chosen at random from all $2^{2^n}$ such $f$. What do the Fourier coefficients look like?

(Asked by: username_0 on 2020-05-12)

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.

**Tags:** boolean-functions, fourier-analysis
> **Comments:**
> **username_1**: Each Fourier coefficient will be roughly normal (with variance $1/2^n$), so you can get a sense of how they'll behave approximately.  
> **username_2**: To add a little to Clement's answer: You're asking what's the Hadamard transform of a random Rademacher vector looks like. In such cases, you can safely simulate Rademacher random variables with Gaussians, and observe that the resulting vector essentially behaves like a random Gaussian.  

---

## 1 answers

### Answer by username_3 on 2020-05-13. Score: 5 | Accepted answer

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


---

