别名法与水塘采样

别名法（PBRT 4e A.1）

• 结构：$n$ 个桶，每个桶代表 $1/n$ 的概率质量。桶 $i$ 存 $q_i$ 和别名下标：选中桶 $i$ 后，以概率 $q_i$ 返回 $i$，否则返回别名。可以证明"每个桶对应自身结果 + 至多一个别名"足以表示任意离散分布。所有 $p_i$ 相等时 $q_i=1$，退化为 $\lfloor n\xi\rfloor$。 别名表采样只需一次均匀掷骰：先选桶，再在桶内决定接受本桶结果还是走别名。

flowchart TD
  U["均匀随机数 u"] --> Bucket["桶下标 i = floor(n·u)"]
  Bucket --> Frac["小数部分决定接受"]
  Frac --> Q{"小于 q_i？"}
  Q -->|"是"| RetI["返回结果 i"]
  Q -->|"否"| RetA["返回别名 alias[i]"]

• 例（表 A.1）：$p=\{1/2,1/4,1/8,1/8\}$，表为 桶 1：$q=1$；桶 2：$q=0.5$，别名 1；桶 3：$q=0.5$，别名 1；桶 4：$q=0.5$，别名 2。笔者逐项核算：$P(1)=\tfrac14+\tfrac14\cdot\tfrac12+\tfrac14\cdot\tfrac12=\tfrac12$，$P(2)=\tfrac14\cdot\tfrac12+\tfrac14\cdot\tfrac12=\tfrac14$，$P(3)=P(4)=\tfrac18$，正确。（按下面的 Vose 算法，桶 2 的 $\hat p=1$，实际会得到 $q_2=1$ 的另一张同样合法的表。）
• 构建（Vose 1991）：把概率乘以 $n$ 得 $\hat p_i=np_i$（平均值为 1），分成 $\hat p<1$ 的 under 表和 $\hat p\ge1$ 的 over 表。每次各取一项 un、ov：桶 un 的 $q=\hat p_{un}$、别名为 ov；ov 剩下 $\hat p_{un}+\hat p_{ov}-1$，按大小放回相应的表。每轮恰好消耗 1 单位质量、少一个桶，剩余桶的平均值仍为 1，所以总能继续直到结束，总时间 $O(n)$。浮点舍入可能使某一表剩下几项（值略大于或略小于 1），把它们设为 $q=1$。
• 实现细节：权重和用 double 累加（结果数多、量级差大时单精度会让构建出错）；采样时 $u$ 只用于选桶，$nu-\lfloor nu\rfloor$ 又是一个均匀数，用它决定是否取别名，再把剩余部分重映射成新的均匀样本返回（与 随机变量变换与逆变换采样 中 SampleDiscrete() 的样本复用同理）。每个桶同时存结果本身的 $p$，以便返回 PMF。
• 用途：PowerLightSampler 按功率选光源（见 多光源采样与光源 BVH）。

水塘采样（A.2）

• 基本算法（源自磁带时代，只能顺序读一遍、数据放不进内存）：第 $n$ 个候选以概率 $1/n$ 放入水塘。归纳证明：前 $n$ 个之后水塘中每个候选的概率都是 $1/n$；第 $n+1$ 个以 $1/(n+1)$ 进入，原样本以 $n/(n+1)$ 保留，乘积仍是 $1/(n+1)$。Vitter 1985 把这个基本算法归功于 Alan Waterman。
• 加权版本（Chao 1982）：候选以 $w/\sum w$ 的概率替换，WeightedReservoirSampler 记录权重和与水塘样本的权重，PMF 即二者之比。另有一个 Add() 接受回调，只在样本真正入选时才计算其值，适合"权重便宜、值昂贵"的情况。 加权水塘每次看到新候选，就以「自身权重 / 已见权重和」的概率替换水塘中的样本。

flowchart TD
  Cand["新候选权重 w"] --> Sum["累加 W ← W + w"]
  Sum --> Prob["替换概率 = w / W"]
  Prob --> Roll{"掷骰接受？"}
  Roll -->|"是"| Rep["水塘 ← 该候选"]
  Roll -->|"否"| Keep["水塘不变"]

• 合并：以"第二个水塘的权重和 / 两者权重和"的概率取第二个水塘的样本，结果与一个水塘看过全部候选完全等价——这正是 Add() 的操作（练习 A.1 要求证明）。这一性质使得空间、时间复用成为可能，如 ReSTIR（Bitterli 等 2020，PBRT 第 16 章与 多光源采样与光源 BVH 的延伸阅读都提到它）。水塘采样本身是一种重要性重采样，其无偏性来自 蒙特卡洛积分与重要性采样 中的离散估计。
• 数组中的采样器用默认构造，之后用 Seed() 分别设置随机数种子（见 伪随机数生成）。

其他加速表格化分布查找的方法（延伸阅读）

引导表 (guide table)：Chen–Asau 1974，Cline 等 2009 引入图形学并提出分段线性逆 CDF 的常数时间近似；Lawrence 等 2005 的自适应 CDF；GPU 上并行构建的基数树森林（Binder–Keller 2020）；用光追硬件做逆变换采样（Morrical–Zellmann 2021）；从算术编码角度看，最优的二叉查找树就是 Huffman 树（MacKay 2003、Piponi 2012）。别名法最早由 Walker（1974、1977）提出，Schwarz 2011 有详细的实现讨论。

取舍