Fourier-Walsh transform

For $f:\{-1,1{\}}^n\to \mathbb{R}$, the characters ${\chi }_S(x)={\prod }_{i\in S}{x}_i$ form an orthonormal basis, and the Fourier-Walsh expansion is

For $S\subseteq [n]$, the Walsh character on the Boolean hypercube is ${\chi }_S(x)={\prod }_{i\in S}{x}_i$, equivalently $(-1{)}^{{\sum }_{i\in S}{x}_i}$ in the zero-one convention.

Under the $p$-biased product measure ${\mu }_p$ on $\{-1,1{\}}^n$, the coordinates are independent random variables with $\mathbb{P}(x_i=-1)=p$ and $\mathbb{P}(x_i=1)=1-p$. Writing $\mu =1-2p$, $\sigma =2\sqrt{p(1-p)}$, and ${\varphi }_i=(x_i-\mu )/\sigma$, the products ${\varphi }_S={\prod }_{i\in S}{\varphi }_i$ form the $p$-biased Fourier basis.

The $p$-biased Fourier coefficient of $f$ at $S$ is ${\hat{f}}_p(S)={\mathbb{E}}_{{\mu }_p}[f{\varphi }_S]$.

On the unbiased cube, the discrete derivative isFor the p-biased product measure, the normalization factor is $\sigma /2$.

The influence of coordinate $i$ is ${\mathrm{Inf}}_i(f)=\Vert D_{i}f{\Vert }_2^2$. For a Boolean-valued function on the unbiased cube, it is the probability that flipping coordinate $i$ changes the function value.

The total influence is

For the indicator $f$ of a monotone family under a p-biased product measure, the Margulis-Russo formula identifies the derivative of ${\mathbb{E}}_{{\mu }_p}f$ with the suitably normalized total influence of $f$.

The noise operator averages $f(y)$ over a random $y$ correlated with $x$ by $\rho$. It acts diagonally on the Fourier-Walsh transform:

The noise stability is

The linear Fourier weight is $W_1(f)={\sum }_{|S|=1}\hat{f}(S{)}^2$.