なぜ円周率は圧縮できるのに、ランダムなデータはダメなのか：統計的圧縮とアルゴリズム的圧縮の対立

1. はじめに：パズルの設定と問いかけ

先日の投稿で未完に終わらせてしまいましたが、この回ではその続きを取り上げます。円周率（$\pi$）という「置かれたパズル」を、なぜ統計的にランダムなデータとは異なる扱いを受けるのかについて探ります。

• ファイル A: 純粋なノイズ（例：10 万回サイコロを振った結果）。
• ファイル B: 円周率 $\pi$ の最初の 100 万桁。

統計的視点での矛盾

どちらも以下の点で「同一」と見なされます。

• 出現頻度: 「0」から「9」までがすべて約 10% ずつ存在する（平坦なヒストグラム）。
• ランダム性テスト: どの統計的基準に対しても合格し、圧縮不可能に見える純粋なランダム性を有する。

しかし、実用上の処理能力に決定的な差があります。

特性	$\pi$ (円周率)	ランダムノイズ
再構築可能か？	できる	できない
理由	「$\pi$ の最初の $N$ 桁を出力する」という短小なプログラムが存在するため。	それ自体が最短記述であり、より短い記述が存在しないため。

ここで問われる核心的疑問

「統計学的には同一なのに、なぜ片方は圧縮可能で、もう片方は不可能なのか？」

この質問は単純な答えを持っていません。この事実にこそ興味があり、本記事はその理由を解明します。「圧縮可能」という概念には実は 2 つの異なる意味があります。

---

2. 2 種類の圧縮：統計的 vs プロセス的

ロスレス圧縮の定義

• 情報量を減らさず、ビット単位で完全な再構築を行う「損失なし」の圧縮のみを扱います。

本記事は主に以下の 2 つのパターンを引き分けます。

① 統計的な圧縮（頻度に基づく）

• 原理: 記号の出現頻度に差がある場合、多い記号に短い符号化、少ない記号に長い符号化を割り当てることで平均長を短くする。
• 手法例: ZIP 形式、ハフマン符号化。
• 対象: 「ノイズ」など、特定の統計的特徴（頻度分布）を持つデータ群。

② プロセス的な圧縮（生成規則に基づく）

• 原理: データ自体が「単純なルール（短いプログラム）」によって生成されている場合、そのルールを記述することで巨大なデータを要約できる。
• 対象: $\pi$ や「0 の無限反復」など、分布はランダムに見えても背後に決定論的な規則があるデータ。

結論：$\pi$ の不思議

$\pi$ は、統計的には「圧縮できない（最大エントロピー）」はずなのに、プロセス的には「極小のプログラムで記述可能」です。この矛盾こそが、情報の本質を暴く鍵となります。

---

3. 統計的圧縮の限界：エントロピー

エントロピーとは何か

シャノンのエントロピー（$H$）は、データ源に含まれる「情報量」や「予期せぬ驚きの度合い」を測定する尺度です。

• 予測可能（常に同じシンボルが出る）= 驚きがない = エントロピー 0 ビット。
• 完全にランダム（すべての可能性が等確率）= 最大の驚き = エントロピー最大化。

「予算制約」という捉え方

シンボルを送信する際、私たちは「驚き」を支払うビット数が必要です。

• 確率 $p$ で現れるシンボルに割り当てる最適なコードワードの長さは $\log_2(1/p)$ ビットです。
• これは直感的に理解できるルール（希少で高価、多発で格安）に基づいています。

エントロピーの最大値と盲点

すべての桁が等しく出現する場合（一様分布）、エントロピーは最大になります。

• 10 進数の場合：約 3.32 ビット/桁。
• $\pi$ とランダムノイズはいずれもこの最大エントロピーを達成しています。

つまり、統計的にはどちらも「圧縮の限界（床）」に到達しているのです。

エントロピーが見落としているもの

• 順序: シンボルの出現順には全く興味を持ちません。
• 規則: 「0, 1, 2, 3...」という単純な規則があっても認識しません。
• 指紋: $\pi$ が持つ数学的な構造や生成プロセスの痕跡を無視します。

$\pi$ は「規則で生成されたデータ」ですが、エントロピーはそれを「ランダムなノイズ」と見なします。ここにはエントロピーという定規では計れない別の次元（圧縮可能性）が存在しています。

---

4. プロセス的な圧縮：コロモゴロフ複雑性 (Kolmogorov Complexity)

定義

「文字列 $x$ の複雑性 $K(x)$ は、その文字列を出力する『最短のプログラム』の長さである。」

• ランダムな文字列: 自身とほぼ同じ長さのプログラムが必要（$K(x) \approx x$）。圧縮不可能。
• 規則的な文字列（例：

  "0"

  を 10 億回出力）:

  print("0") * 10_000_000,000

  のような短いプログラムで済む。圧縮可能。
• $\pi$: 「円周率を計算するアルゴリズム」が極めて短いため、複雑性は非常に小さい。

シャノンとコロモゴロフの違い

特性	シャノンのエントロピー (Shannon Entropy)	コロモゴロフ複雑性 ($K(x)$)
対象	集合（多数のデータ）や分布	特定の個別の文字列
視点	統計的・頻度ベース	構造的・プロセスベース
$\pi$ への評価	「ランダムな圧縮不可能」	「単純な構造を持つ」

両方の定義が正解ですが、異なる問いに答えいています。ここで初めて「統計的なランダム性」と「アルゴリズム的簡潔さ」のギャップが見えてきます。

---

5. なぜ「ほとんどすべてのデータ」は圧縮できないのか？（计数の論理）

組み合わせの法則による証明

長さ $n$ の二進文字列の総数は $2^n$ です。 より短い記述（長さが $m < n$）の総数は $1 + 2 + 4 + \dots + 2^{n-1} = 2^n - 1$ です。

• 結論: 「長さ $n$ の文字列」と「長さ $< n$ の記述」では、数え上げの結果、記述するほうが一つだけ足りません。
• したがって、少なくとも 1 つの文字列は、それ自身よりも短い記述にはなり得ない。

圧縮可能なのは「例外」ばかり

もし 10 ビットも節約できるような深い圧縮を望むとすれば、対象となる文字列は総数の約 $2^{-10}$ （千分の一程度）しかありません。

• 深い圧縮 = 極めて稀な現象。
• 「ほとんどの」データ = それ自体が最短記述（圧縮不可能）。

名前をつけるコスト：「選択」とは何か

もし「リストのインデックス」だけで指定できれば圧縮できるか？ 答えはネーミングのコストで否定されます。 $N$ 個の中から特定する場合は、約 $\log_2 N$ ビットの情報を追加して指示する必要があり、元々持っていたデータ量と同程度のコストがかかります。

$\pi$ が特別である理由

$\pi$ は「生成器」という意味合いを持ちます。プログラムを実行すればただ 1 つの出力が得られます。 「$N$ 個の中から選ぶ」必要がないため、選択のコスト（インデックス分）がかからないのです。これが $\pi$ が圧縮可能な真の理由です。

---

6. 罠：コロモゴロフ複雑性は計算不可能

ここが最も重要な転換点です。 定義はシンプルですが、「ある文字列の $K(x)$ の値を実際に計算するアルゴリズム」は存在しません。

なぜ計算できないのか？（上限 vs 下限）

1. 上限 ($\le$) は見つけやすい: 長さ 50 で出力可能なプログラムが見つかれば、「複雑性は 50 以下」と証明できます。
2. 下限 ($\ge$) は永遠に見つからない: 「これより短いプログラムはない（これが最短だ）」と証明するには、すべての短いプログラムの実行結果を確認し、無限ループしているものも含めて否定する必要があります。これは不可能です。

ハートリーのパラドックスによる不可算性の証明

もし複雑性を計算するアルゴリズムが存在すると仮定しましょう。

• そのプログラムで「複雑性が $10^9$ を超える最小の文字列を出力せよ」という手順を考えると矛盾が生じます。
  • 「その手順を記述したプログラム」は短い（数千ビット）。
  • しかし、そのプログラムから出力される文字列は「極めて長い複雑性（十億ビット以上）」を持つはず。
  • **「短いプログラムから超複雑な結果が出る」**という矛盾が生じます。

したがって、複雑性は計算可能ではない（uncomputable）のです。 これは単に難しい問題ではなく、理論的に解けないという結論です。私たちは「これが最短だ」と証明することはできず、「もっと短いものが隠れていないかもしれない」という不確かさを抱えたままです。

---

7. シンクロニシティ：コストと選択の価格

エントロピー論（統計的）と複雑性論（個体別）が最終的に一致するのは、**「情報とは区別（Selection）のコスト」**であることに起因します。

$$ \boxed{\text{選択のコスト} = \log_2(\text{区別しなければならない候補の総数})} $$

• 統計的圧縮: 集団全体の分布（エントロピー）を平均コストとして見積もる。
• 構造的好奇心: 特定の物体が、なぜ他のものから際立っているのか（選択されやすいか）を見る。

$\pi$ のケース:

• 候補集の中で「円周率」という生成元があるため、特定の値を指し示す必要がありません（区別のコスト 0 あるいは極小）。
• つまり、$\pi$ は「生成ルールによって選ばれた唯一無二のもの」です。

ランダムノイズのケース:

• 「ランダムなのでどれでも良く」ですが、実際に特定の桁列を指し示すには、その桁列自体の情報（全ビット）が必要です。
• 区別する候補数が膨大 ($2^n$) なので、選択コストも同様に高くなります。

---

8. おわりに：未解決の地平へ

この投稿は「なぜ $\pi$ は圧縮可能で、ランダムデータは不可能なのか」という問いに対して、以下の結論を導き出しました。

1. 2 つの圧縮タイプ: 統計的頻度（エントロピー）と生成プロセス（複雑性）の違い。
2. $\pi$ の本質: エントロピーではランダムに見えるが、プロセス的には「最短プログラム」が存在する。
3. 計算の可能性: ショートのプログラムを探す上限は見つかるが、「これが最短だ」と証明する下限は理論上存在しない。

今後さらに深まる問い（次のステップ）

• 機械学習との関係: ロスレス圧縮から「ノイズを捨てて構造だけ抽出する」処理へと拡張すると、それはまさに**機械学習（オッカムの剃刀：最良の説明は最短のプログラム）**になります。
• 証明の限界: 「この文字列は複雑だ」と証明することは、数学的に不可能（ゲーデル的パラドックス）であることを示唆しています。
• 熱力学的視点: 宇宙が「稀有な圧縮可能な状態」から圧倒的に多数の「圧縮不可能な状態」へと漂流しているプロセス（二項対立法則）との関連が見えてきます。

最終的な結論: $\pi$ が圧縮可能であることは、単なる数学的な事実ではありません。それは、「短い記述で世界を記述できる余地」が存在することを示しています。その一方で、ランダムなノイズが圧縮できないことも、「全ての情報は選択のコストを支払う必要がある」という真理を物語っています。