查看“︁随机数列”︁的源代码

[[File:Kuntze-Konicz Fortune.jpg|thumb|240px|[[福尔图娜]]，[[罗马神话]]中的命运女神，由{{link-pl|Tadeusz Kuntze|Tadeusz Kuntze}}于1754年绘制（[[华沙国家博物馆]]）]]

'''随机数列'''（英文：{{lang|en|random sequence}}）的概念在[[概率论]]和[[统计学]]中都十分重要。整个概念主要构建在'''由[[随机变量]]组成的数列'''的基础之上，因此每每提及到随机数列，人们常常会这样开场：“设<math>X_{1} \cdots X_{n}</math>为随机变量……”<ref>{{cite journal|author1=Sergio B. Volchan|title=What Is a Random Sequence?|journal=The American Mathematical Monthly|date=2002年|volume=109|pages=46-63|url=http://www.maa.org/programs/maa-awards/writing-awards/what-is-a-random-sequence|trans-title=什么是随机数列？|language=en|access-date=2017-03-28|archive-date=2021-04-27|archive-url=https://web.archive.org/web/20210427141355/https://www.maa.org/programs/maa-awards/writing-awards/what-is-a-random-sequence}}</ref>但是也如同美国数学家{{tsl|en|D. H. Lehmer|得瑞克·亨利·雷莫}}在1951年时说的那样：“随机数列是一个很模糊的概念……它每一项都是无法预测中的无法预测，但是这些数字却能够通过传统的统计学上的考验。”<ref>{{cite book|author1=Philip J. Davis|title=Mathematics and common sense : a case of creative tension|url=https://archive.org/details/mathematicscommo00pjda|date=2006|publisher=A. K. Peters|location=Wellesley (Mass.)|isbn=1-56881-270-1|pages=[https://archive.org/details/mathematicscommo00pjda/page/n226 180]-182|accessdate=2017-03-30|language=en|chapter=Mathematics and common sense}}</ref>

[[概率公理]]'''有意'''绕过了对随机数列的定义。<ref>{{cite book|last1=Beck|first1=József|title=Inevitable randomness in discrete mathematics|url=https://archive.org/details/inevitablerandom0049beck|date=2009|publisher=American Mathematical Society|location=Providence, R.I.|isbn=0-8218-4756-2|page=[https://archive.org/details/inevitablerandom0049beck/page/n57 44]|language=en}}</ref>传统的统计学理论并没有直接阐明某个数列是否随机，而是直接跳过这部分，在假设某种随机性存在的前提之下讨论随机变量的性质。比如[[Nicolas Bourbaki|布尔巴基学派]]就认为，“‘假设一个随机数列’这句话是对[[濫用符號|术语的滥用]]。”<ref>{{cite book|last1=Uspensky|first1=Vladimir|last2=Semenov|first2=Alexei|title=Algorithms : main ideas and applications|date=1993|publisher=Kluwer Acad. Publ.|location=Dordrecht [u.a.]|isbn=0-7923-2210-X|pages=166|language=en}}</ref>

==早期历史==
法国数学家[[埃米尔·博雷尔]]是1909年第一批给出随机性的正式定义的数学家之一。<ref>{{cite journal|last1=Émile Borel|first1=M.|title=Les probabilités dénombrables et leurs applications arithmétiques|journal=Rendiconti del Circolo Matematico di Palermo|date=1909-12|volume=27|issue=1|pages=247–271|doi=10.1007/BF03019651|trans-title=有限概率及其算数应用|language=fr}}</ref>在1919年，受[[大数定理]]的启发，奥地利数学家[[理查德·冯·米泽斯]]给出了第一个算法随机性的定义。但是，他使用了“集合”这个词，而不是“随机数列”。利用{{tsl|en|Impossibility of a gambling system|赌博系统的不可能性}}，冯·米泽斯定义道：若由0和1构成的无穷数列具有“频率稳定性的特点”，也就是说，0的频率趋进于1/2，且该数列的每个“以适当方式选取的”子数列也都没有偏差，那么我们说，这个数列是“随机的”。<ref>{{cite book|last1=(ed.)|first1=24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007. Wolfgang Thomas ; Pascal Weil|title=Proceedings / STACS 2007|date=2007|publisher=Springer|location=Berlin|isbn=3-540-70917-7|pages=260}}</ref>

冯·米泽斯的这个方法中，“适当选取子数列”的标准非常重要，因为虽然说“01010101……”本身没有偏差（0出现的概率为1/2），但是若我们只选奇数位置上的数字，得到的子数列便成了完全不随机的“000000……”。冯·米泽斯未曾就这个问题正式给出一个选取规则上的解释。1940年，美国数学家[[阿隆佐·邱奇]]将这个规则定义为“任何已经读取该无穷数列的前N项，并决定是否读取其第N+1项的[[递归#正式定义|递归函数]]。”邱其是[[可计算函数]]方面的先驱，他给出的这个定义的可计算性基于[[邱奇－图灵猜想]]。<ref>{{cite journal | last1 = Church | first1 = Alonzo | authorlink = Alonzo Church | year = 1940 | title = On the Concept of Random Sequence | url = | journal = Bull. Amer. Math. Soc. | volume = 46 | issue = | pages = 254–260 }}</ref>这个定义经常被称作“米泽斯-邱其随机性”（英文：{{lang|en|Mises-Church randomness}}）。

==现代方法==
在20世纪，人们发展出了一些技术手段来定义随机数列。在1960年代中期，苏联数学家[[安德雷·柯尔莫哥洛夫]]和美国数学家{{tsl|en|D. W. Loveland|唐纳德·W·罗弗兰德}}各自独立提交了一份更宽容的子数列选取规则。<ref>{{cite journal|last1=Kolmogorov|first1=A. N.|title=Three approaches to the quantitative definition of information|page=http://alexander.shen.free.fr/library/Kolmogorov65_Three-Approaches-to-Information.pdf}}</ref><ref>{{cite journal|last1=Loveland|first1=Donald|title=A New Interpretation of the von Mises' Concept of Random Sequence|journal=Mathematical Logic Quarterly|date=1966-01-01|volume=12|issue=1|pages=279–294|doi=10.1002/malq.19660120124|url=http://onlinelibrary.wiley.com/doi/10.1002/malq.19660120124/abstract|language=en|issn=1521-3870}}</ref>在他们看来，邱其的递归函数过于严苛，因为它只能按顺序读取数列的前N项。与邱其相反，他们的规则是允许从数列中选取“任意”N项，并决定是否需要再选一个项。这个定义经常被称作“柯尔莫哥洛夫-罗弗兰德随机性”（英文：{{lang|en|Kolmogorov-Loveland stochasticity}}）。但是[[Alexander Shen]]则认为这个方法过弱，并给出了一个不符合大众眼中的随机性的柯尔莫哥洛夫-罗弗兰德随机数列。

1966年，瑞典数理统计学家[[佩尔·马丁-洛夫]]引入了一个被后世称为最令人满意的{{tsl|en|algorithmic randomness|算法平均性}}的概念。 他的这一概念中起初涉及到了了测量理论，但后来证明也可以用[[柯氏复杂性]]来表示。（柯尔莫哥洛夫对于随机字符串的定义，即柯氏复杂性，是说，“若一个字符串在[[通用图灵机]]中没有一个比自身要更短的描述，那么这个字符串是随机的”。）<ref>{{cite book|last1=Vitányi|first1=Ming Li ; Paul|title=An introduction to Kolmogorov complexity and its applications|date=1997|publisher=Springer|location=New York [u.a.]|isbn=0387948686|edition=2. ed.|page=149-151}}</ref>

现如今，有三个处理随机数列的方式：<ref>{{cite book|last1=(ed.)|first1=Jiři Fiala ...|title=Mathematical foundations of computer science 2004 : 29th international symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004 ; proceedings|date=2004|publisher=Springer|location=Berlin [u.a.]|isbn=3-540-22823-3|page=44}}</ref>

:* '''频率／测量理论'''法。这个方法建立在前文的米泽斯和邱其的方法的基础之上。 在1960年代，佩尔·马丁-洛夫注意到，人们能够写下基于频率生成随机数列的代码，而这些代码的集合是一种特殊的{{tsl|en|measure zero|零测度}}集。在此基础之上，通过利用所有的零测度集，人们能够得到一个更加放之四海而皆准的随机数列定义。

:* '''复杂度／可压缩度'''法。柯尔莫哥洛夫本人对这个方法贡献巨大，其次还有列文和阿根廷裔美国数学家{{tsl|en|Gregory Chaitin|格里高列·蔡廷}}等也作出了一定的贡献。对于有限项的随机数列，柯尔莫哥洛夫将它的随机性定义为“熵”，也就是后来的[[柯氏复杂性]]。这个定义下，一个包含了0与1组成的、长度为<math>K</math>的字符串（或者数列，二者并无本质上的区别），其“熵”的大小为这个数列的最短描述的长度和<math>K</math>的接近程度。字符串的复杂度越接近于<math>K</math>，它也会越随机；而字符串的复杂性越低于<math>K</math>，它也就越不随机。

:* '''可预测性'''法。这个方法由德国数学家{{tsl|en|Claus P. Schnorr|克劳斯·施诺}}提出。他用了一个和传统概率论稍有不同的[[鞅 (概率论)|鞅]]的定义。<ref>{{cite journal | last1 = Schnorr | first1 = C. P. | year = 1971 | title = A unified approach to the definition of a random sequence | url = | journal = Mathematical Systems Theory | volume = 5 | issue = 3| pages = 246–258 | doi=10.1007/bf01694181}}</ref>他证明了“若人们拥有一个下注策略，可以从多种可能中选择出最优的方案，那么人们也可以用类似的策略选出一个有偏差的子集。”如果人们只需要一个递归性的鞅（而不是构造的方式）便能够成功选出数列的话，那么人们就该使用递归随机性的概念中。美国数学家{{tsl|en|Yongge Wang|Yongge Wang}}则证明出，递归随机性和施诺的随机性并不是同一个概念。<ref>Yongge Wang: Randomness and Complexity. PhD Thesis, 1996. http://webpages.uncc.edu/yonwang/papers/IPL97.pdf {{Wayback|url=http://webpages.uncc.edu/yonwang/papers/IPL97.pdf |date=20200921163245 }}</ref><ref>{{cite journal | last1 = Wang | first1 = Yongge | year = 1999 | title = A separation of two randomness concepts | url = http://www.sciencedirect.com/science/article/pii/S0020019098002026 | journal = Information Processing Letters | volume = 69 | issue = 3| pages = 115–118 | doi=10.1016/S0020-0190(98)00202-6}}</ref>

这三个方式在大多数情况下被证实是等价的。<ref>{{cite book|last1=(eds.)|first1=Peter Widmayer ... [et al.]|title=Automata, languages and programming 29th international colloquium, ICALP 2002, Málaga, Spain, 2002年7月8日-13日 : proceedings|url=https://archive.org/details/automatalanguage2002widm|date=2002|publisher=Springer|location=Berlin|isbn=3-540-43864-5|pages=[https://archive.org/details/automatalanguage2002widm/page/391 391]}}</ref>

需要注意的是，按照以上任意一个关于无限数列的随机性定义，由于都是着眼于随机性趋势，因此对数据开头部分的随机性不敏感。如果在随机数列的第一项前插入哪怕一百万个0，得出的仍然会是随机数列。因此，应用这几个定义时应该小心谨慎。<ref>{{cite book|last1=Uspensky|first1=Vladimir|last2=Semenov|first2=Alexei|title=Algorithms : main ideas and applications|date=1993|publisher=Kluwer Acad. Publ.|location=Dordrecht [u.a.]|isbn=0-7923-2210-X|pages=176}}</ref>

==参见==
* [[随机性]]
* {{tsl|en|History of randomness|随机性历史}}
* [[随机数生成器]]
* {{tsl|en|Seven states of randomness|随机数的七个阶段}}
* {{tsl|en|Statistical randomness|统计随机性}}

==参考资料==
{{Reflist}}

==外部链接==
* {{springer|title=Random sequence|id=p/r077350}}
* [https://www.youtube.com/watch?v=H2lJLXS3AYM 【视频】为何没法“人工”生成随机数字？] {{Wayback|url=https://www.youtube.com/watch?v=H2lJLXS3AYM |date=20210427040635 }}关于频率的稳定性。
* http://www.ciphersbyritter.com/RES/RANDTEST.HTM#vonNeumann63 {{Wayback|url=http://www.ciphersbyritter.com/RES/RANDTEST.HTM#vonNeumann63 |date=20100104091134 }}

{{DEFAULTSORT:随机数列}}
[[Category:序列]]
[[Category:随机过程]]
[[Category:隨機性]]