Combinatorial Capacity Bounds for the $q$-ary Deletion Channel

技術要約：q-ary 削除チャネルにおける組合せ論的容量境界

問題設定

本論文は、$q$-ary 削除チャネルの容量を特徴付けるという根本的な問題に取り組んでいる。このチャネルモデルでは、伝送される各シンボルが確率 $d$ で独立に削除され、受信者はどの位置が削除されたかを知ることなく、生存した部分列を観測する。数十年にわたる研究にもかかわらず、特に一般的なアルファベットサイズ $q \ge 2$ および有限ブロック長 $n$ において、タイトな容量の特性付けは未解決の課題として残っている。既存の境界は緩いことが多く、また、大きな $n$ に対して正確な容量計算を行うことは計算量的に困難である。

手法

著者らは、パターンカウント・スカラー（pattern-count scalar）と表記される $N_n(x, y)$ を中心とした、自己完結的な組合せ論的フレームワークを導入している。この整数スカラーは、入力語 $x \in \Sigma_q^n$ から $n-k$ 個の削除集合 $S \subseteq [n]$ を削除した結果、出力語 $y \in \Sigma_q^k$ が得られるような、異なる削除集合 $S$ の総数として定義される。

手法は以下のステップで進行する：

1. 因数分解： チャネルの遷移確率を、特定の削除パターンの確率的重みと、組合せ論的なカウント $N_n(x, y)$ に因数分解する。具体的には、$\Pr(Y=y | X=x) = N_n(x, y) \cdot d^{n-k}(1-d)^k$ となる。
2. 再帰構造： すべての $q \ge 2$ に対して一様に成立する $N_n$ の2ケース再帰式を確立する。この再帰式は、チャネルの組合せ論的構造をその確率的重みから分離する。
3. 和の恒等式： 2つの主要な恒等式を証明する：
   • 行和の恒等式： 固定された入力 $x$ に対して、すべての可能な出力 $y$（長さ $k$）に関する $N_n(x, y)$ の和は $\binom{n}{k}$ に等しい。
   • 列和の恒等式： 固定された出力 $y$ に対して、すべての可能な入力 $x$ に関する $N_n(x, y)$ の和は $q^{n-k}\binom{n}{k}$ に等しい。
4. エントロピー解析： これらの恒等式を用いて、一様入力分布の下での出力エントロピーを導出する。その後、複数の削除集合が同じ入力を同じ出力へと写す場合（すなわち $N_n(x, y) \ge 2$ の場合）の条件付き分布の集中度を定量化するエントロピー補正項 $\Phi_{k,n}$ を導入する。

主な貢献

1. 正確な出力エントロピーと容量のサンドイッチ

一様入力分布の仮定の下で、著者らは出力エントロピー $H(Y)$ の閉形式の式を導出する。これにより、有限ブロック容量 $C_{q,n}$ に対する「サンドイッチ」境界が得られる：
$$(1-d)\log_2 q - h_2(d) \le C_{q,n} \le (1-d)\log_2 q$$
ここで $h_2(d)$ は 2 元エントロピー関数である。上界は古典的なものであり、下界は一様入力の解析から直接導出される。

2. エントロピー補正による下界のタイト化

本論文の主要な貢献は、$N_n(x, y)$ の値に基づいた $\Delta_n(d)$ を用いて、条件付き出力の非一様性を考慮することで下界を精緻化することである。著者らは以下のように $\Delta_n(d)$ を定義する：
$$\Delta_n(d) = \sum_{k=0}^n w_k \Phi_{k,n}$$
ここで $w_k$ は出力の長さが $k$ である確率であり、$\Phi_{k,n}$ は $N_n$ の整数値から導かれる平均エントロピー補正である。これにより、一様入力の下での相互情報量の正確な式が得られる：
$$\frac{1}{n}I_U(X; Y) = (1-d)\log_2 q + \frac{1}{n}H_{\text{Bin}}(n, 1-d) - h_2(d) + \frac{\Delta_n(d)}{n}$$
容量は相互情報の最大値であるため、この式は認定された下界を提供する：
$$C_{q,n} \ge (1-d)\log_2 q + \frac{1}{n}H_{\text{Bin}}(n, 1-d) - h_2(d) + \frac{\Delta_n(d)}{n}$$

3. 正値性と漸近境界

著者らは、すべての $n \ge 2$ および $d \in (0, 1)$ に対して $\Delta_n(d) > 0$ であることを証明し、タイト化された下界が基本的な下界よりも厳密に優れていることを保証している。また、$\Phi_{k,n}$ の閉形式の下限を導出し、小削除（small-deletion）の漸近挙動を導出する：
$$C_q(d) \ge \log_2 q + d \log_2 d + O(d)$$
この結果はすべての $q \ge 2$ に対して成立する。

4. 数値検証

本論文では、$q \in \{2, 3\}$ およびブロック長 $n \in \{3, 5, 10\}$ についての数値実験を示す。Blahut–Arimoto アルゴリズムを用いて正確な有限ブロック容量を計算することで、著者らは、提案されたタイト化された下界（$LB+$）が、従来の境界（Diggavi–Grossglauser 境界や $q=2$ の場合の Kanoria–Montanari 展開など）よりも真の容量に厳密に近くなっていることを示している。真の容量とタイト化された下界との差は、$n$ が増加するにつれて縮小する。

意義と主張

本論文は、組合せ論的構造と確率的解析を統一する、削除チャネルの自己完結的な $q$-ary 処理を提供すると主張している。$N_n(x, y)$ を利用することで、著者らはすべての容量計算を単一の整数配列を通じて整理している。

本研究の意義は以下の点にある：

• 認定された境界： $N_n(x, y)$ の整数値から導かれる正確なエントロピー補正項を組み込むことにより、任意の $q \ge 2$ に対して $q$-ary 削除チャネルの容量に対する明示的かつ認定された下界を提供する。
• 解析的な利便性： 一様入力はすべての $d$ に対してグローバルに最適ではない可能性があるものの、それが扱いやすく正確な出力エントロピーおよび、ブロック長が増加するにつれて改善される厳密な下界をもたらすことを示している。
• 構造的洞察： $N_n$ の再帰構造と導出された和の恒等式は、削除パターンのカウントをその確率から分離するという、チャネルに対する新しい組合せ論的な視点を提供する。

著者らは、一様入力は扱いやすさのために選択されたものであり、すべての $q$ および $d$ に対して容量達成的であることを主張していないと謙虚に述べている。しかし、導出された境界は真の容量に対して有効であり、数値結果は提案された下界が小さな $n$ に対してタイトであり、$n$ が大きくなるにつれて改善されることを裏付けている。著者らによって示唆されている今後の課題には、$n \to \infty$ における $\Delta_n(d)/n$ の漸近的特性化、およびこれらの手法の挿入・削除チャネルへの拡張が含まれる。