New Capacity Upper Bounds For Binary Deletion Channel

技術要約：バイナリ削除チャネルにおける新たな容量上界

問題の定義
本論文は、入力ビットが確率 $d$ で独立に削除され、受信側は削除位置を知ることなく残った部分列を観測するという通信モデルである、バイナリ削除チャネル（BDC）を取り扱う。チャネル容量 $C(d)$ は明確に定義されているものの、閉形式（closed-form）の式は存在しない。既存の文献では、上限および下限による近似に依存しており、注目すべき既存の境界には、$d < 0.5$ における $1-h(d)$ や、$d \ge 0.65$ における $0.4143(1-d)$ などがある。容量を正確に計算する上での主要な課題は、入力シーケンスから出力部分列へのマッピングにおける組合せ論的な曖昧さにある。

手法
著者らは、チャネル入力として一次マルコフ過程を利用した、2つの新しい閉形式の $C(d)$ の上界を提案している。その手法は、次の2つの核心的な直感に基づいている。(1) BDCを近似する補助チャネルは有用な境界を与え得る、(2) 入力の相関はデコーダによる削除されたビットの推定を助ける。

1. 補助チャネル・アプローチ (定理1):
   著者らは、入力長が $n$ で固定されているが、出力長は変動する固定長入力BDC (FI-BDC) を導入している。彼らは特に、2ビットFI-BDC（$n=2$ のFI-BDC）に焦点を当てている。

   • 彼らは、この2ビットチャネルの遷移行列を構築した（表II）。
   • 対称な一次マルコフ入力分布（または、記号の反復確率 $p_0$ でパラメータ化された分布）の下で、この補助チャネルの相互情報量 $I(X; Y)$ を導出した。
   • 最適化問題を解くことで、一意の閉形式の最大化値 $p_0^*(d)$ を求めた。
   • 最終的な境界は、独立した2ビット・サブブロックにわたる相互情報量の劣加法性を利用し、2ビット容量を $1/2$ 倍することで導出される。

2. 直接相互情報量近似 (定理2):
   第2の境界は、送信されたビットと受信されたビットの間の相互情報を直接近似することによって導出される。

   • このアプローチでは、最後の未削除の前方要素の位置を示すための補助的なサイド情報変数を利用している。
   • 得られる式は、マルコフ相関パラメータ $\gamma$ によってパラメータ化されている。
   • 定理1とは異なり、この境界は $\gamma$ に関する最大化の結果ではなく、$\gamma$ は設計パラメータまたはソースによって決定される値として扱われる。

主な貢献と結果

• 定理1 (閉形式の境界1):
  論文は以下の閉形式の上界を導出している：
  $$C \le \frac{1}{2}(1 - d)^2 \log_2 \left(1 + 2^{-\frac{2d}{1-d}}\right) + \frac{1 - d^2}{2}$$

  • 最適化の検証: 著者らは、2ビット補助チャネルの目的関数が厳密に凹であり、一意の内部最大値を持つことを厳密に検証した。コンピュータ代数システムと数値チェックを用いて、最適な入力分布 $p_0^*(d)$ の閉形式の解を確認した。
  • 単調性: 最適な相関パラメータ $\gamma^*(d)$ は、$d \to 0$ に伴い $0.5$（独立なビット）から、$d \to 1$に伴い$1$（完全な相関）へと、$d$ に対して厳密に増加することが示されている。これは、削除確率が高くなるほど、デコーディングを助けるために、入力における時間的相関を強める必要があるという直感を反映している。
  • 複雑性: この境界の評価には $O(1)$ の算術演算が必要であり、指数関数的に巨大な状態空間に対する反復最適化を必要とする従来の境界（例：Fertonani–Duman）とは対照的である。

• 定理2 (閉形式の境界2):
  論文は以下の第2の境界を提示している：
  $$C_{BDC} \le (1 - d) \left(1 - H\left(\frac{d(1 - \gamma)}{1 + d(1 - 2\gamma)}\right)\right)$$

  • $\gamma$ の性質: 著者らは、この境界が $\gamma$ に関して単調であり、内部最大値を持たないことを明らかにしている。したがって、$\gamma$ は最適化される変数ではなく、ソースによって決定されるか、設計のために選択されるパラメータである。
  • 端点の挙動: この境界は、$d=0$（$\gamma=0.5$ のとき）において $C \le 1$ に、$d=1$（$\gamma=1$ のとき）において $C=0$ に正しく減少する。論文では、これらの端点を橋渡しするために線形補間 $\gamma = 0.5 + d/2$ を提案しているが、これは解析的な最適値ではなく、設計上の選択であることに注意している。

• 先行研究との比較:
  論文は、定理1から導かれる境界が、固定長入力固定長出力 (FIFO-BDC) 補助チャネルから導かれる境界（補題1）と同等以上にタイトであることを述べている。第2の境界については、元のテキストの図4においてFertonani–DumanおよびDalaiの境界と比較されている（ただし、図はここでは再現されていない）。

意義と主張
本論文の意義は、主に、計算効率が高く（$O(1)$）、解析的に検証された2つの新しい閉形式の上界を提供したことにある。

• 理論的厳密性: 著者らは、定理1の最適化に関する厳密な検証を強調しており、中間ドラフトで見つかった軽微な代数的な誤りを修正し、目的関数の厳密な凹性を確認している。
• パラメータの明確化: 定理2におけるパラメータ $\gamma$ に関する明確化は、主要な貢献の一つである。著者らは、$\gamma$ を近似的な最適値と見なすべきではなく、ソースによって決定されるパラメータと見なすべきであると明示しており、式の振る舞いに関する潜在的な誤解を正している。
• 範囲の限定: 論文は、その範囲を控えめに定義している。本論文は、一般的なBDC容量問題を解決したと主張しているわけでも、すべての許容されるプロセス（例：高次マルコフ過程やランレングス符号化ソース）に対する最適な入力メモリを見つけたわけでもない。結果は、導出に使用された特定の一次対称マルコフ族に厳密に限定されている。
• 除外事項: 著者らは、解析的な精度を維持するために、特定の「統一的な」主張、導出されていない漸近形式、およびより広範な収束定理を意図的に除外したことを明記している。

要約すると、本論文は、補助チャネル解析と直接的な相互情報量近似に基づき、計算可能で閉形式の、数学的検証に重点を置いた、計算容易な（$O(1)$）BDCの上界を提供することで、当該分野の進展に寄与している。