分析运行时

Question

我遇到了一个问题，要实现一个输出 0 或 1 的无偏随机函数，该函数使用有偏输出函数输出 0 或 1，输出 1 的概率为 P。并预测运行时间如何根据 P

我是这样实现的

Random() {
     i = BRand();
     j = BRand();

    if(i!=j)
          Return i;
    else
           Random();
    }

但我无法弄清楚运行时间在 P 方面会如何变化。

Answer 1

假设 BRand 有 70% 的机会 (P = 0.7) 产生一 (1)，因此有 30% 的机会 (1 - P) 产生零 (0 )-

i = 1 1 1 1 1 1 1 0 0 0
j = 1 1 1 1 1 1 1 0 0 0

当 i != j 时，我们只有 return 结果，因此排除了 (i, j) 都产生零、(0, 0) 或两者都产生一的任何组合， (1, 1)。因此运行Random()一次的效果是-

30% * 30% = 9% (0, 0) 的概率，recur
70% * 70% = 49% (1, 1) 的概率，recur
30% * 70% = 21% (0, 1), return 0
70% * 30% = 21% (1, 0), return 1

其中P = .7，58% (49% + 9%) 的时间我们会重复出现。在其他 42% 中，return 为零或一的概率相等。以较低的递归成本，确实这种聪明的算法将从有偏生成器中生成无偏随机数生成器。

将概率更改为 P = 0.1 我们会看到不同的结果：

i = 1 0 0 0 0 0 0 0 0 0
j = 1 0 0 0 0 0 0 0 0 0

运行Random()的效果是

90% * 90% = 81% (0, 0) 的概率，recur
10% * 10% = 1% (1, 1) 的概率，recur
90% * 10% = 9% (0, 1), return 0
10% * 90% = 9% (1, 0), return 1

其中P = 0.1，82%的时候我们会重复出现。在另外 18% 中， return 0 或 1 的概率相等。

练习 1：说明为什么 P = 0.9 与 P = 0.1 有相同的结果。你在这里看到什么关系？

练习 2：当 P = 0.001 时，我们重现的概率是多少？ P = 0.999 呢？

练习 3：P = 0.5 有什么特别之处？

完成练习后，揭开下面的文字-

当 P = 0.5 时，我们看到 Random() 的最低运行时间，只有 50% 的机会重复出现。这是有道理的，因为 P = 0.5 已经没有偏见了！也就是说，运行 BRand 的效果已经有相同的机会产生零或一。由于 P 偏离 0.5，我们注意到 Random() 出现的可能性更高，因此 Random() 需要更长的运行时间才能生成无偏生成器。

练习 4：根据 P

编写一个计算递归概率的公式

F(p) = p² + (1 - p)² -其中 0 <= p <= 1

分析运行时

Analysing runtime

recursion

runtime

probability