使用rand5()计算rand7()

Question

我有一个问题的解决方案,只使用rand5()生成rand7().其中一个解决方案状态: 5 * rand5() + rand5()将以相等的概率生成数字0 - 24,因此我们只需要循环直到我们得到一个数字<21(3*7)而不是%7来得到0到6之间的正确答案.

我的问题是为什么我们不能只3 * rand5() + rand5()生成数字<14(2*7)呢？

Answer 1

如果X并且Y是独立且均匀地分布在集合上S_5 = {0,1,2,3,4},那么

1. 5*X + Y在集合上均匀分布{0,...,24},但是
2. 3*X + Y不是均匀分布的{0,...,16},也不是它的限制{0,...,13}

很容易看出(1)确实如此,因为f(x,y) = 5*x + y是S_5 x S_5和之间的双射S_25.

如果我们看看3*X + Y我们得到的分布:

>>> Counter(3*x + y for x in range(5) for y in range(5))
Counter({3: 2, 4: 2, 6: 2, 7: 2, 9: 2, 10: 2, 12: 2, 13: 2, 0: 1, 1: 1, 2: 1, 5: 1, 8: 1, 11: 1, 14: 1, 15: 1, 16: 1}

结果3,4,6,7,9,10,12,13的可能性是1,2,5,8或11的两倍.更多证据:

>>> def rand7():
...   x = 3*rand5() + rand5()
...   if x < 14: return x % 7
...   return rand7()
... 
>>> Counter(rand7() for _ in xrange(100000))
Counter({6: 18219, 3: 18105, 4: 13734, 5: 13715, 2: 13634, 0: 13560, 1: 9033}

6和3的发生几率为4/22~18.2%,4,5,2和0的几率为3/22~13.6%,1只有2/22~9.1%的几率.这是一个操纵骰子.

Answer 2

3 * rand5() + rand5()

不是均匀分布的。例如，它只以一种方式生成 0，但以两种方式生成 3，因此 3 比 0 更可能出现。

就像2 * rand5() * rand5(), 4 * rand5() + rand5(), 等等。

但是5 * rand5() + rand5()是均匀分布的。

这就像生成一个基数为 5 的数字的两个随机数字。

00 => 0
01 => 1
02 => 2
03 => 3
04 => 4
10 => 5
11 => 6
12 => 7
...

只有一种方法可以生成从 0 到 24 的每个数字。