Return to Answer

$\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 -- just as claimed.

Therefore, the joint distribution of $(Y_n,Z_n)$ converges to the standard bivariate normal distribution. 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}

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

$\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 -- just as claimed.

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}

$\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 -- just as claimed.

Therefore, the joint distribution of $(Y_n,Z_n)$ converges to the standard bivariate normal distribution. 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}

$\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 -- just as claimed.

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}\big([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}

$\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 -- just as claimed.

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}