技术摘要：插入列表译码容量与改进的删除列表译码上界

问题陈述

本文研究了在对抗性同步错误（特别是插入和删除）下，二进制码的列表译码容量（list-decoding capacity）。与比特翻转或擦除信道（其列表译码容量已被充分理解，且与相应概率信道的香农容量一致）不同，同步错误的容量目前仍不明确。

核心问题是：对于一族二进制码，在列表大小 $L$ 为块长度 $n$ 的多项式量级时，能够实现 $\delta$ 分数插入或删除的 최대 率 $R$ 是多少？

在此项工作之前，已知知识非常有限：

• 删除（Deletions）： 已知的最佳下界是 $1 - h(\delta)$，由均匀随机码实现。而上界较为宽松（$1 - 2\delta$）。
• 插入（Insertions）： 对于 $\delta \leq 1/2$，下界同样为 $1 - h(\delta)$。对于 $\delta > 1/2$，仅已知一个极小的正下界，而上界为 $(1+\delta)(1 - h(\frac{\delta}{1+\delta}))$。
• 差距： 存在显著的上下界差距，特别是在插入且 $\delta > 1/2$ 的情况下；此外，尚不清楚结构化随机码（如马尔可夫链）是否能在删除场景下优于均匀随机码。

研究方法

作者采用了概率方法，具体分析了带有记忆的随机码（马尔可夫链）与均匀随机码的性能对比。

1. 马尔可夫链采样： 作者并非通过独立采样每个比特（均匀随机）来生成码字，而是根据对称的一阶马尔可夫链对码字进行采样。这引入了相邻比特之间的相关性，由参数 $\alpha$（即 $X_i = X_{i-1}$ 的概率）控制。
2. 大偏差理论： 为了分析随机码字包含特定接收字符串作为子序列（针对删除）或超序列（针对插入）的概率，作者利用了克拉默定理（Cramér's theorem）以及矩生成函数的拉格朗日-费恩切尔变换（Lagrange-Fenchel transform）。这使得他们能够推导出关于“坏事件”（即接收字符串成为过多码字的子序列）概率的精确渐近界。
3. 组合计数（连通块/Run）： 在分析删除容量的上界时，作者分析了码字中“连通块”（相同符号构成的最大连续块）的数量。他们结合鸽巢原理和对删除球大小的估计（列文斯坦界/Levenshtein bounds），证明了高率码必须包含具有大量连通块的码字，从而迫使存在具有大列表大小的接收字符串。

核心贡献与结果

1. 插入列表译码的精确容量

本文确定了插入列表译码的精确容量，记作 $C_{ins}(\delta)$，适用于所有 $\delta \in [0, 1]$。

• 结果：
  $$C_{ins}(\delta) = (1 + \delta) \left( 1 - h\left( \frac{\delta}{1 + \delta} \right) \right)$$
• 可达性： 通过从精心选择的转移概率 $\alpha = \frac{1+\delta}{2}$ 的对称一阶马尔可夫链中采样的码字，可以以高概率实现该容量。
• 意义： 该结果填补了插入问题的空白。它改进了此前仅在 $\delta \leq 1/2$ 时有效的下界 $1-h(\delta)$，以及 $\delta > 1/2$ 时极小的正下界。它证明了先前已知的基于平均值的上界是紧致的，并证明了其可达性。该构造保证了在速率低于容量时，列表大小为常数级 $L = O(1/\epsilon)$。

2. 马尔可夫码在删除场景下的局限性

作者研究了适用于插入的马尔可夫链是否也能在删除场景下提升性能。

• 结果： 一阶马尔可夫码在处理删除列表译码时，并不能优于均匀随机码。
• 定理： 对于任何删除比例 $\delta \in [0, 1/2]$ 和任何速率 $R > 1 - h(\delta)$，采样自一阶马尔可夫链的码集，以高概率会包含一个接收字符串 $y$，该字符串是指数级数量（$2^{\Omega(\epsilon n)}$）码字的子序列。
• 意义： 这揭示了插入与删除之间的二分性（dichotomy）。虽然引入记忆（马尔可夫结构）有助于实现插入的最优容量，但在删除场景下，这种方法对于提升列表译码性能并无优势，均匀随机性仍然是最优的。

3. 改进的删除容量上界

本文为删除容量 $C_{del}(\delta)$ 提供了一个新的、更紧凑的上界，特别是在 $\delta$ 较小时。

• 结果：
  $$C_{del}(\delta) \leq 1 - \delta - (\gamma - \delta)h\left( \frac{\delta}{\gamma - \delta} \right) = 1 - h(\delta) + o(\delta)$$
  其中 $\gamma = \frac{1}{2} - \sqrt{\frac{h(\delta) \ln 2}{2}}$。
• 渐近行为： 当 $\delta \to 0$ 时，容量的行为表现为 $1 - h(\delta) + o(\delta)$。
• 意义： 这与概率删除信道（比特以概率 $\delta$ 被删除）的容量相匹配。这表明，在低噪声区域，对抗性列表译码容量与概率信道容量具有相同的阶数行为，尽管两者属于不同的错误模型（对抗性 vs 概率性）。

重要性与主张

本文声称在理解同步错误纠正的极限方面取得了基础性进展：

1. 解决插入问题： 通过确定插入的精确容量，作者解决了一个长期悬而未决的问题。他们证明了“平均值界”是紧致的，并且可以通过马尔可夫随机编码实现。
2. 模型分离： 本研究强调了插入错误与删除错误之间的本质区别。优化插入容量的技术（通过马尔可夫链引入记忆）在删除场景下是无效的，在删除场景中，均匀随机性在所有一阶马尔可夫码类中仍然是最优的。
3. 与概率信道的联系： 改进后的删除容量上界将对抗性列表译码容量与概率删除信道容量在低噪声机制下统一起来，为对抗性模型与概率模型之间的理论联系提供了更深的见解。

作者强调，其关于插入的研究结果是非构造性的（基于随机码的存在性），但提供了第一个证明——即证明了容量在 $\delta > 1/2$ 时严格大于 $1-h(\delta)$。对于删除问题，其工作主要在于精炼上界并刻画特定随机编码策略的局限性。