Algorithms, Complexity, and Entropy of the Bernard-Letac Fair-Sampling Construction

技术摘要：Bernard–Letac 公平采样构造的算法、复杂度与熵

问题陈述
本文探讨了一个基本问题：如何从一个具有未知分布 $\pi$ 的偏置、独立同分布（i.i.d.）源中，生成 $m$ 种可能结果的均匀随机结果。该过程必须对每一个可容许的 $\pi$ 均有效，且无需预先知晓偏差，通过有限但随机的抽取次数来实现。这扩展了经典的冯·诺依曼拒绝方案（von Neumann rejection scheme, 1951）以及霍夫丁–西蒙斯二元行走（Hoeffding–Simons binary walk, 1970），将其应用到了任意字母表和任意模数 $m$ 上。

方法论
本研究基于 Bernard 和 Letac 在 1971 年提出的构造，该构造定义了一个停止集 $H_m = \{x \in \mathcal{M} : c(x) \equiv 0 \pmod m\}$，其中 $c(x)$ 是累积符号计数 $x$ 的多项式系数。随机行走在首次到达 $H_m$ 时终止。作者从原始的组合与数论定理中提取了五种不同的算法，并提供了形式化的正确性保证和复杂度分析。

关键方法论工具包括：

• 库默尔定理（Kummer's Theorem）： 用于通过基-$p$ 加法中的进位传播，高效计算多项式系数的 $p$ 进估值（$p$-adic valuation）。
• 雷尼熵（Rényi Entropy）： 用于刻画期望停止时间，揭示其复杂度受限于阶数为 $p, p^2, p^3, \dots$ 的雷尼熵。
• 有限自动机（Finite Automata）： 构建了一个七状态自动机来计算二元行走的模-2 一阶通过核（first-passage kernel），取代了动态规划方法。
• 转移定理（Transfer Theorems）： 用于确立核的截面族（section family）是有限的，从而实现高效计算。

主要贡献与结果

1. 算法提取与复杂度：
   本文形式化了五种算法：

   • 算法 1： 以 $O(|I| \cdot (\log_p(\max x_i) + \log_p |I|))$ 的时间计算 $v_p(c(x))$。
   • 算法 2： 主要的公平 $m$ 路采样器。它几乎处处停止并产生均匀结果。路径分配步骤（对观察到的路径进行排序）被确定为计算瓶颈。
   • 算法 3： 使用“三角形定理”加速的 $H_{p^n}$ 成员判定算子。
   • 算法 4： 模 $p^n$ 下多项式系数的周期性查找表。
   • 算法 5： 计算 $p$ 进极限 $L(x) = \lim_{n \to \infty} c(p^n x)$。
     对于一般情况，期望计算成本为 $O(E(T) \cdot |I| \cdot \log T \cdot \omega(m))$，其中 $\omega(m)$ 是 $m$ 的不同素因子的数量。

2. 精确期望停止时间与熵：
   对于素数模数 $m=p$，本文推导出了期望抽取次数 $E(T)$ 的精确乘积公式：
   $$E(T) = p \prod_{n=1}^{\infty} \frac{1 - (U_n(\pi))^p}{1 - U_n(\pi)}$$
   其中 $U_n(\pi) = \sum_i \pi_i^{p^n} = e^{(1-p^n)H_{p^n}(\pi)}$。

   • 近似： 证明了一阶近似 $E(T) \approx p / (1 - e^{(1-p)H_p(\pi)})$ 总是严格高估真实值。
   • 香农极限： 当 $p \to 1^+$ 时，$E(T)$ 收敛于一个依赖于全分布 $\pi$ 而非仅依赖于其香农熵 $H(\pi)$ 的常数 $C(\pi)$。对于对称二元源，$C(\pi) \approx 2.8457$，而信息论下界 $1/H(\pi) \approx 1.4427$。
   • 效率： 效率 $\eta(p) = \log p / (E(T)H(\pi))$ 在 $p \to 1^+$ 和 $p \to \infty$ 时趋于 0，并在中间尺度 $p^*$ 达到最大值。下界 $E(T) \ge \log m / H(\pi)$ 永远无法达到。

3. 二元行走优化（定理 D）：
   针对 $m=2$ 且为二元字母表的特定情况，本文提出了一个转移定理。一个七状态自动机可以计算避开停止集的单调格点路径数量的奇偶性。这使得公平分组的计算复杂度从通过动态规划实现的 $O(T^2)$ 降低到了 $O(T \log T)$ 比特运算。

4. 复合模数：
   论文指出，对于复合模数 $m$，由于不同素数基底之间数字与进位结构的耦合，不存在闭式解表达式 $E(T)$。数值证据表明，即使对于复合模数，Bernard–Letac 方法也优于结合了冯·诺依曼去偏技术和 Lumbroso 快速骰子生成器（Fast Dice Roller）的方法。

意义与主张
本文声称弥合了 Bernard 和 Letac 的原始组合结果与现代计算及信息论视角之间的鸿沟。

• 它提供了第一个关于期望成本的、以雷尼熵表示的精确乘积公式。
• 它确立了采样器的效率严格小于信息论下界且永远无法达到该下界，这与通过牺牲延迟来换取效率的渐近最优块程序（如 Elias 方案）形成对比。
• 它证明了 Bernard–Letac 构造虽然优先考虑即时性（在线、顺序操作）而非渐近最优性，但通过在不经过中间去偏阶段的情况下提取有用信息，展现了结构上的优势。
• 将二元分配成本通过转移自动机降低至近线性时间，被视为二元情况下显著的计算改进。

开放问题
论文识别了若干尚未解决的问题，包括：

• 复合模数是否存在闭式解 $E(T)$ (P2)。
• 数据自适应的停止边界是否能在保持公平性的同时提高效率 (P4)。
• $p$ 进极限 $L(x)$ 在熵层面的解释 (P5)。
• 对于一般素数模数 $p > 2$，是否存在转移系统 (P1)。