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

Question

假设我有一个非均匀函数并在集合 A 中生成元素。我有一个集合 B，它具有生成 A 中每个元素的概率。有什么方法可以使非均匀伪随机函数表现得像均匀伪随机函数。

Answer 1

当然。从 A 以均匀概率生成元素的简单方法:

为 A

的每个元素分配一个数字

对于A的每个元素，生成一个对应的随机元素，并记下其对应的编号

选择 A 中随机数最小的元素。如果有平局，则对第一个平局的元素重复。

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