随机生成所有数需要的尝试次数

今天碰到一件很出乎意料的事情。随机生成0-65535里的每一个数，总共需要多少次才能生成出来？即总共生成了X把，X个随机数中，涵盖了所有0-65535的数。

发现需要10+倍的次数。大约需要～724539次。如果是生成0-1023里的每个数，需要大约～6858次

1. Random rand = new Random();
   
2.     int TOTAL = 65536;
   
3.     boolean[] visited = new boolean[TOTAL];
   
4.     int missing = TOTAL;
   
5.     int attempts = 0;
   
6.     while (missing != 0) {
   
7.       attempts++;
   
8.       int index = rand.nextInt(TOTAL); // 伪随机数，不晓得和实验结果是不是有关系。
   
9.       if (visited[index])
   
10.         continue;
    
11.       visited[index] = true;
    
12.       missing--;
    
13.     }
    
14.     System.out.println(attempts);

复制代码

我不懂所以发到这里。统计上讲，在每次生成中，某个数不出现的几率是65535/65536，经过多少把出现的几率才能是10%之内呢？瞎想了。如果不上路忽略。

https://zh.wikipedia.org/wiki/贈券收集問題  的确是NlogN

brave2 发表于 2019-4-16 02:57
有点意思。。
用概率的思路 去计算一个确定的事情(每个数字至少出现一次) 具有很大的误差吧

嗯。概率不可能完全确定多少次一定完成。有可能总完不成就差一个数。但是这个问题是不是可以用期望来约束住呢？

反正今天彻底被惊住了。本来觉得也就4倍N就可以。但是发现好像是LogN * N的关系。

14417335 发表于 2019-4-16 03:11
嗯。概率不可能完全确定多少次一定完成。有可能总完不成就差一个数。但是这个问题是不是可以用期望来约束 ...

如果你要测试的数集大小和伪随机数列长度一致的话，那么倍数关系就只有1了。

所以肯定不是LogN*N的关系。

微信用户_0x045 发表于 2019-4-16 05:46
如果你要测试的数集大小和伪随机数列长度一致的话，那么倍数关系就只有1了。

所以肯定不是LogN*N的关 ...

有道理。矛盾没解决。如果真随机的话，更不可能保证N个肯定可以1*N能全覆盖。

即便伪随机数好像也没有特别小的数，使得average能够趋紧N。我运行了100次上面的程序。使用同一个Random instance：

Min=596668 Max=999962

如果真的是1*N，那么总应该有很lucky的情况吧。可是似乎没有。

补充内容 (2019-4-16 07:15):
运行了10000次，93秒还可以承受。
Min=566342 Max=1335667

Aba 发表于 2019-4-16 09:03
https://zh.wikipedia.org/wiki/贈券收集問題  的确是NlogN

多谢你提供的关键信息：Coupon Collector Problem

数学太差看不懂。以后有时间会followup。

我把楼顶那个思路又想了想，做了个表格，也许对其它同学有启发作用：



99.99%概率见过所有数，那么需要1358109次尝试，和上面所提到的“Max=1335667“呼应了一下。

14417335 发表于 2019-4-16 06:54
有道理。矛盾没解决。如果真随机的话，更不可能保证N个肯定可以1*N能全覆盖。

即便伪随机数好像也没有 ...

计算机语言里的随机数发生器都是伪随机的，说白了就是一个固定序列，这个序列有良好的随机分布性。随机种子决定了从这个序列里的哪个位置开始取数。如果每次随机实验的种子都一样的话那么实验的结果也都是一样的。

你得看你用的那个伪随机数发生器原始数据的位数。一般应该是32或者64位。

假设RNG的原始数据的位数是M的话，你要是想看到1*N的情况的话你开的数组必须是2^M这么大才行。

微信用户_0x045 发表于 2019-4-17 01:29
计算机语言里的随机数发生器都是伪随机的，说白了就是一个固定序列，这个序列有良好的随机分布性。随机种 ...

是的。如果真的是不用MOD，那么的确是N。用了MOD后就和真随机数更像了。即给定一系列shuffle过后的0-N的数，最后16位存在有重复（鸽笼吗，也因此会导致有些数不出现）。

昨晚又继续想了想。

假定基数是2048。 ( 1 - ( 2047 / 2048 ) ^ K 是在K把中见过某个数的概率

( ( 1 - ( 2047 / 2048 ) ^ K ) ^ 2048 是在K把中见过所有8192个数的概率P

如果指定概率P为50%，这样就可以求出K。



到这里我就简化不下去了。以后有能力了再看看coupon collection的数学推导吧。