algorithm - 使用 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 是independent和 uniformly distributed在集合 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% 的几率。那是一个被操纵的骰子。