ランダム数列の概念は、確率論と統計学において不可欠です。この概念は一般的に、ランダム変数の列の概念に基づいており、多くの統計的議論は「 X 1、...、X nを独立なランダム変数とする...」という言葉で始まります。しかし、1951 年にDH Lehmer が述べたように、「ランダム数列は曖昧な概念であり、各項は初心者には予測不可能であり、その桁は統計学者が伝統的に行う一定数のテストに合格する」のです。[ 1 ]
公理的確率論は、意図的にランダムな数列の定義を避けている。[ 2 ]伝統的な確率論は、特定の数列がランダムであるかどうかを述べず、一般的にランダム性の定義を前提として、ランダム変数と確率的数列の性質について議論を進める。ブルバキ学派は、「ランダムな数列を考えてみよう」という表現を言葉の濫用とみなした。[ 3 ]
初期の歴史
エミール・ボレルは、1909年にランダム性を正式に扱った最初の数学者の1人でした。[ 4 ] 1919年、リヒャルト・フォン・ミーゼスは、大数の法則に触発されたアルゴリズム的ランダム性の最初の定義を与えましたが、ランダムシーケンスではなく集合的という用語を使用しました。ギャンブルシステムの不可能性の概念を使用して、フォン・ミーゼスは、ゼロとイチの無限シーケンスが、周波数安定性特性、つまりゼロの頻度が1/2に収束し、そこから「適切な」選択方法で選択できるすべての部分シーケンスも偏りがないという特性を持つことで偏りがない場合に、ランダムであると定義しました。[ 5 ]
フォン・ミーゼスが課した部分列選択基準は重要である。なぜなら、0101010101... は偏りがないものの、奇数番目の位置を選択すると、ランダムではない 000000... が得られるからである。フォン・ミーゼスは部分列の適切な選択規則の定義を完全に形式化することはなかったが、1940 年にアロンゾ・チャーチはそれを、シーケンスの最初の N 個の要素を読み取った後、要素番号N + 1 を選択するかどうかを決定する任意の再帰関数として定義した。チャーチは計算可能関数の分野の先駆者であり、彼が行った定義は、計算可能性に関するチャーチ・チューリングのテーゼに基づいていた。[ 6 ]この定義はしばしばミーゼス・チャーチのランダム性と呼ばれる。
現代的なアプローチ
20 世紀には、ランダム シーケンスを定義するさまざまな技術的アプローチが開発され、現在では 3 つの明確なパラダイムが識別できます。1960 年代半ば、AN コルモゴロフとDW ラブランドは、より寛容な選択ルールを独立して提案しました。[ 7 ] [ 8 ]彼らの見解では、チャーチの再帰関数の定義は、要素を順番に読み込むため制限が厳しすぎました。代わりに、シーケンスの任意のN個の要素 を読み込んだ後、まだ読み込まれていない別の要素を選択するかどうかを決定する、部分的に計算可能なプロセスに基づくルールを提案しました。この定義は、コルモゴロフ-ラブランド確率性と呼ばれることがよくあります。しかし、この方法は、ランダム性の一般的な概念に適合しないコルモゴロフ-ラブランド確率シーケンスが存在することをアレクサンダー シェンが示したように、弱すぎると考えられました。
1966年、ペル・マルティン＝レーフは、現在ではアルゴリズム的ランダム性の最も満足のいく概念と一般的に考えられている新しい概念を導入した。彼の当初の定義は測度論に基づいていたが、後にコルモゴロフ複雑性の観点から表現できることが示された。コルモゴロフのランダム文字列の定義は、万能チューリングマシンによってそれ自身よりも短い記述が存在しない場合にランダムであるというものである。[ 9 ]
ランダムシーケンスを扱うための3つの基本的なパラダイムが出現しました。[ 10 ]
- 周波数／測度論的アプローチ。このアプローチは、リチャード・フォン・ミーゼスとアロンゾ・チャーチの研究から始まった。1960年代にペル・マルティン＝レーフは、このような周波数に基づく確率的性質を符号化する集合は、測度ゼロ集合の特殊な種類であり、すべての有効な測度ゼロ集合を考慮することで、より一般的で滑らかな定義が得られることに気づいた。
- 複雑性／圧縮性アプローチ。このパラダイムは、レオニード・レヴィンとグレゴリー・チャイティンの貢献とともに、A.N.コルモゴロフによって提唱されました。有限シーケンスの場合、コルモゴロフは、長さnのバイナリ文字列のランダム性を、長さnで正規化されたエントロピー（またはコルモゴロフ複雑性）として定義します。言い換えれば、文字列のコルモゴロフ複雑性がnに近いほど、非常にランダムであり、複雑性がnよりはるかに小さいほど、ランダム性は低くなります。ランダム性の双対概念は圧縮性です。シーケンスがランダムであればあるほど、圧縮性は低くなり、その逆もまた然りです。
- 予測可能性アプローチ。このパラダイムはClaus P. Schnorrによるもので、従来の確率論で使用されるマルチンゲールとは少し異なる構成的マルチンゲールの定義を使用しています。 [ 11 ] Schnorr は、選択的賭け戦略の存在が偏った部分列の選択ルールの存在を意味することを示しました。再帰的マルチンゲールがシーケンスで構成的に成功する代わりに、シーケンスで成功することだけを要求すると、再帰的ランダム性の概念が得られます。Yongge Wang は、再帰的ランダム性の概念が Schnorr のランダム性の概念とは異なることを示しました[ 12 ] [ 13 ] 。
ほとんどの場合、3つのパラダイム（多くの場合、等価性）を関連付ける定理が証明されている。[ 14 ]
注記
- ↑「ランダムという言葉の意味」フィリップ・J・デイビス著『数学と常識』（2006年、 ISBN） 1-56881-270-1180～182ページ
- ↑離散数学における必然的なランダム性、 József Beck 著、2009 ISBN 0-8218-4756-244ページ
- ↑アルゴリズム: 主なアイデアと応用Vladimir Andreevich Uspenskiĭ、Alekseĭ、Lʹvich Semenov 著、1993 Springer ISBN 0-7923-2210-X166ページ
- ↑ E. Borel、 Les probabilites denombrables et leurs application arithmetique Rend。円マット。パレルモ 27 (1909) 247–271
- ↑ローラン・ビアンヴニュ「コルモゴロフ・ラブランド確率論」STACS 2007：第24回コンピュータサイエンス理論シンポジウム（ウォルフガング・トーマス編）ISBN 3-540-70917-7260ページ
- ↑ Church, Alonzo (1940). "On the Concept of Random Sequence" . Bull. Amer. Math. Soc . 46 (2): 130– 136. doi : 10.1090/S0002-9904-1940-07154-X .
- ↑ AN コルモゴロフ、「情報の定量的定義への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-344ページ
- ↑ Schnorr, CP (1971). "ランダムシーケンスの定義への統一的アプローチ". Mathematical Systems Theory . 5 (3): 246– 258. doi : 10.1007/bf01694181 . S2CID 8931514 .
- ↑ Yongge Wang: Randomness and Complexity. 博士論文、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-5391ページ
外部リンク
- 「ランダムな数列」、数学百科事典、EMS Press、2001年 [1994年]
- 周波数安定性に関するビデオ。なぜ人間はランダムに「推測」できないのか
- テリー・リッターによるランダム性テスト
