An Improved Lower Bound on Support Size of Capacity-Achieving Inputs for the Binomial Channel: Extended version

技術的概要：二項分布チャネルにおける容量達成入力分布のサポートサイズの改善された下限

問題定義
本論文は、$x \in [0, 1]$ および $y \in \{0, \dots, n\}$ に対して遷移確率 $P_{Y|X}(y|x) = \binom{n}{y} x^y (1-x)^{n-y}$ で定義される二項分布チャネルにおける、容量達成入力分布の構造的特性を調査する。容量達成入力分布 $P_{X^*}$ が離散的であり、有限個の点でサポートされることが既知である一方、試行回数 $n$ が増加するにつれてこのサポートサイズがどのように増加するかという正確な成長率は依然として研究対象となっている。[10] による先行研究では、サポートサイズが $\sqrt{n}$ のオーダーの項で下限付けられ、$n/2$ のオーダーの項で上限付けられることが示された。しかし、[10] で知られている容量の下限と上限の間のギャップは $n \to \infty$ において消失しないため、より鋭い基数の下限を導出する能力が制限されていた。

手法
著者は、サポートサイズに対するよりtightな下限を導出するために、3段階の解析的枠組みを採用する。

1. tightな容量の上下限: 著者はまず、チャネル容量 $C(n)$ に対する新しい明示的な上限と下限を導出する。下限は、参照入力 $X_r \sim \text{Beta}(1/2, 1/2)$ における相互情報量を評価することで得られ、上限は Xie–Barron のミニマックス冗長性構成 [8] を利用する。重要なのは、これらの上下限のギャップが $n \to \infty$ において消失することが示され、漸近展開 $C(n) = \frac{1}{2} \log \frac{n\pi}{2e} + o(1)$ が得られる点である。

2. 参照出力の最適性: 容量ギャップの消失を用いて、著者は参照入力によって誘発される出力分布 $P_{Y_r}$（ベータ - 二項分布）が漸近的に最適であることを示す。具体的には、参照出力と真の容量達成出力 $P_{Y^*}$ との間の相対エントロピー $D(P_{Y_r} \| P_{Y^*})$ および $\chi^2$ 発散 $\chi^2(P_{Y^*} \| P_{Y_r})$ が、容量ギャップに比例する速度で消失することを証明する。

3. 有限混合近似による下限: 議論の核心は、参照ベータ - 二項出力を二項分布の有限混合で近似するための定量的な下限に依存している。加法性ガウスチャネル [11] や最良近似理論 [12] で用いられた手法に触発され、著者は三角関数モーメント法を適応させる。彼らは、Beta(1/2, 1/2) 分布に関連する直交多項式（シフトされたチェビシェフ多項式）を用いてモーメント行列を構成する。この行列に対して Eckart-Young-Mirsky 定理を適用することで、任意の $K$ 点入力出力と参照出力との間の $\chi^2$ 発散に関する下限を導出する。

主要な貢献と結果
本論文の主要な貢献は、容量達成入力分布 $P_{X^*}$ のサポートの基数に対する改善された下限である。

• 改善された下限: 著者は、サポートサイズ $|\text{supp}(P_{X^*})|$ が $\sqrt{n} \log \log n$ のオーダーの項で下限付けられることを証明する。具体的には、十分に大きな $n$ に対して：
  $$|\text{supp}(P_{X^*})| \geq \Omega\left(\sqrt{n} \log \log n\right)$$
  これは、[10] で確立された以前の $\Omega(\sqrt{n})$ の下限を改善するものである。

• 容量の特性化: 本論文は、ギャップが消失する明示的な容量 $C(n)$ の上限と下限を提供し、漸近的な挙動 $C(n) = \frac{1}{2} \log \frac{n\pi}{2e} + o(1)$ を確認する。

• 近似理論: 本論文は、ベータ - 二項分布と $K$ 個の成分を持つ任意の二項混合との間の $\chi^2$ 発散に対する特定の下限を確立する。これは、$K$ が十分に大きくなければ、そのような近似は任意に近づくことができないことを示している。

重要性
本論文は、容量推定におけるギャップの消失が、容量値とサポートサイズとの間の接続を可能にする不可欠な要素であると主張している。容量達成出力が $\chi^2$ 発散においてベータ - 二項参照出力に近くなければならないことを示し、かつこの参照出力が疎な混合によってよく近似できないことを証明することで、著者は容量達成入力が以前に証明されたものよりも著しく大きなサポートを持たなければならないという結論を導き出す。

著者は、$\sqrt{n}$ から $\sqrt{n} \log \log n$ への改善が漸近的なものであり、明示的な定数は最適化されていないものの、この結果は既知の下限と $n/2$ のオーダーの上限との間のギャップを狭めると指摘している。論文は、サポートサイズの正確な漸近成長の決定や、明示的な定数および非漸近的推定の精緻化を含む未解決の問題を特定して結論付けている。