# Joint distribution of random Fourier coefficients

Consider choosing a Boolean function $$f : \{0, 1\}^{n} \rightarrow \{-1, 1\}$$ uniformly at random from the set of all Boolean functions and consider the random variable $$\left(\hat f(z_{1}), \hat f(z_{2})\right)$$ for some fixed choice of $$z_{1}, z_{2} \in \{0, 1\}^{n}$$ with $$z_{1} \neq z_{2}$$, where $$$$\hat f(z) = \frac{1}{2^{n}} \sum_{x \in \{0, 1\}^{n}} (-1)^{x.z} f(x),$$$$ ie, $$\hat f(z)$$ is the Fourier transform of $$f$$ evaluated on $$z$$ and $$x.z$$ is the bitwise inner product of the binary representations of $$x$$ and $$z$$. I am trying to find the distribution for $$\left(\hat f(z_{1}), \hat f(z_{2})\right)$$.

I know that for any fixed $$z$$, the random variable $$\frac{2^{n}}{2}(\hat f(z) + 1)$$ obeys a Binomial distribution with $$2^{n}$$ trials and success probability $$1/2$$, so $$\hat f(z_{1})$$ and $$\hat f(z_{2})$$ are identically distributed. However, they may not be independent and I am not sure whether the joint distribution is just a product distribution.

What is the pmf for the joint distribution and is it approximately a product distribution for large values of $$n$$, in the limiting case?

• They are not independent. For example when $n=1$, the two possibilities for $\widehat{f}(z)$ are (essentially) $X_1+X_2$ and $X_1-X_2$, with $X_j$ iid, taking the values $\pm 1$. These are not independent: for example, if $X_1+X_2=2$, then you know with certainty that $X_1-X_2=0$. Dec 23, 2020 at 15:57
• What might be a pmf of the joint distribution? Dec 23, 2020 at 17:07

$$\newcommand{\Om}{\Omega}$$Let $$(Y_n,Z_n):=2^{n/2}(\hat f(y),\hat f(z))$$ for distinct $$y,z$$ in $$\Om^n$$, where $$\Om:=\{0,1\}$$. Then the limit distribution of $$(Y_n,Z_n)$$ (as $$n\to\infty)$$ is the standard bivariate normal distribution.
Indeed, for the joint characteristic function $$\phi_n$$ of $$(Y_n,Z_n)$$, any real $$s$$ and $$t$$, and $$w:=y-z\ne0$$ we have \begin{align*} \phi_n(s,t)&=E\exp\big\{i2^{n/2}(s\hat f(y)+t\hat f(z))\big\} \\ &=E\exp\Big\{\frac i{2^{n/2}}\,\sum_{x\in\Om^n}[s(-1)^{x\cdot y}+t(-1)^{x\cdot z}]f(x)\Big\} \\ &=\prod_{x\in\Om^n}E\exp\Big\{\frac i{2^{n/2}}\,[s(-1)^{x\cdot y}+t(-1)^{x\cdot z}]f(x)\Big\} \\ &=\prod_{x\in\Om^n}\cos\Big\{\frac1{2^{n/2}}\,[s(-1)^{x\cdot y}+t(-1)^{x\cdot z}]\Big\} \\ &=\prod_{x\in\Om^n}\cos\Big\{\frac1{2^{n/2}}\,[s+t(-1)^{x\cdot w}]\Big\}. \end{align*} The third equality in the above display holds because the $$f(x)$$'s are independent, and the fourth equality there holds because $$P(f(x)=\pm1)=1/2$$ for each $$x\in\Om^n$$. Since $$\ln\cos u=-u^2/2+O(u^4)$$ as $$u\to0$$, we further have \begin{align*} \phi_n(s,t)&=\exp\Big\{-\frac12\frac1{2^n}\,\sum_{x\in\Om^n}\big([s+t(-1)^{x\cdot w}]^2+O(1/2^{2n})\big)\Big\} \\ &=\exp\Big\{-\frac{s^2+t^2}2+O(1/2^n)\Big\}\to e^{-s^2/2}e^{-t^2/2}; \end{align*} see below for details on the last displayed equality.
Thus, the joint characteristic function $$\phi_n$$ of $$(Y_n,Z_n)$$ converges pointwise to the joint characteristic function of the standard bivariate normal distribution.
Therefore, the joint distribution of $$(Y_n,Z_n)$$ converges to the standard bivariate normal distribution -- just as claimed. In particular, $$Y_n$$ and $$Z_n$$ -- and hence $$\hat f(y)$$ and $$\hat f(z)$$ -- are indeed asymptotically independent.
Details on the last displayed equality: Take any nonzero $$w=(w_1,\dots,w_n)\in\{-1,0,1\}^n$$. Then
$$$$\sum_{x\in\Om^n}[s+t(-1)^{x\cdot w}]^2=\sum_{x\in\Om^n}[s^2+t^2+2st(-1)^{x\cdot w}] =2^n(s^2+t^2)+2st\sum_{x\in\Om^n}(-1)^{x\cdot w}$$$$ and $$$$\sum_{x\in\Om^n}(-1)^{x\cdot w}=\sum_{x_1\in\Om}\cdots\sum_{x_n\in\Om}\prod_{j=1}^n(-1)^{w_jx_j} =\prod_{j=1}^n\sum_{x_j\in\Om}(-1)^{w_jx_j}=\prod_{j=1}^n(2\times1(w_j=0))=0$$$$ because $$w\ne0$$. So,
$$$$\sum_{x\in\Om^n}\big([s+t(-1)^{x\cdot w}]^2=2^n(s^2+t^2).$$$$