For $f:\{\pm1\}^n\to\mathbb{R}$, $I\subset\{1,\dots,n\}$ and $x\in\{\pm1\}^{\{1,\dots,n\}\setminus I}$ we define $f_I[x]:\{\pm1\}^I\to\mathbb{R}$ by $f_I[x](y)=f(x,y)$. (We denote by ($x,y$) the assignment to all $n$ variables given by $x$ and $y$.)

Let $S\subseteq I$. I have proved that $\mathbb{E}_x\left[\widehat{f_I[x]}(S)\right]=\widehat{f}(S)$, where $\widehat{f}(S)$ is the Fourier coefficient of $f$ corresponding to $S$. Now I want to show (possibly using the first result) that $$\mathbb{E}_x\left[\widehat{f_I[x]}^2(S)\right]=\sum\limits_{T:T\cap I=S}\widehat{f}^2(T).$$

Any useful ideas would be greatly appreciated.


1 Answer 1


This is Corollary 3.22 of Analysis of Boolean Functions, by Ryan O'Donnell (2014). You may want to consult the proof in the book, or look directly at the online version (which has a different numbering: this corresponds to Corollary 22 there).

Note that you can obtain a version of the book following this link.


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.