covar]

2026-08-27

The covariance of $𝑓, 𝑔 : {\pm 1}^{𝑛} \to ℝ$ is

\begin{aligned} 𝐂𝐨𝐯 [𝑓, 𝑔] & = ⟨ 𝑓 - 𝐄 [𝑓], 𝑔 - 𝐄 [𝑔] ⟩ \\ = 𝐄 [𝑓 𝑔] - 𝐄 [𝑓] 𝐄 [𝑔] . \end{aligned}

Note. [#]

For $𝑓, 𝑔 : {\pm 1}^{𝑛} \to ℝ$ ,

𝐂𝐨𝐯 [𝑓, 𝑔] = \sum_{𝑆 \neq \emptyset} \hat{𝑓} (𝑆) \hat{𝑔} (𝑆) .

By Plancherel, $𝐄 [𝑓 𝑔] = \sum_{𝑆} \hat{𝑓} (𝑆) \hat{𝑔} (𝑆)$ , and by the Fourier coefficient of the mean, $𝐄 [𝑓] 𝐄 [𝑔] = \hat{𝑓} (\emptyset) \hat{𝑔} (\emptyset)$ . Subtracting leaves the sum over nonempty $𝑆$ .