5D Library › 算法营销、多触点沙普利归因与获客漏斗的随机控制 · English

第三章 偷看的代价:可选停止、群序贯设计与始终有效推断

每天看一眼

一个 A/B 测试上线后,结果每天更新。常见的做法是:每天早上看一眼 p 值,一旦小于 0.05 就宣布胜出、停止测试;如果一直不显著,就等到预定日期。这叫可选停止:停止的时间取决于数据本身。问题在于,固定样本量下的 p 值只保证「在预定的那一次检验中」犯第一类错误的概率为 5%;多看几次,每一次都有机会因为随机波动越过门槛,而一旦越过就停,越过之后可能的回落就再也看不到了。

第 33 本已经用西蒙斯(Simmons)等人的研究者自由度模拟说明过可选停止对假阳性率的贡献,这里不重复。本章做三件事:精确计算「看 KK 次」时第一类错误率是多少,以核对作者框架中的「飙升至 25%+」;介绍允许中途查看而控制错误率的两类方法;并说明它们各自的代价。

精确计算

在零假设下(两个版本完全相同),把累积的标准化差值看作一个随机游走:第 kk 次查看时的部分和 SkS_k 服从 N(0,k)N(0, k),相邻查看之间的增量独立。等间隔查看、每次用 |z|≥1.96|z| \ge 1.96 作判据,相当于在 |Sk|≥1.96k|S_k| \ge 1.96\sqrt{k} 时停止。第一类错误率就是这个游走在 KK 步内越出边界的概率。阿米蒂奇(Armitage)、麦克弗森(McPherson)与罗(Rowe)1969 年研究了这个「对累积数据重复做显著性检验」的问题 (Armitage et al. 1969)。计算方法是递推:把第 kk 步「仍未越界」的子密度在区间 (−1.96k,1.96k)(-1.96\sqrt{k}, 1.96\sqrt{k}) 上离散化,与下一步增量的正态密度卷积,再截断到下一个区间。

推导

# Optional stopping: an A/A test is checked K times at equally spaced looks, and the
# experimenter stops at the first look with |z| >= 1.96 (nominal two-sided 5 %).
# Exact probability of a false positive by recursive numerical integration of the
# sub-density of the partial sum S_k ~ N(0, k) inside the continuation region
# (Armitage, McPherson & Rowe 1969), checked by a Monte Carlo of Bernoulli A/A tests.
import math, random

def stay_probs(bounds, h=0.1, drift=0.0):
    """P(|S_j| < bounds[j-1] for all j <= k), k = 1..K, S a Gaussian random walk with
    N(drift, 1) steps: Simpson's rule on a grid spanning each continuation interval."""
    phi = lambda x: math.exp(-x * x / 2) / math.sqrt(2 * math.pi)
    def grid(b):
        n = 2 * max(1, math.ceil(b / h)); d = 2 * b / n
        w = [(1 if i in (0, n) else 4 if i % 2 else 2) * d / 3 for i in range(n + 1)]
        return [-b + i * d for i in range(n + 1)], w
    xs, w = grid(bounds[0]); f = [phi(x - drift) for x in xs]
    out = [sum(a * b for a, b in zip(w, f))]
    for b in bounds[1:]:
        ys, v = grid(b)
        g = [sum(wi * fi * phi(y - x - drift) for x, wi, fi in zip(xs, w, f)
                 if abs(y - x - drift) < 8.5)
             for y in ys]
        xs, w, f = ys, v, g
        out.append(sum(a * b for a, b in zip(w, f)))
    return out

if __name__ == "__main__":
    z = 1.959964
    print("looks K   false-positive rate (exact)   1 - 0.95^K (independent looks)")
    stay = stay_probs([z * math.sqrt(k) for k in range(1, 101)])
    rates = {K: 1 - stay[K - 1] for K in (1, 2, 3, 5, 10, 20, 50, 100)}
    for K in rates:
        print(f"   {K:4d}          {rates[K]:6.3f}                      "
              f"{1 - 0.95 ** K:6.3f}")
    print("Monte Carlo check: A/A test, conversion 5 %, 400 users per arm per look,")
    print("  two-proportion z-test at every look, 2,000 simulated experiments")
    rng = random.Random(1969)
    for K in (5, 20):
        hits = 0
        for _ in range(2000):
            a = b = n = 0
            for _ in range(K):
                a += sum(rng.random() < 0.05 for _ in range(400))
                b += sum(rng.random() < 0.05 for _ in range(400)); n += 400
                p = (a + b) / (2 * n); se = math.sqrt(2 * p * (1 - p) / n)
                if se > 0 and abs(a - b) / n / se >= z:
                    hits += 1; break
        print(f"   K = {K:2d}: {hits / 2000:.3f}  (exact Gaussian value {rates[K]:.3f})")
# looks K   false-positive rate (exact)   1 - 0.95^K (independent looks)
#       1           0.050                       0.050
#       2           0.083                       0.098
#       3           0.107                       0.143
#       5           0.142                       0.226
#      10           0.193                       0.401
#      20           0.248                       0.642
#      50           0.320                       0.923
#     100           0.374                       0.994
# Monte Carlo check: A/A test, conversion 5 %, 400 users per arm per look,
#   two-proportion z-test at every look, 2,000 simulated experiments
#    K =  5: 0.149  (exact Gaussian value 0.142)
#    K = 20: 0.237  (exact Gaussian value 0.248)

看 1 次时为 5.0%,看 2 次 8.3%,3 次 10.7%,5 次 14.2%,10 次 19.3%,20 次 24.8%,50 次 32.0%,100 次 37.4%。这些值随查看次数无限增加而趋于 1(由重对数律,随机游走迟早会越过 1.96k1.96\sqrt{k}),但增长很慢。它们远小于把每次查看当作独立检验时的 1−0.95K1 – 0.95^K(看 20 次为 64.2%),因为相邻查看的数据大部分重叠,检验统计量高度相关。用二项转化数据(转化率 5%、每次每组新增 400 人)做的蒙特卡洛核对得到 14.9% 与 23.7%,与正态近似的精确值相差在模拟误差与离散性的范围之内。所以作者框架中的「飙升至 25% 以上」应限定为:在大约 20 次以上的等间隔查看、且每次都用未经调整的 1.96 作判据时成立;每天看一眼、跑三周的测试大致就是这个量级。图 2 左画出了完整的曲线。

左:名义 5% 的双侧检验在 K 次等间隔查看下的实际第一类错误率(实线,数值积分精确计算),以及把各次查看当作独立时的 1 - 0.95^K(虚线)。右:5 次查看的波科克与奥布赖恩—弗莱明边界(双侧总 \alpha = 0.05)与未经调整的 1.96。

群序贯设计:事先规定看几次、怎样看

如果事先知道要看 KK 次,可以把每次的临界值调高,使总的第一类错误率仍为 5%。波科克(Pocock)1977 年提出每次使用相同的临界值 (Pocock 1977);奥布赖恩(O’Brien)与弗莱明(Fleming)1979 年提出前期临界值很高、后期逐渐降低的边界,形如 zk=cK/kz_k = c\sqrt{K/k} (O’Brien and Fleming 1979)。下面的程序用上一段的精确计算求出 K=5K = 5 时两种边界的常数,并计算它们在一个「固定样本、只在最后检验一次时有 90% 把握度」的效应下的把握度、平均查看次数,以及要保持 90% 把握度需要把最大样本量放大多少。

推导

# Ways to look at a running test without inflating the error rate.
# A: group-sequential boundaries for K = 5 equally spaced looks, two-sided alpha 0.05:
#    Pocock (one constant z) and O'Brien-Fleming (z_k = c sqrt(K / k)), constants found
#    by bisection on the exact crossing probability of p04; power at the drift that
#    gives a fixed-sample test 90 % power, and the expected number of looks used.
# B: mixture SPRT (normal mixture, Johari et al.) monitored after every observation:
#    always-valid type I error, and how long it takes to stop under an effect.
import math, random

# --- helpers repeated from earlier programs, so that this one runs on its own ---
def stay_probs(bounds, h=0.1, drift=0.0):
    """P(|S_j| < bounds[j-1] for all j <= k), k = 1..K, S a Gaussian random walk with
    N(drift, 1) steps: Simpson's rule on a grid spanning each continuation interval."""
    phi = lambda x: math.exp(-x * x / 2) / math.sqrt(2 * math.pi)
    def grid(b):
        n = 2 * max(1, math.ceil(b / h)); d = 2 * b / n
        w = [(1 if i in (0, n) else 4 if i % 2 else 2) * d / 3 for i in range(n + 1)]
        return [-b + i * d for i in range(n + 1)], w
    xs, w = grid(bounds[0]); f = [phi(x - drift) for x in xs]
    out = [sum(a * b for a, b in zip(w, f))]
    for b in bounds[1:]:
        ys, v = grid(b)
        g = [sum(wi * fi * phi(y - x - drift) for x, wi, fi in zip(xs, w, f)
                 if abs(y - x - drift) < 8.5)
             for y in ys]
        xs, w, f = ys, v, g
        out.append(sum(a * b for a, b in zip(w, f)))
    return out
# --- end of repeated helpers ---

def calibrate(shape, K=5, alpha=0.05):
    lo, hi = 1.5, 5.0
    for _ in range(40):
        c = (lo + hi) / 2
        b = [c * shape(k) * math.sqrt(k) for k in range(1, K + 1)]
        if 1 - stay_probs(b)[-1] > alpha:
            lo = c
        else:
            hi = c
    return (lo + hi) / 2

def operating(c, shape, drift, K=5):
    b = [c * shape(k) * math.sqrt(k) for k in range(1, K + 1)]
    st = stay_probs(b, drift=drift)               # ignores the (tiny) wrong-side crossing
    return 1 - st[-1], 1 + sum(st[:-1])

def pw_drift(c, shape, K, target=0.90):
    lo, hi = 0.5, 3.0                             # drift per look giving target power
    for _ in range(30):
        d = (lo + hi) / 2
        if operating(c, shape, d, K)[0] < target:
            lo = d
        else:
            hi = d
    return (lo + hi) / 2 * math.sqrt(K)

def msprt_stop(rng, delta, tau2=1.0, alpha=0.05, nmax=20_000):
    """Paired differences x_i ~ N(delta, 2); stop when the mixture likelihood ratio
    exceeds 1/alpha. Returns the stopping time or None."""
    s2, s = 2.0, 0.0
    for n in range(1, nmax + 1):
        s += rng.gauss(delta, math.sqrt(s2))
        lr = math.sqrt(s2 / (s2 + n * tau2)) * math.exp(
            tau2 * s * s / (2 * s2 * (s2 + n * tau2)))
        if lr >= 1 / alpha:
            return n
    return None

if __name__ == "__main__":
    K = 5; z = 1.959964; zb = 1.281552
    drift = (z + zb) / math.sqrt(K)               # per-look drift: 90 % power at look K
    print(f"A. K = {K} looks, two-sided alpha 0.05; effect with 90 % power for one test")
    for name, shape in (("Pocock", lambda k: 1.0),
                        ("O'Brien-Fleming", lambda k: math.sqrt(K / k))):
        c = calibrate(shape, K)
        zs = [c * shape(k) for k in range(1, K + 1)]
        pw, el = operating(c, shape, drift, K)
        print(f"   {name:16s} z-bounds " + " ".join(f"{x:.3f}" for x in zs))
        print(f"   {'':16s} power {pw:.3f}; expected looks {el:.2f} of {K}"
              f" (null: {operating(c, shape, 0.0, K)[1]:.2f})")
        n_inf = (pw_drift(c, shape, K) / (z + zb)) ** 2
        print(f"   {'':16s} max sample to keep 90 % power: {n_inf:.3f} x fixed design")
    print("   fixed sample, one look at the end: power 0.900, looks 5 of 5")
    print("B. mixture SPRT, checked after every pair, alpha 0.05, tau^2 = 1")
    rng = random.Random(2017); n0 = 400
    fp = sum(msprt_stop(rng, 0.0, nmax=5000) is not None for _ in range(n0))
    print(f"   A/A, 5,000 pairs each, {n0} runs: rejected {fp / n0:.3f}"
          f" (any time; bound 0.05)")
    for delta in (0.3, 0.1):
        n_fix = math.ceil((z + zb) ** 2 * 2 / delta ** 2)
        t = [msprt_stop(rng, delta) for _ in range(200)]
        ok = sorted(x for x in t if x is not None)
        print(f"   effect {delta} sd: fixed design {n_fix:,} pairs; mSPRT stopped in"
              f" {len(ok)}/200, median {ok[len(ok) // 2]:,}")
# A. K = 5 looks, two-sided alpha 0.05; effect with 90 % power for one test
#    Pocock           z-bounds 2.413 2.413 2.413 2.413 2.413
#                     power 0.835; expected looks 3.13 of 5 (null: 4.88)
#                     max sample to keep 90 % power: 1.206 x fixed design
#    O'Brien-Fleming  z-bounds 4.562 3.226 2.634 2.281 2.040
#                     power 0.892; expected looks 3.69 of 5 (null: 4.96)
#                     max sample to keep 90 % power: 1.026 x fixed design
#    fixed sample, one look at the end: power 0.900, looks 5 of 5
# B. mixture SPRT, checked after every pair, alpha 0.05, tau^2 = 1
#    A/A, 5,000 pairs each, 400 runs: rejected 0.022 (any time; bound 0.05)
#    effect 0.3 sd: fixed design 234 pairs; mSPRT stopped in 200/200, median 194
#    effect 0.1 sd: fixed design 2,102 pairs; mSPRT stopped in 200/200, median 2,193

波科克边界每次都是 2.413,奥布赖恩—弗莱明边界从 4.562 降到最后一次的 2.040(接近固定样本的 1.96)。在同样的最大样本量下,两者的把握度都略低于固定设计(0.835 与 0.892 对 0.900),但平均只需要 3.13 次与 3.69 次查看就能结束,即平均节省约三分之一与四分之一的样本;在零假设下几乎总是跑满 5 次。要保持 90% 把握度,波科克设计的最大样本量需要放大到固定设计的 1.206 倍,奥布赖恩—弗莱明只需 1.026 倍。这说明了两者的取舍:波科克容易早停,但如果效应不大,最后要付出更多样本;奥布赖恩—弗莱明在前期几乎不会因为偶然的好看结果而停止,最终检验与固定设计几乎一样。营销实验可以采用后者,或用更一般的 α 消耗函数。

始终有效推断:可以随时看

群序贯设计要求事先规定查看的次数与时间。在线实验平台上,使用者往往想随时查看、随时停止。约哈里(Johari)、库门(Koomen)、佩凯利斯(Pekelis)与沃尔什(Walsh)把序贯检验包装成始终有效的 p 值与置信区间:无论使用者在何时、出于何种理由停止,报告的 p 值都保证第一类错误率不超过名义水平 (Johari et al. 2017, 2022)。他们采用的是混合序贯概率比检验(mSPRT):对效应 θ\theta 取一个先验混合分布 HH(例如 N(0,τ2)N(0, \tau^2)),计算混合似然比

Λn=∫∏i=1nfθ(xi)f0(xi)dH(θ),\Lambda_n = \int \prod_{i=1}^n \frac{f_\theta(x_i)}{f_0(x_i)}\,dH(\theta),

一旦 Λn≥1/α\Lambda_n \ge 1/\alpha 就拒绝零假设。由于 Λn\Lambda_n 在零假设下是非负鞅,维尔(Ville)不等式保证它曾经越过 1/α1/\alpha 的概率不超过 α\alpha,与停止规则无关。这一思路可以追溯到沃尔德(Wald)的序贯概率比检验与罗宾斯(Robbins)关于重对数律的统计方法 (Wald 1945; Robbins 1970);霍华德(Howard)等人后来给出了一般的、非渐近的时间一致置信序列 (Howard et al. 2021)。

程序 B 部分在每一对观测之后都检查一次。在 A/A 测试中,400 次运行(每次 5,000 对)中有 2.2% 曾经拒绝零假设,低于 5% 的上界(鞅不等式是保守的)。代价在于效应大小:效应为 0.3 个标准差时,mSPRT 停止所需样本的中位数是 194 对,少于固定设计的 234 对;效应为 0.1 个标准差时,中位数是 2,193 对,略多于固定设计的 2,102 对。混合方差 τ2\tau^2 的选择决定了它对哪种大小的效应最有效率;约哈里等人证明,在不知道使用者对样本量与把握度的偏好时,这种检验仍能在二者之间取得有效的平衡 (Johari et al. 2022)。

证据

大型平台的实践。 约哈里等人报告,他们的方法已部署在一个大型商业 A/B 测试平台上,应用于数十万次实验 (Johari et al. 2022)。科哈维(Kohavi)、唐(Tang)与徐(Xu)的在线受控实验手册系统讨论了偷看、样本比例失衡、新奇效应与多重比较等在线实验中常见的陷阱 (Kohavi et al. 2020)。

本章小结

在每次都用 1.96 作判据的等间隔查看下,名义 5% 的检验在看 5 次时实际第一类错误率为 14.2%,20 次为 24.8%,100 次为 37.4%;「飙升至 25% 以上」只在约 20 次以上查看时成立。问题不在于查看,而在于没有事先规定停止规则。群序贯设计在事先固定的查看次数下调整临界值(5 次查看时波科克 2.413、奥布赖恩—弗莱明从 4.562 降到 2.040),平均可节省四分之一到三分之一的样本;始终有效推断允许随时查看与停止,以对小效应稍多的样本为代价。

假说 · 尚未验证 · 偷看与报告的提升幅度

作者的假说(尚未确立): 在没有序贯校正的在线实验平台上,因为显著而提前停止的实验所报告的提升幅度,系统性地大于把同一版本在后续独立的随机实验中复测得到的提升幅度(赢家诅咒与可选停止的共同作用)。什么样的结果能证明它是错的: 在事先登记的一组提前停止的实验中(由独立研究者从平台日志中随机抽取并复测),报告提升与复测提升之比的几何平均数,其 95% 置信区间包含 1。

参考文献

Armitage, P., C. K. McPherson, and B. C. Rowe. 1969. “Repeated Significance Tests on Accumulating Data.” Journal of the Royal Statistical Society, Series A 132 (2): 235–44.
Howard, Steven R., Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. 2021. “Time-Uniform, Nonparametric, Nonasymptotic Confidence Sequences.” Annals of Statistics 49 (2): 1055–80. https://doi.org/10.1214/20-AOS1991.
Johari, Ramesh, Pete Koomen, Leonid Pekelis, and David Walsh. 2017. “Peeking at A/B Tests: Why It Matters, and What to Do about It.” Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’17), 1517–25.
Johari, Ramesh, Pete Koomen, Leonid Pekelis, and David Walsh. 2022. “Always Valid Inference: Continuous Monitoring of A/B Tests.” Operations Research 70 (3): 1806–21. https://doi.org/10.1287/opre.2021.2135.
Kohavi, Ron, Diane Tang, and Ya Xu. 2020. Trustworthy Online Controlled Experiments: A Practical Guide to A/B Testing. Cambridge University Press.
O’Brien, Peter C., and Thomas R. Fleming. 1979. “A Multiple Testing Procedure for Clinical Trials.” Biometrics 35 (3): 549–56.
Pocock, Stuart J. 1977. “Group Sequential Methods in the Design and Analysis of Clinical Trials.” Biometrika 64 (2): 191–99.
Robbins, Herbert. 1970. “Statistical Methods Related to the Law of the Iterated Logarithm.” Annals of Mathematical Statistics 41 (5): 1397–409.
Wald, Abraham. 1945. “Sequential Tests of Statistical Hypotheses.” Annals of Mathematical Statistics 16 (2): 117–86.

Fan, Y. (2026). Algorithmic Marketing, Multi-Touch Shapley Attribution and Stochastic Control of Acquisition Funnels: From Thompson Sampling Bandits and Absorbing Markov Chains to BG/NBD Customer Lifetime Value, Read Beside the Strategic Dispositions of the Sunzi [算法营销、多触点沙普利归因与获客漏斗的随机控制] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23836264 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).