Mismatch Capacity under Stochastic Decoding

1. 問題設定 (Problem)

• 背景: 従来の情報理論の多くの符号化定理は、復号器がチャネルの遷移確率（チャネル法則）を完全に知っていることを前提としています。この場合、最尤復号（Maximum Likelihood Decoding）が誤り確率を最小化する最適復号器となります。
• ミスマッチ復号: しかし、実際のシステムではチャネル法則が未知であったり、計算コストが高すぎたりするため、最適ではない固定された復号メトリック（指標）$q_n$ を用いる「ミスマッチ復号」が一般的です。
• 既存の課題:
  • 離散メモリレスチャネル（DMC）において、最大メトリック復号器（式 1）を用いたミスマッチ容量 $C_M$ の単一文字表現（single-letter expression）は、Csiszár-Narayan 予想を含め、未解決または限定的なケースしか知られていません。
  • 既存の一般チャネルに対する容量公式（Verdú-Han 型など）は多文字表現（multi-letter）であり、具体的な解析が困難です。
• 本研究の焦点: 最大メトリック復号の代わりに、**確率的尤度復号（Stochastic Likelihood Decoder）**を採用した場合の誤り確率と容量を解析すること。この復号器は、受信信号 $y^n$ に対して、各メッセージ $m$ を確率 $P(\hat{m}=m|y^n) \propto q_n(x^n(m), y^n)$ に比例してランダムに選択します。

2. 手法 (Methodology)

本研究は、Verdú と Han が開発した**情報スペクトラム手法（Information-Spectrum Method）**を、ミスマッチな確率的復号器に適用・拡張しています。

• 確率的復号の定義:
  復号器は、メトリック $q_n(x^n, y^n)$ を用いて、メッセージ $m$ を以下の確率で出力します。
  $$P(\hat{m}=m|y^n) = \frac{q_n(x^n(m), y^n)}{\sum_{\bar{m}=1}^{M_n} q_n(x^n(\bar{m}), y^n)}$$
• ミスマッチ情報密度の定義:
  標準的な情報密度 $\imath(x^n, y^n)$ を一般化し、メトリック $q_n$ を用いたミスマッチ情報密度 $\imath_{q_n}(x^n, y^n)$ を以下のように定義します。
  $$\imath_{q_n}(x^n, y^n) \triangleq \log \frac{q_n(x^n, y^n)}{\sum_{\bar{x}^n} P_{X^n}(\bar{x}^n) q_n(\bar{x}^n, y^n)}$$
• 誤り確率の上下界導出:
  Feinstein 型の上界と Verdú-Han 型の下界を、一般のチャネルとメトリックに対して導出しました。これにより、誤り確率を「正規化されたミスマッチ情報密度の確率分布の尾部」として評価可能にしました。
• 一様可積分性の利用:
  正規化されたミスマッチ情報密度の列が一様可積分（uniformly integrable）である場合、確率極限（limit in probability）が期待値の極限に一致する性質を利用し、容量公式の上限評価を導きました。

3. 主要な貢献 (Key Contributions)

1. 誤り確率の Feinstein 型および Verdú-Han 型上下界の導出:
   一般のチャネルとメトリックに対して、確率的復号器の平均誤り確率 $P_e(C_n)$ に対する以下の上下界を示しました（$\gamma > 0$ は任意）。

   • 上界: $P_e(C_n) \le P\left[ \frac{1}{n}\imath_{q_n}(X^n, Y^n) \le R_n + \gamma \right] + e^{-n\gamma}$
   • 下界: $P_e(C_n) \ge P\left[ \frac{1}{n}\imath_{q_n}(X^n, Y^n) \le R_n - \gamma \right] - e^{-n\gamma}$
     これらは、決定論的な復号器に対する既存の結果を確率的復号に自然に拡張したものです。

2. 一般チャネルにおけるミスマッチ容量の一般公式:
   確率的復号器を用いたミスマッチ容量 $\hat{C}_q(W)$ について、入力分布列の supremum として以下の情報スペクトラム公式を導出しました。
   $$\hat{C}_q(W) = \sup_{P_X} \underline{I}_q(X; Y)$$
   ここで、$\underline{I}_q(X; Y)$ は正規化されたミスマッチ情報密度列の**確率下限極限（limit inferior in probability）**です。これは Verdú-Han の一般チャネル容量公式のミスマッチ版に相当します。

3. Csiszár-Narayan 予想の解決（DMC における tightness）:
   離散メモリレスチャネル（DMC）と積メトリック（product metrics）の条件下において、正規化されたミスマッチ情報密度列が一様可積分であることを示しました。これにより、上記の一般公式が期待値の極限として表現可能になり、以下の結果が得られました。
   $$\hat{C}_q(W) = \lim_{k \to \infty} \sup_{P_{X^k}} \frac{1}{k} E \left[ \log \frac{q_k(X^k, Y^k)}{E[q_k(\bar{X}^k, Y^k)|Y^k]} \right]$$
   この結果は、Csiszár-Narayan 予想が確率的復号器に対して真（tight）であることを証明したことを意味します。

4. 結果 (Results)

• 容量公式の等価性:
  確率的復号器におけるミスマッチ容量は、最適化された多文字 GMI（Generalized Mutual Information）や LM 率（LM rate）の極限と一致します。
  $$\hat{C}_q(W) = \lim_{k \to \infty} \hat{C}^{(k)}_{\text{GMI}} = \lim_{k \to \infty} \hat{C}^{(k)}_{\text{LM}}$$
• 最大メトリック復号との関係:
  最大メトリック復号（Deterministic Max-Metric）の容量は、確率的復号の容量以上であることが示されました（$C_{\text{mm}} \ge \hat{C}_q$）。これは、最大メトリック復号が確率的復号よりも「強い」復号器であることを示唆していますが、容量の観点では確率的復号も同様の性能限界に達します。
• 一様可積分性の重要性:
  DMC と有界メトリックの条件下では、一様可積分性が保証され、期待値による上限評価が達成可能となります。これにより、単一文字表現に依存しない多文字最適化（product-space improvement）が容量達成に必要であることが再確認されました。

5. 意義と重要性 (Significance)

• 理論的統一:
  本研究は、Verdú-Han の一般チャネル容量理論を、ミスマッチな確率的復号という文脈に拡張し、理論的な枠組みを完成させました。
• Csiszár-Narayan 予想の解決:
  長年未解決であった Csiszár-Narayan 予想（DMC におけるミスマッチ容量の多文字表現に関する予想）について、確率的復号器の文脈ではその予想が正しい（tight）ことを初めて証明しました。これは、最大メトリック復号における未解決問題に対する重要な進展です。
• 実用的な洞察:
  確率的復号器は、量子情報理論や誤り訂正符号の解析において、計算の簡便さ（derivation simplicity）と最大尤度復号と同等の性能（レートおよび誤り指数）を両立できる利点があります。本研究は、この利点を理論的に裏付け、ミスマッチ復号の容量限界を明確に定式化しました。
• 将来への示唆:
  得られた容量公式は、メモリチャネルや複雑なメトリックを用いた通信システムの設計指針を提供します。また、$\epsilon$-ミスマッチ容量や一般化された確率的復号（関数 $f(q_n)$ を適用する場合）への拡張も可能であることを示しています。

要約すると、この論文は確率的復号器を用いたミスマッチ通信の容量を、情報スペクトラム手法を用いて厳密に特徴付けし、離散メモリレスチャネルにおける Csiszár-Narayan 予想の正当性を証明した画期的な研究です。