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

技术摘要：二项式信道容量达成输入支持集大小的改进下界

问题陈述
本文研究了二项式信道容量达成输入分布的结构特性。该信道由转移概率 $P_{Y|X}(y|x) = \binom{n}{y} x^y (1-x)^{n-y}$ 定义，其中 $x \in [0, 1]$，$y \in \{0, \dots, n\}$。虽然已知容量达成输入分布 $P_{X^*}$ 是离散的且支撑在有限个点上，但随着试验次数 $n$ 的增加，该支撑集大小的精确增长率仍是研究课题。[10] 的先前结果确立了支撑集大小具有 $\sqrt{n}$ 量级的下界和 $n/2$ 量级的上界。然而，[10] 中已知容量界限之间的差距并未随 $n \to \infty$ 而消失，这限制了推导更精确的基数下界的能力。

方法论
作者采用三步分析框架来推导支撑集大小的更紧下界：

1. 紧容量界限：作者首先推导了信道容量 $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}$（一种 Beta-二项分布）是渐近最优的。具体而言，他们证明了参考输出与真实容量达成输出 $P_{Y^*}$ 之间的相对熵 $D(P_{Y_r} \| P_{Y^*})$ 和 $\chi^2$ 散度 $\chi^2(P_{Y^*} \| P_{Y_r})$ 以与容量间隙成比例的速率趋于零。

3. 有限混合近似下界：论证的核心依赖于使用有限个二项分布的混合来近似参考 Beta-二项输出的定量下界。受用于加性高斯信道 [11] 的技术和最佳逼近理论 [12] 的启发，作者改进了三角矩方法。他们利用与 Beta(1/2, 1/2) 分布相关的正交多项式（移位切比雪夫多项式）来构造矩矩阵。通过对该矩阵应用 Eckart-Young-Mirsky 定理，他们推导出了任意 $K$ 点输入输出与参考输出之间 $\chi^2$ 散度的下界。

主要贡献与结果
本文的主要贡献是对容量达成输入分布 $P_{X^*}$ 支撑集基数 $|\text{supp}(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)$。

• 逼近理论：该工作建立了 Beta-二项分布与任何具有 $K$ 个分量的二项混合分布之间 $\chi^2$ 散度的特定下界，表明除非 $K$ 足够大，否则此类逼近无法任意接近。

意义
本文声称，容量估计中消失的间隙是将容量值与支撑集大小联系起来的关键要素。通过证明容量达成输出必须在 $\chi^2$ 散度上接近 Beta-二项参考输出，并证明该参考输出不能被稀疏混合良好逼近，作者得出了容量达成输入必须具有比先前证明的显著更大支撑集的结论。

作者指出，虽然从 $\sqrt{n}$ 到 $\sqrt{n} \log \log n$ 的改进是渐近的，且显式常数未进行优化，但该结果缩小了已知下界与 $n/2$ 量级上界之间的差距。本文最后指出了开放性问题，包括确定支撑集大小的确切渐近增长，以及改进显式常数和非渐近估计。