隨機數列
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/17/Kuntze-Konicz_Fortune.jpg/240px-Kuntze-Konicz_Fortune.jpg)
隨機數列(英文:random sequence)的概念在概率論和統計學中都十分重要。整個概念主要構建在由隨機變量組成的數列的基礎之上,因此每每提及到隨機數列,人們常常會這樣開場:「設為隨機變量……」[1]但是也如同美國數學家得瑞克·亨利·雷莫在1951年時說的那樣:「隨機數列是一個很模糊的概念……它每一項都是無法預測中的無法預測,但是這些數字卻能夠通過傳統的統計學上的考驗。」[2]
概率公理有意繞過了對隨機數列的定義。[3]傳統的統計學理論並沒有直接闡明某個數列是否隨機,而是直接跳過這部分,在假設某種隨機性存在的前提之下討論隨機變量的性質。比如布爾巴基學派就認為,「『假設一個隨機數列』這句話是對術語的濫用。」[4]
早期歷史
[編輯]法國數學家埃米爾·博雷爾是1909年第一批給出隨機性的正式定義的數學家之一。[5]在1919年,受大數定理的啟發,奧地利數學家理察·馮·米澤斯給出了第一個算法隨機性的定義。但是,他使用了「集合」這個詞,而不是「隨機數列」。利用賭博系統的不可能性,馮·米澤斯定義道:若由0和1構成的無窮數列具有「頻率穩定性的特點」,也就是說,0的頻率趨進於1/2,且該數列的每個「以適當方式選取的」子數列也都沒有偏差,那麼我們說,這個數列是「隨機的」。[6]
馮·米澤斯的這個方法中,「適當選取子數列」的標準非常重要,因為雖然說「01010101……」本身沒有偏差(0出現的概率為1/2),但是若我們只選奇數位置上的數字,得到的子數列便成了完全不隨機的「000000……」。馮·米澤斯未曾就這個問題正式給出一個選取規則上的解釋。1940年,美國數學家阿隆佐·邱奇將這個規則定義為「任何已經讀取該無窮數列的前N項,並決定是否讀取其第N+1項的遞歸函數。」邱其是可計算函數方面的先驅,他給出的這個定義的可計算性基於邱奇-圖靈猜想。[7]這個定義經常被稱作「米澤斯-邱其隨機性」(英文:Mises-Church randomness)。
現代方法
[編輯]在20世紀,人們發展出了一些技術手段來定義隨機數列。在1960年代中期,蘇聯數學家安德雷·柯爾莫哥洛夫和美國數學家唐納德·W·羅弗蘭德各自獨立提交了一份更寬容的子數列選取規則。[8][9]在他們看來,邱其的遞歸函數過於嚴苛,因為它只能按順序讀取數列的前N項。與邱其相反,他們的規則是允許從數列中選取「任意」N項,並決定是否需要再選一個項。這個定義經常被稱作「柯爾莫哥洛夫-羅弗蘭德隨機性」(英文:Kolmogorov-Loveland stochasticity)。但是Alexander Shen則認為這個方法過弱,並給出了一個不符合大眾眼中的隨機性的柯爾莫哥洛夫-羅弗蘭德隨機數列。
1966年,瑞典數理統計學家佩爾·馬丁-洛夫引入了一個被後世稱為最令人滿意的算法平均性的概念。 他的這一概念中起初涉及到了了測量理論,但後來證明也可以用柯氏複雜性來表示。(柯爾莫哥洛夫對於隨機字符串的定義,即柯氏複雜性,是說,「若一個字符串在通用圖靈機中沒有一個比自身要更短的描述,那麼這個字符串是隨機的」。)[10]
現如今,有三個處理隨機數列的方式:[11]
- 頻率/測量理論法。這個方法建立在前文的米澤斯和邱其的方法的基礎之上。 在1960年代,佩爾·馬丁-洛夫注意到,人們能夠寫下基於頻率生成隨機數列的代碼,而這些代碼的集合是一種特殊的零測度集。在此基礎之上,通過利用所有的零測度集,人們能夠得到一個更加放之四海而皆準的隨機數列定義。
這三個方式在大多數情況下被證實是等價的。[15]
需要注意的是,按照以上任意一個關於無限數列的隨機性定義,由於都是著眼於隨機性趨勢,因此對數據開頭部分的隨機性不敏感。如果在隨機數列的第一項前插入哪怕一百萬個0,得出的仍然會是隨機數列。因此,應用這幾個定義時應該小心謹慎。[16]
參見
[編輯]參考資料
[編輯]- ^ Sergio B. Volchan. What Is a Random Sequence? [什麼是隨機數列?]. The American Mathematical Monthly. 2002年, 109: 46–63 [2017-03-28]. (原始內容存檔於2021-04-27) (英語).
- ^ 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 (英語).
- ^ 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.
- ^ Kolmogorov, A. N. Three approaches to the quantitative definition of information: http://alexander.shen.free.fr/library/Kolmogorov65_Three-Approaches-to-Information.pdf.
- ^ 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 (英語).
- ^ 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.
- ^ (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.
- ^ 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.
- ^ (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.
- ^ Uspensky, Vladimir; Semenov, Alexei. Algorithms : main ideas and applications. Dordrecht [u.a.]: Kluwer Acad. Publ. 1993: 176. ISBN 0-7923-2210-X.
外部連結
[編輯]- Hazewinkel, Michiel (編), Random sequence, 数学百科全书, Springer, 2001, ISBN 978-1-55608-010-4
- 【視頻】為何沒法「人工」生成隨機數字? (頁面存檔備份,存於網際網路檔案館)關於頻率的穩定性。
- http://www.ciphersbyritter.com/RES/RANDTEST.HTM#vonNeumann63 (頁面存檔備份,存於網際網路檔案館)