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

Question

这是我的问题。

假设您有这样一个函数：（在 C 中）

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

这个return0个概率0.7 和 1 的概率为 0.3

这就是我想要做的，创建一个 return 0 的概率为 0.5 和 1 的概率也为 0.5 的函数。

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

有人知道怎么做吗？

谢谢。

Answer 1

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

算法的工作原理如下：

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

所提供的 link 包含对 为什么 该算法有效的解释。