Loading article…
ランダム シーケンスの概念は、確率論と統計学において不可欠です。この概念は一般に、ランダム変数のシーケンスの概念に依存しており、多くの統計的議論は「X 1、...、X nを独立したランダム変数とする...」という言葉で始まります。しかし、 DH Lehmer は1951 年に次のように述べています。「ランダム シーケンスは漠然とした概念であり...各項は初心者には予測できず、その数字は統計学者の伝統的なテストに合格します」。[1]
公理的確率論は、 ランダムなシーケンスの定義を意図的に避けています。 [2]伝統的な確率論では、特定のシーケンスがランダムであるかどうかは述べられていませんが、一般的には、ランダム性の定義を前提として、ランダム変数と確率的シーケンスの特性について議論を進めます。ブルバキ学派は、 「ランダムなシーケンスを考えてみましょう」という発言は言葉の乱用であると考えていました。[3]
初期の歴史
エミール・ボレルは、 1909年にランダム性について正式に論じた最初の数学者の1人でした。[4] 1919年にリチャード・フォン・ミーゼスは、大数の法則に触発されたアルゴリズム的ランダム性の最初の定義を与えましたが、ランダムなシーケンスではなく集合的な用語を使用しました。ギャンブルシステムの不可能性の概念を使用して、フォン・ミーゼスは、周波数安定性プロパティを持つことによって偏りがない場合、つまり、ゼロの周波数が1/2になり、「適切な」選択方法によって選択できるすべてのサブシーケンスも偏りがない場合、ゼロと1の無限シーケンスをランダムであると定義しました。[5]
フォン・ミーゼスによって課された部分列選択基準は重要である。なぜなら、0101010101... は偏っていないが、奇数の位置を選択すると 000000... となり、これはランダムではないからである。フォン・ミーゼスは部分列の適切な選択規則の定義を完全に形式化することはなかったが、1940 年にアロンゾ・チャーチはそれを、列の最初の N 要素を読み取って要素番号N + 1を選択するかどうかを決定する 任意の再帰関数として定義した。 チャーチは計算可能関数の分野の先駆者であり、彼が行った定義は計算可能性に関するチャーチ・チューリングのテーゼに依存していた。 [6]この定義はしばしばミーゼス・チャーチのランダム性と呼ばれる。
現代的なアプローチ
20 世紀には、ランダムなシーケンスを定義するためのさまざまな技術的アプローチが開発され、現在では 3 つの異なるパラダイムが識別できます。1960 年代半ばに、AN コルモゴロフとDW ラブランドはそれぞれ独立して、より許容度の高い選択規則を提案しました。[7] [8]彼らの見解では、チャーチの再帰関数の定義は、要素を順番に読み取るという点で制限が厳しすぎました。代わりに彼らは、シーケンスの任意の N 要素を読み取った後、まだ読み取っていない別の要素を選択するかどうかを決定する、部分的に計算可能なプロセスに基づく規則を提案しました。 この定義は、しばしばコルモゴロフ–ラブランド確率性と呼ばれます。しかし、この方法は、一般的なランダム性の概念に適合しないコルモゴロフ–ラブランド確率シーケンスが存在することを示したアレクサンダー シェンによって弱すぎると考えられました。
1966年にペル・マルティン＝レーフは、現在ではアルゴリズム的ランダム性の最も満足のいく概念であると一般的に考えられている新しい概念を導入した。彼の当初の定義は測度論を含んでいたが、後にコルモゴロフ複雑性の観点から表現できることが示された。コルモゴロフによるランダム文字列の定義は、ユニバーサルチューリングマシンを介してそれ自身よりも短い記述がない場合にランダムであるというものであった。[9]
ランダムシーケンスを扱うための3つの基本的なパラダイムが現在出現している: [10]
- 頻度/測度理論的アプローチ。このアプローチは、リチャード・フォン・ミーゼスとアロンゾ・チャーチの研究から始まりました。1960 年代に、ペル・マーティン＝レーフは、このような頻度ベースの確率的特性をコード化する集合は特別な種類の測度ゼロ集合であり、すべての有効な測度ゼロ集合を考慮することで、より一般的でスムーズな定義が得られることに気付きました。
- 複雑性 / 圧縮性アプローチ。このパラダイムは、 AN Kolmogorov がLeonid LevinとGregory Chaitinの貢献とともに提唱しました。有限シーケンスの場合、 Kolmogorov は長さnのバイナリ文字列のランダム性を、長さnで正規化されたエントロピー (またはKolmogorov 複雑性) として定義します。言い換えると、文字列の Kolmogorov 複雑性がnに近い場合、それは非常にランダムであり、複雑性がnよりはるかに低い場合、それほどランダムではありません。ランダム性の二重の概念は圧縮性です。シーケンスがランダムであればあるほど、圧縮性は低くなり、その逆も同様です。
- 予測可能性アプローチ。このパラダイムはクラウス・P・シュノアによるもので、従来の確率論で使用されているマルチンゲールとは少し異なる構成的マルチンゲールの定義を使用しています。 [11]シュノアは、選択的ベッティング戦略の存在が、偏ったサブシーケンスの選択ルールの存在を意味することを示しました。シーケンスで成功するために再帰的マルチンゲールのみが必要であり、シーケンスで建設的に成功することが必要ではない場合、再帰的ランダム性の概念が得られます。[さらに説明が必要] Yongge Wangは[12] [13]再帰的ランダム性の概念はシュノアのランダム性の概念とは異なることを示しました。[さらに説明が必要]
ほとんどの場合、3つのパラダイムに関連する定理（多くの場合同値性）は証明されています。[14]
参照
参考文献
- セルジオ・B・ボルチャン ランダムシーケンスとは何か？アメリカ数学月刊誌、第109巻、2002年、pp. 46-63
注記
- ^ 「ランダムという言葉の意味」数学と常識フィリップ・J・デイビス 2006 ISBN 1-56881-270-1 180-182ページ
- ^ 離散数学における避けられないランダム性József Beck 著 2009 ISBN 0-8218-4756-2 44 ページ
- ^ アルゴリズム: 主なアイデアとアプリケーション、Vladimir Andreevich Uspenskiĭ、Alekseĭ、Lʹvovich Semenov 著、1993 Springer ISBN 0-7923-2210-X 166 ページ
- ^ E. Borel、Les probabilites denombrables et leurs application arithmetique Rend。円マット。パレルモ 27 (1909) 247–271
- ^ Laurant Bienvenu「Kolmogorov Loveland Stochasticity」、STACS 2007: 24th Annual Symposium on Theoretical Aspects of Computer Science、Wolfgang Thomas著、ISBN 3-540-70917-7、260ページ
- ^ チャーチ、アロンゾ( 1940)。「ランダムシーケンスの概念について」。ブル。アメリカ数学協会。46 (2): 130–136。doi : 10.1090 /S0002-9904-1940-07154-X。
- ^ AN Kolmogorov、「情報の量的定義への3つのアプローチ」情報伝達の問題、1(1):1–7、1965年。
- ^ DW Loveland、フォン ミーゼスのランダム シーケンスの概念の新しい解釈Z. Math。 Logik Grundlagen Math 12 (1966) 279–294
- ^ コルモゴロフ複雑性とその応用への入門ミン・リー著、PMB Vitányi 1997 0387948686 149–151 ページ
- ^ R. ダウニー、コンピューター サイエンスの数学的基礎におけるアルゴリズムのランダム性に関する最近の進歩2004: Jiří Fiala、Václav Koubek 著、2004 ISBN 3-540-22823-3、44ページ
- ^ Schnorr, CP (1971). 「ランダムシーケンスの定義に対する統一的なアプローチ」.数学システム理論. 5 (3): 246–258. doi :10.1007/bf01694181. S2CID 8931514.
- ^ Yongge Wang: ランダム性と複雑性。博士論文、1996 年。http://webpages.uncc.edu/yonwang/papers/IPL97.pdf
- ^ Wang, Yongge (1999). 「2つのランダム性概念の分離」. Information Processing Letters . 69 (3): 115–118. CiteSeerX 10.1.1.46.199 . doi :10.1016/S0020-0190(98)00202-6.
- ^ Wolfgang Merkle、Kolmogorov Lovelandオートマトン、言語、プログラミングにおける確率性: 第 29 回国際コロキウム、ICALP 2002、Peter Widmayer 他著、ISBN 3-540-43864-5、391ページ