二種類のランダム性：πが圧縮できてノイズができない理由

ここに矛盾に見えるパズルがある：それぞれ100万桁の2つのファイルは、すべての統計的ランダム性テストに合格し、同一のヒストグラムを持つ。しかし、一方は小さなプログラム（πの桁）に圧縮でき、もう一方（純粋なノイズ）はできない。その答えは、圧縮可能性の考え方における根本的な分裂を明らかにする。

統計的圧縮は壁にぶつかる

標準的なツールはシャノンエントロピーであり、これはシンボルがその頻度を考慮して平均的にどれほど驚くべきかを測定する。10桁の一様分布では、エントロピーは1桁あたり約3.32ビットで最大となる。両方のファイルは一様であるため、エントロピーは両方とも圧縮不可能と判断する。これはノイズファイルについては正しいが、πについては間違っている——なぜならエントロピーは頻度だけを見て、構造を見ないからだ。順序を捨ててしまう。

エントロピーは単一の系列ではなく、ソースの特性である。系列の桁数からエントロピーを計算するとき、桁がその分布からの独立した抽出であると仮定している。その仮定は、複数の位置にまたがるパターン——まさにπが持つパターン——を捨て去る。

コルモゴロフ複雑性はプログラムを見る

代替案はコルモゴロフ複雑性である：その文字列を出力する最短プログラムの長さ。10億個のゼロは複雑性が小さい；真にランダムな文字列は複雑性がほぼその長さに等しい。πの複雑性は小さい——短いプログラムで生成できる。ノイズファイルの複雑性はその長さに等しい。なぜなら、より短い記述が存在しないからだ。

これでパズルは解決する：2つのファイルは統計的に同一だが、アルゴリズム的に異なる。一方には短い生成規則があり、他方にはない。落とし穴は、コルモゴロフ複雑性が計算不可能であることだ——最短プログラムを見つけたと確信することは決してできない。短いプログラムを見つけたときに圧縮可能性を確認できるが、それを否定することは決してできない。

したがって、二種類のランダム性とは：統計的ランダム性（高エントロピー、頻度バイアスなし）とアルゴリズム的ランダム性（高コルモゴロフ複雑性、短い生成プログラムなし）である。これらはノイズについては一致するが、πについては一致しない。その不一致こそがすべての話である。