Fourier–Walsh 展开与影响度

字符是不同坐标的奇偶组合：单坐标字符观察一位，二阶字符观察两位乘积，全部坐标的字符就是奇偶函数。展开式告诉我们，输出与每一种奇偶模式有多大相关。

正交性来自 ${\chi }_S{\chi }_T={\chi }_{S\mathrm{△}T}$。只要 $S\ne T$，乘积中有某个独立均匀坐标只出现一次，其期望为零；$S=T$ 时乘积恒为一。共有 $2^n$ 个字符，恰等于所有实函数空间的维数，所以它们不仅正交，也完整。

影响公式可直接从离散差分得到。$(f(x)-f(x^{\oplus i}))/2$ 只保留含 $i$ 的字符；对布尔值函数，它的平方恰是“翻转后输出改变”的指示函数。再用 Parseval，便得到上面的平方和。

三人多数的完整频谱 ​

令 ${\mathrm{Maj}}_3(x)=\mathrm{sign}(x_1+x_2+x_3)$。逐一代入八个输入，或按对称性配对，可验证

因此常数、三项二阶系数均为零；三个一次系数各为 $1/2$，唯一三阶系数为 $-1/2$。平方和为 $3/4+1/4=1$。每个坐标影响为 $1/4+1/4=1/2$，总影响为 $3/2$。

对奇偶 $f(x)=x_1{x}_2{x}_3$，只有三阶系数为 $1$，所以每个坐标影响都是 $1$，总影响为 $3$。两个函数都均值为零、方差为一，但其质量分布在不同 Fourier 层上。

平均影响不是最坏敏感度 ​

坐标影响对随机输入取平均。多数函数在票数接近打平时对很多坐标敏感，在悬殊局面则不敏感；最坏点敏感度保留最极端输入，平均影响则衡量这些输入出现的比例，不能混为同一个量。

偏置输入下，$x_i$ 不再均值为零，当前字符基也不再正交标准。需要先中心化并归一化各坐标，建立适合该乘积分布的基。

噪声算子公理库布尔噪声算子Boolean noise operator · Bonami-Beckner noise operator把逐坐标随机扰动写成条件平均，并利用字符特征值 rho 的次数幂解析它的平滑作用。按次数给字符乘权，KKL 定理公理库KKL 影响定理KKL theorem在均匀立方体上，以方差和维数约束最大坐标影响，并用 tribes 展示对数因子的必要尺度。则从这些平方和推出某坐标不可过小的影响。旧有的BLR 测试公理库BLR 线性测试BLR linearity test · Blum-Luby-Rubinfeld linearity test以三个函数值检查 f(x)+f(y)=f(x+y)，并用 Fourier 一致性证明高通过率函数接近某个线性函数。使用三点相关检验是否接近一个字符；本页的完整展开还可描述远非线性的函数结构。

也可以固定字符而改变输入分布。小偏分布公理库小偏分布与线性测试Small-bias distribution · Epsilon-biased space以所有非零奇偶测试的偏差定义小偏分布，用有限域多项式构造短种子分布并证明偏差界，区分线性测试保证与密码学安全。让每个非平凡字符的期望都接近零，从而节省奇偶测试需要的随机位。对一般测试函数，展开后只能得到“字符偏差乘以 Fourier 系数绝对值之和”的误差界；每个字符都难以区分，并不意味着所有高效测试都难以区分。

若给出完整真值表，逐个计算全部系数需 $O(4^n)$ 的直接求和；快速 Walsh–Hadamard 变换通过递归加减将其降为 $O(n{2}^n)$。输入本身已有 $2^n$ 项，这与通过少量查询寻找显著系数是不同访问模型。