MathLabs

解法:多项式方法解决帽集问题(克罗特–列夫–帕赫,埃伦伯格–海斯维克,2016年)

第 6/7 步:用大偏差理论计数单项式:常数 2.7562.756
通俗地说

剩下的只是算术问题:在 3n3^n 个单项式中,总次数至多为 2n/32n/3 的到底有多少个,而最大可能次数是 2n2n?由于 nn 个坐标各自独立地贡献次数 00、11 或 22,这恰好就是 nn 个独立随机数字之和低于其通常平均值的概率——一个经典的大偏差(切尔诺夫型)计算。

3e−I(2/3)<2.7563e^{-I(2/3)} < 2.756
详细分析

埃伦伯格与海斯维克(2017年,最终计算)注意到 m(q−1)n/3/qnm_{(q-1)n/3}/q^n 恰好等于 nn 个在 {0,…,q−1}\{0,\ldots,q-1\} 上独立均匀分布的随机变量之和至多为 (q−1)n/3(q-1)n/3(即远低于其均值 (q−1)n/2(q-1)n/2)的概率;标准大偏差理论给出 lim⁡n→∞1nlog⁡(m(q−1)n/3/qn)=−I((q−1)/3)\lim_{n\to\infty} \frac{1}{n}\log(m_{(q-1)n/3}/q^n) = -I((q-1)/3),其中 I(x)=sup⁡θ(θx−log⁡1+eθ+⋯+e(q−1)θq)I(x) = \sup_\theta \left(\theta x - \log\frac{1+e^\theta+\cdots+e^{(q-1)\theta}}{q}\right) 是单个均匀数字的勒让德变换速率函数。将帽集情形的 q=3, x=2/3q=3,\ x=2/3 代入并对 θ\theta 求最优,即得数值上界 3e−I(2/3)<2.7563e^{-I(2/3)} < 2.756。

本步骤中的术语
大偏差/速率函数
大偏差理论用于估计许多独立随机变量之和远离其均值的指数级小概率;速率函数 I(x)I(x) 控制该概率的指数。