1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ The distribution in question is obviously discrete, supported on a finite set of cardinality $\le2^{2^n}$. So, how can it be an (absolutely continuous) Dirichlet distribution? More generally, what is the meaning of your question: "What multivariate distribution is [...] distributed as?" This distribution is just what it is. Specifically, what more do you want to know about it? $\endgroup$ Oct 11, 2020 at 21:17
  • $\begingroup$ I edited my question. $\endgroup$ Oct 12, 2020 at 3:57
  • $\begingroup$ What do you mean by "the categorical distribution $\operatorname{Categotical}\big(2^{n},\mathbf{\hat f}\big)$"? $\endgroup$ Oct 12, 2020 at 16:00
  • $\begingroup$ I mean a categorical distribution with $2^{n}$ categories. The probability of getting category $i$ is $\hat f(i)^{2}$. $\endgroup$ Oct 12, 2020 at 17:32

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ I did not understand how to get \begin{equation} \mathrm{E}\bigg(\hat f(z)^{2} \mid \big(z_{1}, z_{2}, \ldots, z_{k} \big)\bigg), \end{equation} from here. Also, intuitively, how can the Fourier coefficients be uncorrelated, when the sum of the squares of all the Fourier coefficients is $1$? $\endgroup$ Oct 14, 2020 at 9:24
  • $\begingroup$ I don't quite get what you mean by that expression -- $\hat{f}$ doesn't take values on points $z\in\{-1,1\}^n$, it takes values on subsets of the hypercube. Could you clarify that part of the question? $\endgroup$ Oct 18, 2020 at 13:42
  • $\begingroup$ For the second, it's unintuitive to me too, but I can't see any error in my argument, so I do believe it is true. $\endgroup$ Oct 18, 2020 at 13:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.