标题： 米开朗基罗滚动：精确且高效地雕刻有理分布 显示英文标题

标题： MichelangeRoll: Sculpting Rational Distributions Exactly and Efficiently

摘要： 使用公平的硬币投掷来模拟任意离散分布 $D \in [0, 1]^n$ 会在熵复杂度与空间和时间复杂度之间产生权衡。 香农的理论表明 $H(D)$ 次投掷是必要且充分的，但不能保证精确分布。 Knuth 和 Yao 表明，决策树在获取一个精确样本时消耗的投掷次数少于 $H(D) + 2$。 Drapper 和 Saad 近期的研究探讨了空间和时间层面的问题，表明其成本仅为 $H(D) + 2$ 次投掷、$O(n \log(n) \log(m))$ 的内存空间以及 $O(H(D))$ 的运算次数，其中 $m$ 是 $D$ 中概率质量的公分母，$n$ 是可能结果的数量。 在本文中，MichelangeRoll 回收了剩余的熵，从而突破了“$+2$”的障碍。 使用$O((n + 1/\varepsilon) \log(m/\varepsilon))$内存，生成持续序列$D$的熵成本降低到每个样本$H(D) + \varepsilon$。 显示英文摘要

摘要： Simulating an arbitrary discrete distribution $D \in [0, 1]^n$ using fair coin tosses incurs trade-offs between entropy complexity and space and time complexity. Shannon's theory suggests that $H(D)$ tosses are necessary and sufficient, but does not guarantee exact distribution. Knuth and Yao showed that a decision tree consumes fewer than $H(D) + 2$ tosses for one exact sample. Drapper and Saad's recent work addresses the space and time aspect, showing that $H(D) + 2$ tosses, $O(n \log(n) \log(m))$ memory, and $O(H(D))$ operations are all it costs, where $m$ is the common denominator of the probability masses in $D$ and $n$ is the number of possible outcomes. In this paper, MichelangeRoll recycles leftover entropy to break the "$+2$" barrier. With $O((n + 1/\varepsilon) \log(m/\varepsilon))$ memory, the entropy cost of generating a ongoing sequence of $D$ is reduced to $H(D) + \varepsilon$ per sample.