将非均匀伪随机生成转换为均匀随机生成？

Question

假设我有一个非均匀的函数，可以生成 A 集合中的元素。我有一个集合 B，其中包含 A 集合中每个元素生成的概率。是否有办法使非均匀伪随机函数表现得像均匀伪随机函数。

- Ricky

---

你能提供一些代码吗？不太清楚你想要什么。你想从A中均匀选择吗？然后以1/sizeof(N)的概率进行采样。 - Severin Pappadeux

Answer 1

当然。一个从A中等概率生成元素的简单方法是：

1. 为A中的每个元素分配一个数字
2. 对于A中的每个元素，生成一个相应的随机元素，并记录其相应的数字
3. 选择具有最小随机数的A元素。如果存在平局，则重复与排名并列的元素。

一种高效的方法是使用范围编码器根据给定的概率对一系列随机（非均匀）元素进行编码。这将生成一系列均匀的随机位。然后你可以解码它，假设所有符号的概率相等，以获得A的均匀分布元素。参见：https://en.wikipedia.org/wiki/Range_encoding 另一种生成均匀随机比特流的方法是计算您的随机源的熵，然后将输出分成块，并使用像SHA-1这样的加密哈希函数进行散列。这些块应足够大，以提供比哈希函数的比特长度更多的熵位。在现实生活中，这种方法可能更安全，因为即使您的生成器产生的符号分布错误，它也可以工作。详见：https://en.wikipedia.org/wiki/Entropy_(information_theory)

- Matt Timmermans

Answer 2

让我建议一个简单的算法，您不需要知道选择A中每个元素（问题中的B集合）的概率。 我假设A中的每个元素都有已知的顺序（例如，每个元素都是一个数字）。

该算法分为两部分。 第一部分是生成无偏随机位的算法。 我们将其称为“RandomBit()”（Morina等人，2019）。

1. 从A中抽取一个独立元素，称之为X，然后再从A中抽取另一个独立元素，称之为Y。
2. 如果X小于Y，则返回0。 如果Y小于X，则返回1。 如果都不是这种情况，请转到步骤1。

这可行的原因是从A中抽取的独立对在统计上是相同的（Montes Gutiérrez 2014，De Schuymer等人2003）； 有关详细信息，请参阅我的有关随机性提取的说明附录。

下面是一个在[0,1]范围内生成均匀随机数的算法。你所要做的就是“并置足够多的随机二进制数字”（von Neumann 1951）：加上RandomBit()/2 + RandomBit()/4 + RandomBit()/8 + ....

如果你的非均匀分布是正态分布，请参考Cross Validated上的以下问题，了解更多技巧：https://stats.stackexchange.com/questions/117689

参考文献：

• Von Neumann, J., "Various techniques used in connection with random digits", J. Res. Nat. Bur. Stand. Appl. Math. Series 3, 36-38 (1951)。
• Morina, G., Łatuszyński, K., et al., "从伯努利工厂到骰子企业：通过马尔可夫链的完美抽样", arXiv:1912.09229 [math.PR], 2019。
• Montes Gutiérrez, I., "Comparison of alternatives under uncertainty and imprecision", 博士论文, Universidad de Oviedo, 2014。
• De Schuymer, Bart, Hans De Meyer, and Bernard De Baets. "A fuzzy approach to stochastic dominance of random variables", 国际模糊系统协会2003年世界大会论文集。

- Peter O.