随机数列：修订间差异

删除的内容添加的内容

行内

2017年3月30日 (四) 05:49的版本

随机数列（英文：random sequence）的概念在概率论和统计学中都十分重要。整个概念主要构建在由随机变量组成的数列的基础之上，因此在使用的过程中人们常常会这样开场：“设 $X_{1}\cdots X_{n}$ 为随机变量……”^[1]但是也如同得瑞克·亨利·雷莫（英语：D. H. Lehmer）在1951年时说的那样：“随机数列是一个很模糊的概念……它每一项都是无法预测中的无法预测，但是这些数字却能够通过传统的统计学上的考验。”^[2]

概率公理有意绕过了对随机数列的定义。^[3]传统的统计学理论并没有直接阐明某个数列是否随机，而是直接跳过这部分，在假设某种随机性存在的前提之下讨论随机变量的性质。比如布尔巴基学派就认为，“‘假设一个随机数列’这句话是对术语的滥用（英语：Abuse of notation）。”^[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]这个定义经常被称作“米泽斯-邱其随机性”。

现代的方法

在20世纪，人们发展出了一些技术手段来定义随机数列，现今流传的有三个方式。In the mid 1960s, A. N. Kolmogorov and D. W. Loveland independently proposed a more permissive selection rule.^[8]^[9] In their view Church's recursive function definition was too restrictive in that it read the elements in order. Instead they proposed a rule based on a partially computable process which having read any N elements of the sequence, decides if it wants to select another element which has not been read yet. This definition is often called Kolmogorov-Loveland stochasticity. But this method was considered too weak by Alexander Shen who showed that there is a Kolmogorov-Loveland stochastic sequence which does not conform to the general notion of randomness.

In 1966 Per Martin-Löf introduced a new notion which is now generally considered the most satisfactory notion of algorithmic randomness. His original definition involved measure theory, but it was later shown that it can be expressed in terms of Kolmogorov complexity. Kolmogorov's definition of a random string was that it is random if has no description shorter than itself via a universal Turing machine.^[10]

Three basic paradigms for dealing with random sequences have now emerged:^[11]

The frequency / measure-theoretic approach. This approach started with the work of Richard von Mises and Alonzo Church. In the 1960s Per Martin-Löf noticed that the sets coding such frequency-based stochastic properties are a special kind of measure zero sets, and that a more general and smooth definition can be obtained by considering all effectively measure zero sets.

The complexity / compressibility approach. This paradigm was championed by A. N. Kolmogorov along with contributions Levin and Gregory Chaitin. For finite random sequences, Kolmogorov defined the "randomness" as the entropy, i.e. Kolmogorov complexity, of a string of length K of zeros and ones as the closeness of its entropy to K, i.e. if the complexity of the string is close to K it is very random and if the complexity is far below K, it is not so random.

The predictability approach. This paradigm was due to Claus P. Schnorr and uses a slightly different definition of constructive martingales than martingales used in traditional probability theory.^[12] Schnorr showed how the existence of a selective betting strategy implied the existence of a selection rule for a biased sub-sequence. If one only requires a recursive martingale to succeed on a sequence instead of constructively succeeds on a sequence, then one gets the recursively randomness concepts. Yongge Wang showed^[13]^[14] that recursively randomness concept is different from Schnorr's randomness concepts.

In most cases, theorems relating the three paradigms (often equivalence) have been proven.^[15]

It is important to realize that for each of the definitions given above for infinite sequences, if one adds a billion zeros to the front of the random sequence the new sequence will still be considered random. Hence any application of these concepts to practical problems needs to be performed with care.^[16]

参见

参考资料

^ Sergio B. Volchan. What Is a Random Sequence? [什么是随机数列？]. The American Mathematical Monthly. 2002年, 109: 46–63 （英语）.
^ Philip J. Davis. Mathematics and common sense. Mathematics and common sense : a case of creative tension. Wellesley (Mass.): A. K. Peters. 2006: 180–182. ISBN 1-56881-270-1 （英语）.
^ Beck, József. Inevitable randomness in discrete mathematics. Providence, R.I.: American Mathematical Society. 2009: 44. ISBN 0-8218-4756-2 （英语）.
^ Uspensky, Vladimir; Semenov, Alexei. Algorithms : main ideas and applications. Dordrecht [u.a.]: Kluwer Acad. Publ. 1993: 166. ISBN 0-7923-2210-X （英语）.
^ É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 （法语）.
^ (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.
^ Church, Alonzo. On the Concept of Random Sequence. Bull. Amer. Math. Soc. 1940, 46: 254–260.
^ A. N. Kolmogorov, Three approaches to the quantitative definition of information Problems of Information and Transmission, 1(1):1--7, 1965.
^ D.W. Loveland, A new interpretation of von Mises' concept of random sequence Z. Math. Logik Grundlagen Math 12 (1966) 279-294
^ An introduction to Kolmogorov complexity and its applications by Ming Li, P. M. B. Vitányi 1997 0387948686 pages 149-151
^ R. Downey, Some Recent Progress in Algorithmic Randomness in Mathematical foundations of computer science 2004: by Jiří Fiala, Václav Koubek 2004 ISBN 3-540-22823-3 page 44
^ 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.
^ Yongge Wang: Randomness and Complexity. PhD Thesis, 1996. http://webpages.uncc.edu/yonwang/papers/IPL97.pdf
^ Wang, Yongge. A separation of two randomness concepts. Information Processing Letters. 1999, 69 (3): 115–118. doi:10.1016/S0020-0190(98)00202-6.
^ Wolfgan Merkel, Kolmogorov Loveland Stochasticity in Automata, languages and programming: 29th international colloquium, ICALP 2002, by Peter Widmayer et al. ISBN 3-540-43864-5 page 391
^ Algorithms: main ideas and applications by Vladimir Andreevich Uspenskiĭ, Alekseĭ, Lʹvovich Semenov 1993 Springer ISBN 0-7923-2210-X page 176

外部链接

Hazewinkel, Michiel (编), Random sequence, 数学百科全书, Springer, 2001, ISBN 978-1-55608-010-4
【视频】为何没法“人工”生成随机数字？关于频率的稳定性。
Terry Ritter的随机性检验

{{DEFAULTSORT:Random Sequence}} [[Category:Sequences and series]] [[Category:Statistical randomness]]

[1] Sergio B. Volchan. What Is a Random Sequence? [什么是随机数列？]. The American Mathematical Monthly. 2002年, 109: 46–63 （英语）.

[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. 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] A. N. Kolmogorov, Three approaches to the quantitative definition of information Problems of Information and Transmission, 1(1):1--7, 1965.

[9] D.W. Loveland, A new interpretation of von Mises' concept of random sequence Z. Math. Logik Grundlagen Math 12 (1966) 279-294

[10] An introduction to Kolmogorov complexity and its applications by Ming Li, P. M. B. Vitányi 1997 0387948686 pages 149-151

[11] R. Downey, Some Recent Progress in Algorithmic Randomness in Mathematical foundations of computer science 2004: by Jiří Fiala, Václav Koubek 2004 ISBN 3-540-22823-3 page 44

[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] Wolfgan Merkel, Kolmogorov Loveland Stochasticity in Automata, languages and programming: 29th international colloquium, ICALP 2002, by Peter Widmayer et al. ISBN 3-540-43864-5 page 391

[16] Algorithms: main ideas and applications by Vladimir Andreevich Uspenskiĭ, Alekseĭ, Lʹvovich Semenov 1993 Springer ISBN 0-7923-2210-X page 176

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

@@ 第5行： / 第5行： @@
 '''随机数列'''（英文：{{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}}</ref>但是也如同{{tsl|en|D. H. Lehmer|得瑞克·亨利·雷莫}}在1951年时说的那样：“随机数列是一个很模糊的概念……它每一项都是无法预测中的无法预测，但是这些数字却能够通过传统的统计学上的考验。”<ref>{{cite book|author1=Philip J. Davis|title=Mathematics and common sense : a case of creative tension|date=2006|publisher=A. K. Peters|location=Wellesley (Mass.)|isbn=1-56881-270-1|pages=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|date=2009|publisher=American Mathematical Society|location=Providence, R.I.|isbn=0-8218-4756-2|page=44|language=en}}</ref>传统的统计学理论并没有直接阐明某个数列是否随机，而是直接跳过这部分，在假设某种随机性存在的前提之下讨论随机变量的性质。比如[[Nicolas Bourbaki|布尔巴基学派]]就认为，“‘假设一个随机数列’这句话是对{{tsl|en|Abuse of notation|术语的滥用}}。”<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}}</ref>
+[[概率公理]]'''有意'''绕过了对随机数列的定义。<ref>{{cite book|last1=Beck|first1=József|title=Inevitable randomness in discrete mathematics|date=2009|publisher=American Mathematical Society|location=Providence, R.I.|isbn=0-8218-4756-2|page=44|language=en}}</ref>传统的统计学理论并没有直接阐明某个数列是否随机，而是直接跳过这部分，在假设某种随机性存在的前提之下讨论随机变量的性质。比如[[Nicolas Bourbaki|布尔巴基学派]]就认为，“‘假设一个随机数列’这句话是对{{tsl|en|Abuse of notation|术语的滥用}}。”<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>
-[[Émile Borel]] was one of the first mathematicians to formally address randomness in 1909.<ref>E. Borel, ''Les probabilites denombrables et leurs applications arithmetique'' Rend. Circ. Mat. Palermo 27 (1909) 247-271</ref> In 1919 [[Richard von Mises]] gave the first definition of algorithmic randomness, which was inspired by the law of large numbers, although he used the term ''collective'' rather than random sequence. Using the concept of the [[impossibility of a gambling system]], von Mises defined an infinite sequence of zeros and ones as random if it is not biased by having the ''frequency stability property'' i.e. the frequency of zeros goes to 1/2 and every sub-sequence we can select from it by a "proper" method of selection is also not biased.<ref>Laurant Bienvenu "Kolmogorov Loveland Stochastocity" in STACS 2007: 24th Annual Symposium on Theoretical Aspects of Computer Science by Wolfgang Thomas ISBN 3-540-70917-7 page 260</ref>
-The sub-sequence selection criterion imposed by von Mises is important, because although 0101010101... is not biased, by selecting the odd positions, we get 000000... which is not random. Von Mises never totally formalized his definition of a proper selection rule for sub-sequences, but in 1940 [[Alonzo Church]] defined it as any [[recursion#Functional recursion|recursive function]] which having read the first N elements of the sequence decides if it wants to select element number N+1. Church was a pioneer in the field of computable functions, and the definition he made relied on the [[Church Turing Thesis]] for computability.<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> This definition is often called ''Mises-Church randomness''.
+冯·米泽斯的这个方法中，“适当选取子数列”的标准非常重要，因为虽然说“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>这个定义经常被称作“米泽斯-邱其随机性”。
 ==现代的方法==
+在20世纪，人们发展出了一些技术手段来定义随机数列，现今流传的有三个方式。In the mid 1960s, [[A. N. Kolmogorov]] and [[D. W. Loveland]] independently proposed a more permissive selection rule.<ref>A. N. Kolmogorov, ''Three approaches to the quantitative definition of information'' Problems of Information and Transmission, 1(1):1--7, 1965.</ref><ref>D.W. Loveland, ''A new interpretation of von Mises' concept of random sequence'' Z. Math. Logik Grundlagen Math 12 (1966) 279-294</ref> In their view Church's recursive function definition was too restrictive in that it read the elements in order. Instead they proposed a rule based on a partially computable process which having read ''any'' N elements of the sequence, decides if it wants to select another element which has not been read yet. This definition is often called ''Kolmogorov-Loveland stochasticity''. But this method was considered too weak by [[Alexander Shen]] who showed that there is a Kolmogorov-Loveland stochastic sequence which does not conform to the general notion of randomness.
-在20世纪，人们发展出了一些技术手段来定义随机数列，现今流传的有三个方式。
-In the mid 1960s, [[A. N. Kolmogorov]] and [[D. W. Loveland]] independently proposed a more permissive selection rule.<ref>A. N. Kolmogorov, ''Three approaches to the quantitative definition of information'' Problems of Information and Transmission, 1(1):1--7, 1965.</ref><ref>D.W. Loveland, ''A new interpretation of von Mises' concept of random sequence'' Z. Math. Logik Grundlagen Math 12 (1966) 279-294</ref> In their view Church's recursive function definition was too restrictive in that it read the elements in order. Instead they proposed a rule based on a partially computable process which having read ''any'' N elements of the sequence, decides if it wants to select another element which has not been read yet. This definition is often called ''Kolmogorov-Loveland stochasticity''. But this method was considered too weak by [[Alexander Shen]] who showed that there is a Kolmogorov-Loveland stochastic sequence which does not conform to the general notion of randomness.
 In 1966 [[Per Martin-Löf]] introduced a new notion which is now generally considered the most satisfactory notion of [[algorithmic randomness]]. His original definition involved measure theory, but it was later shown that it can be expressed in terms of [[Kolmogorov complexity]]. Kolmogorov's definition of a random string was that it is random if has no description shorter than itself via a [[universal Turing machine]].<ref>''An introduction to Kolmogorov complexity and its applications'' by Ming Li, P. M. B. Vitányi 1997 0387948686 pages 149-151</ref>
@@ 第43行： / 第41行： @@
 ==外部链接==
 * {{springer|title=Random sequence|id=p/r077350}}
-* [https://www.youtube.com/watch?v=H2lJLXS3AYM Video] on frequency stability. Why humans can't "guess" randomly
+* [https://www.youtube.com/watch?v=H2lJLXS3AYM 【视频】为何没法“人工”生成随机数字？]关于频率的稳定性。
-* [http://www.ciphersbyritter.com/RES/RANDTEST.HTM#vonNeumann63 Randomness tests by Terry Ritter]
+* [http://www.ciphersbyritter.com/RES/RANDTEST.HTM#vonNeumann63 {{lang|en|Terry Ritter}}的随机性检验]
 <nowiki>