3つの同値な定義
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/04/21 00:17 UTC 版)
「アルゴリズム的ランダムな無限列」の記事における「3つの同値な定義」の解説
マルティンレーフによるランダムな列の元の定義は構成可能なヌルの被覆によるものである。すなわちランダムな列とは、そのようなどんな被覆にも含まれないことを言う。レオニード・レビンやクラウス・ピーター・シュノアがコルモゴロフ複雑性による次のような特徴付けを与えた。ある列がランダムであるとはその最初の有限部分の圧縮可能性に一様な下限があることを言う。シュノアはマルチンゲール（賭の戦略の一つ）を使って3つ目の同値な定義を与えた。LiとVitanyiのAn Introduction to Kolmogorov Complexity and Its Applicationsはこれらの良い入門書であろう。 コルモゴロフ複雑性（シュノア1973、レビン1973）: コルモゴロフ複雑性は(文字もしくはビットの)有限列のアルゴリズム的圧縮可能性の下限と考えることができ、有限列wに対して自然数K(w)を対応させる。直感的には(ある固定のプログラミング言語で書かれた)コンピュータプログラムで入力なしでwを出力するものの最小の長さを測っている。ある自然数cとwに対して、wがc圧縮不可能であるとは、であることを言う。 無限列Sがマルティンレーフランダムであることは、ある定数cがあってすべてのSの有限接頭辞がc圧縮不可能であることと同値。 構成可能なヌル被覆（マルティンレーフ1966）: これはマルティンレーフによる元の定義である。二進有限列wに対して、Cwでwから作られるシリンダーを表すことにする。これはwで始まる無限列の集合であり、カントール空間における基本開集合である。wから作られるシリンダーの積測度はで定義される。カントール空間上のすべての開集合は可算個の互いに素な基本開集合の列の和で書け、開集合の測度はその基本開集合の列の測度の和となる。構成可能な開集合は開集合で帰納的可算な二進有限列の列で定めされる基本開集合の列の和で書けるものを言う。構成可能なヌル被覆または構成可能な測度0の集合とは構成可能な開集合の帰納的可算な列ですべてのiに対してかつとなるものを言う。すべての構成可能なヌル被覆は測度0の集合であるの積集合を決める。 列がマルティンレーフランダムであるとは、構成可能なヌル被覆で決められるどんな集合にも含まれないことを言う。 構成可能なマルチンゲール（シュノア1971）: マルチンゲールは関数で、すべての有限文字列wに対してとなるものを言う。ここでは文字列aとbの連結である。これは「公平な条件」とも呼ばれる。マルチンゲールを賭けの戦略と見ると、上記の条件は公平なオッズであることを要求していると思えるからである。マルチンゲールdが列Sで成功するとは、となることを言う。ここではSの最初のnビットである。マルチンゲールdが構成可能（弱計算可能、下方半計算可能、下計算可能とも言われる）であるとは、ある計算可能な関数があってすべての二進有限列wに対して以下を満たすことを言う。 すべての正の整数tに対して ある列がマルティンレーフランダムであることは、どんな構成可能なマルチンゲールでも成功しないことと同値。 (ここでのマルチンゲールの定義は確率論で使われるものと微妙に異なる。確率論で使われるマルチンゲールは似たような公平な条件で定義される。すなわち、事前観察の歴史が与えられたときに、ある観察後の期待値が観察前の期待値と同じであることを要求する。確率論では事前の観察の歴史が資産の歴史であるのに対し、ここでの歴史は具体的な0と1の文字列である。)
※この「3つの同値な定義」の解説は、「アルゴリズム的ランダムな無限列」の解説の一部です。
「3つの同値な定義」を含む「アルゴリズム的ランダムな無限列」の記事については、「アルゴリズム的ランダムな無限列」の概要を参照ください。
- 3つの同値な定義のページへのリンク
