一种良好而简单的随机性度量

Question

采用长整数序列(比如说100,000个)的最佳算法是什么,并返回序列随机性的测量值？

该函数应返回单个结果,如果序列不是全部随机,则为0,如果完全随机则为1.如果序列有些随机,它可以在中间给出一些东西,例如0.95可能是一个合理的随机序列,而0.50可能有一些非随机部分和一些随机部分.

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

通过这种方式,我可以轻松获取30个数字序列,识别每个数字的随机性,并返回有关其相对随机性的信息.

有这样的动物吗？

Answer 1

你的问题回答了自己."如果我要将Pi的前100,000个数字传递给函数,它应该给出一个非常接近1"的数字,除了Pi的数字不是随机数,所以如果你的算法不能识别非常特定的序列为非随机然后它不是很好.

这里的问题是有许多类型的非随机性: - 例如."121,351,991,7898651,12398469018461"或"33,27,99,3000,63,231"或甚至"14297141600464,14344872783104,819534228736,3490442496"绝对不是随机的.

我认为你需要做的是确定对你来说很重要的随机性方面 - 分布,数字分布,缺乏共同因素,预期素数,斐波那契和其他"特殊"数字等.

PS.快速和肮脏(并且非常有效)的随机性测试是,在您对其进行gzip后,文件的大小大致相同.

pi不是一个随机的数字序列,它是一个非常特定的数字序列 - 它很长并且不包含任何重要的重复 - 但它始终是相同的序列. (14认同)
@lkessler:你用什么随机数？如果它是用于加密的,正如你所建议的那样,一旦密码学家意识到你正在使用来自pi的序列,你就会丢失. (3认同)
我很困惑你怎么能说 Pi 的数字不是随机的。对于数据加密等某些应用，Pi 在前一亿位内的随机性可能确实不如其他一些随机生成器有效（请参阅：http://www.sciencedaily.com/releases/2005/04/050427094258）。 htm ），但我从未见过任何声明 Pi 的数字是非随机的。 (2认同)
+1表示"识别对您来说很重要的随机性方面".如果它是随机的,那么它将通过随机性测试; 但反过来并不成立 - 没有可以验证随机性的测试,例如,人们可能在远离的元素之间具有非常强的相关性,并且通常必须明确地测试它.事实上,我非常喜欢这个,我会把它写成我自己的答案...... (2认同)

Answer 2

它可以这样做:

他们的研究结果页评估使用7个测试(熵,生日间距,矩阵秩,6×8矩阵秩,最小距离,任意大小的球,和挤压)各随机序列.然后将每个测试结果颜色编码为"无问题","潜在确定性"和"非随机"之一.

因此可以编写一个接受随机序列并执行7次测试的函数.如果7个测试中的任何一个是"非随机",则该函数返回0.如果所有7个测试都是"没有问题",那么它返回1.否则,它可以根据有多少返回一些数字测试以"潜在的确定性"进行.

此解决方案中唯一缺少的是7个测试的代码.

结果页面是伪随机数生成器的宝库.它还显示了pi的数字相当高的分数(搜索PiDigits).当然,对pi数字的评估"可能是非确定性的"揭示了我们术语的根本弱点. (2认同)

Answer 3

你可以尝试拉链压缩序列.成功越好,序列随机性越小.

因此,启发式随机性=邮政编码的长度/原始序列的长度

好吧,zip无法发现PI中的非随机性.由于PI不合理,它不会重复,重复是zip可以发现的.但是,它只需要3.32 = log(10)/ log(2)位来表示二进制数字(0 ... 9).3.32位是8位字节的41.5%.如果你压缩了1GB的PI,我估计zip会达到41.5% (2认同)

Answer 4

正如其他人所指出的那样,你不能直接计算序列的随机性,但有几种统计测试可以用来提高你对序列是否随机的信心.

该DIEHARD套件是这种测试的事实上的标准,但它没有返回一个值,也不是简单的.

ENT - 伪随机数序列测试程序,是一种更简单的替代方案,它结合了5种不同的测试.该网站解释了每个测试的工作原理.

如果您确实只需要一个值,您可以选择5个ENT测试中的一个并使用它.该卡方检验很可能是最好的使用,但可能无法满足的简单定义.

请记住,单个测试不如在同一序列上运行多个不同的测试.根据其测试选择,它应该是标志了明显可疑的序列作为非随机的不够好,但可能不会失败,对于表面上看起来是随机的,但实际上表现出一定的规律性序列.

Answer 5

您可以将100.000输出视为随机变量的可能结果并计算其相关熵.它会给你一定程度的不确定性.(以下图片来自维基百科,您可以在那里找到有关Entropy的更多信息.)简单地说:

熵公式

您只需计算序列中每个数字的频率.这将给你p(xi)(例如,如果10出现27次p(10)= 27/L,其中L对于你的情况是10.000.)这应该给你熵的量度.

虽然它不会给你0到1之间的数字.仍然0将是最小的不确定性.但是上限不会是1.您需要对输出进行标准化以实现该目的.

明确地说，我认为熵可能有用，但是不能只是将公式推算到数据上。在重复数字的示例中，尽管分布具有较高的熵（对于数字1-9），但是相邻数字之间的差异具有非常低的熵（即，如人们可以清楚地看到的那样，它不是随机的）。但是在这里，您又回到了定义随机性的含义，然后直接测试该功能。（此外，熵是一项比较棘手的措施，需要做一些研究才能弄清楚，因此最好避免熵，除非有人真正需要它。） (2认同)