1

如何从较小的概率集中生成较大的概率集？
这是来自算法设计手册 -Steven Skiena
Q：

使用随机数生成器 (rng04) 从 {0,1,2,3,4} 以相等的概率生成数字来编写随机数生成器以相等的概率生成从 0 到 7 (rng07) 的数字？

我现在尝试了大约 3 个小时，主要是基于对两个rng04输出求和。问题在于，在这种情况下，每个值的概率是不同的 - 4 的概率为 5/24，而 0 的概率为 1/24。我尝试了一些方法来掩盖它，但不能。

有人可以解决这个问题吗？

4

3 回答 3

4

您必须找到一种方法来组合两组随机数（第一个和第二个 random {0,1,2,3,4}）并产生n*n不同的可能性。基本上问题是，加上你会得到这样的东西

        X
      0 1 2 3 4

  0   0 1 2 3 4
Y 1   1 2 3 4 5
  2   2 3 4 5 6
  3   3 4 5 6 7
  4   4 5 6 7 8

哪个有重复项，这不是您想要的。组合这两个集合的一种可能方法是Z = X + Y*5whereX和Yare 两个随机数。这会给你一组这样的结果

        X
       0  1  2  3  4

  0    0  1  2  3  4
Y 1    5  6  7  8  9
  2   10 11 12 13 14
  3   15 16 17 18 19
  4   20 21 22 23 24

所以现在你有一组更大的随机数，你需要做相反的事情并使其更小。该集合具有25不同的值（因为您从 5 开始，并使用了两个随机数，所以5*5=25）。您想要的集合有 8 个不同的值。一种天真的方法是

x = rnd(5)  // {0,1,2,3,4}
y = rnd(5)  // {0,1,2,3,4}
z = x+y*5   // {0-24}
random07 = x mod 8

这确实有一个范围{0,7}。但是值{1,7}会出现 3/25 次，而值0会出现 4/25 次。这是因为0 mod 8 = 0,8 mod 8 = 0和16 mod 8 = 0。24 mod 8 = 0

要解决此问题，您可以将上面的代码修改为此。

do {
  x = rnd(5)  // {0,1,2,3,4}
  y = rnd(5)  // {0,1,2,3,4}
  z = x+y*5   // {0-24}
while (z != 24)

random07 = z mod 8

这将采用一个值 ( 24) 抛弃您的概率并将其丢弃。如果你得到一个像这样的“坏”值，生成一个新的随机数将使你的算法运行时间稍长（在这种情况下，1/25 的时间需要 2 倍的运行时间，1/625 的运行时间需要 3 倍长等）。但它会给你正确的概率。

于 2009-08-12T19:12:14.017 回答
3

当然，真正的问题是总和中间的数字（在这种情况下为 4）以多种组合出现（0+4、1+3 等），而 0 和 8 只有一种方式被生产。

我不知道如何解决这个问题，但我会尝试为你减少一点。需要考虑的几点：

  • 0-7 范围有 8 个可能的值，因此最终您应该针对的可能情况的总数必须是 8 的倍数。这样，​​您可以在该 codomain 中的每个值有整数个分布。
  • 当您取两个密度函数的总和时，可能情况的数量（在评估总和时不一定不同，只是根据输入的不同排列）等于每个输入集大小的乘积。
  • 因此，给定两个 {0,1,2,3,4} 集合加在一起，您有 5*5=25 种可能性。
  • 不可能从 5 的幂中得到 8 的倍数（参见第一点）（参见第二点，但可以将其外推到任何数量 > 1 的集合），因此您需要在您的如果它们发生，则忽略其中一些。
  • 就我目前所见，最简单的方法是使用两个 {0,1,2,3,4} 集的总和（25 种可能性）并忽略 1（留下 24，一个倍数8).
  • 因此，现在的挑战已简化为：找到一种方法，在 8 个输出值中分配剩余的 24 种可能性。为此，您可能不想使用总和，而只想使用输入值。

一种方法是，想象一个从您的输入构建的以 5 为底的数字。忽略 44（这是你的第 25 个，多余的值；如果你得到它，合成一组新的输入）并取其他的，模 8，你将在 24 个不同的输入组合（每个 3 个）中得到你的 0-7，这是均等分布。

于 2009-08-12T19:09:41.120 回答
2

我的逻辑是这样的：

rn07 = 0;
do {
  num = rng04;
}
while(num == 4);

rn07 = num * 2;
do {
  num = rng04;
}
while(num == 4);

rn07 += num % 2
于 2009-08-12T19:05:51.393 回答