一道随机数题目的求解

有这样一道算法题：

给定一个能够生成均匀 1~5 随机枚举数的函数，请设计一个能够生成均匀 1~7 随机枚举数的函数。

就是说，有一个生成随机数的函数 rand5，可能返回 1、2、3、4、5 这 5 个枚举值，其中每个值被返回的概率都是严格的 1/5，现在需要设计一个类似的随机数函数 rand7，可能返回 1、2、3、4、5、6、7 这几个枚举值，每个值被返回的概率都是严格的 1/7。

先掩卷思考，脑海中浮现的思路包括：

• 调用 rand5 的结果除以 5，再乘以 7，这样的结果范围为 7/5~7，并非所希望的结果；
• 反复调用 rand5 函数 7 次，结果再除以 5，这样的结果范围为也为 7/5 ~ 7，并非所希望的结果。

如果题目反过来呢，已知 rand7，求 rand5 呢？

那我可以先调用 rand7，看看结果，如果结果为 1~5，直接返回；如果结果为 6、7，继续重试不就得了？

那再回到现实，怎么根据 rand5 求 rand7？

• 如果 rand5 + rand5 的结果，范围是 2~10，用上面类似的办法只能得到 2~7 的值，无法得到 1，不合题意。

([2019-4-5] 有人说，那可以把上面的结果减 1 不就行了？即 rand5 + rand5 – 1，取得的数的范围是 1~9，舍弃掉 8、9，似乎是可以了，但是仔细想想还是错的：以舍弃掉的这个 9 为例，要得到它必须两次 rand5 都得是 5，因此概率就是 1/5*1/5=1/25，这个概率明显是低于单个数值的平均概率的。也就是说，这种方法得到 1~7 中的每个数并非是等可能的)

但是依然得到了一种启发，调用一次 rand5，结果的各种可能性有 5 种，要映射到 rand7 的 7 种结果可能性，是不现实的。但是如果扔两次，在不考虑去重的情况下，结果有 5*5=25 种可能，用某种方式映射并保留那最终的 7 种可能性，却是一个值得去尝试的思路。

想到了 5*5，于是尝试建立二维数组 arr[5][5]，那么数组的每一个元素都可以表示一种结果的可能性，在数组中取前 7 个元素，分别映射到 1~7：

于是调用 rand5 两次，分别得到横坐标 i 和纵坐标 j，如果 arr[i][j]>0，则保留，否则重试。

这样的方法还不完美，因为 25 个数里面只有 7 个是有效的，大部分情况下都只能重试了，效率太低。

于是，在这个二维数组里面不止保留前 7 位，而是尽可能多地保留了所有 7 的完整倍数：

这样一来，大部分情况下，都会命中大于 0 的元素。

那就写出代码：

再写个 main 函数测试一下：

重复测试一千万次，但是从结果看，分布却并不足够随机：

重复测试了几次，都是输出 2 的情况居多。就这个数据量而言，我觉得这不是巧合。

为了让这个可能的差异更加明显，我把从 rand5 求 rand7 改成了从 rand2 求 rand3：

再同样测试一千万次，结果却大跌眼镜：

居然有一倍的差异。

怎么回事呢？我开始怀疑 Java 的这个伪随机函数得出的结果（在计算机的世界里要实现绝对随机是不可能的）不足够随机，于是写了个程序调用一千万次 Java 的伪随机函数来看结果：

从结果来看分布非常均匀：

一下子觉得百思不得其解。

于是我重新审视自己的思路，还是觉得没有什么问题。虽然总结果最初有 25 个，但是前 21 个的结果每个得到的可能性都是一致的，最后四个丢掉并重来，继续的测试依然是能保证结果概率均等的。本质上这种方式在统计学上面叫做 “Reject Sampling”。

我请教了一下数学家 @万精油墨绿，他说思路是没什么问题的，有问题的话，只能是代码的问题。

其实还有一种方法，本质上也是类似的，即根据：

上面这个式子的结果可以得到从 1 到 25 所有的结果，并且显而易见这 25 个结果出现时，这两个 rand5() 都可以被唯一确定返回值，因此他们出现的概率都是彼此相等的。于是可以根据上面的公式，在结果大于 3*7=21 的时候重新计算，否则则返回除以 7 的余数即可：

同样跑了几次测试，每次测试一千万条数据，这次发现这个偏大的数跑到 3 上面去了：

这么一来反而有点开窍的感觉了，我觉得是不是因为 Java 的伪随机数生成的方法，生成的数不足够随机呢？虽然看起来是随机的，但是那也只是看起来而已。当用 “小随机” 去生成 “大随机” 的时候，那些不随机的缺陷被放大了。而比较 rand2 生成 rand3，和 rand5 生成 rand7，明显是前者 “放大” 的倍数更大，因此最后得出的结果中，“随机性” 显得差。

为了进一步检验这种猜想，我开始考虑能否让随机数的种子变化更大。因为目前使用的随机数种子是 System.nanoTime()，这个方法看似纳秒，其实也只是：

Returns the current value of the most precise available system timer, in nanoseconds.

我想在我的实验中它远比毫秒精确，但是也只是保证了尽可能精确而已。

那好，要验证或者说部分验证这样的猜想，现在假设这样的猜想是正确的，那么可以得出这样的推论：

1. 如果随机数种子换成 System.currentTimeMillis()，也就是说，换成毫秒，那么最后的结果应该是更不随机；
2. 如果我在每次取随机数之前休息几毫秒，使得每两次之间的时间种子差异增大，应该能够看到最终的结果随机性增加。

（注，我测试的版本下 JDK 对于设置的种子的处理方式是：seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) -1)。）

好吧，现在来验证第一条，为了尽可能使得结果明显，使用 rand2 生成 rand3 的那个方案。把使用纳秒作为随机数种子改成使用毫秒作为随机数种子，结果居然是：

换言之，二维数组中横坐标和纵坐标居然在一千万次测试当中，得到的都是一样的结果，即绝大多数情况下求 i 和 j 的操作都在同一个毫秒量级内完成。

现在来验证第二条，在每次取随机数前，休眠 3 毫秒，当然，这个 3 毫秒肯定也是不精确的 3 毫秒。为了在增加休眠时间的情况下，能够在我的耐心时间范围内得到最终结果，我没法测试一千万次了，我的测试用例改成了测试一万次，结果为：

果然，分布的均匀性要好了很多。

问题还没完，为了尽可能消除这种种子相似所带来的伪随机性，其实可以只初始化一遍种子，然后在迭代方法内部不断调用 Random 的 nextInt 方法就好了，这也是在这种情形下更加合理的使用随机数生成器的方式：

这一次，不但分布均匀了，而且执行速度还快了很多：

还蛮好玩的。

文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接 《四火的唠叨》

9 thoughts on “一道随机数题目的求解”

1. hax says:
   07/20/2016 at 10:18 PM

   其实你可以视无限多次 rand5() 得到的结果构造一个 5 进制数，把这个 5 进制数转换为 7 进制数，即得到连续的 rand7() 的结果了。

   所以不需要 reject sampling。把除法得到余数留着下次继续算就可以了。

   随手写了个 js 的实现：
   
let x = 1, v = 0
function rand7() {
while (x < 7) {
x *= 5
v *= 5
v += rand5() - 1
}
const result = v % 7
v -= result
v /= 7
x /= 7
return result + 1
}


   Reply
2. ooxx says:
   03/15/2016 at 9:55 AM

   结论虽对，过程错误太多
   比如
   如果 rand5 * 2 的，范围是 2~10，只能得到 2~7 的值。
   如果能得到 2～10，减一不就是 1～9，然后不就可以 2～7，可惜的是得到的不是 2～10 而是 {2，4，6，8，10}
   再比如/5×7，1-5 虽然是 7/5～7，但是减 1 之后/4×6 再+1，不就是 1～7 了，不行的根本原因是因为计算机做除法不靠谱
   楼主根本没明白这题

   Reply
3. 网站源码 says:
   04/15/2015 at 4:13 PM

   支持一下博主

   Reply
4. 王大德 says:
   03/16/2015 at 3:01 PM

   http://www.matrix67.com/blog/archives/6151
   这篇文章阐述了, 您的方法不能保证在有限步中完成

   Reply
   1. Anonymous says:
      03/17/2015 at 1:42 AM

      没错，有这种可能，因为 Sampling reject 的关系，但是我还可以在这种情况出现时，选择上一次的执行结果，这样就不会出现这种可能在有限步中完不成的情况了。这也是不影响概率分配的。

      Reply
5. Nicholas Ren says:
   03/14/2015 at 10:20 AM

   渐进的思路比较有意思，所以问题确实 shi 由于 java 的伪随机引起，通过 sleep 修改 seed，可以消除这种伪随机被放大的因素？

   Reply
   1. Anonymous says:
      03/14/2015 at 11:24 PM

      严格说无法消除或者减弱伪随机性，但是可以减少两次随机数间因为 seed 相同或者相近导致的“ 结果不随机”

      Reply
6. nnkken says:
   03/13/2015 at 4:19 PM

   random 不應每次調用時 setSeed，而應只在構造函數裡初始化一下，不然如果時間精度不足，連續調用時就會一直使用同一個種子，導致結果不夠隨機。
   至於那個跑 10000000 次的程序，我用 Ideone 跑了一下，結果還是很不均勻：
   https://ideone.com/ckd6BN
   1: 1427164
   2: 1435913
   3: 1395810
   4: 1447688
   5: 1415879
   6: 1472439
   7: 1405107
   而把 random.setSeed(System.nanoTime()); 放在 for 外面則沒問題（而且還快很多）：
   https://ideone.com/luYWz4
   1: 1429394
   2: 1429356
   3: 1429751
   4: 1429016
   5: 1426168
   6: 1427692
   7: 1428623
   至於為甚麼你會得到均勻的結果，我猜是因為 Map 太慢，讓 setSeed 的間隔足夠長。
   你可以改用 int[] 試試：
   https://ideone.com/fZXxnx

           int[] map = new int[7];
           for (int i = 0; i < 7; i++) {
           map[i] = 0;
           }
           for (int i = 0; i < 10000000; i++) {
       random.setSeed(System.nanoTime());
               map[random.nextInt(7)]++;
           }
           for (int i = 0; i < 7; i++) {
               System.out.println(i + ": " + map[i]);
           }

   Reply
   1. 四火 says:
      03/15/2015 at 9:37 AM

      首先，感谢有价值的回复。

      1. “不應每次調用時 setSeed，而應只在構造函數裡初始化一下”，这个确实如此，而且这确实也是更加合理的方法，我把这个办法更新到我的文中去。

      2. “我猜是因為 Map 太慢，讓 setSeed 的間隔足夠長”，那好，我把根据 rand2 求 rand3 的那个程序也使用 Map 的机制来实现一遍：

      
public class R {
private static Random random = new Random();
private static int[][] arr = new int[][]{
{1,2},
{3,0}
};

      public static int rand2(){
random.setSeed(System.nanoTime());
return random.nextInt(2) + 1;
}

      public static int rand3() {
int i = rand2() - 1;
int j = rand2() - 1;

      if (i == 1 && j == 1)
return rand3();

      return arr[i][j];
}

      public static void main(String[] args) {
Map counter = new HashMap();

      for (int i = 0; i < 10000000; i++) { int key = rand3(); Integer val = counter.get(key); if (null == val) val = 0; val++; counter.put(key, val); } for (Map.Entry entry : counter.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
}
}
,>

      1: 4741216

      2: 2602806

      3: 2655978

      因此，可见和是否使用 Map 无关。
      Reply