12

如果我有一个名为 rand1() 的函数生成数字 0（30% 概率）或 1（70% 概率），如何编写一个函数 rand2() 生成数字 0 或 1 等概率使用 rand1() ？

更新：</p>

最后发现这是《算法导论（第2）》（我买了这本书的中文版）Excercise 5.1-3这本书的一个问题，原来的问题是：

5.1-3 假设要以概率 1/2 输出 0，以概率 1/2 输出 1。您可以使用一个程序 BIASED-RANDOM，它输出 0 或 1。它以某个概率 p 输出 1，以概率 1− p 输出 0，其中 0 < p < 1，但您不知道 p 是什么。给出一个使用 BIASED-RANDOM 作为子程序的算法，并返回一个无偏的答案，以 1/2 的概率返回 0，以 1/2 的概率返回 1。作为 p 的函数，您的算法的预期运行时间是多少？

解决办法是：（见：http ://www.cnblogs.com/meteorgan/archive/2012/05/04/2482317.html ）

为了得到一个无偏的随机位，只需要调用 BIASED-RANDOM，调用 BIASED-RANDOM 两次。重复这样做，直到两个调用返回不同的值，当这种情况发生时，返回两个位中的第一个：

UNBIASED-RANDOM
while TRUE
do
x ← BIASED-RANDOM
y ← BIASED-RANDOM
if x != y
then return x

要查看 UNBIASED-RANDOM 以 1/2 的概率返回 0 和 1，请观察给定迭代返回 0 的概率是

Pr {x = 0 and y = 1} = (1 − p)p ,

并且给定迭代返回 1 的概率是

Pr {x = 1 and y = 0} = p(1 − p) .

（我们依赖 BIASED-RANDOM 返回的位是独立的。）因此，给定迭代返回 0 的概率等于它返回 1 的概率。由于 UNBIASED-RANDOM 没有其他方法可以返回值，因此它返回0 和 1 各有 1/2 的概率。

4

4 回答 4

13

生成两个数，a和b。

如果a为 0 且b为 1（21% 的机会），则生成 0。
如果a为 1 且b为 0（21% 的机会），则生成 1。

对于所有其他情况（58% 的机会），只需生成一个新的a，b然后再试一次。

于 2012-08-25T13:02:11.027 回答
4

如果您调用两次，则获得and的rand1机会均等，因此，如果您返回每个不匹配对中的第一个（并丢弃匹配对），您将平均获得每个输入位的输出位（其中返回; 在您的示例中为 0.7）并且独立于，每个输出位将为 1，概率为 0.5。[1 0][0 1]0.5(1 - p2 - (1-p)2)prand11p

但是，我们可以做得更好。

我们可以记住它们，而不是丢弃匹配对，希望它们后面跟着相反的匹配对 - 序列[0 0 1 1]和[1 1 0 0]也同样可能，并且我们可以再次在看到这样的序列时返回第一位（仍然有输出概率 0.5。）我们可以无限期地组合它们，寻找诸如此类的序列[0 0 0 0 1 1 1 1]。

我们可以走得更远——考虑输入序列[0 0 0 1]并[0 1 0 0]产生相同的输出 （第二。这是它变得更加复杂的地方，因为您需要开始缓冲输出位。[0][0 0][0 1]

这两种技术都可以递归地应用，并且达到了无损的极限（即，如果rand1概率为 0.5，则每个输入位平均得到一个输出位。）

完整描述（数学）在这里：http ://www.eecs.harvard.edu/~michaelm/coinflipext.pdf

于 2012-08-25T14:42:43.820 回答
0

下面rand2的函数将提供 50% 的概率出现 0 或 1。

#define LIMIT_TO_CALCULATE_PROBABILITY 10 //set any even numbers

int rand2()
{
    static int one_occurred = 0;
    static int zero_occured = 0;
    int rand_value = 0;
    int limit = (LIMIT_TO_CALCULATE_PROBABILITY / 2);

    if (LIMIT_TO_CALCULATE_PROBABILITY == (one_occured + zero_occured))
    {
        one_occured = 0;
        zero_occured = 0;
    }

    rand_value = rand1();   

    if ((1 == rand_value) && (one_occured < limit))
    {
        one_occured++;
        return rand_value;
    }
    else if ((0 == rand_value) && (zero_occured < limit))
    {
        zero_occured++;
        return rand_value;
    }
    else if (1 == rand_value)
    {
        zero_occured++;
        return 0;
    }
    else if (0 == rand_value)
    {
        one_occured++;
        return 1;
    }   
}
于 2012-08-25T14:10:22.643 回答
0

你需要弄清楚你想要多接近 50% 0 50% 1。

如果您将重复调用的结果添加到 rand1. 如果结果为 0 或 2，则返回的值为 0，如果为 1，则返回 1。（在代码中，您可以使用模 2）

int val = rand1();   // prob 30%      0, and 70%      1

val=(val+rand1())%2; // prob 58%      0, and 42%      1  (#1 see math bellow)
val=(val+rand1())%2; // prob 46.8%    0, and 53.2%    1  (#2 see math bellow)
val=(val+rand1())%2; // prob 51.28%   0, and 48.72%   1
val=(val+rand1())%2; // prob 49.488%  0, and 50.512%  1
val=(val+rand1())%2; // prob 50.2048% 0, and 49.7952% 1

你明白了。所以由你决定你想要的概率有多接近。随后的每个电话都会使您更接近 50% 50%，但它永远不会完全相等。

如果你想要概率的数学：

1

prob ((val+rand1()%2) = 0) = (prob(val = 0)*prob(rand1() = 0)) + (prob(val = 1)*prob(rand1() = 1)
                           = (0.3*0.3)+(0.7*0.7)
                           = 0.09 + 0.49
                           = 0.58
                           = 58%

prob ((val+rand1()%2) = 1) = (prob(val = 1)*prob(rand1() = 0)) + (prob(val = 0)*prob(rand1() = 1)
                           = (0.7*0.3)+(0.3*0.7)
                           = 0.21 + 0.21
                           = 0.42 
                           = 42%

2

 prob ((val+rand1()%2) = 0) = (prob(val = 0)*prob(rand1() = 0)) + (prob(val = 1)*prob(rand1() = 1)
                            = (0.58*0.3)+(0.42*0.7)
                            = 0.174 + 0.294
                            = 0.468
                            = 46.8%

 prob ((val+rand1()%2) = 1) = (prob(val = 1)*prob(rand1() = 0)) + (prob(val = 0)*prob(rand1() = 1)
                            = (0.42*0.3)+(0.58*0.7)
                            = 0.126 + 0.406
                            = 0.532
                            = 53.2%
于 2012-08-25T14:24:07.200 回答