隨機數列

隨機數列（英文：random sequence）的概念在概率論和統計學中都十分重要。整個概念主要構建在由隨機變量組成的數列的基礎之上，因此每每提及到隨機數列，人們常常會這樣開場：「設 $X_{1}\cdots X_{n}$ 為隨機變量……」^[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組成的、長度為 $K$ 的字符串（或者數列，二者並無本質上的區別），其「熵」的大小為這個數列的最短描述的長度和 $K$ 的接近程度。字符串的複雜度越接近於 $K$ ，它也會越隨機；而字符串的複雜性越低於 $K$ ，它也就越不隨機。

可預測性法。這個方法由德國數學家克勞斯·施諾（英語：Claus P. Schnorr）提出。他用了一個和傳統概率論稍有不同的鞅的定義。^[12]他證明了「若人們擁有一個下注策略，可以從多種可能中選擇出最優的方案，那麼人們也可以用類似的策略選出一個有偏差的子集。」如果人們只需要一個遞歸性的鞅（而不是構造的方式）便能夠成功選出數列的話，那麼人們就該使用遞歸隨機性的概念中。美國數學家Yongge Wang（英語：Yongge Wang）則證明出，遞歸隨機性和施諾的隨機性並不是同一個概念。^[13]^[14]

這三個方式在大多數情況下被證實是等價的。^[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 （頁面存檔備份，存於互聯網檔案館）

[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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]