<p>This is Corollary 3.22 of <em>Analysis of Boolean Functions</em>, by Ryan O'Donnell (2014). You may want to consult the proof in the book, or look directly at the <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=560" rel="nofollow noreferrer">online version</a> (which has a different numbering: this corresponds to Corollary 22 there).</p>

<p>Note that you can obtain a version of the book following <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?page_id=2334" rel="nofollow noreferrer">this link</a>.</p>

CC BY-SA 3.0
2017-12-04T04:48:53.410Z
2017-12-04T07:14:30.400Z
2017-12-04T07:14:30.400Z
Clement C.
<p>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$.)</p>

<p>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).$$</p>

<p>Any useful ideas would be greatly appreciated.</p>

<boolean-functions><fourier-analysis>
Basic property of boolean functions with restrictions
Nathan
# Basic property of boolean functions with restrictions

(Asked by: username_0 on 2017-12-02)

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.

**Tags:** boolean-functions, fourier-analysis


---

## 1 answers

### Answer by username_1 on 2017-12-04. Score: 5 | Accepted answer

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](http://www.contrib.andrew.cmu.edu/~ryanod/?p=560) (which has a different numbering: this corresponds to Corollary 22 there).

Note that you can obtain a version of the book following [this link](http://www.contrib.andrew.cmu.edu/~ryanod/?page_id=2334).


---

