技术摘要：q-ary 删除信道的组合容量界限

问题陈述

本文探讨了表征 $q$-ary 删除信道容量这一基本问题。在该信道模型中，来自字母表 $\Sigma_q$ 的每个传输符号以概率 $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$ 的不同删除集合的数量。

该方法通过以下步骤进行：

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$。该递归将信道的组合结构与其概率权重分离开来。
3. 求和恒等式： 证明了两个关键恒等式：
   • 行和恒等式： 对于固定的输入 $x$，所有可能输出 $y$（长度为 $k$）的 $N_n(x, y)$ 之和等于 $\binom{n}{k}$。
   • 列和恒等式： 对于固定的输出 $y$，所有可能输入 $x$ 的 $N_n(x, y)$ 之和等于 $q^{n-k}\binom{n}{k}$。
4. 熵分析： 这些恒等式被用于推导均匀输入分布下的精确输出熵。随后，作者引入了一个熵修正项 $\Phi_{k,n}$，用于量化当多个删除集合将相同的输入映射到相同的输出时（即 $N_n(x, y) \ge 2$）条件分布的集中程度。

主要贡献

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. 通过熵修正强化的下界

本文的主要贡献是通过考虑条件输出分布的非均匀性来优化下界。作者根据 $N_n(x, y)$ 的值定义了一个修正项 $\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}$ 的闭式下界，并推导了小删除情形下的渐近行为：
$$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)$，作者将所有的容量计算都组织在一个单一的整数数组中。

这项工作的意义在于：

• 经过认证的界限： 它为任何 $q \ge 2$ 的 $q$-ary 删除信道提供了显式的、经过认证的容量下界，通过引入精确的熵修正项改进了现有结果。
• 分析便利性： 它表明，虽然均匀输入对于所有的 $d$ 可能并非全局最优，但它产生了一个易于处理且精确的输出熵，并提供了一个随块长度增加而改进的严谨下界。
• 结构洞察： $N_n$ 的递归结构及其导出的求和恒等式为该信道提供了一个新的组合视角，将删除模式的计数与其概率分离开来。

作者谦虚地指出，选择均匀输入是为了处理的简便性，并不声称其对于所有的 $q$ 和 $d$ 都是容量达到的（capacity-achieving）。然而，所推导的界限对真实容量是有效的，且数值结果证实了所提议的下界在小 $n$ 时是紧致的，并随 $n$ 增大而改善。作者建议未来的工作包括研究 $\Delta_n(d)/n$ 在 $n \to \infty$ 时的渐近特征，以及将这些方法扩展到插入-删除信道。