Entropic Generation of Binary Words

问题陈述
本文探讨了具有固定汉明重量 $k$ 的长度为 $n$ 的二进制词的均匀生成问题（等价于从 $n$ 个元素中抽取 $k$-子集）。虽然此类生成器的计算时间复杂度已有深入研究，但作者将关注点放在了随机比特的消耗上，将其视为一种关键资源，特别是在依赖硬件真随机数生成器（TRNG）且随机性成本高昂的场景下。

生成来自大小为 $\binom{n}{k}$ 的状态空间的均匀样本，其信息论下界为 $H = \log_2 \binom{n}{k}$ 比特。目标是设计出期望随机比特消耗量在渐近意义上接近该熵值 $H$ 的算法。本文专门针对“多项式稀疏区间”，即定义为 $k \sim n^\beta$ 且 $\beta \in (0, 1)$ 的固定情形。现有的方法往往呈现两极分化：部分 Fisher-Yates 洗牌适用于高度稀疏的输入（$k \ll n$），而 MERGE 算法的变体则适用于较稠密的输入（$k = \Omega(n^{2/3+\epsilon})$）。然而，此前尚无算法能在中间稀疏区间（即 $\beta \in (0, 2/3]$）内同时实现线性时间复杂度 $O(n)$ 和近乎最优的熵成本。

方法论：随机比特回收
其核心创新在于“随机比特回收”范式。作者观察到，标准的生成方法（如 Fisher-Yates 洗牌）在形成组合对象后，会隐式地生成并随后丢弃内部结构（如置换）。这一过程实际上“浪费”了熵。

所提出的方法论通过反转标准的生成过程来倒置这一过程：

1. 解构： 算法并非仅通过消耗比特来构建结构，而是通过概念性地逆转生成过程，从生成的结构（或中间状态）中提取独立的随机比特。
2. 回收： 这些提取出的比特随后被重复利用（“回收”），用于驱动后续的生成步骤，从而降低净新鲜随机比特的消耗。

本文详细介绍了两种主要的机制：

• 平衡二进制词： 对于平衡词（$k=n/2$），作者反转了“平衡合并”（Balanced Merge）程序。通过对耗尽条件进行采样（由 Banach Matchbox 分布建模）并反转 Fisher-Yates 插入步骤，提取出一系列独立的均匀比特。
• 置换解构： 对于一般置换，算法递归地将一个大小为 $n$ 的置换拆分为一个平衡二进制词和两个较小的置换。通过解构该平衡词来产生比特，并对子置换进行递归处理。这实现了从大小为 $n$ 的置换中提取出 $n \log_2 n - O(n)$ 比特的速率。

核心贡献与算法
本文提出了一种新型的均匀二进制词生成器，填补了在多项式稀疏区间内实现线性时间复杂度与近乎最优熵成本之间的空白。

1. 带解构的可区分 Fisher-Yates 法：
   为了生成一个权重为 $k$ 的词，作者使用具有不同标识符 $1, \dots, k$ 而非不可区分标识符的数组进行初始化。随后执行部分 Fisher-Yates 洗牌。生成的数组索引定义了该二进制词，而由非零元素组成的序列则构成了一个大小为 $k$ 的均匀随机置换。该置换随后被送入 DeconstructPermutation 算法，以回收“浪费”的熵（$\log_2 k!$ 比特）。

   • 结果： 这产生了一个**一阶熵（first-order entropic）**算法。其净比特消耗为 $\log_2 \binom{n}{k} + O(k)$。由于在目标区间内 $O(k) = o(\log_2 \binom{n}{k})$，其消耗在渐近意义上匹配了熵的下界。运行时间为 $O(n)$。

2. 链式回收实现近熵生成：
   为了实现**近熵（near-entropic）**生成（即消耗量为 $(1+\epsilon)H$，其中 $\epsilon > 0$），作者提出了一个迭代方法（算法 5：l-ChainedRecyclingFY）。

   • 生成过程被分为 $l+1$ 个步骤。在每个步骤 $i$ 中，使用 Fisher-Yates 插入 $k_i$ 个元素的一个子集。
   • 由这些元素形成的置换会被立即解构以提取随机比特。
   • 这些回收的比特被用于资助下一步骤（$i+1$）的插入操作。
   • 通过调整参数 $l$，可以将随机比特的多倍过量消耗限制在任意接近 1 的范围内。
   • 结果： 该算法运行时间为 $O(n)$，并能实现比特复杂度为 $\frac{1-\beta}{1-\beta^{l+1}} k \log_2 n + O(k)$，随着 $l$ 的增加，该复杂度趋向于熵的下界。

结果

• 时间复杂度： 所提算法在多项式稀疏区间（$k \sim n^\beta, \beta \in (0,1)$）内的期望运行时间为线性时间 $O(n)$。
• 比特复杂度：
  • 可区分插入法是一阶熵的：消耗为 $\log_2 \binom{n}{k} + O(k)$。
  • 链式回收法是近熵的：对于任何 $\epsilon > 0$，算法可以配置为消耗 $(1+\epsilon)\log_2 \binom{n}{k} + o(\log_2 \binom{n}{k})$ 比特。
• 最优性： 这些算法在随机比特消耗方面接近最优，紧密匹配了由信息论推导出的 Shannon 熵下界。

意义与主张
本文声称提供了首个在多项式稀疏区间内，能同时实现线性时间复杂度和近乎最优熵成本的固定汉明重量二进制词生成算法。

作者强调，将随机比特视为一种稀缺资源，比单纯进行标准运行时分析提供了更精确的分析框架。他们认为，“熵解构”与回收的范式具有普适性。具体而言，他们指出正在进行的相关工作，旨在将这种机制应用于从 Boltzmann 型采样器中被拒绝的结构里回收“浪费”的熵，以实现精确规模的生成。文章最后总结道，这种方法既允许在大批量处理中进行高效的熵生成（通过汇集回收的比特），也允许通过递归链式调用实现单实例的近熵生成。