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
\begin{equation}
\hat f(z) = \frac{1}{2^{n}} \sum\_{x \in \{0, 1\}^{n}} (-1)^{x.z} f(x),
\end{equation}
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?



Joint distribution of random Fourier coefficients
$\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  

\begin{equation}
 \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} 
\end{equation}
and
\begin{equation}
 \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 
\end{equation}
because $w\ne0$. So,  

\begin{equation}
 \sum\_{x\in\Om^n}\big([s+t(-1)^{x\cdot w}]^2=2^n(s^2+t^2). 
\end{equation}


