2

在最近的采访中，我被问到以下问题。有一个函数random2()，它以相等的概率（0.5）返回 0 或 1。编写实现random4()和random3()使用random2(). random4()像这样很容易实现

if(random2())
  return random2();
return random2() + 2;

但我遇到了困难random3()。我能代表的唯一认识：

uint32_t sum = 0;
for (uint32_t i = 0; i != N; ++i)
  sum += random2();
return sum % 3;

这种实现random4()仅基于我的直觉。我不确定它实际上是否正确，因为我无法从数学上证明它的正确性。有人可以帮我解决这个问题吗？

4

2 回答 2

4

随机3：

不确定这是否是最有效的方法，但这是我的看法：

x = 随机2 + 2*随机2

会发生什么：

0 + 0 = 0
0 + 2 = 2
1 + 0 = 1
1 + 2 = 3

以上是可能发生的所有可能性，因此每个可能性都相等，所以...

(p(x=c)是 x = c 的概率)

p(x=0) = 0.25
p(x=1) = 0.25
p(x=2) = 0.25
p(x=3) = 0.25

现在当 x = 3 时，我们只是继续生成另一个数字，因此给 0、1、2 等概率。从技术上讲，您可以将 x=3 的概率重复分配给所有这些，使得 p(x=3) 趋于 0，因此其他的概率将趋于 0.33。

代码：

do
  val = random2() + 2*random2();
while (val != 3);
return val;

随机4：

让我们运行您的代码：

if(random2())
  return random2();
return random2() + 2;

第一次调用有 50% 的机会 1 (true) => 以 50% * 50% 的概率返回 0 或 1，因此每个 25%

第一次调用有 50% 的机会为 0（假）=> 以 50% * 50% 的概率返回 2 或 3，因此每个 25%

因此，您的代码以相等的概率生成 0,1,2,3。

受 e4e5f4 的回答启发的更新：

对于比我上面提供的答案更确定的答案...

通过多次调用生成一些大数字，random2然后将结果修改为所需的数字。

对于每个人来说，这并不是完全正确的概率，但它会很接近。

因此，对于一个 32 位整数，调用random232 次，target = 3：

Total numbers: 4294967296
Number of x's such that x%3 = 1 or 2: 1431655765
Number of x's such that x%3 = 0: 1431655766
Probability of 1 or 2 (each): 0.33333333325572311878204345703125
Probability of 0: 0.3333333334885537624359130859375

因此，在正确概率的 0.00000002% 以内，似乎非常接近。

代码：

sum = 0;
for (int i = 0; i < 32; i++)
  sum = 2*sum + random2();
return sum % N;

笔记：

正如 pjr 所指出的，这通常远低于上述拒绝方法的效率。使用拒绝方法获得相同数量的调用random2（即 32）（假设这是最慢的操作）的概率是0.25^(32/2) = 0.0000000002 = 0.00000002%。再加上这种方法不精确的事实，让我们更倾向于拒绝方法。降低这个数字会减少运行时间，但会增加错误，并且可能需要降低很多（从而达到高错误）才能接近拒绝方法的平均运行时间。

值得注意的是，上述算法有一个最大运行时间。拒绝方法没有。如果您的随机数生成器由于某种原因完全损坏，它可能会继续生成被拒绝的数字并使用拒绝方法运行一段时间或永​​远，但上面的 for 循环将运行 32 次，无论发生什么。

于 2013-04-24T08:30:33.660 回答
3

%不推荐使用 modulo( )，因为它会引入偏差。只有当是 的力量时，映射才会很好。否则，正如其他答案所建议的那样，会涉及某种拒绝。n2

另一种通用方法是通过以下方式模拟内置 PRNG -

  • 生成 32random2()并将其映射为 32 位整数
  • (0,1)通过将其除以最大整数值来获取范围内的随机数
  • 只需将此数字乘以n（=3,4...73 依此类推）floor即可获得所需的输出
于 2013-04-24T08:52:46.607 回答