如何从指定的离散分布生成随机数？
假设我们有一些可能结果数量有限的离散分布，是否有可能比 O(logn) 更快地从该分布生成随机数，其中 n 是可能结果的数量？
如何在 O(logn) 内完成：
- 创建一个具有累积概率的数组（Array[i] = 随机数小于或等于 i 的概率）
- 从均匀分布中生成随机数（用 k 表示）
- 找到最小的 i 使得 k <数组[i]。可以使用二分搜索来完成。
- i 是我们的随机数。
Lets say we have some discrete distribution with finite number of possible results, is it possible to generate a random number from this distribution faster than in O(logn), where n is number possible results?
How to make it in O(logn):
- Make an array with cumulative probability (Array[i] = Probability that random number will be less or equal to i)
- Generate random number from uniform distribution (lets denote it by k)
- Find the smallest i such that k < Array[i]. It can be done using binary search.
- i is our random number.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
Walker 的别名方法可以使用一些需要预先计算的大小为 n 的辅助数组，在恒定的最坏情况时间内抽取样本。此方法在Devroye关于采样的书的第3章中进行了描述并实现在 R Sample() 函数中。您可以从 R 的源代码或此线程。 Vose 于 1991 年发表的论文声称可以降低初始化成本。
请注意，除非您指定输入的确切形式以及要绘制多少个随机数，否则您的问题没有明确定义。例如，如果输入是给出每个结果的概率的数组，那么您的算法不是 O(log n)，因为它需要首先计算输入数组的累积概率，这需要 O(n) 时间。
如果您打算抽取许多样本，那么生成单个样本的成本并不那么重要。相反，重要的是生成 m 个结果的总成本以及所需的峰值内存。在这方面，别名方法非常好。如果您想一次生成所有样本，请使用发布的 O(n+m) 算法 此处，然后打乱结果。
Walker's alias method can draw a sample in constant worst-case time, using some auxiliary arrays of size n which need to be precomputed. This method is described in Chapter 3 of Devroye's book on sampling and is implemented in the R sample() function. You can get code from R's source code or this thread. A 1991 paper by Vose claims to reduce the initialization cost.
Note that your question isn't well-defined unless you specify the exact form of the input and how many random numbers you want to draw. For example, if the input is an array giving the probability of each result, then your algorithm is not O(log n) because it requires first computing the cumulative probabilities which takes O(n) time from the input array.
If you intend to draw many samples then the cost of generating a single sample is not so important. Instead what matters is the total cost to generate m results, and the peak memory required. In this regard, the alias method very good. If you want to generate the samples all at once, use the O(n+m) algorithm posted here and then shuffle the results.