var]

2026-08-27

The variance of a function $𝑓 : {\pm 1}^{𝑛} \to ℝ$ is

𝐕𝐚𝐫 [𝑓] = 𝐄 [{(𝑓 - 𝐄 [𝑓])}^{2}] = 𝐄 [𝑓^{2}] - {𝐄 [𝑓]}^{2} .

Note. [#]

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

𝐕𝐚𝐫 [𝑓] = \sum_{𝑆 \neq \emptyset} \hat{𝑓} {(𝑆)}^{2} .

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