“则 $\operatorname{Stab}\rho(f)\le\Gamma\rho(\mu)+\eta$。输入均匀,稳定性采用逐坐标相关定义。”
形式陈述
对均匀输入上的布尔值函数
最后等式因为乘积在相同输出时为
直觉
频谱平方和表示输出波动分布在哪些阶数。噪声给第
“有一定概率翻转”是有限函数的数值;“噪声敏感”通常还包含输入规模增长、噪声率固定的量词。把翻转率随
例子与边界
多数与奇偶的可核对比较
三位多数的三个一次系数平方和为
三位奇偶只有三阶质量,稳定性为
一般
奇数位多数在
为什么要逐坐标独立扰动
取两位均匀输入
小噪声与总影响
对固定
因此总影响是噪声敏感度起点处的斜率;它不是任意噪声强度下的完整曲线。对不断变大的函数族交换求导与极限,还需额外论证。
推论与应用
对于非平衡函数,独立输出也会因共同均值而有正的原始相关。例如常量函数稳定性恒为
多数最稳定定理在固定均值、低坐标影响与非负相关下给稳定性上界。它不是对所有函数的无条件排序;单个独裁者就可以比平衡多数更稳定。
参考资料
- O’Donnell,《Analysis of Boolean Functions》§2.4、§5.2、§11.1,稳定性谱公式、多数极限与高斯关联。