假设我有每个边k具有一定的概率上来时，我把它卷的P K n边装模。我很好奇，如果有好的算法，静态存储该信息（即一组固定的概率），这样我就可以有效地模拟一个随机卷的模具。

Suppose that I have an n-sided loaded die where each side k has some probability pk of coming up when I roll it. I'm curious if there is good algorithm for storing this information statically (i.e. for a fixed set of probabilities) so that I can efficiently simulate a random roll of the die.

目前，我对这个问题的O（LG n）的解决方案。我们的想法是存储的前k侧面对于所有的k的累积概率的表，它们产生在范围[0的随机实数，1）和在表执行二进制搜索，获得的累积最大索引值不大于所选择的值越大。我比较喜欢这样的解决方案，但似乎奇怪的是，运行时不走的概率考虑。特别是，在一侧的极值情况下，总是想出或值均匀分布，这是可能的（1）用幼稚的方式，以产生辊为O的结果，但我的解决方案仍然需要logarithmicallh许多步骤。

Currently, I have an O(lg n) solution for this problem. The idea is to store a table of the cumulative probability of the first k sides for all k, them to generate a random real number in the range [0, 1) and perform a binary search over the table to get the largest index whose cumulative value is no greater than the chosen value. I rather like this solution, but it seems odd that the runtime doesn't take the probabilities into account. In particular, in the extremal cases of one side always coming up or the values being uniformly distributed, it's possible to generate the result of the roll in O(1) using a naive approach, though my solution will still take logarithmicallh many steps.

有没有人有关于如何解决这个问题的方式，是某种自适应，在它的运行有什么建议？

Does anyone have any suggestions for how to solve this problem in a way that is somehow "adaptive" in it's runtime?

修改：基于这个问题的答案，我已经写了 文章描述了多种方法对这一问题 ，连同他们的分析。它看起来像Vose公司的执行别名方法，给出了与西塔（N）preprocessing时间和O（1）每掷骰，这是真正的即时通讯pressive时间。希望这是一个有用的除了包含在答案的信息！

EDIT: Based on the answers to this question, I have written up an article describing many approaches to this problem, along with their analyses. It looks like Vose's implementation of the alias method gives Θ(n) preprocessing time and O(1) time per die roll, which is truly impressive. Hopefully this is a useful addition to the information contained in the answers!

推荐答案

您正在寻找别名方法提供一个 O（1）方式产生一个固定的离散概率分布（假设你可以访问条目长度的数组N的固定时间）与一次性O（n）的设置。你可以找到它在第3章（PDF）中的