假设我们有一些具有有限数量的可能结果的离散分布，是否可以比O（logn）更快地从该分布生成随机数，其中n是数字可能的结果？
How to make it in O(logn):
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然后随机播放结果 .
1 回答
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然后随机播放结果 .