从加权概率列表中随机选择

Question

我有一个N元素的数组（表示给定字母表中的N个字母），数组的每个单元格都包含一个整数值，该整数值表示在给定文本中该字母出现的次数。现在我想根据以下约束条件从所有字母中随机选择一个字母：

• 如果该字母具有正（非零）值，则算法始终可以选择它（当然具有更大或较小的概率）。
• 如果字母A的值比字母B高，则算法选择字母A的可能性应更大。

现在，考虑到这一点，我想出了一个简单的算法可能会完成任务，但我只是想知道是否有更好的方法。这似乎是相当基础的，我认为可能有更聪明的方法来更有效地实现这一点。这是我想到的算法：

• 将数组中所有频率相加。将其存储在SUM中
• 从0到SUM中选择一个随机值。将其存储在RAN中
• [当] RAN > 0时，从第一个开始，按顺序访问数组中的每个单元格，并从其中减去该单元格的值
• 最后访问的单元格就是选择的字母

那么，除了这个之外有更好的方法吗？我有什么遗漏的吗？

我知道大多数现代计算机可以如此快地计算出这个算法，以至于我甚至不会注意到我的算法是否低效，因此这更多是一个理论问题而不是实际问题。

我更喜欢解释性算法而不是提供答案的代码，但如果您更喜欢用代码提供答案，我没有问题。

- Setzer22

Answer 1

这个想法：

• 遍历所有元素，并将每个元素的值设置为到目前为止的累积频率。
• 生成一个介于 1 和所有频率之和之间的随机数。
• 对这个数字的值进行二分查找（找到第一个大于或等于该数字的值）。

例子：

Element    A B C D
Frequency  1 4 3 2
Cumulative 1 5 8 10

在1-10的范围内生成一个随机数（1+4+3+2=10，与累积列表中的最后一个值相同），进行二分查找，将返回以下值：

Number   Element returned
1        A
2        B
3        B
4        B
5        B
6        C
7        C
8        C
9        D
10       D

- Bernhard Barker

---

顺便说一下，这种方法被称为“逆变换抽样”。 - Thomas

Answer 2

别名方法每产生一个值的时间复杂度为O(1)，但每次查找需要两个均匀分布随机数。基本上，您需要创建一张表，其中每一列包含要生成的其中一个值、另一个被称为别名的值和选择该值或其别名的条件概率。使用第一个随机数以相等的可能性选择任何一列。然后根据第二个随机数在主值和别名之间进行选择。初始化一个有效表格需要O(n log n)的工作量，但构建完成后，生成值的时间是固定的。您可以下载此 Ruby gem 查看实际实现。

Marsaglia等人提出的另外两种非常快速的方法在这里进行了描述。他们提供了C语言实现。

- pjs

---

这里有肯特·贝克制作的Vose Alias示例图片：https://www.facebook.com/note.php?note_id=323786247654246 - aka.nice

@aka.nice 还有在 Smalltalk 中也是。太好了！ - pjs

+1。感谢分享 - 我有一个项目，其中我正在使用上述二分查找方法，而你的方法看起来是很大的改进。阅读Marsaglia的论文，我是否理解正确，Marsaglia方法II本质上只是别名方法？我很惊讶方法I更快；你能分享任何有关为什么会这样的直觉吗？ - Julian

补充aka.nice的评论，Keith Schwarz在http://www.keithschwarz.com/darts-dice-coins/上提供了一个视觉解释（链接在Facebook笔记中）。非常酷！ - Mark Peschel

@pjs，我看到你将时间复杂度从O(n)改为了O(n log n)。然而，《Darts，Dice和Coins》声称Vose Alias的运行时间为O(n)，并且假设添加和删除集合的平摊时间为O(1)，我同意这个结论。我是否有误解？ - Mark Peschel

@pjs 不用在意，我误解了。建立表的时间复杂度O(n)假设元素已经排序好；O(n log n)考虑了排序时间。 - Mark Peschel