如何确定一列数是否随机

如何确定一列数是否随机？比如我想输出一列0~9之间的随机数算法1输出：999999999999...我认为这个输出并不随机，这列数的分布距离均一分布偏离太远算法2输出：12345678901234567890...我认为这个输出也不随机，因为两个1之间的距离的分布距离泊松分布太远算法3输出：112358314594370774...我认为这个输出不随机，因为但是这种评价不够机械，比如算法3的输出，如果我看不出来这种递推关系那我很可能就会认为它是随机的。有没有一种机械的方法来确定一列数是不是随机的呢？首先，“一个随机的数列”是什么意思？某个给定的数列，不可能是随机的。想像一下，我们拿这个数列抛硬币，抛出来的结果是给定的，与“随机”的行为差很远。如果是要谈随机性的话，起码要是一个数列的概率分布才可以。那么，真随机就很好定义了：每个数列出现概率都一样的概率分布。但在现实生活中，真随机是否存在还是不太确定的。一般我们生成的，都是伪随机数。一般来说，伪随机数程序会在外界拿到一个随机的“种子”，然后从这个种子开始生成随机数列。这样看的话，给定外部种子的概率分布，这个伪随机数程序的结果实际上是一个数列的概率分布。这样我们就可以下定义了。伪随机的一个可操作的定义在这里：简单来说，给定一个可计算的序列的概率分布，如果没有程序可以（在一定的时间空间限制下）有效地将它与真随机序列对应的概率分布区分开来，那么这个序列就是（相对于对应的时间空间限制下的）伪随机序列。这个区分的程序我们一般叫distinguisher。一般我们希望计算序列的程序所需的时间空间限制远远低于distinguisher的限制，这样才能比较省时间，因为运算的大头一般也还不是在随机数生成上。现在有很多随机性测试，其实这些测试都可以视为distinguisher，而且是复杂度相当低的。在上面的定义中，一个很重要的思想是：因为所有利用随机序列来做某件事情的过程，都可以视为以这个随机序列为输入的一个程序，而得出的结果服从输入序列的概率分布经过程序处理后得出的概率分布。如果某个伪随机分布处理后得到的结果分布与真随机分布得到的结果非常接近，那么我们就可以将其视为真随机，因为只有结果是重要的嘛。只问结果，不问本质；只看关系，不看细节。这是搞数学的人希望厘清概念的时候常用的做法。学过一点密码学的同学应该知道，distinguisher是攻击方用的，我们当然重视它的成本，希望这个成本越高越好。一般的攻击者都只有有限资源，如果是多项式时间的distinguisher的话，增加密钥长度一般没多大效果，所以我们希望不存在多项式时间的distinguisher。所以，在伪随机序列的讨论中，一般这个时间空间限制取为多项式时间。而在这个情况下，伪随机数存在当且仅当单向函数存在，而这是密码学里一个极其重要的未解问题，因为它关系到完全安全的公钥密码体系的存在性。大数乘法一般被认为是单向陷门，但其实没有证据。所以说，（多项式时间）伪随机数是否存在，其实也是不知道的。歪一下楼，distinguisher在密码中是怎么用来攻击的呢？直观地说，如果一个密码体系生成的数据越接近随机，那么就越难找到规律，因为看起来就像是随机数嘛。然后，如果对于某个密码体系，我们能构建一个distinguisher，将这个密码体系的输出与随机数据分开的话，就说明我们找到了某种规律，相当于破解有希望了。一般这种攻击可以让大家知道某个系统用的是什么密码体系，还可能可以排除某些密钥，减少暴力破解所需的时间。扯远了，回到随机性。既然不知道伪随机数是否存在，那么当然也不存在一个（多项式时间内的）程序能判断某个伪随机数生成器是否真的伪随机。所以，基本上我们用到现在的伪随机数生成器，都是靠蒙的，不能证明它们真的是伪随机。不过既然结果还凑合，在没有其它办法的情况下也就先用着了。---------------------然后是有关复杂度的思考---------------------但如果我们坚持不考虑数列的概率分布，坚持“一个数列”的原则，那么LZ的疑问又到底是什么呢？LZ列举了几个数列，然后列举了它们的规律。但是，这些数列的复杂程度很显然是不一样的。最后一个显然比第一个复杂，但我们如何界定这种复杂性呢？这种复杂性与“随机”又有什么关系呢？我们来想一下，当我们说“一个随机的数列”的时候，我们到底在说什么。如果一个数列很有规律，看着前几项就可以猜出后面的项的话，那么显然这个数列“不随机”。“一个随机的数列”，应该是无论我们给多少项，接下来的一项都很难猜出来。如果这些数列都是一些程序生成出来的话，我们会觉得，越复杂的程序，生成的数列看起来就越随机。那么，对于一个有限的数列，我们可以定义它的“随机性”为生成它所需要的程序的最短长度。如果一个数列只需要一个非常短的程序就能生成的话，它看起来就很“不随机”；反之，如果一个数列需要一个非常长的程序，甚至是一个跟数列本身差不多长的程序才能生成的话，它看上去就很“随机”。我们说一个数列是“随机”的，当且仅当它比能生成它的最短的程序还要短。在信息学中，这被称为Kolmogorov复杂度。这个概念可以适当地推广到无限序列上。很不幸，它是不可计算的。Kolmogorov复杂度有些很诡异的性质。如果随机取一个无限序列的话，它是Kolmogorov随机的概率是1。但有一个叫Chaitin不完备性定理的东西却说，对于任意（可有限生成）的包含皮亚诺公理的公理系统（以及程序描述的语言）来说，存在一个常数L，使得我们不能举出一个Kolmogorov复杂度大于L的数列s，并形式地证明这一点。也就是说，随便抓一个都是随机，但是就是证明不了……显然这个定理的证明方式与哥德尔不完备性定理的很像，都是某种诡异的自指……