如何确定随机数生成器使用均匀分布的可能性?

机器算法验证 分布 随机变量 均匀分布 随机生成 生日悖论
2022-03-31 06:30:24

假设我有一个黑盒函数generate_number(),可以生成 1-N 之间的随机数;并且假设N是已知的。每个函数调用相互独立,不携带任何状态。

我用它来生成X数字;假设这些数字没有存储在任何地方,所以我无法建立它们的确切列表。

我还有另一个黑盒函数num_seen_numbers(),它告诉我生成Y了多少个唯一数字N

例如。假设N = 100(给定),我调用了generate_number()40 次(X = 40)。然后我打电话num_unseen_numbers(),它说在所有N = 100可能的数字中,它只生成了 15 个唯一的数字 ( Y = 15)。

有没有办法确定其生成generate_number()具有潜在均匀概率分布的可能性?

2个回答

这是另一种形式的生日问题。

d同样可能的天数和n独立抽签,预期抽签的不同天数为d(1(11d)n)在你的情况下d=100n=40是关于33.1, 而不是15.

的概率x绘制的不同日期是d!S2(n,x)(dx)!dn在哪里S2(n,x)是第二类斯特林数。

在你的情况下d=100n=40x=15这个概率大约是9.47×1017并且对于x15是关于9.61×1017,两者都非常小。相比之下,概率为29x38是关于0.9765.

您可以将其用作可能的测试,以确保抽签是统一且独立的。

N=365x=23,随机生成的数字,您的审查程序类似于著名的生日问题,其中人们会期望匹配的数字在x略多于一半的时间。但是,生日匹配的可能性23对于现实生活中某些月份比其他月份更有可能产生实际人类生日的现实情况来说是相当稳健的。

因此,在大约一半的时间内未能获得一个或多个匹配会让人怀疑“生成器”的随机性,但在接近一半的时间内获得匹配并不能有力地证明这些数字是真正随机生成的。

经典的生日问题,同样可能的 365 个同样可能的生日。通过R中的模拟, P(Y=0)=0.494±0.003[确切的概率0比赛是0.4927到四个地方]和E(Y)=0.678±0.005.

set.seed(1234)
x = 23;  N = 365
y = replicate(10^5, x-length(unique(sample(1:N,x,rep=T))))
mean(y==0);  mean(y)
[1] 0.49395   # aprx P(No Match)
[1] 0.67842   # aprx E(Nr Matches)
2*sd(y==0)/sqrt(10^5)
[1] 0.003162062
2*sd(y)/sqrt(10^5)
[1] 0.005012195

天数不太可能(在一年中的两个半月中大约有 95% 和 110% 的可能性):P(Y=0)=0.491±0.002,E(Y)=0.683±0.003.

在模拟误差范围内,结果与同样可能天数的结果没有显着差异。

set.seed(1235)
x = 23;  N = 365;  pr = c(rep(95, 180), rep(105, 185))
y = replicate(10^5, x-length(unique(sample(1:N,x,rep=T,p=pr))))
mean(y==0);  mean(y)
[1] 0.49102
[1] 0.68265
sd(y==0)/sqrt(10^5)
[1] 0.001580892
sd(y)/sqrt(10^5)
[1] 0.002509512

生日问题已经通过更广泛的模拟显示出来,如果生日的可能性不完全一样,则不会特别挑剔。

有一些问题对随机数生成器中的缺陷非常敏感。您可以在“死硬电池”中搜索特别挑剔的模拟问题,这些问题已用于审查伪随机数生成器。