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

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

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

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

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

* **コルモゴロフ複雑性**（シュノア1973、レビン1973）: コルモゴロフ複雑性は(文字もしくはビットの)有限列のアルゴリズム的圧縮可能性の下限と考えることができ、有限列*w*に対して自然数*K(w)*を対応させる。直感的には(ある固定のプログラミング言語で書かれた)コンピュータプログラムで入力なしで*w*を出力するものの最小の長さを測っている。ある自然数*c*と*w*に対して、*w*が***c''圧縮不可能'''であるとは、<math>K(w) \geq |w| -c </math>であることを言う。
:''無限列''S''がマルティンレーフランダムであることは、ある定数''c''があってすべての''S''の有限接頭辞が''c''圧縮不可能であることと同値。''

* '''構成可能なヌル被覆'''（マルティンレーフ1966）: これはマルティンレーフによる元の定義である。二進有限列''w''に対して、''C<sub>w</sub>''で''w***から作られるシリンダー**を表すことにする。これは''w''で始まる無限列の集合であり、[[カントール空間]]における基本[[開集合]]である。''w''から作られるシリンダーの**積測度**<math>\mu(C_w)</math>は<math>2^{-|w|}</math>で定義される。カントール空間上のすべての開集合は可算個の互いに素な基本開集合の列の和で書け、開集合の測度はその基本開集合の列の測度の和となる。''構成可能な開集合''は開集合で[[帰納的可算集合|帰納的可算]]な二進有限列の列で定めされる基本開集合の列の和で書けるものを言う。''構成可能なヌル被覆''または''構成可能な測度0の集合''とは構成可能な開集合の帰納的可算な列<math>U_i</math>ですべての''i''に対して<math>U_{i+1}\subseteq U_i</math>かつ<math>\mu U_i \leq 2^{-i}</math>となるものを言う。すべての構成可能なヌル被覆は測度0の[[G-delta set|<math>G_\delta</math>]]集合である<math>U_i</math>の積集合を決める。
:''列がマルティンレーフランダムであるとは、構成可能なヌル被覆で決められるどんな<math>G_\delta</math>集合にも含まれないことを言う。''

* **構成可能なマルチンゲール**（シュノア1971）: [[マルチンゲール]]は関数<math>d:\{0,1\}^*\to[0,\infty)</math>で、すべての有限文字列''w''に対して<math>d(w) = (d(w^\smallfrown 0) + d(w^\smallfrown 1))/2</math>となるものを言う。ここで<math>a^\smallfrown b</math>は文字列''a''と''b''の連結である。これは「公平な条件」とも呼ばれる。マルチンゲールを賭けの戦略と見ると、上記の条件は公平なオッズであることを要求していると思えるからである。マルチンゲール''d''が列''S''で**成功する**とは、<math>\limsup_{n\to\infty} d(S \upharpoonright n) = \infty</math>となることを言う。ここで<math>S \upharpoonright n</math>は''S''の最初の''n''ビットである。マルチンゲール''d''が**構成可能**（**弱計算可能**、**下方半計算可能**、**下計算可能**とも言われる）であるとは、ある計算可能な関数<math>\widehat{d}:\{0,1\}^*\times\N\to{\mathbb{Q}}</math>があってすべての二進有限列''w''に対して以下を満たすことを言う。
# すべての正の整数''t''に対して<math>\widehat{d}(w,t) \leq \widehat{d}(w,t+1) < d(w)</math>
# <math>\lim_{t\to\infty} \widehat{d}(w,t) = d(w)</math>
:''ある列がマルティンレーフランダムであることは、どんな構成可能なマルチンゲールでも成功しないことと同値。''

:(ここでのマルチンゲールの定義は[[確率論]]で使われるものと微妙に異なる。確率論で使われるマルチンゲールは似たような公平な条件で定義される。すなわち、事前観察の歴史が与えられたときに、ある観察後の期待値が観察前の期待値と同じであることを要求する。確率論では事前の観察の歴史が資産の歴史であるのに対し、ここでの歴史は具体的な0と1の文字列である。)

== 定義の解釈 ==

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

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

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

== マルティンレーフランダムの性質の例 ==
* [[チャイティンの定数|チャイティンの停止確率<math>\Omega</math>]]はランダムな列の族である。

* RAND<sup>c</sup>（RANDの[[差集合|補集合]]）はすべての無限列の集合の中の[[測度]]0の部分集合である。これは構成可能なヌル被覆は測度0の集合しか覆えず、構成可能なヌル被覆は[[可算集合|可算個]]しか存在せず、測度0の集合の可算和は測度0であることから導かれる。よってRANDは測度1の集合である。

* すべてのランダムな列は[[正規数]]である。

* RAND<sup>c</sup>を決める構成可能なヌル被覆が存在する。すなわちすべての構成可能なランダムネスのテスト（すなわち構成可能なヌル被覆）は、ある意味この''万能な''ランダムネスのテストに含まれる、なぜならこの一つのランダムネスのテストを通過するどんな列はどんなランダムネスのテストをも通過するであろうから。（マルティンレーフ1966年）

* ''万能な''構成可能なマルチンゲール**d**が存在する。すなわちどんな構成可能なマルチンゲール''d''に対しても、''d''がある列で成功すれば**d**もその列で成功するという意味で万能なマルチンゲールである。よって**d**はRAND<sup>c</sup>のどの列でも成功する（が、**d*'は構成可能なので、RANDのどの列でも成功しない）。（シュノア1971）

* RANDはカントール空間の<math>\Sigma^0_2</math>集合である。ここで<math>\Sigma^0_2</math>とは[[算術的階層]]の２番目である。なぜなら列*S*がRANDに入るかどうかは、万能で構成可能なヌル被覆に含まれる*S*を含まない開集合が存在するかどうかと同値であり、これは<math>\Sigma^0_2</math>の式で定義可能であるからである。

* <math>\Delta^0_2</math>（停止問題をオラクルとして計算可能）なランダムな列が存在する。（シュノア1971）チャイティンの[[チャイティンの定数|<math>\Omega</math>]]はそのような列の例である。

* ランダムな列は[[帰納的集合]]でも、[[帰納的可算集合]]でも、帰納的可算集合の補集合でもない。これらはそれぞれ[[算術的階層]]で<math>\Delta_1^0</math>、<math>\Sigma_1^0</math>、<math>\Pi_1^0</math>に対応するから、<math>\Delta_2^0</math>がランダムな列が存在する算術的階層で一番低い層ということになる。

* すべての列はあるランダムな列に[[チューリング還元]]可能である。（クセラ1985/1989、ガックス1986）よって任意の高い[[チューリング次数]]にランダムな列は存在する。

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

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

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

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

## 関連項目
*アルゴリズム情報理論
*K自明集合

## 脚注

## 参考文献
*

*

*

*

*

*

*

*

*

*

*

*