Let \(S,J\subseteq [n]\) and \(x\in \{ 0,1\} ^n\), and let \(x\star _J y\) equal \(x\) on \(J\) and \(y\) elsewhere. Then for uniform \(y\), \(\mathbb E_y\chi _S(x\star _J y)=\chi _S(x)\) if \(S\subseteq J\), and zero otherwise.

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube, \(J\subseteq [n]\), and \(x\in \{ 0,1\} ^n\). If \(x\star _Jy\) keeps \(x\) on \(J\) and \(y\) elsewhere, then \(\mathbb E_y f(x\star _Jy)=\sum _{S\subseteq J}\widehat f(S)\chi _S(x)\).

Let \(f:\{ 0,1\} ^n\to \{ -1,1\} \) be a function on the uniform Boolean cube and \(J\subseteq [n]\). For uniform independent \(z\) and \(x\), and \(x\star _Jz\) keeping \(x\) on \(J\) and \(z\) elsewhere, \(\mathbb E_z\Pr _x(f(x)\ne f(x\star _Jz))=\tfrac 12\sum _{S\nsubseteq J}\widehat f(S)^2\).

Let \(f:\{ 0,1\} ^n\to \{ -1,1\} \) be a function on the uniform Boolean cube and \(J\subseteq [n]\). There exists \(h:\{ 0,1\} ^n\to \{ -1,1\} \) depending only on \(J\) such that \(\Pr (f\ne h)\le \tfrac 12\sum _{S\nsubseteq J}\widehat f(S)^2\).

Let \(f:\{ 0,1\} ^n\to \{ -1,1\} \) be a function on the uniform Boolean cube. There exists a constant \(h:\{ 0,1\} ^n\to \{ -1,1\} \) such that \(\Pr (f\ne h)\le \operatorname {Var}(f)/2\).