如何确定一列数是否随机?

比如我想输出一列0~9之间的随机数
算法1输出:999999999999...
我认为这个输出并不随机,这列数的分布距离均一分布偏离太远
算法2输出:12345678901234567890...
我认为这个输出也不随机,因为两个1之间的距离的分布距离泊松分布太远
算法3输出:112358314594370774...
我认为这个输出不随机,因为

但是这种评价不够机械,比如算法3的输出,如果我看不出来这种递推关系那我很可能就会认为它是随机的。有没有一种机械的方法来确定一列数是不是随机的呢?

推荐  (0) | 25人关注关注
24个答案
37 0

方弦科学松鼠会成员,信息学硕士生

2013-12-15 10:33

我觉得LZ要搞清楚一件事情:随机性和“一个数列”其实是矛盾的。LZ的问题可以有两个方面的思考,一个是关于随机性,一个是关于数列的复杂程度。下面我简单叙述一下这两种思考。

---------------------首先是有关随机性的思考---------------------

首先,“一个随机的数列”是什么意思?

某个给定的数列,不可能是随机的。想像一下,我们拿这个数列抛硬币,抛出来的结果是给定的,与“随机”的行为差很远。如果是要谈随机性的话,起码要是一个数列的概率分布才可以。

那么,真随机就很好定义了:每个数列出现概率都一样的概率分布。

但在现实生活中,真随机是否存在还是不太确定的。一般我们生成的,都是伪随机数。一般来说,伪随机数程序会在外界拿到一个随机的“种子”,然后从这个种子开始生成随机数列。这样看的话,给定外部种子的概率分布,这个伪随机数程序的结果实际上是一个数列的概率分布。

这样我们就可以下定义了。伪随机的一个可操作的定义在这里:
http://en.wikipedia.org/wiki/Pseudorandom_generator_theorem
简单来说,给定一个可计算的序列的概率分布,如果没有程序可以(在一定的时间空间限制下)有效地将它与真随机序列对应的概率分布区分开来,那么这个序列就是(相对于对应的时间空间限制下的)伪随机序列。这个区分的程序我们一般叫distinguisher。一般我们希望计算序列的程序所需的时间空间限制远远低于distinguisher的限制,这样才能比较省时间,因为运算的大头一般也还不是在随机数生成上。

现在有很多随机性测试,其实这些测试都可以视为distinguisher,而且是复杂度相当低的。

在上面的定义中,一个很重要的思想是:因为所有利用随机序列来做某件事情的过程,都可以视为以这个随机序列为输入的一个程序,而得出的结果服从输入序列的概率分布经过程序处理后得出的概率分布。如果某个伪随机分布处理后得到的结果分布与真随机分布得到的结果非常接近,那么我们就可以将其视为真随机,因为只有结果是重要的嘛。

只问结果,不问本质;只看关系,不看细节。这是搞数学的人希望厘清概念的时候常用的做法。

学过一点密码学的同学应该知道,distinguisher 是攻击方用的,我们当然重视它的成本,希望这个成本越高越好。一般的攻击者都只有有限资源,如果是多项式时间的distinguisher的话,增加密钥长度一般没多大效果,所以我们希望不存在多项式时间的distinguisher。所以,在伪随机序列的讨论中,一般这个时间空间限制取为多项式时间。而在这个情况下,伪随机数存在当且仅当单向函数存在,而这是密码学里一个极其重要的未解问题,因为它关系到完全安全的公钥密码体系的存在性。大数乘法一般被认为是单向陷门,但其实没有证据。所以说,(多项式时间)伪随机数是否存在,其实也是不知道的。

歪一下楼,distinguisher在密码中是怎么用来攻击的呢?直观地说,如果一个密码体系生成的数据越接近随机,那么就越难找到规律,因为看起来就像是随机数嘛。然后,如果对于某个密码体系,我们能构建一个distinguisher,将这个密码体系的输出与随机数据分开的话,就说明我们找到了某种规律,相当于破解有希望了。一般这种攻击可以让大家知道某个系统用的是什么密码体系,还可能可以排除某些密钥,减少暴力破解所需的时间。

扯远了,回到随机性。既然不知道伪随机数是否存在,那么当然也不存在一个(多项式时间内的)程序能判断某个伪随机数生成器是否真的伪随机。所以,基本上我们用到现在的伪随机数生成器,都是靠蒙的,不能证明它们真的是伪随机。不过既然结果还凑合,在没有其它办法的情况下也就先用着了。

---------------------然后是有关复杂度的思考---------------------

但如果我们坚持不考虑数列的概率分布,坚持“一个数列”的原则,那么LZ的疑问又到底是什么呢?

LZ列举了几个数列,然后列举了它们的规律。但是,这些数列的复杂程度很显然是不一样的。最后一个显然比第一个复杂,但我们如何界定这种复杂性呢?这种复杂性与“随机”又有什么关系呢?

我们来想一下,当我们说“一个随机的数列”的时候,我们到底在说什么。

如果一个数列很有规律,看着前几项就可以猜出后面的项的话,那么显然这个数列“不随机”。“一个随机的数列”,应该是无论我们给多少项,接下来的一项都很难猜出来。如果这些数列都是一些程序生成出来的话,我们会觉得,越复杂的程序,生成的数列看起来就越随机。

那么,对于一个有限的数列,我们可以定义它的“随机性”为生成它所需要的程序的最短长度。如果一个数列只需要一个非常短的程序就能生成的话,它看起来就很“不随机”;反之,如果一个数列需要一个非常长的程序,甚至是一个跟数列本身差不多长的程序才能生成的话,它看上去就很“随机”。我们说一个数列是“随机”的,当且仅当它比能生成它的最短的程序还要短。

在信息学中,这被称为Kolmogorov复杂度。这个概念可以适当地推广到无限序列上。

很不幸,它是不可计算的。

Kolmogorov复杂度有些很诡异的性质。如果随机取一个无限序列的话,它是Kolmogorov随机的概率是1。但有一个叫Chaitin不完备性定理的东西却说,对于任意(可有限生成)的包含皮亚诺公理的公理系统(以及程序描述的语言)来说,存在一个常数L,使得我们不能举出一个Kolmogorov复杂度大于L的数列s,并形式地证明这一点。 也就是说,随便抓一个都是随机,但是就是证明不了……显然这个定理的证明方式与哥德尔不完备性定理的很像,都是某种诡异的自指……

---------------------最后是免责声明---------------------

其实这方面我也不是很熟,不是做这个的,道听途说……要认真钻研的话还是要去看书啊……

12 0

傅里叶变黄油猫软件工程师,应用数学专业

2013-12-14 19:50

所谓“随机”,要求只有一个:无法预测。

计算机无法生成真正的随机数,使用诸如C语言rand()函数获得的都是伪随机数。生成随机数听起来很简单,但实际上涉及密码学,安全的随机数生成算法都可以保证知道前面N个数也无法预测下一个是什么,或者计算上不可能(计算规模太大)。所以,对于你来说,这样一串用伪随机数生成算法生成的序列就是随机的,因为你无法预测。

先跑一下题说两个事:(1)生成随机数是密码学里面一个重要领域,很多加密算法的安全性依赖于伪随机数生成算法,所以它是现代信息学的基石,这些理论技术每天都在保障你的通讯安全。(2)任何加密算法,其安全性依赖的是密钥的保密而不是算法的保密,才是真正的安全。所以,常用的加密算法本身对大众是公开的,算法所需的密钥才是保密的。

主流的伪随机数生成算法也是公开算法保护密钥的方式来确保安全性。伪随机数生成算法都包含一个你从外部无法得知的“种子”,可能是一个数。只要生成者保密这个种子,他生成出来的随机数序列就无法预测。但是,如果你通过某种途径得知了这个种子,你就可以根据其算法,预测之后每个随机数——欧漏,对于你来说,已经不是随机数了。

所以,你还认为“随机”和“非随机”有绝对的区别吗?随机和不随机,取决于你,而不是生成序列的人。

所以,任意给你一条数列,如果你可以通过自己过往经验,发现其中的规律,那对于你来说它就不是随机的,否则就是随机的。

最后回到你的话题,机器如何判断一串数是否随机?取决于程序。你可以将很多种预测算法实现成程序,让机械去匹配预测,只要有一个匹配,那数列对机械/你来说就不是随机的。实际上这也是我们每天都接触的技术——压缩,数据压缩的本质就是预测,不过那扯远了。

3 0

要证明不随机,本质上只有一个做法,那就是预言下一次输出多少
即使你获取了大量样本也没法看出到底是不是随机的
如果不能获取算法那几乎是无法判断的

2 0

cryyyyMT4专家,PYTHON工程师,程序员

2013-12-16 22:45

如何判断?
基础:大量生成定长M的数,然后根据
1、没有重复
2、统计各个数字的出现次数,基本一致
3、统计N(N=2,3,...,M/2)排列的情况,没有明显的重复
4、........

单一的一个数,没有什么随机不随机

1 0
支持者: B.C.

定性地说,那就是信息的“熵”越大越随机。可是熵的原始定义是出现概率的负对数,直接应用过来就意味着“从无穷多可能的数列中随机抽一个抽中此数列的概率”的负对数,然而这样的概率怎么能计算呢?况且其实它就是零概率(从无穷多中取1);那换一种方式,更接近通常理解的,就是把“上一位数字为X”时“这一位数字是Y”的条件概率作为定义数列信息熵的基石,但是同样也没法说清这个概率究竟该怎么算。
说到底,信息熵的定义只在理想情况下(比如码元之间相互独立且每个码元出现概率为已知)才可计算,否则只是个理论上的东西,没法计算。

1 0
支持者: ..-.-..--.

有一种随机的定义,如果输出一个二进制串所需要的二进制指令长度不比这个二进制串本身短,这个二进制串就是随机的
你可以关注一下蔡汀(Chaitin)的工作

1 0
支持者: 梅梅_2686

有限数列就不多说了,必有“通项公式”
x1,x2,x3,x4..........xn
必然有n次多项式的通项公式;

无限的数列,我们永远无法证明它没有通项公式。
因为,无限数列无论我们取前多少位都能找到其通项公式。
楼主的那个更简单,每个数都是一位,那么他必然有通项,
通项就是,我们把此无限数列排成一个小于1的实数A

xi=A的第i位。

相比整数序列的集合来说,实数的集合是更高阶的无穷大
相比实数的集合,函数的集合是更高阶的无穷大。

换句话就是说,一个数列可以找到无数个通项公式,但一个通项公式只能生成一个数列
1,2,3```````这个序列可以找到无数种通项公式对应
ai=i
ai=isin2πi
ai=i+tanπi
但反过来一个通项公式只能找到一个数列。

0 0

yangyanggoods私立樱才学园学生会入会积极分子

2013-12-14 18:55

算法3输出的数字其实是有规律而且循环的→_→
(10)1123583145943,707741561785381,909987527965167,303369549325729,1011……

0 0

鱼大雷邪恶之王 大毒舌 欢乐

2013-12-14 18:56

理论上说对于一个真正的随机输出,你得到的任何一组数都是随机的,如果你认为他不是,哪怕他看起来是999999999999999999999,那是你的错觉。hiahiahia.

0 0

加饭某审计学校的计算机学生

2013-12-15 22:28

把π或者e,或者任何一个无理数写出来,这一列数组成的数列算不算随机呢 ,它的确可以计算,但是确实没有规律啊

0 0

我感觉DFT是个好办法

我还听说过 可以观察连续出现相同数字的次数多数情况下如果一个“随机”数列是伪造的 那么连续出现同一个数的情况比真的随机序列要少

0 0

已有的结果分布无法说明是否真正随机,就好比9999999999.。。。。。。这个数列,如果这个数列的定义为:掷硬币,正面为9,反面为0,那么不管多少个9相连,我们也肯定人为这是个随机的事件,至于已经存在的数列,这只不过是记录随机事件的历史,这个历史在大量的样本情况下应该遵循概率为50%,但是谁能给出大量的确切含义呢?

所以是否真随机,不是看分布,而是看驱动该分布生成事件本身。

该事件对结果的影响关联性如果强,则事件本身随机性弱,如果关联弱,则事件本身随机性就强,直至纯正的随机事件。比较有代表性的就是量子相关性的验证。。。请有关牛逼人士来细说不妨。

0 0

灯虫生物学博士在读

2013-12-16 15:20

不是游程检验吗?

本来我觉得楼主问的是一个很简单的问题,但是楼上都跑题了,讨论伪随机数的生成……

0 0

能不能这样:
第一步:考虑有限数列
先定义它的子集,然后考虑含有元素个数相同但没有相同元素的那些子集(例如a_{1}, a_{3}, a_{4}, … 与 a_{2}, a_{5}, a_{6},考察这些子集之间的相关性。如果相关性约接近正态分布,则可以认为其约可能是随机数列。(对于真正的随机数列,任意子集(包含不同元素的)之间的相关性显然是0)。
第二步,推广到无限数列
具体怎么推广就要靠大神了。

0 0

随机数本身指的就不是一个固定的数列。
但即使把一个“无规律的数列”叫随机数,也不是那么容易明确
简而言之,看看这列数字有规律没,没规律就是随机数,有规律就不是。至于这个规律是什么,各人有个人的想法

0 0

哪有什么随机数,真正随机的只是生成某个数的算法与初始条件,有了算法与初始条件“随机数"不就变成可预测的了。

0 0

对于任何一列数字,总是能够构建出(或许规则会很复杂,但存在)一条规则使得这列数字符合这条规则。

0 0

Lookis第十维空间旅行家

2016-02-25 21:03

关于随机数楼上都说的很好了……我来补充一个真随机数生成器吧……
https://www.random.org/clients/http/

0 0

不要离题太远了。。

方法很简单,计算数列中出现的数的分布的情况是否符合概率模型。比如各个数字是等概率事件,则统计前10万个数,会符合概率分布。

0 0

对于二进制序列,检验它的随机性,比较简单直接的办法是看它的自相关特性。楼主说的0~9之间的自然数,可以转换成二进制,看序列的自相关特性就行了。

很明显,楼主举的几个例子,自相关都有很多个峰值,随机性很差

0 0

AS001为科学之美着迷 又贪恋人间灯红酒绿

2016-02-26 11:59

我只能说


既然有算法


那就不是随机数



记住,世界上只有伪随机数

0 0

估计只能是模拟量做种子产能生成比较真的随机数.

模拟量来源:摄像头,麦克风.其实网卡的进出流量都可以当做随机数种子来源.你永远都不知道下一秒的网络流量具体数值.

0 0

方弦的回答已经很好了。

这里我认为楼主对随机性的理解类似于“不可压缩性”,一个可压缩的序列可以用更简短的方式无损地描述,而不可压缩的数列则被认为是随机的。

从信息论的角度说,如果数字的分布呈现某种规律(某个子序列出现的概率明显高于平均值),这个序列就是可压缩的。比如楼主第二个例子,序列中相邻的两个1的距离明显不符合泊松分布,这将导致某些子序列出现的概率较高,某些子序列的出现的概率较低。有一些压缩算法可以聪明地找出重复出现的子序列,比如著名的LZ(Lempel-Ziv, 不是楼主)算法。

但是所有压缩算法仍然都有局限性,比如一个序列由圆周率小数点后的100万位构成。若非人类协助,压缩算法自己如何能发现这一点呢?(别说AI, 如果换一个进位制来表示,绝大多数人类也看不出来 吧。)

所以恶魔的部分在于,如何证明一个序列不可压缩。要透彻谈论这个问题就不免要回到烧脑的Kolmogorov Complexity。如方弦所说,这个量是不可计算的。出于可操作性,也许我们必须满足于单向的判断,即一个序列是“可压缩的”还是“未知是否可压缩”。

查看更多

添加回答

登录 后回答问题,你也可以用以下帐号直接登录

相关问答

关于我们 加入果壳 媒体报道 帮助中心 果壳活动 家长监控 免责声明 联系我们 移动版 移动应用

©果壳网    京ICP证100430号    京网文[2018] 6282-492号    新出发京零字第朝200003号     京公网安备11010502007133号

违法和不良信息举报邮箱:jubao@guokr.com    举报电话:18612934101    网上有害信息举报专区    儿童色情信息举报专区