Loading article…
直感的に言えば、アルゴリズム的にランダムなシーケンス（またはランダムシーケンス）とは、プレフィックスフリーまたはプレフィックスフリーの汎用チューリングマシン上で動作するあらゆるアルゴリズムに対してランダムに見えるバイナリ数字のシーケンスのことである。この概念は、任意の有限アルファベット（例えば10進数）上のシーケンスにも同様に適用される。ランダムシーケンスは、アルゴリズム情報理論における重要な研究対象である。
1933年にアンドレイ・コルモゴロフによって導入された測度論的確率論では、ランダムな数列というものは存在しない。例えば、公平なコインを無限回投げることを考えてみよう。どんな特定の数列でも、またはは、ちょうどゼロになる確率が等しい。測度論的確率の言語を用いて、ある数列が別の数列よりも「よりランダム」であると述べる方法はない。しかし、直感的には、ランダムに見えるアルゴリズム的ランダム性理論は、この直感を形式化するものである。
アルゴリズムの種類は、実行時間に特定の制限があるアルゴリズムから、オラクルマシンに質問するアルゴリズムまで多岐にわたるため、ランダム性の概念も様々です。最も一般的なのは、Martin-Löf ランダム性( K ランダム性または1 ランダム性) ですが、より強いランダム性や弱いランダム性も存在します。「アルゴリズム的にランダム」という用語が、特に説明なしに特定の単一の (有限または無限) シーケンスを指す場合、通常は「圧縮不可能」という意味で解釈されます。シーケンスが無限で、アルゴリズム的にランダム (つまり、K 圧縮不可能) という接頭辞が付いている場合は、「Martin-Löf–Chaitin ランダム」という意味になります。
マーティン＝レーフのランダム性は、その誕生以来、圧縮、ランダム性テスト、ギャンブルといった観点から、元の定義とは外見上ほとんど似ていないものの、ランダムな数列が持つべき性質に関する私たちの直感的な概念を満たす、多くの同等な特徴付けを許容することが示されてきた。すなわち、ランダムな数列は圧縮不可能であり、ランダム性に関する統計的テストに合格し、賭けで利益を上げることは困難であるべきだという概念である。マーティン＝レーフのランダム性のこうした複数の定義の存在と、異なる計算モデルの下でのこれらの定義の安定性は、マーティン＝レーフのランダム性が自然なものであり、マーティン＝レーフの特定のモデルの偶然ではないことの証拠となる。
アルゴリズム的ランダム性と確率的ランダム性を区別することが重要です。計算可能な（したがって決定論的な）プロセスに対して定義されるアルゴリズム的ランダム性とは異なり、確率的ランダム性は通常、独立同分布の等確率確率過程によって生成される（またはその結果である）ことが事前にわかっている数列の特性であると言われます。
無限に続く二進数列は単位区間内の実数と同一視できるため、ランダムな二進数列は（アルゴリズム的に）ランダムな実数と呼ばれることが多い。さらに、無限に続く二進数列は自然数の集合の特性関数に対応するため、それらの列は自然数の集合とみなすこともできる。
マーティン・レーフのランダム（二値）シーケンスのクラスは、RANDまたはMLRと表記される。
リヒャルト・フォン・ミーゼスは、ランダム性テストの概念を形式化し、ランダムな数列をすべてのランダム性テストに合格するものと定義した。彼は「集合体」（kollektiv）を無限の二進数文字列と定義した。定義すると
部分列を選択するには、まず二項関数を選択します。任意のバイナリ文字列が与えられた場合出力は0または1のいずれかです。出力が1の場合は、部分列を選択する場合は、そのまま処理を続行します。この定義では、許容される規則の中には、一部のシーケンスに対して永久に処理を中断し、無限部分列を選択できないものもあります。ここでは、無限部分列を選択する規則のみを考慮します。
言い換えれば、無限バイナリ文字列はそれぞれコイン投げゲームであり、許容ルールとはギャンブラーが賭けるタイミングを決定する方法である。集合体は、長期的に見てどのギャンブラーも他のギャンブラーより有利になる方法がないコイン投げゲームである。つまり、このゲームに適したギャンブルシステムは存在しない。
この定義は、二進数アルファベットから可算数アルファベットへと一般化される。
通常、許容される規則はチューリングマシンで計算可能な規則として定義され、我々はこれにより、ミーゼス・ウォルド・チャーチランダムシーケンスが得られます。これは制約ではありません。なぜなら、あるシーケンスが与えられた場合、我々は他の任意の計算可能なものを用いてランダムなシーケンスを構築することができる[ 1 ]（ここで「チャーチ」とは、1940年の論文でチューリング計算可能な規則の使用を提案したアロンゾ・チャーチのことである。[ 2 ]）
定理（アブラハム・ウォルド、1936年、1937年）[ 3 ]許容される規則が可算個しかない場合、ほとんどすべてのシーケンスは集合である。
証明の概略：測度論的確率論を用いる。
許容ルールを 1 つ固定します。ベルヌーイ空間からランダムなシーケンスをサンプリングします。確率 1 (マルチンゲールを使用) で、許容ルールによって選択された部分シーケンスは依然として次のようになります。。次に、可算個のルールをすべて追加します。確率1で、各ルールによって選択された各部分列は依然として。
しかし、この定義は十分強力ではないことが判明した。直感的には、ランダムシーケンスの長期平均は、ランダムウォークが原点を無限回横切るように。しかし、ジャン・ヴィルは、可算個のルールであっても、ある二進数列が存在し、1 の割合ですが、すべての有限接頭辞に対して、1 の割合は以下より小さくなります。[ 4 ]
ヴィル構成は、ミーゼス・ウォルド・チャーチのランダム性の感覚では不十分であることを示唆している。なぜなら、一部のランダム列はランダム性の法則の一部を満たさないからである。例えば、ヴィル構成は反復対数の法則の1つを満たさない。素朴に言えば、この問題を解決するには、数列がすべての可能なランダム性の法則を満たすように要求すればよい。ここで「ランダム性の法則」とは、すべての数列が確率1で満たす性質のことである。しかし、各無限数列についてランダム性の法則があり、結果として、ランダムな数列は存在しないという結論に至る。
（マルティン＝レーフ、1966年）[ 6 ]は、チューリング計算可能なランダム性の法則のみを許容することで「マルティン＝レーフのランダム性」を定義した。言い換えれば、数列は、すべてのチューリング計算可能なランダム性テストに合格する場合に限りランダムである。
マルティン・レーフのランダム性の定義がランダム性の直感的な概念を「正しく」捉えているというテーゼは、マルティン・レーフ＝チャイティン・テーゼと呼ばれており、チャーチ＝チューリング・テーゼといくらか似ている。[ 7 ]
マルティン＝レーフ＝チャイティンのテーゼ。「マルティン＝レーフのランダム性」という数学的概念は、無限数列が「ランダム」であるという直感的な概念を捉えている。
チャーチ＝チューリングのテーゼ。「チューリングマシンで計算可能」という数学的概念は、関数が「計算可能」であるという直感的な概念を捉えている。チューリング計算可能性に多くの同値な定義があるように、マーティン＝レーフのランダム性にも多くの同値な定義がある。次節を参照のこと。
マルティン＝レーフによるランダム列の元の定義は、構成的ヌルカバーの観点からのものでした。彼は、そのようなカバーに含まれない列をランダムと定義しました。グレゴリー・チャイティン、レオニード・レヴィン、クラウス・ペーター・シュノールは、アルゴリズム的複雑性の観点から特徴付けを証明しました。すなわち、列の初期セグメントの圧縮率に一様な上限が存在する場合、その列はランダムであるということです。シュノールは、マルチンゲールの観点から、これと同等の3つ目の定義を与えました。リーとヴィタニの著書『コルモゴロフ複雑性と応用入門』は、これらのアイデアへの標準的な入門書です。
コルモゴロフの複雑性特性は、ランダムなシーケンスは圧縮不可能であるという直感を伝えている。つまり、プレフィックスよりもはるかに短いプログラムでは、プレフィックスを生成することはできない。
ヌルカバーの特徴付けは、ランダムな実数が「珍しい」性質を持たないべきであるという直観を伝えます。各測度 0 の集合は珍しい性質と考えることができます。各 1 点集合の測度は 0 であるため、数列がどの測度 0 集合にも属さないということはあり得ません。マルティン・レーフの考えは、定義を効果的に記述可能な測度 0 集合に限定することでした。効果的なヌルカバーの定義は、効果的に記述可能な測度 0 集合の可算集合を決定し、数列がこれらの特定の測度 0 集合のいずれにも属さない場合にランダムであると定義します。可算集合の測度 0 集合の和集合の測度は 0 であるため、この定義は直ちにランダム数列の測度 1 集合が存在するという定理につながります。バイナリ数列のカントール空間を実数の区間 [0,1] と同一視すると、カントール空間の測度はルベーグ測度と一致することに注意してください。
有効尺度0集合は、無限バイナリ文字列が与えられたときに、その文字列が統計的に有意なレベルでランダムに見えるかどうかを判定できるチューリングマシンとして解釈できる。この集合は、縮小集合の共通部分である。、そして各セットはは、任意の無限バイナリ文字列が与えられた場合、列挙可能な接頭辞のシーケンスによって指定され、そうすれば、チューリングマシンは有限時間内に文字列が範囲内に入ることを判断できる。したがって、有意水準で文字列がランダムであるという仮説を棄却することができる。「チューリングマシンがすべての有意水準で仮説を棄却できる場合、その文字列はランダムではない。ランダムな文字列とは、チューリングマシンで計算可能なランダム性のテストごとに、ある有意水準で永久に棄却されない文字列のことである。[ 8 ]
マルチンゲール特性は、ランダムなシーケンスに賭けて利益を上げる有効な手順は存在しないという直感を伝えます。マルチンゲールdは賭け戦略です。dは有限文字列wを読み込み、次のビットに賭けます。次のビットが 0 になることに賭け金の一部を賭け、残りの賭け金を次のビットが 1 になることに賭けます。dは実際に発生したビットに賭けた金額を 2 倍にし、残りを失います。d ( w )は文字列wを見た後の金額です。文字列wを見た後に賭けた金額はd ( w )、d ( w 0 )、d ( w 1 )の値から計算できるため、金額を計算することは賭け金を計算することと同じです。マルチンゲール特性は、コンピュータで実装可能な賭け戦略 (必ずしも計算可能ではない構成的戦略の弱い意味であっても) は、ランダムなシーケンスに賭けて利益を上げることはできないと述べています。
普遍的な構成的マルチンゲールdが存在する。このマルチンゲールが普遍的であるのは、任意の構成的マルチンゲールdが与えられたとき、d があるシーケンスで成功すれば、d はそのシーケンスでも成功するという意味である。したがって、d はRAND cのすべてのシーケンスで成功する（ただし、 dは構成的であるため、RAND のどのシーケンスでも成功しない）。(Schnorr 1971)
RAND cには構成的ヌルカバーが存在する。これは、ランダム性に関するすべての有効なテスト（つまり、構成的ヌルカバー）が、ある意味でこの普遍的なランダム性テストに包含されることを意味する。なぜなら、この単一のランダム性テストに合格するシーケンスは、すべてのランダム性テストに合格するからである。（Martin-Löf 1966）直感的に言えば、この普遍的なランダム性テストは、「シーケンスに、この普遍チューリングマシン上でますますうまく圧縮できる、ますます長い接頭辞がある場合、それはランダムではない」と言っている。-- 次のセクションを参照。
構築スケッチ:有効なヌルカバーを列挙します列挙は有効でもある（修正されたユニバーサルチューリングマシンによって列挙される）。これで、対角化によるユニバーサル有効ヌルカバーが得られる。。
ある数列がアルゴリズム的ランダム性テストに合格しない場合、その数列はアルゴリズム的に圧縮可能である。逆に、アルゴリズム的に圧縮可能な数列は、アルゴリズム的ランダム性テストに合格しない。
構成の概略:シーケンスがランダム性テストに失敗したと仮定すると、テストに失敗したすべてのシーケンスを辞書式に列挙し、そのようなすべてのシーケンスのリスト内のシーケンスの位置をコード化することで圧縮できます。これは「列挙ソースエンコーディング」と呼ばれます。[ 9 ]
逆に、シーケンスが圧縮可能であれば、鳩の巣原理により、そのようなシーケンスはごくわずかしか存在しないため、 「この万能チューリングマシンによって圧縮される」という新しいランダム性判定法を定義できます。ちなみに、これはランダム性判定のための万能性判定法です。
例えば、ベルヌーイ分布から独立同分布でサンプリングされたバイナリシーケンスを考えてみましょう。多数のサンプルを抽出した後、サンプルの約1。このシーケンスは「長さのすべてのバイナリシーケンスを生成する」とコーディングできます。、 そしてそれらのうち、辞書順の 番目のシーケンス。
スターリング近似により、どこはバイナリエントロピー関数です。したがって、この記述におけるビット数は最初の用語は、数字を接頭辞でコード化するためのものです。そして2番目の項は、数字を接頭辞で符号化するためのものです。（エリアス・オメガ符号化を使用。）3番目の項は、残りの記述を接頭辞符号化するためのものです。大きいので、この説明はちょうどビットなので圧縮可能で、圧縮率は特に、圧縮比がちょうど1（非圧縮）になるのは、（例 14.2.8 [ 10 ]）
ルーレットテーブルで公平なオッズを提供するカジノを考えてみましょう。ルーレットテーブルは乱数列を生成します。この乱数列がアルゴリズム的にランダムである場合、勝つための下半計算可能戦略は存在せず、ひいては勝つための計算可能戦略も存在しないことになります。つまり、どのようなギャンブルアルゴリズムにおいても、長期的な対数ペイオフはゼロ（正でも負でもない）となります。逆に、この乱数列がアルゴリズム的にランダムでない場合、勝つための下半計算可能戦略が存在します。
マーティン・レーフのランダム列の等価な定義はそれぞれ、何らかのチューリングマシンで計算可能なものに基づいているため、チューリングオラクルマシンで計算可能なものは何かという疑問が自然に生じる。固定されたオラクルAに対して、ランダムであるだけでなく、実際にAに対する計算可能性の等価な定義を満たす列B (例えば、オラクルAに対して構成的なマルチンゲールはB上では成功しない) は、 Aに対してランダムであると言われる。2 つの列は、それ自体はランダムであっても、非常に類似した情報を含んでいる場合があり、したがって、どちらも他方に対してランダムではない。ある列から別の列へのチューリング還元がある場合、2 番目の列は最初の列に対してランダムではない。これは、計算可能な列自体がランダムではないのと同様である。特に、これは、チャイティンの Ωが停止問題に対してランダムではないことを意味する。
相対的なランダム性に関する重要な結果の一つに、ファン・ランバルゲンの定理がある。この定理によれば、CがAとBから、 Aの最初のビット、 Bの最初のビット、 Aの 2 番目のビット、 Bの 2 番目のビット、といったように交互に並べられた数列である場合、 Cがアルゴリズム的にランダムであるのは、 Aがアルゴリズム的にランダムであり、かつBがAに対してアルゴリズム的にランダムである場合に限る。これと密接に関連する結果として、 AとBが両方ともランダムである場合、 A がBに対してランダムであるのは、 BがAに対してランダムである場合に限る。
相対ランダム性は、ある固定オラクルAに対するランダム性である Martin-Löf ランダム性よりも強い最初の概念を与えます。任意のオラクルに対して、これは少なくとも同等の強さであり、ほとんどのオラクルに対しては厳密に強いです。なぜなら、オラクルAに対してランダムではない Martin-Löf ランダムシーケンスが存在するからです。よく検討される重要なオラクルは、停止問題です。、n番目のジャンプオラクル、これらの神託は、自然に生じる特定の質問に答えることができる。神託に対してランダムなシーケンスn-ランダムと呼ばれる。したがって、数列が1-ランダムであるのは、それがMartin-Löfランダムである場合に限る。すべてのnに対してn-ランダムである数列は、算術ランダムと呼ばれる。n-ランダム数列は、より複雑な性質を考察する際に現れることがある。例えば、n-ランダム数列は可算個しかない。集合なので、これらは非ランダムであるべきだと考えるかもしれない。しかし、停止確率Ωはそして 1-ランダム。2-ランダム性が達成された後にのみ、ランダムな集合が。
さらに、Martin-Löf ランダム性よりも弱いランダム性の概念がいくつかあります。これらには、弱い 1-ランダム性、Schnorr ランダム性、計算可能なランダム性、部分計算可能なランダム性などがあります。Yongge Wang は[ 11 ] で、Schnorr ランダム性は計算可能なランダム性とは異なることを示しました。また、Kolmogorov–Loveland ランダム性は Martin-Löf ランダム性よりも強くないことが知られていますが、実際に弱いかどうかはわかっていません。
ランダム性のスペクトルの反対側には、K-自明集合の概念があります 。これらの集合は、すべての初期セグメントが対数的に圧縮可能である（つまり、各初期セグメント w) に対して、それらは計算できません。
