如何从指定的离散分布生成随机数? [英] How to generate a random number from specified discrete distribution?
问题描述
让我们说我们有一些具有有限数量可能结果的离散分布，是否有可能比O(logn)更快地从这种分布中生成一个随机数，其中n是数量可能的结果?
如何在O(登录)中创建它:
-制作具有累积概率的数组(Array [i] =随机数小于或等于i的概率)
-根据均匀分布生成随机数(用k表示)
-找出最小的i，使k ＜k.数组[i].可以使用二进制搜索来完成.
-我是我们的随机数.
Walker的别名方法可以使用一些大小为n的辅助数组在恒定的最坏情况下绘制样本，而这些辅助数组需要预先计算.此方法在 Devroye的关于采样的书的第3章中进行了描述并实现了在R sample()函数中.您可以从R的源代码或此线程. Vose的 1991年论文声称可以降低初始化成本./p>
请注意，除非您指定输入的确切形式以及要绘制的随机数，否则问题的定义不明确.例如，如果输入是给出每个结果概率的数组，则您的算法不是O(log n)，因为它需要首先计算从输入数组花费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.
这篇关于如何从指定的离散分布生成随机数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
