良好且简单的随机性度量

Question

取长整数序列（例如100,000个整数）并返回该序列有多随机的度量的最佳算法是什么？

该函数应该返回一个结果，如果序列不是全部都是随机的，则返回0，如果完全随机，则返回1。如果序列有点随机，则可以在两者之间给出一些信息，例如0.95可能是一个合理的随机序列，而0.50可能具有一些非随机部分和一些随机部分。

如果我要将Pi的前100,000个数字传递给该函数，则它应给出一个非常接近1的数字。如果我将序列1、2，… 100,000传递给该函数，则应返回0。

这样，我可以轻松地获取30个数字序列，确定每个数字的随机性，并返回有关其相对随机性的信息。

有这样的动物吗？

…..

2019年9月24日更新：Google可能刚刚迎来了量子霸权时代：

“据报道，谷歌的量子计算机能够在3分20秒内解决计算问题-
证明随机数发生器产生的数字具有随机性，这将使世界上最快的传统超级计算机Summit大约需要10,000年。这实际上意味着传统计算机无法执行这种计算，这使Google率先证明了量子至上性。”

因此，显然有一种“证明”随机性的算法。有谁知道它是什么？这个算法还能提供一种随机性的度量吗？

Answer 1

可以通过以下方式完成：

CAcert研究实验室进行随机数生成器分析。

他们的结果页使用7个测试（熵，生日间隔，矩阵等级，6x8矩阵等级，最小距离，随机球体和挤压）评估每个随机序列。然后，每个测试结果都将颜色编码为“无问题”，“可能确定性”和“非随机”之一。

因此，可以编写一个接受随机序列并执行7个测试的函数。如果7个测试中的任何一个为“非随机”，则该函数返回0。如果7个测试中的所有均为“无问题”，则它返回1。否则，它可以根据多少个中间值返回一些数字。测试以“潜在确定性”的形式出现。

该解决方案唯一缺少的是7个测试的代码。