假设我们有一些可能结果数量有限的离散分布，是否有可能比 O(logn) 更快地从此分布生成随机数，其中 n 是可能结果的数量？
如何在 O(logn) 中实现:
- 用累积概率创建一个数组(Array[i] = 随机数小于或等于 i 的概率)
- 从均匀分布中生成随机数(用 k 表示)
- 找到最小的 i，使得 k < Array[i]。它可以使用二分搜索来完成。
- i 是我们的随机数。
最佳答案
Walker 的别名方法可以使用一些需要预先计算的大小为 n 的辅助数组，在恒定的最坏情况时间内抽取样本。此方法在 Devroye's book on sampling 的第 3 章中有所描述。并在 R sample() 函数中实现。您可以从 R 的源代码或 this thread 中获取代码。 .一个 1991 paper by Vose声称可以降低初始化成本。
请注意，除非您指定输入的确切形式以及要绘制的随机数数量，否则您的问题并没有明确定义。例如，如果输入是给出每个结果概率的数组，那么您的算法不是 O(log n)，因为它需要首先计算从输入数组中花费 O(n) 时间的累积概率。
如果您打算绘制许多样本，那么生成单个样本的成本就不是那么重要了。相反，重要的是生成 m 个结果的总成本以及所需的峰值内存。在这方面，别名方法非常好。如果您想一次生成所有样本，请使用 O(n+m) 算法发布 here然后对结果进行洗牌。
关于random - 如何从指定的离散分布生成随机数？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4207238/