algorithm - 来自非线性概率的线性概率

Question

这是我的问题。

假设您有一个这样的函数:(在 C 中)

int strangeRand() {
    if ( rand() % 100 <= 70 ) return 0;
    else return 1;
}

这个返回 0 的概率为 0.7 和 1 的概率为 0.3

这就是我想要做的，创建一个以 0.5 的概率返回 0 和以 0.5 的概率返回 1 的函数。

我只需要使用 strangeRand() 函数 [不能修改它](和循环，以及 if 等但没有 rand() 函数)

有人知道怎么做吗？

谢谢。

Answer 1

这实际上是一个已解决的问题!它通常被称为获得 fair result from an unfair coin .

算法的工作原理如下:

1. 调用该函数两次。
2. 如果结果匹配，重新开始，忘记两个结果。
3. 如果结果不同，使用第一个结果，忘记第二个。

提供的链接包含对算法工作的原因的解释。