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

On the finite Boolean hypercube, these coefficients are the Hadamard transform of the vector of function values, with expectation normalization.

Fourier weight is the squared Fourier-Walsh transform coefficient mass on specified levels or a specified family of subsets. Parseval's identity identifies the total weight with $\mathbb{E}|f{|}^2$, and the nonconstant weight with variance. A decision tree of depth at most $s$ has no weight above level $s$.

For a random restriction, first fix the live set $J$ and average over the unbiased assignment $a$ outside it. The coefficient at $U\subset J$ is ${\sum }_{B\subset J^c}\hat{f}(U\cup B){\chi }_B(a)$. Orthogonality eliminates cross terms in its squared expectation. Averaging over $J$ gives the displayed identity. The original Fourier weight is weighted by a binomial distribution survival probability, not simply preserved.

For independent coordinate flips at rate $1/2$, a Walsh character $w_A$ is an eigenfunction with eigenvalue $-|A|$. The generator is self-adjoint and negative semidefinite. Its Dirichlet form of a Markov chain is $-\mathbb{E}[fLf]=\frac{1}{4}{\sum }_i\mathbb{E}(f({\omega }^{(i)})-f(\omega ){)}^2$.

Global sign-even functions have zero coefficients on odd-size Walsh characters. Every nonconstant remaining character has generator eigenvalue at most $-2$, yielding the displayed improvement from gap one to gap two. Combining this with the convexity of a norm proves the sharp Rademacher second-moment inequality.

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$.

For the $\{-1,1\}$-valued convention on the unbiased Boolean hypercube, the influence of coordinate $i$ is ${\mathrm{Inf}}_i(f)=\Vert D_{i}f{\Vert }_2^2$, where $D_{i}f$ is the discrete derivative of a Boolean function. It equals the probability that flipping coordinate $i$ changes $f$. For the $\{0,1\}$-valued convention, the same flip probability is instead $4\Vert D_{i}f{\Vert }_2^2$, since a nonzero discrete derivative has magnitude $1/2$.

For a zero-one Boolean function, the flip-probability influence is ${\beta }_i=4{\sum }_{S\ni i}\hat{f}(S{)}^2$. Apply Beckner's inequality with noise parameter $\sqrt{\delta }$ to the discrete derivative of a Boolean function, whose nonzero magnitude is $1/2$. Its $L^{1+\delta }$ norm squared is ${\beta }_i^{2/(1+\delta )}/4$. Summing over coordinates gives the displayed weighted Fourier weight bound, a useful intermediate step in influence lower bounds.

The total influence isThis Fourier-Walsh transform identity uses $\{-1,1\}$-valued $f$ and the flip-probability convention for influence of a variable. For $\{0,1\}$-valued $f$, the right-hand side is multiplied by four. Indeed Parseval's identity applied to the discrete derivative of a Boolean function gives $\Vert D_{i}f{\Vert }_2^2={\sum }_{S\ni i}\hat{f}(S{)}^2$; sum over coordinates and apply the chosen normalization.

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$.

A coordinate is pivotal for an increasing event in a configuration when changing only that coordinate changes whether the event occurs. Its pivotal probability is the coordinate's influence.

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

For $1<p\le q<\infty$ and $0\le \rho \le \sqrt{(p-1)/(q-1)}$, the noise operator on the Boolean hypercube satisfies $\Vert T_{\rho }f{\Vert }_q\le \Vert f{\Vert }_p$ for the uniform probability measure. In particular,Here $\hat{f}(S)$ are Fourier-Walsh transform coefficients. The endpoint $\rho =0$ follows by averaging. This hypercontractive inequality on the Boolean hypercube controls Fourier-Walsh transform coefficients of discrete derivatives of a Boolean function and is a principal ingredient in the Kahn-Kalai-Linial theorem.

For a subset of the unbiased Boolean hypercube of density $\alpha$, use normalized Fourier-Walsh transform coefficients. Applying Beckner's inequality with $\rho =1/\sqrt{3}$ gives $\Vert T_{\rho }{1}_A{\Vert }_2^2\le \Vert 1_A{\Vert }_{4/3}^2={\alpha }^{3/2}$. On levels at most two the weights ${\rho }^{2|S|}$ are at least $1/9$, giving the displayed bound. Parseval's identity gives total Fourier mass $\alpha$, so when $9\sqrt{\alpha }<1/2$ the higher levels contain strictly more than the lower levels.

The noise stability is

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