均匀随机数累加超过 1

题

不断从 \(U(0,1)\) 独立抽数累加，记 \(N\) 为累加和首次超过 1 时用掉的个数。\(E[N]\) 是多少？

一句话

\(E[N] = e \approx 2.718\)——\(N > n\) 等价于前 \(n\) 个数之和不超过 1，概率是 \(n\) 维单纯形的体积 \(1/n!\)，尾和一加就是 \(e\) 的级数。

关键技巧

一、算尾概率，不算点概率。 对取正整数值的 \(N\)：

\[ E[N] = \sum_{n \ge 0} P(N > n) \]

与最长连正里用的是同一个尾和公式——凡是"首次达到"类的停时，\(P(N > n)\) 往往比 \(P(N = n)\) 好算得多。

二、\(P(N > n)\) 是单纯形体积。 \(N > n\) 当且仅当 \(U_1 + \cdots + U_n \le 1\)，即点 \((U_1, \ldots, U_n)\) 落在单纯形 \(\{x_i \ge 0,\ \sum x_i \le 1\}\) 里。它的体积：

\[ \mathrm{Vol} = \int_0^1 \frac{(1-x)^{n-1}}{(n-1)!}\, dx = \frac{1}{n!} \]

对称论证更快——单位立方体被 \(n!\) 种坐标排序等分，单纯形体积恰好是其中一份（映射 \(y_k = x_1 + \cdots + x_k\) 把单纯形变成 \(0 \le y_1 \le \cdots \le y_n \le 1\)，雅可比为 1）。

解

\[ E[N] = \sum_{n=0}^{\infty} \frac{1}{n!} = e \]

\(n=0\) 项是 \(P(N > 0) = 1\)，\(n=1\) 项是 \(P(U_1 \le 1) = 1\)，之后 \(\frac12, \frac16, \ldots\)。\(N\) 的分布：\(P(N = n) = \frac{1}{(n-1)!} - \frac{1}{n!} = \frac{n-1}{n!}\)，\(N = 2\) 占一半，\(N = 3\) 占三分之一。

方差也顺手：\(E[N^2] = \sum_{n\ge0}(2n+1)P(N>n) = 3e\)，\(\mathrm{Var}(N) = 3e - e^2 \approx 0.766\)。

延伸

超过 \(t \le 1\)：同样的单纯形缩放 \(t\) 倍，\(P(N_t > n) = t^n / n!\)，\(E[N_t] = e^t\)。
超过一般的 \(t\)：更新理论给出闭式 \(E[N_t] = \sum_{k=0}^{\lfloor t \rfloor} \frac{(-1)^k (t-k)^k}{k!} e^{t-k}\)。\(t=2\) 时 \(e^2 - e \approx 4.671\)，\(t = 10\) 时 \(20.667\)。大 \(t\) 下 \(E[N_t] \approx 2t + \frac23\)——由 Wald 恒等式 \(\frac12 E[N_t] = t + E[\text{过冲}]\)，而过冲的极限均值是 \(\frac{E[U^2]}{2E[U]} = \frac13\)。
Wald 恒等式验收：\(E[S_N] = E[N] \cdot E[U] = e/2 \approx 1.359\)——停下来时平均超过 1 大约 0.36。
同分布的另一道题：抽 \(U_1, U_2, \ldots\) 直到首次出现下降（\(U_{k} < U_{k-1}\)），\(N\) 是这个位置。\(N > n\) 等价于前 \(n\) 个严格递增，概率同样是 \(1/n!\)，于是期望同样是 \(e\)。两题共用一个"\(n!\) 种排序等分"。
常见错误：以为"均值 \(\frac12\)，两个就到 1"，答 2。\(E[N]\) 看的是停时，右尾（有时要 4 个、5 个）把期望推到 \(e\)。

数值验证

尾和的精确有理数、闭式更新函数、蒙特卡洛（含 Wald 验收和"首次下降"版本）：

from fractions import Fraction as F
import math, random

# P(N > n) = P(U1 + ... + Un <= 1) = 1/n!   （单纯形体积）
E  = sum(F(1, math.factorial(n)) for n in range(25))              # 尾和：E[N] = sum P(N > n)
E2 = sum(F(2 * n + 1, math.factorial(n)) for n in range(25))      # E[N^2] = sum (2n+1) P(N > n)
print(float(E), math.e)                     # 2.718281828459045 2.718281828459045
print(float(E2 - E * E), 3 * math.e - math.e ** 2)   # 0.7657893864464855 0.7657893864464862

def m(t):
    """首次超过 t 的期望次数（更新函数的闭式）。"""
    return sum((-1) ** k * (t - k) ** k / math.factorial(k) * math.exp(t - k)
               for k in range(math.floor(t) + 1))
print([round(m(t), 4) for t in (0.5, 1, 2, 3, 10)])
# [1.6487, 2.7183, 4.6708, 6.6666, 20.6667]  ->  2t + 2/3

random.seed(2024)
T, tot, sq, over = 10 ** 6, 0, 0, 0.0
for _ in range(T):
    s, k = 0.0, 0
    while s <= 1: s += random.random(); k += 1
    tot += k; sq += k * k; over += s
print(tot / T, sq / T - (tot / T) ** 2, over / T)
# 2.718477 0.7668338004709989 1.358733950107968   （E[S_N] = e/2 = 1.3591）

random.seed(5)
T, tot = 10 ** 6, 0
for _ in range(T):
    prev, k = random.random(), 1
    while True:
        x = random.random(); k += 1
        if x < prev: break
        prev = x
    tot += k
print(tot / T)                              # 2.718442   首次下降的位置，期望同样是 e