一句话：提出离散分布近似采样的理论框架，并构造在 k 位精度下统计与熵消耗均最优的采样算法。
论文研究随机变量生成的基础问题：在只能使用独立公平比特流且输出分布需用至多 k 位精度表示时，如何从离散分布 (p1,…,pn) 采样。作者建立理论框架，从统计精度与熵消耗两方面刻画采样算法，并提出寻找统计最优（输出分布最接近目标）且信息论最优（期望熵消耗最小）算法的新技术。基于此实现系统，对广泛统计精度度量，能给出所有同分布熵最优 k 位近似采样器中最接近目标者，并优于浮点反演采样等有界熵方法。实验在大量分布上评估精度、熵消耗、精度需求与运行时间，表明其优于现有近似采样器，且常比精确采样器节省显著资源。
This paper addresses a fundamental problem in random variate generation: given access to a random source that emits a stream of independent fair bits, what is the most accurate and entropy-efficient algorithm for sampling from a discrete probability distribution ( p 1 , …, p n ), where the probabilities of the output distribution ( p̂ 1 , …, p̂ n ) of the sampling algorithm must be specified using at most k bits of precision? We present a theoretical framework for formulating this problem and provide new techniques for finding sampling algorithms that are optimal both statistically (in the sense of sampling accuracy) and information-theoretically (in the sense of entropy consumption). We leverage these results to build a system that, for a broad family of measures of statistical accuracy, delivers a sampling algorithm whose expected entropy usage is minimal among those that induce the same distribution (i.e., is “entropy-optimal”) and whose output distribution ( p̂ 1 , …, p̂ n ) is a closest approximation to the target distribution ( p 1 , …, p n ) among all entropy-optimal sampling algorithms that operate within the specified k -bit precision. This optimal approximate sampler is also a closer approximation than any (possibly entropy-suboptimal) sampler that consumes a bounded amount of entropy with the specified precision, a class which includes floating-point implementations of inversion sampling and related methods found in many software libraries. We evaluate the accuracy, entropy consumption, precision requirements, and wall-clock runtime of our optimal approximate sampling algorithms on a broad set of distributions, demonstrating the ways that they are superior to existing approximate samplers and establishing that they often consume significantly fewer resources than are needed by exact samplers.
@article{paperbot528,
title = {Optimal approximate sampling from discrete probability distributions},
author = {Feras A. Saad and Cameron E. Freer and Martin C. Rinard and Vikash K. Mansinghka},
journal = {Proceedings of the ACM on Programming Languages},
volume = {4},
number = {POPL},
year = {2019},
doi = {10.1145/3371104}
}