我在一次面试中被问到这个问题。
我不知道该如何处理这个问题，你有什么建议吗?给定一个随机数生成器生成一个介于[0,N)之间的数，如何为了证明这个数是均匀分布的
要证明，您需要知道正在使用的算法，并在图项中显示所有状态的集合构成一个循环，没有子循环，并且状态空间模N的基数为零，因此没有一组状态比其他状态出现的频率更高/更低。例如，这就是为什么我们知道梅森绕口令是均匀分布的，即使64位版本的周期长度为219937-1，并且在宇宙的生命周期内永远无法枚举。
否则使用统计检验来检验一致性假设。统计不能证明一个结果，它不能反驳一个假设。你的样本量越大，反驳假设的失败就越引人注目，但这绝不是证据。(据我所知，这种观点与非统计学家/非科学家之间的沟通问题最多。)有许多一致性检验，包括卡方检验、安德森-达林检验和柯尔莫戈洛夫-斯米尔诺夫检验等等。
所有均匀性测试都将通过诸如0、1、2、…、N-1、0、1、…等值序列。所以均匀性不足以说明你有一个好的发电机。您还应该测试序列相关性，例如间隔测试、上升/下降测试、高于/低于平均值测试、"生日"测试等等。
George Marsaglia在他的职业生涯中创建了一套非常全面的一致性和序列相关性测试，并于1995年出版，他开玩笑地称之为"顽固测试"(因为这是一组繁重的测试)。
对于黑盒测试(您无法访问源代码)，您无法证明它是均匀分布的(UD)。但是，您可以执行统计测试来发现它是UD的可能性。多次运行生成器(例如，N*X次)，并且0到N之间的每个数字应该出现大约X次。
这完全忽略了它是否是随机数，它只关注一致性。但是，如果您要运行无限次测试，则只能证明生成器是均匀分布的。在最好的情况下，在第一个N*X次迭代中，生成器有可能是一致的，但它很简单，易于实现。
没有办法证明它，因为生成器可能首先生成均匀分布，然后偏离成非均匀分布。
既然这是一次面试，真正的问题不是证明均匀分布，真正的问题是被这份工作选中。我建议你采用一种方法，让你迅速判断面试官是在寻找关于高等数学的有趣讨论，还是在测试你的实践思维。我的猜测是，面试官很有可能会寻找后者。一个好的面试答案可以是这样的:"这完全取决于需要随机数生成器做什么。如果它在音乐播放器上提供洗牌功能，我会让它生成100个数字，检查平均值是否大致等于N/2，然后简要查看这些数字，并在这一点上感到满意。如果目的与加密有关，那就完全是另一回事了，我会开始做研究，但可能最终不是自己证明，而是依赖现有的独立证据。"
仅一个数字从生成器，或尽可能多的你想要的?如果只有一个，你就不能说一致性。只要0 ≤数量& lt;N，没关系。
假设面试官的意思是"[大量结果的一致性]"，那么你既需要看结果的分布，也需要看结果中的模式。第一种方法是对结果进行排序和分类，并查看结果的直方图。对于大量的值，它应该是合理的"平坦"(例如，不是高斯曲线)。
第二个测试有点困难，因为您可能会得到2、3甚至4个或更多数字长的模式。我看到的一个测试是用球坐标(首先是方位角，其次是高度，第三是半径)将结果以三人为一组绘制出来。我不记得细节了，但是IIRC你应该看到一个均匀填充的球体，或者类似的东西。这个测试可能有一个正式的术语，但底线是有许多测试可以看到RNG在做什么，所以很难从上一个数字中预测下一个数字(没有明显的模式)。
我会首先询问他们需要多长时间才能得到答案，以及一旦你有了生成器，他们希望得到多好的答案。
是的，如果你想要彻底的话，运行一套全面的统计测试是不错的。但这可能需要几天或几周的时间。在某些情况下，这个问题可能会在会议上被问到，一群人想马上得到答案，最好的答案可能就是在会议上使用谷歌，看看其他用户是否认为生成器"足够好"。在"快速谷歌"one_answers"综合测试"之间有一系列的答案。
值得一提的是，在现实中你不能证明生成器在所有情况下都是100%均匀的。案例如下:
1)你不能看源代码。因此，即使您生成N个看起来均匀的随机数，如果不生成更多的数字，也无法知道从N+1开始的每个数字都是10(例如)。无论你停在哪里，你都不能对你还没有生成的数字提出任何要求
2)你可以看看源代码。它可能太难看了，难以理解，除非它是一个非常简单的线性同余生成器。如果它太丑，我想说，除了欣赏代码之外，你可能无法得出任何可靠的结论。
尽管有风险，但值得一提的是，如果应用程序对随机数生成器有可预测的调用次数，那么您可以测试该生成器的调用次数。然而，我看到一些面试官会误解这一点，并认为你不知道如何制作健壮且可扩展性良好的算法。
《普林斯顿数学指南》中对此有详细的讨论
然而，人们如何使用确定性计算机来在10、30和之间随机选择一万个数字10 31 ?答案是，实际上不需要这样做:它几乎总是足够好，而做一个伪随机选择. ...
什么时候我们应该把这样的序列看作是"随机的"?同样，有许多不同的答案被提出。一个想法是考虑简单的统计测试:我们从长远来看，零出现的频率是多少应该和1大致相同，甚至更多一般来说，任何小的子序列，如00110应该以"正确"的频率出现(哪一个这个序列是1/32，因为它的长度是5)。
然而，序列完全有可能通过这些简单的测试，但要由确定性过程生成。如果有人试图决定是否一个0和1的序列实际上是随机的也就是说，通过投掷等方式产生如果是硬币，那么我们就会对序列产生怀疑我们可以找出一种算法来产生相同的结果序列。例如，我们会拒绝一个序列是从π的数字中简单推导出来的，对吧如果它通过了统计测试。然而，仅仅问一个序列不能由递归过程产生，并不能很好地检验随机性举个例子，如果一个人采取这样的顺序并交替这个序列的项是0，然后得到1一个新的序列，远不是随机的，但仍然不能递归生成。
因此，冯·米塞斯在1919年建议a0和1的序列应该称为随机if不仅1的频率极限是1/2，而且对于任何可以"通过合理的程序"提取的子序列也是如此。1940年，Church将"by means a reasonable procedure"翻译成"通过合理的程序"，使其更加精确"通过递归函数"然而，即便如此条件太弱:有这样的序列不满足"迭代对数定律"(随机序列可以满足的定律)。目前,1966年提出的所谓Martin-Löf论点是随机最常用的定义之一Ness:随机序列是一个满足所有条件的序列"有效的统计顺序测试"这个概念我们在这里不能精确地表述，但它在递归函数的基本概念。通过与丘奇的论点形成鲜明对比，几乎所有人都赞同丘奇的论点数学家同意，Martin-Löf论文仍在讨论中
对于面试来说这是一个有点残酷的问题(除非这是一个研究职位)，但对于论坛来说这是一个有趣的问题。20年前，在完成我的数学学位后，我会很高兴地展示一个我自己编写的随机生成器，并给出它是随机的数学证明。现在看着这些代码，我很难相信这是我写的。这些天，我做了任何实际程序员都会做的事情，使用由NAG, numpy, matlab或其他一些受人尊敬的软件包实现的算法(我信任NAG)，并且可能做一些简单的统计分析来验证，如果分布由于某种原因或其他原因是关键的。
在面试中最重要的是要诚实。如果你不知道，那就告诉他们你得去查一下。如果你不知道，也没有兴趣去查，也可以告诉他们。做一份具有挑战性的工作，需要不断的研究，雇主必须提供一个良好的工作环境。挑战是好的，但对抗和竞争是适得其反的(太多的"C")。