0
$\begingroup$

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?

$\endgroup$
2
  • 3
    $\begingroup$ 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$. $\endgroup$ Commented Dec 23, 2020 at 15:57
  • $\begingroup$ What might be a pmf of the joint distribution? $\endgroup$ Commented Dec 23, 2020 at 17:07

1 Answer 1

3
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.