随机数列

(重定向自随机序列

随机数列(英文:random sequence)的概念在概率论统计学中都十分重要。整个概念主要构建在随机变量组成的数列的基础之上,因此每每提及到随机数列,人们常常会这样开场:“设为随机变量……”[1]但是也如同美国数学家得瑞克·亨利·雷莫英语D. H. Lehmer在1951年时说的那样:“随机数列是一个很模糊的概念……它每一项都是无法预测中的无法预测,但是这些数字却能够通过传统的统计学上的考验。”[2]

福尔图娜罗马神话中的命运女神,由Tadeusz Kuntze波兰语Tadeusz Kuntze于1754年绘制(华沙国家博物馆

概率公理有意绕过了对随机数列的定义。[3]传统的统计学理论并没有直接阐明某个数列是否随机,而是直接跳过这部分,在假设某种随机性存在的前提之下讨论随机变量的性质。比如布尔巴基学派就认为,“‘假设一个随机数列’这句话是对术语的滥用。”[4]

早期历史

编辑

法国数学家埃米尔·博雷尔是1909年第一批给出随机性的正式定义的数学家之一。[5]在1919年,受大数定理的启发,奥地利数学家理查德·冯·米泽斯给出了第一个算法随机性的定义。但是,他使用了“集合”这个词,而不是“随机数列”。利用赌博系统的不可能性英语Impossibility of a gambling system,冯·米泽斯定义道:若由0和1构成的无穷数列具有“频率稳定性的特点”,也就是说,0的频率趋进于1/2,且该数列的每个“以适当方式选取的”子数列也都没有偏差,那么我们说,这个数列是“随机的”。[6]

冯·米泽斯的这个方法中,“适当选取子数列”的标准非常重要,因为虽然说“01010101……”本身没有偏差(0出现的概率为1/2),但是若我们只选奇数位置上的数字,得到的子数列便成了完全不随机的“000000……”。冯·米泽斯未曾就这个问题正式给出一个选取规则上的解释。1940年,美国数学家阿隆佐·邱奇将这个规则定义为“任何已经读取该无穷数列的前N项,并决定是否读取其第N+1项的递归函数。”邱其是可计算函数方面的先驱,他给出的这个定义的可计算性基于邱奇-图灵猜想[7]这个定义经常被称作“米泽斯-邱其随机性”(英文:Mises-Church randomness)。

现代方法

编辑

在20世纪,人们发展出了一些技术手段来定义随机数列。在1960年代中期,苏联数学家安德雷·柯尔莫哥洛夫和美国数学家唐纳德·W·罗弗兰德英语D. W. Loveland各自独立提交了一份更宽容的子数列选取规则。[8][9]在他们看来,邱其的递归函数过于严苛,因为它只能按顺序读取数列的前N项。与邱其相反,他们的规则是允许从数列中选取“任意”N项,并决定是否需要再选一个项。这个定义经常被称作“柯尔莫哥洛夫-罗弗兰德随机性”(英文:Kolmogorov-Loveland stochasticity)。但是Alexander Shen则认为这个方法过弱,并给出了一个不符合大众眼中的随机性的柯尔莫哥洛夫-罗弗兰德随机数列。

1966年,瑞典数理统计学家佩尔·马丁-洛夫引入了一个被后世称为最令人满意的算法平均性英语algorithmic randomness的概念。 他的这一概念中起初涉及到了了测量理论,但后来证明也可以用柯氏复杂性来表示。(柯尔莫哥洛夫对于随机字符串的定义,即柯氏复杂性,是说,“若一个字符串在通用图灵机中没有一个比自身要更短的描述,那么这个字符串是随机的”。)[10]

现如今,有三个处理随机数列的方式:[11]

  • 频率/测量理论法。这个方法建立在前文的米泽斯和邱其的方法的基础之上。 在1960年代,佩尔·马丁-洛夫注意到,人们能够写下基于频率生成随机数列的代码,而这些代码的集合是一种特殊的零测度英语measure zero集。在此基础之上,通过利用所有的零测度集,人们能够得到一个更加放之四海而皆准的随机数列定义。
  • 复杂度/可压缩度法。柯尔莫哥洛夫本人对这个方法贡献巨大,其次还有列文和阿根廷裔美国数学家格里高列·蔡廷英语Gregory Chaitin等也作出了一定的贡献。对于有限项的随机数列,柯尔莫哥洛夫将它的随机性定义为“熵”,也就是后来的柯氏复杂性。这个定义下,一个包含了0与1组成的、长度为 的字符串(或者数列,二者并无本质上的区别),其“熵”的大小为这个数列的最短描述的长度和 的接近程度。字符串的复杂度越接近于 ,它也会越随机;而字符串的复杂性越低于 ,它也就越不随机。
  • 可预测性法。这个方法由德国数学家克劳斯·施诺英语Claus P. Schnorr提出。他用了一个和传统概率论稍有不同的的定义。[12]他证明了“若人们拥有一个下注策略,可以从多种可能中选择出最优的方案,那么人们也可以用类似的策略选出一个有偏差的子集。”如果人们只需要一个递归性的鞅(而不是构造的方式)便能够成功选出数列的话,那么人们就该使用递归随机性的概念中。美国数学家Yongge Wang英语Yongge Wang则证明出,递归随机性和施诺的随机性并不是同一个概念。[13][14]

这三个方式在大多数情况下被证实是等价的。[15]

需要注意的是,按照以上任意一个关于无限数列的随机性定义,由于都是着眼于随机性趋势,因此对数据开头部分的随机性不敏感。如果在随机数列的第一项前插入哪怕一百万个0,得出的仍然会是随机数列。因此,应用这几个定义时应该小心谨慎。[16]

参见

编辑

参考资料

编辑
  1. ^ Sergio B. Volchan. What Is a Random Sequence? [什么是随机数列?]. The American Mathematical Monthly. 2002年, 109: 46–63 [2017-03-28]. (原始内容存档于2021-04-27) (英语). 
  2. ^ Philip J. Davis. Mathematics and common sense. Mathematics and common sense : a case of creative tension. Wellesley (Mass.): A. K. Peters. 2006: 180-182 [2017-03-30]. ISBN 1-56881-270-1 (英语). 
  3. ^ Beck, József. Inevitable randomness in discrete mathematics. Providence, R.I.: American Mathematical Society. 2009: 44. ISBN 0-8218-4756-2 (英语). 
  4. ^ Uspensky, Vladimir; Semenov, Alexei. Algorithms : main ideas and applications. Dordrecht [u.a.]: Kluwer Acad. Publ. 1993: 166. ISBN 0-7923-2210-X (英语). 
  5. ^ Émile Borel, M. Les probabilités dénombrables et leurs applications arithmétiques [有限概率及其算数应用]. Rendiconti del Circolo Matematico di Palermo. 1909-12, 27 (1): 247–271. doi:10.1007/BF03019651 (法语). 
  6. ^ (ed.), 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007. Wolfgang Thomas ; Pascal Weil. Proceedings / STACS 2007. Berlin: Springer. 2007: 260. ISBN 3-540-70917-7. 
  7. ^ Church, Alonzo. On the Concept of Random Sequence. Bull. Amer. Math. Soc. 1940, 46: 254–260. 
  8. ^ Kolmogorov, A. N. Three approaches to the quantitative definition of information: http://alexander.shen.free.fr/library/Kolmogorov65_Three-Approaches-to-Information.pdf. 
  9. ^ Loveland, Donald. A New Interpretation of the von Mises' Concept of Random Sequence. Mathematical Logic Quarterly. 1966-01-01, 12 (1): 279–294. ISSN 1521-3870. doi:10.1002/malq.19660120124 (英语). 
  10. ^ Vitányi, Ming Li ; Paul. An introduction to Kolmogorov complexity and its applications 2. ed. New York [u.a.]: Springer. 1997: 149-151. ISBN 0387948686. 
  11. ^ (ed.), Jiři Fiala ... Mathematical foundations of computer science 2004 : 29th international symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004 ; proceedings. Berlin [u.a.]: Springer. 2004: 44. ISBN 3-540-22823-3. 
  12. ^ Schnorr, C. P. A unified approach to the definition of a random sequence. Mathematical Systems Theory. 1971, 5 (3): 246–258. doi:10.1007/bf01694181. 
  13. ^ Yongge Wang: Randomness and Complexity. PhD Thesis, 1996. http://webpages.uncc.edu/yonwang/papers/IPL97.pdf页面存档备份,存于互联网档案馆
  14. ^ Wang, Yongge. A separation of two randomness concepts. Information Processing Letters. 1999, 69 (3): 115–118. doi:10.1016/S0020-0190(98)00202-6. 
  15. ^ (eds.), Peter Widmayer ... [et al.]. Automata, languages and programming 29th international colloquium, ICALP 2002, Málaga, Spain, 2002年7月8日-13日 : proceedings. Berlin: Springer. 2002: 391. ISBN 3-540-43864-5. 
  16. ^ Uspensky, Vladimir; Semenov, Alexei. Algorithms : main ideas and applications. Dordrecht [u.a.]: Kluwer Acad. Publ. 1993: 176. ISBN 0-7923-2210-X. 

外部链接

编辑