Posterior expected value for squared Fourier coefficients of random Boolean function

Question

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, \ldots, 2^{n} - 1\}$, where $x \cdot z$ is the bitwise inner product between the binary representations of $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\}\}. $$

Is there any "nice" name/form to the distribution of the $2^{n}$-tuple

\begin{equation} \mathbf{\hat f} =\bigg(\hat f(0)^{2}, \hat f(1)^{2}, \ldots, \hat f(2^{n} - 1)^{2}\bigg)? \end{equation}

More specifically, given $k$ samples $ \big(z_{1}, z_{2}, \ldots, z_{k})$ from the categorical distribution $\operatorname{Categotical}\big(2^{n},\mathbf{\hat f}\big)$, I am trying to find

\begin{equation} \mathrm{E}\bigg(\hat f(z)^{2} \mid \big(z_{1}, z_{2}, \ldots, z_{k} \big)\bigg), \end{equation}

for a fixed $z$.

My attempt:

We know that \begin{equation} \sum_{z = 0}^{2^{n} - 1} \hat f(z)^{2} = 1. \end{equation} There are a few more properties that might be of interest. It can be seen that \begin{equation} \frac{2^{n}}{2}\big(\hat f(z) + 1\big) \end{equation} follows a binomial distribution with $2^{n}$ trials and success probability $\frac{1}{2}$, for each $z$. From there, one can reason that each $\hat f(z)^{2}$ is identically distributed (but not independent) and compute the mean of each $\hat f(z)^{2}$ to be $\frac{1}{2^{n}}$ and variance to be $\frac{2^{n} - 1}{2^{3n-1}}$. But I can't get much beyond this point.

Is there anything else we can say about the distribution and, finally, the expected value? Maybe it is a "discrete-variant" of a Dirichlet distribution, but I don't know how to formalize that.

Answer 1

To begin with, I'll be switching to considering functions $\Omega^n = \{-1,1\}^n\to \{-1,1\} = \Omega$. This is of course entirely isomorphic to the $\{0,1\}$-valued bit setting, it just makes the notation a bit neater. Note that our characters are then $\chi_S(\omega) = \prod_{i\in S}\omega_i$.

So we have a random function $f: \Omega^n \to \Omega$, drawn uniformly from all such functions. It is clear that this means $f(\omega)$ is uniform on $\Omega$, and $f(\omega)$ and $f(\omega')$ are independent for $\omega\neq\omega'$. So we can compute $$\hat{f}(S) = \mathbb{E}_\omega[f(\omega)\chi_S(\omega)] = 2^{-n}\sum_{\omega\in\Omega} f(\omega)\chi_S(\omega)$$ and the terms in this sum are independent and uniform on $\Omega$. Note that we actually get no dependence on $S$ at all, since $\chi_S$ takes values in $\Omega$ as well, and of course multiplying a uniform random variable on $\{-1,1\}$ by $1$ or $-1$ changes nothing.

So $\hat{f}(S) \sim 2^{-n}(2\mathrm{Bin}(n,\frac{1}{2})-n)$.

Note that this is not too surprising -- a uniformly random function should of course be extremely irregular and noisy, so we should expect to have lots of energy at every frequency level, which is what we got.

It is also not too hard to see that $\hat{f}(S)$ and $\hat{f}(T)$ are uncorrelated for $S\neq T$. We can compute $$\mathbb{E}_f[\hat{f}(S)\hat{f}(T)] = \mathbb{E}_f\left[\left(2^{-n}\sum_\omega f(\omega)\chi_S(\omega)\right)\left(2^{-n}\sum_{\omega'} f(\omega')\chi_T(\omega)\right)\right]$$ $$= 2^{-2n}\mathbb{E}_f\left[\sum_{\omega,\omega'} f(\omega)f(\omega')\chi_{S\triangle T}(\omega)\right]$$ $$= 2^{-2n}\mathbb{E}_f\left[\sum_\omega f(\omega)^2\chi_{S\triangle T}(\omega) + \sum_{\omega\neq\omega'} f(\omega)f(\omega')\chi_{S}(\omega)\chi_{T}(\omega')\right]$$ $$= 2^{-2n}\hat{1}(S\triangle T) + 2^{-2n}\sum_{\omega\neq\omega'} \chi_S(\omega)\chi_{T}(\omega')\mathbb{E}_f[f(\omega)f(\omega')] $$ and here of course $S\neq T$ implies $S\triangle T \neq \emptyset$, and so that Fourier coefficient of the constant function is zero. For the second term, $f(\omega)$ and $f(\omega')$ are independent, so $\mathbb{E}[f(\omega)f(\omega')] = \mathbb{E}[f(\omega)]\mathbb{E}[f(\omega')] = 0$ and so that term is zero as well.

I think they should actually be independent, not just uncorrelated, but that is not something I immediately saw how to prove.