Tom*_*ski 8 random probability
假设我们有一些具有有限数量的可能结果的离散分布,是否可以比O(logn)更快地从该分布生成随机数,其中n是数字可能的结果？
如何在O(logn)中创建它:
- 创建一个具有累积概率的数组(Array [i] =随机数将小于或等于i的概率)
- 从均匀分布生成随机数(让我们用k表示)
-找到最小的i,使得k <Array [i].它可以使用二进制搜索来完成.
- 我是我们的随机号码.
Walker的别名方法可以在恒定的最坏情况下绘制样本,使用一些需要预先计算的大小为n的辅助数组.这种方法在Devroye关于采样的书的第3章中有描述,并在R sample()函数中实现.您可以从R的源代码或此线程获取代码.Vose在1991年发表的一篇论文声称可以降低初始化成本.
请注意,除非您指定输入的确切形式以及要绘制的随机数,否则您的问题定义不明确.例如,如果输入是给出每个结果概率的数组,那么您的算法不是O(log n),因为它需要首先计算从输入数组花费O(n)时间的累积概率.
如果您打算绘制许多样本,那么生成单个样本的成本就不那么重要了.相反,重要的是产生m个结果的总成本,以及所需的峰值内存.在这方面,别名方法非常好.如果要一次生成所有样本,请使用此处发布的O(n + m)算法,然后对结果进行洗牌.
| 归档时间： |
|
| 查看次数： |
3631 次 |
| 最近记录： |