跳至內容

隨機數列

維基百科,自由的百科全書
福爾圖娜羅馬神話中的命運女神,由Tadeusz Kuntze波蘭語Tadeusz Kuntze於1754年繪製(華沙國家博物館

隨機數列(英文:random sequence)的概念在概率論統計學中都十分重要。整個概念主要構建在隨機變量組成的數列的基礎之上,因此每每提及到隨機數列,人們常常會這樣開場:「設為隨機變量……」[1]但是也如同美國數學家得瑞克·亨利·雷莫英語D. H. Lehmer在1951年時說的那樣:「隨機數列是一個很模糊的概念……它每一項都是無法預測中的無法預測,但是這些數字卻能夠通過傳統的統計學上的考驗。」[2]

概率公理有意繞過了對隨機數列的定義。[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. 

外部連結

[編輯]