如何仅用Random(0,1)实现Random(a,b)？

Question

可能的重复：
如何穿制服通过已知的均匀随机函数 RANDOM(0,1) 在 a, b 之间随机生成

在算法导论一书中，有一个注释：

描述该过程的实现Random(a, b) 仅调用 Random(0,1)。作为 a 和 b 的函数，程序的预期运行时间是多少？ Random(a,b) 结果的概率应该是纯均匀分布的，如 Random(0,1)

对于 Random 函数，结果是 a 和 b 之间的整数（含）。例如，Random(0,1) 生成 0 或 1； Random(a, b) 生成 a, a+1, a+2, ..., b

我的解决方案是这样的：

for i = 1 to b-a
    r = a + Random(0,1)
return r

运行时间是 T=ba

这是正确的吗？我的解决方案的结果是均匀分布的吗？

谢谢

如果我的新解决方案是这样的怎么办：

r = a
for i = 1 to b - a //including b-a
    r += Random(0,1)
return r

如果不正确，为什么 r += Random(0,1) 使 r 不均匀分布？

Answer 1

其他人已经解释了为什么您的解决方案不起作用。正确的解决方案如下：

1) 找到最小的数 p，使得 2^p > ba。

2) 执行以下算法：

r=0
for i = 1 to p
    r = 2*r + Random(0,1)

3) 如果 r 大于 ba，则转至步骤 2。

4) 您的结果是 r+a

那么让我们尝试随机(1,3)。
所以 ba 是 2。
2^1 = 2，因此 p 必须为 2，以便 2^p 大于 2。

所以我们将循环两次。让我们尝试所有可能的输出：

00 -> r=0, 0 is not > 2, so we output 0+1 or 1.
01 -> r=1, 1 is not > 2, so we output 1+1 or 2.
10 -> r=2, 2 is not > 2, so we output 2+1 or 3.
11 -> r=3, 3 is > 2, so we repeat.

所以 1/4 的时间，我们输出 1。我们输出 2 的时间的 1/4。我们输出 3 的时间的 1/4。我们必须重复的时间的 1/4第二次算法。看起来不错。

请注意，如果您必须经常这样做，则有两种优化方法很方便：

1）如果您经常使用相同的范围，请使用一个计算 p 一次的类，这样您就不必计算它每次。

2) 许多 CPU 有快速的方法来执行高级语言中未公开的步骤 1。例如，x86 CPU 具有 BSR 指令。

Answer 2

不，这是不正确的，该方法将集中在 (a+b)/2 周围。这是二项分布。

您确定 Random(0,1) 生成整数吗？如果它产生 0 到 1 之间的浮点值，则更有意义。那么解决方案将是仿射变换，运行时间独立于 a 和 b。

我刚刚想到的一个想法，如果它与整数值有关：使用二分法。每一步都有一个低-高范围。如果 Random(0,1) 返回 0，则下一个范围是 low-(low+high)/2，否则 (low+high)/2-高。
细节和复杂性留给你，因为这是家庭作业。

这应该会创建（大约）均匀分布。

编辑：大约是那里的重要词。如果 b-a+1 是 2 的幂，则为统一，如果接近则相差不太远，但总体来说还不够好。啊，好吧，这是一个自发的想法，无法让他们一切顺利。

Answer 3

不，您的解决方案不正确。这个总和将服从二项式分布。

但是，您可以生成 0、1 的纯随机序列并将其视为二进制数。

repeat
  result = a
  steps = ceiling(log(b - a))

  for i = 0 to steps
    result += (2 ^ i) * Random(0, 1)
until result <= b

KennyTM：我的错。

Answer 4

我阅读了其他答案。为了好玩，这里有另一种查找随机数的方法：

分配一个包含 ba 元素的数组。
将所有值设置为 1。
迭代数组。对于每个非零元素，就像掷硬币一样。如果出现0，则将该元素设置为0。

每当完成一次迭代后，只剩下 1 个元素时，您就会得到随机数：a+i，其中 i 是非零元素的索引（假设我们开始在 0 上建立索引）。那么所有数字都有相同的可能性。 （您必须处理平局的情况，但我将其作为练习留给您。）

这将有 O(infinity) ... :)
但平均而言，一半的数字将被消除，因此它的平均案例运行时间为 log_2 (ba)。

Answer 5

首先，我假设您实际上是在累加结果，而不是在每个步骤中向 a 添加 0 或 1。
使用一些概率，您可以证明您的解决方案不是均匀分布的。结果值 r 为 (a+b)/2 的可能性最大。例如，如果 a 为 0，b 为 7，则获得值 4 的机会是（7 的组合 4）除以 2 的 7 次方。原因是，无论 7 个值中的哪 4 个，是 1，结果仍然是 4。

您估计的运行时间是正确的。

Answer 6

您的解决方案的伪代码应如下所示：

r=a
for i = 0 to b-a
    r+=Random(0,1)
return r

至于均匀分布，假设该随机数生成器所基于的随机实现完全均匀，则获得 0 或 1 的几率为 50%。因此，得到你想要的号码是一次又一次选择的结果。

所以对于a=1，b=5，有5种选择。

获得 1 的几率涉及 5 个决策，全为 0，其几率为 0.5^5 = 3.125%

获得 5 的几率涉及 5 个决策，全部为 1，其几率为 0.5^5 = 3.125%

如您所见由此看来，分布并不均匀——任何数字的几率都应为 20%。

Answer 7

在您创建的算法中，它实际上并不是均匀分布的。

结果“r”将始终是“a”或“a+1”。它永远不会超出这个范围。

它应该看起来像这样：

r=0;
for i=0 to b-a
   r = a + r + Random(0,1)

return r;

通过在计算中包含“r”，您就包含了所有先前“for”循环运行的“随机性”。