algorithm - 加载骰子的数据结构？

Question

假设我有一个 n 面加载的骰子，其中每一面 k 都有一定的概率 p_k 当我滚动它时出现。我很好奇是否有一个好的数据结构来静态存储此信息(即，对于一组固定的概率)，以便我可以有效地模拟随机掷骰子。

目前，我有一个 O(lg n) 的解决方案来解决这个问题。这个想法是存储所有 k 前 k 边的累积概率表，然后生成范围 [0, 1) 内的随机实数并执行对表进行二分查找，得到累积值不大于所选值的最大索引。

我更喜欢这个解决方案，但运行时没有考虑概率似乎很奇怪。特别是，在总是出现一侧或值均匀分布的极端情况下，可以使用天真的方法在 O(1) 中生成滚动结果，而我的解决方案仍将采取对数方式的许多步骤。

对于如何在运行时以某种方式“自适应”的方式解决这个问题，有没有人有任何建议？

更新:根据这个问题的答案，我写了 an article describing many approaches to this problem ，以及他们的分析。看起来 Vose 的别名方法的实现给出了 Θ(n) 预处理时间和每个掷骰子的 O(1) 时间，这确实令人印象深刻。希望这是对答案中包含的信息的有用补充!

Answer 1

您正在寻找 alias method它提供了一种O(1) 方法，用于生成固定的离散概率分布(假设您可以在恒定时间内访问长度为 n 的数组中的条目)，一次性 O(n) 设置.您可以在 chapter 3 (PDF) 中找到它的 "Non-Uniform Random Variate Generation"作者:Luc Devroye。

想法是采用概率数组 p_k 并生成三个新的 n 元素数组，q_k、a_k，和 b_k。每个q_k是0到1之间的概率，a_k和b_k是1到n之间的整数。

我们通过生成两个介于 0 和 1 之间的随机数 r 和 s 来生成介于 1 和 n 之间的随机数。设 i = floor(r*N)+1。如果 q_i < s 则返回 a_i 否则返回 b_i。别名方法的工作是弄清楚如何生成 q_k、a_k 和 b_k。