问题描述
您有一个有偏随机数生成器,它以概率 p 生成 1,以概率 (1-p) 生成 0.你不知道 p 的值.使用它制作一个无偏随机数生成器,它以 0.5 的概率产生 1,以 0.5 的概率产生 0.
You have a biased random number generator that produces a 1 with a probability p and 0 with a probability (1-p). You do not know the value of p. Using this make an unbiased random number generator which produces 1 with a probability 0.5 and 0 with a probability 0.5.
注意:此问题是 Cormen、Leiserson、Rivest、Stein 的《算法导论》中的一个练习题.(clrs)
Note: this problem is an exercise problem from Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein.(clrs)
推荐答案
事件 (p)(1-p) 和 (1-p)(p) 是等概率的.将它们分别取为 0 和 1 并丢弃另外两对结果,您将得到一个无偏随机生成器.
The events (p)(1-p) and (1-p)(p) are equiprobable. Taking them as 0 and 1 respectively and discarding the other two pairs of results you get an unbiased random generator.
在代码中,这很简单:
int UnbiasedRandom()
{
int x, y;
do
{
x = BiasedRandom();
y = BiasedRandom();
} while (x == y);
return x;
}
这篇关于使用有偏随机数生成器的无偏随机数生成器的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!