← 返回 PaperDaily 大模型与智能体

CMU等三校破解20年E值合并猜想：半鞅一招制胜，置信区间逼近最优

E-values是p-value的进阶替代品，这篇论文直接把20年前Wang–Zhao猜想一次性击穿，而且统计口径比原猜想更紧、适用条件比独立更宽，全靠demi-supermartingale这把新钥匙。对做统计检验、多臂赌博机、置信区间收敛的读者，这篇值得精读。

龙哥读论文 阅读 3 查看原文
#人工智能
原论文信息如下：
论文标题:
Combining e-values using demi-supermartingales
发表日期:
2026年3月 发表单位:
滑铁卢大学（加拿大）、卡内基梅隆大学（美国）、加州大学伯克利分校（美国） 原文链接:
https://arxiv.org/pdf/2603.10329v2.pdf

什么是e-values？为什么它们比p-values更强大？

先聊一个很多读者可能没接触过的概念：e-values。在经典统计推断里，p值几乎是默认的“证据货币”：在零假设为真时，观测到当前或更极端结果的概率。p值越小，越有理由拒绝零假设。但p值有一堆让人头疼的毛病——两个独立实验的p值没法直接“合并”成一个靠谱的全局p值；实验做到一半偷看数据再决定是否继续，p值的解释就崩了；多重比较时还得做Bonferroni之类的事后校正。这些痛点催生了e-values这一替代工具。
e-variable的定义简单到有点“反高潮”：一个非负随机变量E，如果它在所有零假设分布下的期望都不超过1，就称它为一个e-variable，它的具体观测值就是e-value。换句话说，e-value不是“概率”，而是“证据倍数”：如果一次实验算出E=10，就说明数据把零假设的“可信预算”压缩到了原来的十分之一，这个证据强度相当可观。与p值不同，多个e-values天然支持合并——两个独立实验的e-values相乘，期望仍然不超过1，所以乘积还能继续当e-value用。这种“组合友好”的特性，让e-values在序贯检验、多重检验和“事后α决策”的语境下占据了明显优势。
不过，组合e-values的玩法远不止“乘起来”这一种。假设有n个独立的e-variables E₁, E₂, …, Eₙ，对任意固定的λ∈[0,1]，可以构造这样一个过程：
Mₙ(λ) = ∏ᵢ₌₁ⁿ [(1 − λ) + λEᵢ]。
直觉上，λ相当于一个“下注强度”：λ=0时Mₙ(λ)恒等于1，表示完全不采信证据；λ=1时就退化成纯乘积∏Eᵢ。可以证明，对任意固定的λ，Mₙ(λ)关于n是一个非负super-martingale，因此利用经典的Ville不等式（Ville, 1939），对任意α∈(0,1)有
P( supₙ Mₙ(λ) ≥ 1/α ) ≤ α。
也就是说，1 / supₙ Mₙ(λ)是一个有效的p值。但这里有个“先射箭后画靶”的问题：λ是预先固定的，如果研究者想等看到数据之后再挑一个最有利的λ，上面的保证还成立吗？这正是本文要解决的核心问题。

一个悬而未决的猜想：Wang–Zhao猜想

2003年，Wang和Zhao在研究非参数似然比时遇到了这样一个量：sup_{λ∈[0,1]} Mₙ(λ)。他们发现，这个上确界恰好是“零假设为均值不超过1”时，对独立同分布非负观测数据的非参数似然比。换句话说，它是“看完数据后选择最优常数下注策略”所能达到的最佳收益。他们据此提出了一个猜想：
对所有x > 0，P( sup_{λ∈[0,1]} Mₙ(λ) ≥ x ) ≤ 1/x。
注意这里的sup是对λ取的。如果对n也取sup，那就回到了固定λ的Ville不等式场景；但这里n是固定的，λ才是被最大化的对象。Wang和Zhao在论文中只证明了n=1和n=2两种特殊情况，对一般n的情况，他们坦承“不知如何证明”。这一悬置就是二十多年。
这个猜想为什么这么难？关键在于λ→Mₙ(λ)这条路根本走不通。从随机过程的角度看，Mₙ(λ)关于λ并不构成任何形式的super-martingale。事实上，作为λ的函数，Mₙ(λ)是一条从1出发的对数凹曲线，整条曲线由λ=0邻域的值完全确定，这意味着只要它在某个地方有所上升，就直接违反super-martingale的定义。既然传统的Doob停时和Ville不等式都使不上劲，就必须另辟蹊径。
另外，这个量在统计学习的另一个方向上也举足轻重。在多臂赌博机（multi-armed bandit）文献中，log sup_{λ} Mₙ(λ)有一个响当当的名字：KL-inf统计量，它度量的是经验分布与“均值不超过m”的零假设集之间的最小KL散度。Honda和Takemura（2010）以及后续一系列工作都依赖KL-inf做置信区间和探索策略，但那些工作给出的浓度界总带着n的多项式因子——也就是所谓的“遗憾界”。因此，如果能把sup_{λ} Mₙ(λ)的浓度界做到干净的1/x，就等于给KL-inf颁发了一张“无遗憾通行证”。

半鞅（demi-supermartingale）如何一击破题

破题的关键，是一种比super-martingale更弱、更“松弛”的随机过程——demi-supermartingale。先给定义：一个可积过程(Mₖ)被称为demi-martingale，如果对任意递减函数g，都满足 E[(Mₖ − Mₖ₋₁)·g(M₀, …, Mₖ₋₁)] ≤ 0；如果把g进一步限制为“递减且非负”，就得到demi-supermartingale的版本。换句话说，它只要求未来增量与过去路径的“单调函数”之间的相关性非正，而不像super-martingale那样要求对任意可测函数都成立。显然，所有super-martingale都是demi-supermartingale，但反过来一般不成立。
论文的第一板斧，是把Ville不等式推广到非负demi-supermartingale上：对任意非负demi-supermartingale(Mₖ)，有
P( supₖ Mₖ ≥ x ) ≤ E[M₀] / x，对所有x > 0成立。
证明过程其实非常简洁：取首达时τ = inf{k : Mₖ ≥ x}，利用demi-supermartingale的定义构造一个“Doob型停时不等式”E[M_τ] ≤ E[M₀]，再套用Fatou引理，最后两边同乘x即可。这个推广的价值在于，它不要求过程适应某个预给 filtration，也不要求停时是通常意义下的停时，只需要“demi”这一条性质就够用。
第二板斧才是真正让人拍案叫绝的地方。论文引入了一个新的依赖结构——co-valid e-variables（共效e值变量）。定义如下：对任意i，
E[ Eᵢ | E₁, …, Eᵢ₋₁, Eᵢ₊₁, …, Eₙ ] ≤ 1。
也就是每个e-variable在“知道其他所有e-variable的值”之后，条件期望仍然不超过1。独立e-variables当然满足co-valid；co-valid又强于sequential（序贯有效）。所以有包含关系：独立 ⊆ co-valid ⊆ sequential。论文给了一个例子说明为什么需要co-valid：如果只要求sequential，supλ Mₙ(λ)的1/x界会以9/16 > 1/2的方式被直接违反。这意味着co-valid是“刚好够用”的临界条件。
接下来最神奇的操作来了：对co-valid e-variables E₁,…,Eₙ，考虑一个“阶梯状”的序列——Aₖ = Sₖ(E) / C(n, k)，其中Sₖ是k阶基本对称多项式，C(n,k)是组合数。也就是说，Aₖ是“从n个e-variables里随机挑k个相乘”的平均值。论文的核心定理证明：把k当作“时间”，(Aₖ)ₖ₌₀ⁿ是一个非负demi-supermartingale！时间轴不是观测顺序，而是对称多项式的阶数，这种“阶数即时间”的视角在鞅理论里极为少见。
这一步能成立，靠的是一个关键的差分恒等式：
Aₖ₊₁ − Aₖ = [1 / (n·C(n−1, k))] · Σᵢ (Eᵢ − 1)·Sₖ(E₋ᵢ)，
其中E₋ᵢ表示去掉第i个分量后的向量。这个等式把相邻两项的差分解成了“每个e-variable相对1的偏差”乘以“不含该变量的k阶对称多项式”的加权和。利用co-valid性，E[Eᵢ−1 | E₋ᵢ] ≤ 0；再利用Chebyshev关联不等式，可以证明E[(Aₖ₊₁−Aₖ)·g(A₀,…,Aₖ)] ≥ 0对合适符号的g成立。整个证明环环相扣，几乎没有多余的动作。
meng
到这里，把第一板斧和第二板斧接在一起，就得到了论文的核心成果——SymPol不等式：
P( max₀≤ₖ≤ₙ Aₖ(E) ≥ x ) ≤ 1/x，且 sup_{λ∈[0,1]} ∏ᵢ (1−λ+λEᵢ) ≤ max₀≤ₖ≤ₙ Aₖ(E)。
第二个不等式只需将乘积按λ的多项式展开，然后用“加权平均不超过最大值”的初等代数即可证明。两个不等式合起来，直接推出Wang–Zhao猜想，而且比猜想本身更强：一方面，所用的统计量max Aₖ比supλ Mₙ(λ)更大，因此p值更小、检验功效更高；另一方面，成立条件从“独立”放宽到了“co-valid”。

SymPol：用基本对称多项式组合e-values

SymPol这个名字是“symmetric polynomials”（对称多项式）的缩写。基本对称多项式是代数学里的老朋友：对n个变量x₁,…,xₙ，k阶基本对称多项式Sₖ(x)就是把所有大小为k的子集的乘积加起来。例如S₁ = Σxᵢ，S₂ = Σᵢ<ⱼ xᵢxⱼ。Aₖ则是Sₖ除以组合数C(n,k)，可以理解为“随机挑k个变量的乘积的期望值”。
SymPol统计量的计算，可以转化为多项式求积问题。注意到关键恒等式：
∏ᵢ₌₁ⁿ (1 + Eᵢz) = Σₖ₌₀ⁿ Sₖ(E)·zᵏ。
也就是说，想要拿到全部Sₖ，只需把n个一次因式(1+Eᵢz)全部乘起来。直接乘是O(n²)的，但用分治+快速傅里叶变换（FFT），可以把复杂度压到O(n log² n)。算法可以用十几行伪代码说清楚：
    函数 BuildProduct(区间[L, R])：
    如果 L = R，返回多项式 1 + E_L·z
    取中点 M
    左多项式 = BuildProduct(L, M)
    右多项式 = BuildProduct(M+1, R)
    返回 FFTMultiply(左多项式, 右多项式)

P(z) = BuildProduct(1, n)
提取系数 c₀, c₁, …, cₙ
对 k = 0 到 n：
    Aₖ = cₖ / C(n, k)
返回 max Aₖ
    有了max Aₖ之后，可以定义两种p值。一种是基于原始优化乘积的形式Pₙ = inf_λ ∏ᵢ 1/(1−λ+λEᵢ)，另一种就是SymPol p值：
    P̄ₙ = 1 / max₀≤ₖ≤ₙ Aₖ(E)。
    由于max Aₖ ≥ supλ Mₙ(λ)，所以SymPol p值只会比KL-inf p值更小，也就是证据更强。而且它天然具备鲁棒性：即便个别e-value小于1，也不会像纯乘积那样把整体证据“一键清零”。

    从理论到应用：置信区间与KL-inf的意外联系

    理论讲完，总得看看能不能落地。论文把这套SymPol技术用在了一个经典问题上：有界随机变量均值的置信区间。考虑X₁,…,Xₙ独立同分布，取值在[0,1]上，共同均值为μ。要检验“μ ≤ m”，只需令Eᵢ = Xᵢ/m，则在零假设下Eᵢ是非负且期望不超过1的e-variables。将SymPol检验反演成置信区间，居然能得到一个闭式解：
    Lₙ^SP = max₁≤ₖ≤ₙ [ (α/2)·Aₖ(X₁,…,Xₙ) ]^{1/k}，
    Uₙ^SP = 1 − max₁≤ₖ≤ₙ [ (α/2)·Aₖ(1−X₁,…,1−Xₙ) ]^{1/k}。
    这个区间(Lₙ^SP, Uₙ^SP)的覆盖率至少为1−α，不需要任何数值优化或求根，直接套公式就能算。为什么它一定包含样本均值？用Maclaurin不等式即可看出：Aₖ^{1/k} ≤ 样本均值X̄ₙ，所以Lₙ^SP ≤ X̄ₙ ≤ Uₙ^SP。更妙的是，论文还证明了SymPol置信区间被KL-inf反演所得的置信区间“夹在中间”——上界不超过KL-inf区间的上界，下界不低于KL-inf区间的下界。换言之，SymPol区间总是更紧的。
    接下来是KL-inf的“无遗憾界”浓度不等式。定义KLinf(Q∥S) = inf_{P∈S} KL(Q∥P)，即从分布Q到集合S的最小KL散度。Honda和Takemura在2010年证明了一个漂亮的二元性：log Wₙ^(ℓ)(m) = n·KLinf(Q̂ₙ ∥ P_{≤m})，其中Q̂ₙ是经验分布，P_{≤m}是均值不超过m的分布集合。将SymPol不等式与这个对偶结合，论文直接得到：
    P( n·KLinf(Q̂ₙ ∥ P_{≤m}) ≥ log(1/α) ) ≤ α。
    熟悉bandit文献的读者一定知道，以往的KL-inf浓度界长这样：P(n·KLinf ≥ log(1/α) + log(n+1)/2 + log 2) ≤ α。多出来的两项正是“遗憾界”的代价。本文的结果把这两项直接删掉，所以叫“regret-free”（无遗憾界）。代价是什么？以往的带遗憾界版本具有“任意时刻有效”（anytime-valid）的性质，即样本量n可以替换成数据依赖的停时；而本文的干净版本只针对固定样本量n。这本质上是在“固定样本量的锐利性”和“随时停止的灵活性”之间做了一次取舍。
    论文还仔细分析了KL-inf置信区间的渐近宽度。在σ² > 0的条件下，区间长度wₙ满足：
    √n·wₙ → 2σ√(2log(2/α))，几乎必然。
    这是教科书级别的O(1/√n)速率，常数也是干净的2σ√(2log(2/α))。作为对比，anytime-valid的置信区间通常只能做到√(log log n / n)量级，或者常数要大得多。SymPol区间因为总是被KL-inf区间包含，所以它的宽度也不会超过上面这个渐近值。如果σ² = 0（数据几乎没有波动），区间宽度则退化为1 − (α/2)^{1/n}，这一边界也被精确刻画了。

    总结与开放问题

    这篇论文的贡献可以梳理成清晰的三个层次。第一，在工具层面，把Ville不等式从非负super-martingale推广到了非负demi-supermartingale，为后续研究提供了一把新钥匙；第二，在理论层面，正面解决了悬置二十余年的Wang–Zhao猜想，而且给出的统计量比原猜想更大、依赖条件比独立更宽松；第三，在应用层面，导出了闭式解的SymPol置信区间，并给出了KL-inf统计量的“无遗憾界”浓度不等式，直接改进了bandit文献中沿用了十余年的结果。
    当然，开放问题也不少。比如，固定λ的Ville不等式天然支持“随时停止”，而新的SymPol不等式只在固定n下成立，两者之间是否存在一个可调的折中？又比如，demi-supermartingale这套工具能不能推广到连续时间过程，或者用来构造其他类型的统计量？再比如，co-valid这一条件在真实实验设计中是否容易验证——论文给出了“条件独立且条件有效”的充分条件，但更一般的co-valid结构是否自然存在，还有待挖掘。这些问题，论文作者在结论部分也坦诚地留给了未来。

    龙迷三问

    下面是龙哥对于大家可能的一些问题的解答：

    e-value和p-value到底是什么关系？一个e-value E可以通过1/E构造p值，所以在单次检验中两者可以互相转化。但e-value的“组合友好性”是p值不具备的：多个e-values可以直接相乘、加权平均甚至做更复杂的对称多项式组合，而p值之间没有这么干净的运算规则。此外，e-value有明确的贝叶斯解释——它是数据对零假设的“证据折扣因子”，这让它在序贯实验和多重比较中表现更稳健。

    co-valid和sequential到底差在哪？sequential（序贯）要求E[Eᵢ | E₁,…,Eᵢ₋₁] ≤ 1，也就是给定过去的e-values之后，第i个的条件期望不超过1；co-valid要求E[Eᵢ | 除了Eᵢ以外的所有Eⱼ] ≤ 1，也就是给定“未来”之后仍然有效。直观来说，sequential对应“按顺序做实验，后面的实验可以参考前面的结果”；co-valid对应“多个实验室同时做实验，每个实验室的结果在知道其他所有实验室结果之后仍然有效”。论文证明SymPol不等式对co-valid成立，并给出了一个反例说明sequential条件下该不等式会失效。

    为什么说KL-inf的浓度是“regret-free无遗憾界”？在多臂赌博机文献里，“遗憾”（regret）衡量的是算法因探索不足而损失的收益。此前KL-inf统计量的浓度界总带着log(n)量级的“惩罚项”，例如log(n+1)/2 + log 2，这些惩罚项本质上是为了维持随时有效性而付出的代价。本文用SymPol不等式在固定样本量n下直接去掉了这些惩罚项，得到P(n·KLinf ≥ log(1/α)) ≤ α。把多出来的对数因子删掉，就像把“遗憾”降到了零，所以叫“无遗憾界”。代价是牺牲了随时停止的性质——这是理论上的精准取舍。

    如果你还有哪些想要了解的，欢迎在评论区留言或者讨论~

    龙哥点评

    论文创新性分数：★★★★☆

    用demi-supermartingale分析对称多项式序列，视角新颖，首次打通了e-values理论与demi鞅理论之间的联系，创新性相当突出。

    实验合理度：★★★☆☆

    这是一篇纯理论论文，核心贡献在于数学证明而非数值实验；算法只给出了复杂度和伪代码，没有附上大规模模拟或真实数据案例，因此实验部分略单薄。

    学术研究价值：★★★★★

    解决了二十余年的公开猜想，并且推广了Ville不等式这一基础工具，对e-values理论、非参数检验和bandit领域都有实质推动，研究价值很高。

    稳定性：★★★☆☆

    理论保证本身是严格的，但SymPol统计量的计算依赖FFT多项式乘法，在n很大或e-values动态范围极广时，数值精度可能成为隐患；论文没有讨论数值稳定性问题。

    适应性以及泛化能力：★★★☆☆

    核心结果针对co-valid依赖结构，比独立更宽，但尚未推广到一般sequential依赖或连续时间过程；不过置信区间和KL-inf两方面的应用展示了不错的延展面。

    硬件需求及成本：★★★★★

    算法复杂度O(n log² n)，几乎不需要训练，普通机器即可运行，计算开销非常低。

    复现难度：★★★★☆

    推导完整、伪代码清晰，理论上容易复现；但论文没有给出官方开源代码，也没有公开模拟数据的详细设置，这是减分项。

    产品化成熟度：★★☆☆☆

    方法适合嵌入A/B测试平台、风险限定审计、bandit算法等场景，但现阶段仍是理论成果，缺少工程化封装和真实业务验证。

    可能的问题：论文偏重理论推演，缺少数值模拟和真实数据案例；FFT计算在极端数值下的精度问题未讨论；co-valid条件虽比独立宽松，但在实际实验中是否自然出现仍需更多论证。

    整体来看，这是一篇“证明漂亮、工具通用、应用落地潜力明确”的理论佳作。龙哥认为，demi-supermartingale这套方法的价值可能不局限于e-values——任何涉及“对一组非负随机变量做对称组合”的统计问题，都值得试着套一下这个框架。

    主要参考文献

    [1] Ming J., Ramdas A., Shen Y., Wang R., Waudby-Smith I. Combining e-values using demi-supermartingales. arXiv:2603.10329v2, 2026.
    [2] Wang Y., Zhao L. Nonparametric likelihood ratio tests for the mean of nonnegative data. 2003.
    [3] Ville J. Étude critique de la notion de collectif. Gauthier-Villars, 1939.
    [4] Honda J., Takemura A. An asymptotically optimal bandit algorithm for bounded support models. COLT, 2010.
    [5] Orabona F., Jun K.-S. Tight concentrations and confidence sequences from the regret of universal portfolio. IEEE Transactions on Information Theory, 2024.
    [6] Ramdas A., Wang R. E-values: Theory and applications. 2025.

    *本文仅代表个人理解及观点，不构成任何论文审核或者项目落地推荐意见，具体以相关组织评审结果为准。欢迎就论文内容交流探讨，理性发言哦～ 想了解更多原文细节的小伙伴，可以点击"阅读原文"，查看更多原论文细节哦！       

    end
    统计江湖风再起，半鞅出手解难题！
    想和龙哥一起追更E-values、置信区间、赌序列这类硬核统计/ML论文，欢迎加入『龙哥读论文』粉丝群，扫描下方二维码或者添加龙哥助手微信号加群：kangjinlonghelper。一定要备注：研究方向+地点+学校/公司+昵称（如 统计检验+上海+清华+龙哥），根据格式备注，可更快被通过且邀请进群。
    『龙哥读论文』微信群目前包含：图像处理、大模型及智能体、自动驾驶及机器人、AI医疗及AI金融5个群，统计学前沿讨论彩蛋群持续扩充中～
    wechat_helper dianzan
    转发文章 微博 X LinkedIn Facebook
    龙哥读论文 · PaperDaily

    本文基于龙哥读论文 PaperDaily 数据库整理，结合论文原文与工程视角进行解读。