アルゴリズム的ランダムな無限列

アルゴリズム的ランダムな無限列、あるいは単にランダムな列は、直感的にはどんなアルゴリズムにとってもランダムに見える二進無限列のことを言う。この定義は有限文字の列にも上手く適用される。ランダムな列はアルゴリズム情報理論において中心となる対象である。実行時間に特定の上限のあるアルゴリズムや神託への伺いを許したアルゴリズムなど、いくつかの異なった種類のアルゴリズムが考えられ、それに応じて異なったランダムネスの概念が存在する。もっとも良く知られているのはマルティンレーフランダムネスであるが、もっと強いランダムネスや弱いランダムネスも存在する。単に「ランダム」と言った場合には、マルティンレーフランダムであることを意味することが多い。二進無限列は単位区間の実数と同一視できるので、ランダムな2進無限列はランダムな実数と呼ばれることもある。さらに、二進無限列は自然数の集合の特性関数とも同一視されるので、自然数の集合と見ることもある。二進のマルティンレーフランダムの無限列のクラスはRANDやMLRで表される。

1. 歴史
-----

適切なランダムな列の定義を最初に与えたのはペール・マルティン＝レーフであり、1966年のことであった。リヒャルト・フォン・ミーゼスなどの先行研究者もランダムネスのためにテストの概念を定式化して、ランダムネスのテストをすべて通過する列をランダムな列と定義しようとしたが、正確なランダムネスのテストの概念を与えることはできなかった。マルティンレーフによる重要な貢献は計算理論を使ってランダムネスのテストの概念を定式化したことにあった。この定義は、確率論のランダムネスの考え方とは対照的である。つまり、確率論では標本空間のどの特定の元もランダムとは言えないからである。

マルティンレーフランダムネスはその後、多くの同値な特徴付けが可能であることが示された。データ圧縮、ランダムネスのテスト、ギャンブルなどどれも元の定義には似ていないように思われるが、同時にどれもランダムな列が持つべき直感的な特徴を満たしている。ランダムな列は圧縮不可能であるだろうし、確率的なテストを通過するであろうし、賭をして儲けるのは難しいであろう。複数の定義が存在し異なる計算のモデルの異なる定義が一致することから、マルティンレーフランダムネスは数学において基本的な性質であって、マルティンレーフの特別なモデルではないと言える。 マルティンレーフランダムネスがランダムネスの直感的概念を「正しく」捕らえているというテーゼは、マルティンレーフ＝チャイティンのテーゼと呼ばれている。これは「チャーチ＝チューリングのテーゼ」と似たようなものである。

2. 3つの同値な定義
-----------

マルティンレーフによるランダムな列の元の定義は構成可能なヌルの被覆によるものである。すなわちランダムな列とは、そのようなどんな被覆にも含まれないことを言う。レオニード・レビンやクラウス・ピーター・シュノアがコルモゴロフ複雑性による次のような特徴付けを与えた。ある列がランダムであるとはその最初の有限部分の圧縮可能性に一様な下限があることを言う。シュノアはマルチンゲールを使って3つ目の同値な定義を与えた。LiとVitanyiの[1]はこれらの良い入門書であろう。

コルモゴロフ複雑性: コルモゴロフ複雑性は有限列のアルゴリズム的圧縮可能性の下限と考えることができ、有限列//w//に対して自然数//K//を対応させる。直感的にはコンピュータプログラムで入力なしで//w//を出力するものの最小の長さを測っている。ある自然数//c//と//w//に対して、//w//が//圧縮不可能であるとは、であることを言う。//無限列//S//がマルティンレーフランダムであることは、ある定数//c//があってすべての//S//の有限接頭辞が//c//圧縮不可能であることと同値。//
構成可能なヌル被覆: これはマルティンレーフによる元の定義である。二進有限列//w//に対して、//Cw//で//w//から作られるシリンダーを表すことにする。これは//w//で始まる無限列の集合であり、カントール空間における基本開集合である。//w//から作られるシリンダーの積測度はで定義される。カントール空間上のすべての開集合は可算個の互いに素な基本開集合の列の和で書け、開集合の測度はその基本開集合の列の測度の和となる。//構成可能な開集合//は開集合で帰納的可算な二進有限列の列で定めされる基本開集合の列の和で書けるものを言う。//構成可能なヌル被覆//または//構成可能な測度0の集合//とは構成可能な開集合の帰納的可算な列ですべての//i//に対してかつとなるものを言う。すべての構成可能なヌル被覆は測度0の集合であるの積集合を決める。//列がマルティンレーフランダムであるとは、構成可能なヌル被覆で決められるどんな集合にも含まれないことを言う。//
構成可能なマルチンゲール: マルチンゲールは関数で、すべての有限文字列//w//に対してとなるものを言う。ここでは文字列//a//と//b//の連結である。これは「公平な条件」とも呼ばれる。マルチンゲールを賭けの戦略と見ると、上記の条件は公平なオッズであることを要求していると思えるからである。マルチンゲール//d//が列//S//で成功するとは、となることを言う。ここでは//S//の最初の//n//ビットである。マルチンゲール//d//が構成可能であるとは、ある計算可能な関数があってすべての二進有限列//w//に対して以下を満たすことを言う。
すべての正の整数//t//に対して
//ある列がマルティンレーフランダムであることは、どんな構成可能なマルチンゲールでも成功しないことと同値。//

3. 定義の解釈
--------

コルモゴロフ複雑性による特徴付けはランダムな列は圧縮不可能であるという直感を与える。すなわちどんな接頭辞もそれよりもはるかに短いプログラムからは作られない。

ヌル被覆による特徴付けはランダムな実数は「普通でない」性質は持たないという直感を与える。測度0の集合は普通はない性質と思うことができる。列がどの測度0の集合にも入らないことは不可能である、なぜなら1点集合は測度0であるからである。マルティンレーフの発想は測度0の集合を構成的に記述可能なものに制限することであった。すなわち構成可能なヌル被覆の定義は可算個の構成可能で記述可能な測度0の集合を与え、ランダムな列をそのような特別な測度0の集合に含まれないと定義したのである。測度0の集合の可算和は測度0であるから、この定義からランダムな列の測度1の集合があることが分かる。ここで二進列のカントール空間を[0,1]の実数区間と同一視すれば、カントール空間の測度はルベーグ測度に一致することに注意して欲しい。

マルチンゲールによる特徴付けはどんな構成可能なものでもランダムな列に対して儲けることができないという直感を与える。マルチンゲール//d//は賭けの戦略である。マルチンゲール//d//は有限文字列//w//を読んで次のビットにある金額を賭ける。持っている金額のいくらかを次のビットが0であることに賭け、残りを1であることに賭ける。//d//は実際に起こったビットに賭けた金額の2倍を受け取り、残りは失う。//d//は//w//見た後の所持金である。文字列//w//を見た後の賭けは//d//、//d//、//d//の値から計算できるので、金額を計算することは賭けを計算することと同じである。マルチンゲールによる特徴付けはどんなコンピューターによって実装されるどんな賭け戦略もランダムな列に対しては儲けることができないということを意味している。

4. マルティンレーフランダムの性質の例
--------------------

チャイティンの停止確率はランダムな列の族である。
RANDcはすべての無限列の集合の中の測度0の部分集合である。これは構成可能なヌル被覆は測度0の集合しか覆えず、構成可能なヌル被覆は可算個しか存在せず、測度0の集合の可算和は測度0であることから導かれる。よってRANDは測度1の集合である。
すべてのランダムな列は正規数である。
RANDcを決める構成可能なヌル被覆が存在する。すなわちすべての構成可能なランダムネスのテストは、ある意味この//万能な//ランダムネスのテストに含まれる、なぜならこの一つのランダムネスのテストを通過するどんな列はどんなランダムネスのテストをも通過するであろうから。
//万能な//構成可能なマルチンゲールdが存在する。すなわちどんな構成可能なマルチンゲール//d//に対しても、//d//がある列で成功すればdもその列で成功するという意味で万能なマルチンゲールである。よってdはRANDcのどの列でも成功する。
RANDはカントール空間の集合である。ここでとは算術的階層の２番目である。なぜなら列//S//がRANDに入るかどうかは、万能で構成可能なヌル被覆に含まれる//S//を含まない開集合が存在するかどうかと同値であり、これはの式で定義可能であるからである。
なランダムな列が存在する。チャイティンのはそのような列の例である。
ランダムな列は帰納的集合でも、帰納的可算集合でも、帰納的可算集合の補集合でもない。これらはそれぞれ算術的階層で、、に対応するから、がランダムな列が存在する算術的階層で一番低い層ということになる。
すべての列はあるランダムな列にチューリング還元可能である。よって任意の高いチューリング次数にランダムな列は存在する。

5. 相対的なランダムネス
-------------

マルティンレーフランダムの列のそれぞれの定義はチューリングマシンでの計算可能性を元にしているので、神託機械での計算可能性でも考えることができる。ある固定した神託//A//に対して、列//B//が、ランダムであるだけでなく//A//から見た計算可能性による同じ定義を満たすならば、//B//は//A//に対してランダムであると言う。二つの列がそれぞれランダムでも似た情報を持っているために互いにランダムではないということは起こりうる。ある列からもう一方へのチューリング還元が存在すれば、後者の列は前者の列から見てランダムではない。それはちょうど計算可能な列がランダムではないようなものである。特にチャイティンの停止確率は停止性問題の集合から見てランダムではない。

相対的なランダムネスに関して重要な結果の一つが、van Lambalgenの定理である。これは列//C//が列//A//と列//B//から//A//の最初のビット、//B//の最初のビット、//A//の２番目のビットと交互に取って作られる列だとすると、//C//がアルゴリズム的ランダムであるということと//A//がランダムで//B//が//A//から見てランダムであるということが同値であるという定理である。似た結論として//A//と//B//がそれぞれランダムとすると、//A//が//B//から見てランダムであるということと//B//が//A//から見てランダムであることが同値になる。

6. マルティンレーフランダムより強いランダムネス
-------------------------

相対的なランダムネスはマルティンレーフランダムよりも強い最初のランダムネスの概念を与えてくれる、つまりある固定した神託//A//からみたランダムネスである。どんな神託でも少なくとも同じくらい強いランダムであるし、多くの神託にとっては真に強いランダムネスである、なぜなら//A//から見てランダムではないマルティンレーフランダムがあるだろうから。重要な神託でよく考察されるのが停止問題、、//n//回ジャンプの神託、である。というのも、これらの神託が自然に起きる特定の問題に答えることができるからである。から見てランダムな列は//n//ランダムと呼ばれる。よって1ランダムとマルティンレーフランダムは同じである。すべての//n//に対して//n//ランダムである列は算術的ランダムと呼ばれる。//n//ランダムな列はもっと複雑な性質を考えるときによく出てくる。例えば集合は可算個しかないので、ランダムとすべきではないと考えるかもしれない。しかしチャイティンの停止確率はであり1ランダムである。2ランダムネス以上ならばランダムな集合がとはなり得ない。

7. マルティンレーフランダムより弱いランダムネス
-------------------------

さらにマルティンレーフランダムより弱いランダムネスも存在する。例えば、弱1ランダムネス、シュノアランダムネス、計算可能ランダムネス、部分計算可能ランダムネスなどである。またコルモゴロフ・ラブランドランダムネスはマルティンレーフランダムネスより強くないランダムネスとして知られているが、真に弱いかどうかは知られていない。

8. 関連項目
-------

アルゴリズム情報理論
K自明集合

9. 脚注
-----

10. 参考文献
--------