使用一个概率集生成另一个概率集

Question

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

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

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

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

Answer 1

您必须找到一种方法来组合两组随机数（第一个和第二个随机数 {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*5，其中 X 和 Y 是两个随机数。这会给你一组像这样的结果

        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

This 确实有一个 {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 倍的时间）长等）。但它会给你正确的概率。

Answer 2

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

我不知道如何解决这个问题，但我会尽力为您减少一点。需要考虑的一些要点：

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

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

Answer 3

我的逻辑是这样的：

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

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

rn07 += num % 2