这个随机数生成算法的名字是什么？

Question

我正在寻找RNG方法或算法的名称，如下所述。结合一个非均匀随机数发生器的多个结果，可以得到更均匀的结果.这似乎是RNG算法，尤其是HRNG算法所采用的一种常见方法，可以产生更多统计上的随机结果。

--如果有人能帮助识别这个方法的数学/stat/crypto名称，那就太棒了--

下面的代码演示了该方法的一个简单实现，其中“bad”RNG产生的结果不一致，“good”RNG产生的结果约为50/50。

import random

# Function representing a non-uniform random number generator
def bad_RNG():

    result = 0
    if (random.random() > .99):
        result = 1

    return result

# Function that repeatedly applies an RNG function to create a more uniform result
def good_RNG():

    result = 0
    for i in range(100):
        if (bad_RNG() != bad_RNG()):
            result = 1 - result

    return result

# Tests RNG functions by running them 100 times, and printing the distribution of their results
def test_RNG(RNG_func):

    zeros = 0
    ones = 0
    
    for i in range(100):

        result = RNG_func()

        if (0 == result):
            zeros = zeros + 1
        else:
            ones = ones + 1

    print(zeros, end="|")
    print(ones)

print("bad_RNG result:")
test_RNG(bad_RNG)
print("\ngood_RNG result:")
test_RNG(good_RNG)

替代英语解释

假设RNG函数F()返回0或1.F()结果是不一致的，因为它通常返回0。通过对几个F()结果的求和，并应用模2，结果接近50/50的均匀分布。

Answer 1

该算法是一种无偏置算法，是一种随机抽取算法。

另一种方法是von去偏置，在这里，您可以采取2位(X_n,X_{n+1})和输出Z=0，如果

(X_n,X_{n+1})=(0,1),

输出Z=1,

(X_n,X_{n+1})=(1,0),

否则就放弃这两位。如果序列X_n是独立且同分布的，这就给出了完全一致的输出位，因为这两个(0,1),(1,0)都有精确的p(1-p)概率。

Answer 2

good_RNG可以被描述为:实现无偏(或随机抽取，或后处理)算法，执行bad_RNG的200个连续输出的排他或或，使用一个由2倍展开的循环，可能在bad_RNG中有一个意外的依赖于数据的定时依赖。

这是因为

• 当\mathtt{foo}\in\{0,1\}和\mathtt{bar}\in\{0,1\}时，expression foo != bar归结为\mathtt{foo}\oplus\mathtt{bar}，其中\oplus是独占的-OR也就是XOR，可能具有数据定时依赖关系。
• 当\mathtt{zoo}\in\{0,1\}和\mathtt{result}\in\{0,1\}时，code if (zoo): result = 1 - result归结为\mathtt{result}\gets\mathtt{result}\oplus\mathtt{zoo}，可能与数据定时相关。
• \oplus是相联的。

在专业实践中，对这些事实缺乏评论将是一种应受惩罚的罪行。

我怀疑这个基本方法是否有一个具体的名称。如果有，则在Markus的有偏随机数后处理的坏与好方法中没有给出，在FSE 2007议事录中，它声明(关于好的)：

可能最简单的方法是从生成器中异或n位，以便获得一位输出，其中n是一个比1大的固定整数。

这就是good_RNG为n=200所做的。