アルゴリズム情報理論

ウィキペディア

索引トップ用語の索引ランキングカテゴリー

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/06/07 16:40 UTC 版)

正確な定義

詳細は「コルモゴロフ複雑性」を参照

バイナリ列がランダムであるとは、その文字列のコルモゴロフ複雑性が最低でもその文字列の長さである場合である。単純な数え上げでは任意長の文字列の一部はランダムであるとされ、その他の大部分もランダムに非常に近いとされる。コルモゴロフ複雑性は万能チューリング機械（大まかに言えば、「説明」が与えられる固定の「記述言語」）の固定された選択に依存するので、ランダムな文字列の集まりは固定の万能機械の選択に依存する。それにも関わらず、ランダムな文字列の集まりは全体として固定機械がどうであっても似たような性質を示すので、万能機械を最初に指定せずにランダムな文字列のグループの特性を論じることができ、実際そうすることが多い。

詳細は「アルゴリズム的ランダムな無限列」を参照

無限バイナリ列がランダムであるとは、ある定数 c があり、全ての並びの最初のセグメント（長さ n）のコルモゴロフ複雑性が最低でも n-c となる場合である。重要な点は、ここでの複雑性が接頭部のない複雑性だという点である。通常の複雑性を使うと、ランダムな列というものは存在しない。しかし、この定義では（標準的測度論、すなわち "fair coin" またはルベーグ測度の無限バイナリ列空間での観点での）ほとんど全ての並びがランダムとされる。また、2つの異なる万能機械があるとき、コルモゴロフ複雑性の差異は定数的なものに限られるため、無作為無限列の集まりは（有限文字列とは対照的に）万能機械の選択には依存しない。このような無作為性の定義をペール・マルティン＝レーフに因んでマルティン＝レーフ無作為性と呼び、他の無作為性の定義と区別する。

バイナリ（ $\{0,1\}$ をアルファベットとする文字列）以外にも同様の定義が可能である。