5

我得到一个函数 rand5()，它以均匀分布在闭区间 [1,5] 中生成一个随机整数。如何使用 rand5() 来创建函数 rand7()，它在 [1,7] 中生成整数（同样，均匀分布）？

  1. 我搜索了stackoverflow，发现了很多类似的问题，但并不完全像这个问题。
  2. 我最初的尝试是 rand5() + 0.5*rand5() + 0.5*rand5()。但这不会以均匀的概率生成从 1 到 7 的整数。非常欢迎任何答案或答案链接。
4

4 回答 4

7

请注意，有限数量的调用无法实现完美的均匀分布draw5()，因为对于每个k: 5^k % 7 != 0- 所以你总是会有一些“备用”元素。

这是一个使用次数不限的解决方案draw5()：

画两个数，x1,x2。对此有 5*5=25 种可能的结果。

请注意，25/7 ~= 3.57。选择 3*7=21 组合，这样每个组合将映射到 [1,7] 中的一个数字，对于所有其他 4 个数字 - 重绘。

例如：

(1,1),(1,2),(2,1) : 1
(3,1),(1,3),(3,2): 2
(3,3),(1,4),(4,1): 3
(2,4),(4,2)(3,4): 4
(4,3), (4,4), (1,5): 5
(5,1), (2,5), (5,2) : 6
(5,3), (3,5), (4,5) : 7
(5,4),(5,5),(2,3), (2,2) : redraw
于 2012-07-03T05:19:55.477 回答
4

这是一个简单的方法：

  1. 使用 rand5() 从集合 { 1, 2, 4, 5 } 中生成三个随机整数的序列（即，丢弃任何生成的 3）。
  2. 如果所有三个数字都在集合 { 1, 2 } 中，则丢弃序列并返回步骤 1。
  3. 对于序列中的每个数字，将 { 1, 2} 映射到 0 并将 { 4, 5 } 映射到 1。将它们用作 3 位数字的三位值。因为位不能全部为 0，所以数字将在 [1, 7] 范围内。因为每个位是 0 或 1 的概率相等，所以 [1, 7] 上的分布应该是均匀的。
于 2012-07-03T05:20:40.913 回答
2

好的，我不得不考虑一段时间，但实际上并没有那么难。想象一下，你有 rand2 而不是 rand5，它输出 0 或 1。你可以通过简单地使 rand2 成为 rand5

rand2() {
    if(rand5() > 2.5) return 1
    else return 0
}

现在使用 rand2 多次做一棵树来获得 rand7。例如，如果你开始 rand7 可以在 [1,2,3,4,5,6,7] 抛出 rand2 后给出 0 你现在子集到 [1,2,3,4] 并且在另一次抛出或rand2 是 [3,4] 的子集 1，最后一次抛出 1 使 rand7 的输出为 4。一般来说，这个树技巧可以用来获取 rand2 并映射到 randx，其中 x 是任何整数。

于 2012-07-03T05:22:16.420 回答
2

这里有一个元技巧可以解决很多这样的问题：当我们以某种方式不同地对待这些术语时，就会引入偏差，所以如果我们在每一步都对它们都一样对待并且只在集合上执行操作，我们'会远离麻烦的。

我们必须至少调用一次 rand5() （显然！），但是如果我们分支到那个地方，除非我们很聪明，否则就会发生坏事。因此，让我们为 7 种可能性中的每一种调用一次：

In [126]: import random

In [127]: def r5():
   .....:     return random.randint(1, 5)
   .....: 

In [128]: [r5() for i in range(7)]
Out[128]: [3, 1, 3, 4, 1, 1, 2]

显然，这些术语中的每一个都同样可能是这些数字中的任何一个......但其中只有一个恰好是 2，所以如果我们的规则是“选择 rand5() 返回 2 的任何术语”，那么它就会起作用。或者 4，或者其他什么，如果我们简单地循环足够长的时间，就会发生这种情况。因此，有很多方法可以提出可行的方法。这里（在伪代码中——这是可怕的 Python）是一种方法：

import random, collections

def r5():
    return random.randint(1, 5)

def r7():
    left = range(1, 8)
    while True:
        if len(left) == 1: 
            return left[0]
        rs = [r5() for n in left]
        m = max(rs)
        how_many_at_max = rs.count(m)
        if how_many_at_max == len(rs):
            # all the same: try again
            continue
        elif how_many_at_max == 1:
            # hooray!
            return left[rs.index(m)]
        # keep only the non-maximals
        left = [l for l,r in zip(left, rs) if r != m]

这使

In [189]: collections.Counter(r7() for _ in xrange(10**6))
Out[189]: Counter({7: 143570, 5: 143206, 4: 142827, 2: 142673, 6: 142604, 1: 142573, 3: 142547})
于 2012-07-03T05:39:55.287 回答