On the Ziv-Merhav theorem beyond Markovianity

この論文は、Ziv と Merhav が多値マルコフ測度の対に対する普遍的な交差エントロピー推定について得た結果を、g-測度や統計力学における平衡測度など、より広範な非マルコフ的な decoupled 測度のクラスへと一般化したものである。

要約

この論文は、**「2 つの異なる情報源（データの流れ）から、どれくらい『違い』があるかを測る新しいものさし」**について書かれたものです。

元々、この「ものさし」は非常に限られた種類のデータ（マルコフ連鎖と呼ばれる、単純な確率モデル）に対してしか使えないとされていましたが、この論文では、もっと複雑で多様なデータ（物理現象や言語など）に対しても、このものさしが使えることを証明しました。

以下に、専門用語を排し、身近な例え話を使って解説します。

---

1. 物語の舞台：2 つの巨大な図書館

想像してください。2 つの巨大な図書館があるとします。

• 図書館 P（青い本）: あるルールに従って本が並んでいる。
• 図書館 Q（赤い本）: 別のルールに従って並んでいる。

私たちが知りたいのは、**「赤い本（Q）が、青い本（P）のルールにどれだけ従っていないか（＝どれだけ『意外』か）」という「違いの度合い」です。これを情報理論では「クロスエントロピー」と呼びますが、ここでは「驚きの度合い」**と想像してください。

2. 従来の「ものさし」の限界：ジブとメルハブのゲーム

1993 年、ジブとメルハブという研究者が、この「驚きの度合い」を測る面白いゲーム（アルゴリズム）を考え出しました。

【ゲームのルール】

1. 青い本（P）のページを 1 枚ずつめくっていきます。
2. 赤い本（Q）の最初の文字が、青い本のどこかにあるか探します。
3. 見つかったら、その文字だけでなく、その後に続く文字も「青い本に同じ並びがあるか」探して、**「青い本で見つかる最大の長さ」**を記録します。
4. 見つからなくなったら、次の文字からまた探します。
5. これを赤い本全体で繰り返します。

【結果の読み方】

• もし赤い本が青い本と全く同じルールなら、**「とても長い」**文字列が見つかります（分割回数が少ない）。
• もし赤い本が青い本と全く違うルールなら、**「短い」**文字列しか見つかりません（分割回数が非常に多い）。

この「分割回数」を計算することで、2 つのルールの違い（エントロピー）を推測できるのです。

しかし、問題がありました。
このゲームは、**「次の文字が、直前の 1 つの文字だけで決まる」という単純なルール（マルコフ性）を持つ図書館に対しては完璧に機能しましたが、「過去の長い履歴が未来に影響を与える」**ような複雑な図書館（非マルコフ的）では、理論的に正しいかどうか証明されていませんでした。

3. この論文の功績：複雑な世界へ広げる

この論文の著者たちは、**「このゲームは、もっと複雑な図書館でも使える！」**と証明しました。

彼らが使ったのは、**「デカップリング（分離）」**という考え方です。

• イメージ: 複雑なシステム（例えば、大気の流れや人間の脳）は、一見すると全てが絡み合っているように見えます。しかし、**「時間が経てば、過去の出来事の影響は徐々に薄れていく」**という性質を持っています。
• 論文のアプローチ: 「過去の影響が十分遠ざかれば、システムは『独立』した状態に近い」とみなせるような、ある程度の規則性（ID, FE, KB という条件）さえ満たしていれば、ジブとメルハブのゲームは正しく機能すると証明しました。

4. 具体的な例え：天気予報と音楽

この理論が適用される対象は、単なるランダムなサイコロ転がし（マルコフ）よりもずっと広いです。

• 気象学: 明日の天気は、今日の天気だけでなく、数日前の気圧配置や、季節のサイクルにも影響されます。これは単純な「昨日→今日」のルールでは説明できません。しかし、この論文の条件を満たせば、過去のデータから未来の「驚き」を正しく推測できます。
• 統計力学（物理）: 原子や分子の動きは、互いに複雑に相互作用しています。しかし、この論文は「相互作用の範囲が小さければ（小さな空間の相互作用）」、この「驚きの度合い」を測る方法が有効であることを示しています。
• g-メジャー（数学的モデル）: 言語や音楽のように、文脈によって次の言葉や音が決まるような複雑なパターンも対象になります。

5. なぜこれが重要なのか？

この研究は、**「データ圧縮」や「パターン認識」**の基礎理論を強化するものです。

• 実用的な意味: 医療データ、言語処理、金融市場の分析など、現実世界のデータはほとんどが「単純なマルコフ過程」ではありません。この論文は、**「複雑で入り組んだ現実のデータに対しても、このシンプルで強力なアルゴリズムが使える」**という安心感を与えます。
• 追悼: この論文は、アルゴリズムの生みの親であるジブ氏（2023 年没）への献呈でもあります。彼のアイデアが、彼が想定していた範囲を超えて、より広い世界で生き続けることを示したのです。

まとめ

この論文は、**「複雑怪奇な現実世界（非マルコフ的システム）であっても、過去の影響が徐々に消えていく性質さえあれば、2 つの情報の『違い』を測るシンプルなゲームは正しく機能する」**と宣言したものです。

まるで、**「どんなに複雑な迷路でも、出口までの距離を測るための単純なコンパスが、実は広大な森全体で使えることを証明した」**ような発見です。これにより、言語学、物理学、医学など、さまざまな分野でのデータ分析の信頼性が一段と高まることが期待されます。

技術概要

ゼビ・メルハブ定理のマルコフ性を超えた一般化に関する技術的要約

本論文は、Ziv と Merhav が 1993 年に提案した「ユニバーサルなクロスエントロピー（相対エントロピー）推定量」の収束性を、マルコフ連鎖という狭いクラスから、より広範な「非マルコフ的」な確率過程のクラスへと一般化するものです。

以下に、問題設定、手法、主要な貢献、結果、および意義について詳細にまとめます。

1. 問題設定と背景

背景

Ziv と Merhav は、Lempel-Ziv 圧縮アルゴリズムに基づき、2 つの文字列 $x$ と $y$ から推定される「経験的相互情報量（相対エントロピー）」の推定量 $\hat{Q}_N(y, x)$ を提案しました。具体的には、$y$ の文字列を $x$ の部分文字列を用いて逐次的に解析（パース）し、解析された単語の数 $c_N(y|x)$ を用いて、
$$\hat{Q}_N(y, x) := \frac{c_N(y|x) \ln N}{N}$$
を計算します。元の論文 [ZM93] では、この推定量が $N \to \infty$ で、$x$ と $y$ を生成する源が既約な多段階マルコフ連鎖である場合に、特定のクロスエントロピー $h_c(Q|P)$ に収束することが示されました。

課題

しかし、この結果がカバーするマルコフ性のクラスは非常に限定的であり、実際の応用（言語学、医学、物理学など）で広く使われている推定量の汎用性とは対照的に、数学的な理論的裏付けが不足していました。特に、マルコフ性を持たない複雑な確率過程（統計力学の平衡状態や $g$-測度など）に対して、この推定量がどのように振る舞うかは未解決でした。

2. 手法と仮定

著者らは、マルコフ性を仮定せずとも推定量の収束が成り立つための、確率測度 $P$ と $Q$ に対する抽象的な条件を定義し、その下で証明を行いました。

主要な仮定

論文では、以下の 3 つの条件（ID, FE, KB）を確率測度 $P$ に、ID と FE を $Q$ に課しています。

1. ID (Immediately Decoupled: 即時脱結合性)
   • 測度の支持集合上の確率において、長い文字列の確率が、その部分文字列の確率の積から「脱結合誤差」の範囲内で近似できることを示す条件です。具体的には、非減少数列 $(k_n)$（$k_n = o(n)$）を用いて、条件付き確率と周辺確率の比が $e^{\pm k_n}$ の範囲に収まることを要求します。これは、マルコフ性における「過去の情報が遠い未来に及ぼす影響が指数関数的に減衰する」という性質を一般化したものです。
2. FE (Fast Enough decay: 十分な速さでの減衰)
   • cylinder 集合（特定の文字列で始まる集合）の確率が、長さ $n$ に対して指数関数的に減衰すること（$P[a] \le e^{\gamma_+ n}$）を要求します。これは、エントロピーが正であることを保証し、パースされた単語の長さが制御可能であることを意味します。
3. KB (Kontoyiannis' Bound: コントイアニスの待ち時間 bound)
   • 待ち時間 $W_\ell$（ある文字列が初めて現れるまでの時間）の分布に関する確率不等式です。これは、待ち時間が指数分布に従うような挙動を示すことを保証します。ID と適切な支持集合の性質（Specification）があれば、この条件は導かれることが示されています。

証明の戦略

証明は、Ziv-Merhav の元の議論を拡張し、以下のステップで構成されています。

1. 補助的なパースの導入:
   • 元の ZM パース（$x$ の中で最も長い一致部分文字列を探す）の代わりに、確率の閾値（$N^{-1+\epsilon}$ や $N^{-1-\epsilon}$）に基づいて文字列を分割する「補助的なパース」を構成します。
2. 上界の証明:
   • 補助パースの単語が $x$ 中に存在する確率が高いことを示し、$c_N(y|x)$ が過大評価されないことを証明します。これには、Borel-Cantelli 補題と、クロスエントロピー版の Shannon-McMillan-Breiman 定理が用いられます。
3. 下界の証明（確率収束から概収束へ）:
   • Ziv-Merhav の元の議論は確率収束（convergence in probability）まででしたが、著者らはこれを**概収束（almost sure convergence）**に強化しました。
   • そのために、文字列をブロック単位に分割し、「良いブロック（単語が重複しない）」と「悪いブロック」を区別します。
   • 条件 ID と FE を用いて、「悪いブロック」の数が無視できるほど少ないことを示し、確率的な誤差を制御することで、概収束を導出しました。
4. 支持集合の包含関係:
   • $Q$ の支持集合が $P$ の支持集合に含まれない場合（$Q$ が $P$ で確率 0 となる文字列を含む場合）、推定量は発散し、クロスエントロピーも無限大になることを示し、定理の一貫性を確認しました。

3. 主要な貢献と結果

定理 3.1 (主要定理)

確率測度 $P$ が条件 ID, FE, KB を満たし、エルゴード測度 $Q$ が条件 ID, FE を満たすとき、独立なサンプル $x \sim P$ と $y \sim Q$ に対して、以下の収束が**ほぼ至る所（almost everywhere）**で成立します。
$$\lim_{N \to \infty} \hat{Q}_N(y, x) = h_c(Q|P)$$
ここで、$h_c(Q|P)$ は $Q$ に対する $P$ の特定のクロスエントロピーです。

適用範囲の拡大

この結果は、以下の広範なクラスに適用可能です（セクション 4 で詳述）：

• 正則な $g$-測度 (Regular g-measures): 統計力学や力学系で現れる、マルコフ性を一般化した測度。特に、トポロジカルに混合する有限型シフト上の正則 $g$-測度は、本定理の条件を満たすことが示されました。
• 統計力学の平衡状態: 「相互作用の小さな空間（small space of interactions）」から導かれる平衡状態（Gibbs 状態）。絶対和可能な相互作用を持つ系において、ポテンシャルが Ruelle の意味で 0 と物理的に同値でない限り、条件 FE が満たされることが示されました。
• マルコフ測度: 既約で正のエントロピーを持つマルコフ連鎖は、これらの条件を満たすことが確認され、既存の結果を包含しています。

隠れマルコフモデルへの言及

隠れマルコフモデル（HMM）については、条件 FE は満たされるが、条件 ID の下界（Ad）が満たされない場合があることが示されました。これは、HMM に対する ZM 推定量の一般的有效性が未解決の問題であることを示唆しています。

4. 意義と結論

学術的意義

1. 理論的枠組みの拡張: 情報理論における重要な推定量の収束性を、マルコフ性という制約から解放し、統計力学や力学系で自然に現れるより複雑な確率過程（$g$-測度、Gibbs 状態）へと一般化しました。
2. 証明手法の洗練: 確率収束から概収束への強化を達成し、非マルコフ的な過程における待ち時間とパース長の関係を厳密に制御する新しい技術的アプローチ（「良い/悪いブロック」の議論など）を提供しました。
3. 分野横断的な視点: 統計力学の「脱結合（decoupling）」の概念を、情報理論の古典的な問題（Ziv-Merhav 推定量）に適用することで、両分野の深い結びつきを浮き彫りにしました。

実用的意義

この結果は、マルコフ性を仮定できない複雑なデータ（自然言語、生体信号、物理系の時系列データなど）に対して、Lempel-Ziv 型アルゴリズムに基づく相対エントロピー推定が理論的に正当化されることを示しています。これにより、実用的な応用分野におけるアルゴリズムの信頼性が高まります。

結論

本論文は、Ziv-Merhav 定理をマルコフ性の枠を超えて一般化し、その収束性を広範な非マルコフ的測度に対して証明した画期的な成果です。特に、統計力学の平衡状態や正則 $g$-測度といった、現代の確率論・力学系において中心的な対象に対して、ユニバーサルなエントロピー推定が可能であることを示した点が最も重要な貢献です。