c++ - 使用单个生成器卷从多个分布中获取值

Question

我正在尝试实现 Alias method , 还描述了 here .这是一种允许在 O(1) 中从加权 N 面骰子中采样的算法。

该算法需要生成两个值:

• 一个均匀分布的整数 i在 [0, N]
• 均匀分布的实数 y在 [0, 1)

论文规定这两个数可以通过单个实数得到x在 [0, N) 之间.来自 x然后可以得出两个值:

• i = floor(x)
• y = x - i

现在，我看到的其他实现两次调用随机数生成器，一次生成 i和一个生成y .鉴于我使用的是相当昂贵的生成器 ( std::mt19937 ) 并且我需要多次采样，我想知道在性能方面是否有更好的方法，同时保持结果的质量。

我不确定是否使用 uniform_real_distribution生成 x好像 N 是有道理的那么大y的分布将变得更稀疏 double s 不是均匀分布的。有没有办法调用引擎，取出随机位，然后生成 i和 y直接来自他们？

Answer 1

你是对的，用他们的方法，随着 N 的增加，y 的分布会变得越来越不均匀。

事实上，对于大于 2^52 的 N，y 将恰好为 0，因为所有高于该值的数字都是 double 整数。 2^52 是 4,503,599,627,370,496(4.5 千万亿)。

尽管 N 的合理值根本无关紧要。如果您的 N 小于 2^26(6700 万)，凭直觉应该没问题。您的骰子的边数不会是天文数字，对吗？