论文标题
使用偏置随机源生成离散均匀分布的有效方法
An Efficient Method To Generate A Discrete Uniform Distribution Using A Biased Random Source
论文作者
论文摘要
本文提出了一种有效的算法，以使用$ p $ prime的有偏见的随机源在一组$ p $元素上生成离散统一分布。该算法概括了冯·诺伊曼（Von Neumann）的方法，并提高了Dijkstra方法的计算效率。此外，该算法将扩展以根据整数的质量分解在任何有限的集合上生成离散的均匀分布。所建议算法的时间复杂性是总体sublinear $ \ operatatorName {o}（n/\ log n）$
This article presents an efficient algorithm to generate a discrete uniform distribution on a set of $p$ elements using a biased random source for $p$ prime. The algorithm generalizes Von Neumann's method and improves computational efficiency of Dijkstra's method. In addition, the algorithm is extended to generate discrete uniform distribution on any finite set based on the prime factorization of integers. The time complexity of the proposed algorithm is overall sublinear $\operatorname{O}(n/\log n)$
