🔬 condensed matter

The Random Subsequence Model and Uniform Codes for the Deletion Channel

该论文通过引入随机子序列模型并证明其在零温下处于自旋玻璃相，确立了均匀随机码在任意删除概率下均能达到正速率，从而解决了相关猜想并给出了该信道容量的更紧确上下界。

原作者： Ryan Jeong, Francisco Pernice

发布于 2026-04-09

📖 1 分钟阅读☕ 轻松阅读

原作者： Ryan Jeong, Francisco Pernice

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文讲述了一个关于**“在混乱中寻找秩序”**的数学故事，它巧妙地连接了信息传输、密码学和物理学的几个看似不相关的领域。

为了让你轻松理解，我们可以把这篇论文的核心内容想象成一场**“在迷宫中找路”**的游戏。

1. 核心游戏：删除信道与“乱码”

想象一下，你正在给朋友发一条短信（比如一串二进制代码 010110）。但是，这条短信经过了一个非常调皮的**“删除信道”**（Deletion Channel）。

发生了什么？ 这个信道会随机吃掉你信息里的某些字（比特）。比如，它可能把 010110 吃掉了几个，变成了 0110。
问题： 朋友收到 0110 后，怎么知道它原本是什么？是 010110 还是 011000？因为不知道哪些字被删了，原来的顺序乱了，这就叫**“同步错误”**。
目标： 数学家想知道，在这种混乱的情况下，我们最高效能传输多少信息？这被称为**“信道容量”**。

2. 两个关键角色：随机模型 vs. planted（种植）模型

为了解决这个问题，作者引入了一个叫做**“随机子序列模型”**（Random Subsequence Model）的新工具。你可以把它想象成两个不同的游戏场景：

场景 A：完全随机的“盲猜”（Null Model）
- 你手里有两张完全随机生成的纸条，一张长（ $X$ ），一张短（ $Y$ ）。
- 你问：短纸条 $Y$ 是长纸条 $X$ 的一部分吗？
- 结果： 在大多数情况下，它们只是碰巧长得像，或者完全不像。这就像在茫茫大海里随便捞两根稻草，看它们能不能拼成一根。
场景 B：有人“种”下的线索（Planted Model）
- 你手里有一张长纸条 $X$ 。
- 有人偷偷从 $X$ 里剪下了一段，变成了短纸条 $Y$ （这就是“种植”了线索）。
- 你问：能不能找到 $Y$ 在 $X$ 里的位置？
- 结果： 因为 $Y$ 真的来自 $X$ ，所以它们之间有着内在的、隐藏的联系。只要方法对，你一定能找到。

论文的核心发现： 作者证明了，在“种植”场景下，这种隐藏的联系非常强，强到足以让计算机（或解码器）在混乱中成功找回信息。而在“完全随机”的场景下，这种联系非常弱，几乎不存在。

3. 物理学视角：像“玻璃”一样的混乱

论文把这个问题比作物理学中的**“自旋玻璃”**（Spin Glass）。

比喻： 想象一个由无数小磁铁组成的系统，每个磁铁都想和邻居对齐，但邻居之间又互相矛盾。这就形成了一个极度混乱、难以预测的状态。
论文的贡献： 作者发现，在这个“删除信道”的混乱系统中，存在一种**“相变”**。
- 在“随机盲猜”模式下，系统处于一种死寂的混乱状态（就像玻璃一样硬且无序）。
- 在“种植线索”模式下，系统虽然也乱，但内部有一种**“磁化”**的趋势，让磁铁们能自发地排列整齐。
- 结论： 这种“整齐”的趋势（数学上称为“自由能”的差距）是真实存在的，而且非常显著。

4. 为什么这很重要？（打破僵局）

在信息论界，关于“删除信道”有一个长期的猜想：

旧观点： 当删除概率很高（比如超过 50% 的信息被吃掉）时，使用随机生成的代码（Uniform Codes）可能完全无法工作，传输率会降为零。
新发现（本文的突破）： 作者证明了，即使删除概率高达 99%（只要不是 100%），随机生成的代码依然能传输正数的信息！
- 通俗解释： 哪怕你发的短信 99% 的字都被吃掉了，只要剩下的 1% 是随机生成的，接收方依然有办法（虽然很难，但理论上可行）还原出原始信息。这推翻了以前认为“太乱了就没办法”的直觉。

5. 数学魔法：从“数数”到“公式”

为了证明这一点，作者做了一件很酷的事：

计数： 他们计算在混乱中，有多少种方法能把短纸条拼回长纸条。
物理类比： 他们把这个计数过程比作物理学中的“配分函数”（Partition Function），这是计算系统能量状态的关键。
精确公式： 他们不仅证明了“有解”，还推导出了一个精确的数学公式，用来计算在这种混乱下，理论上能传输信息的最大上限。
- 这就好比以前大家只知道“迷宫里可能有出口”，现在作者不仅证明了出口存在，还画出了通往出口的最短路径图。

总结：这篇论文说了什么？

新模型： 发明了一个新的数学模型（随机子序列模型）来研究信息在“被删除”后的传输问题。
关键区别： 证明了“随机巧合”和“真实线索”在数学本质上有巨大的、不可逾越的差距。
重大突破： 确认了即使信息被大量删除，随机编码依然有效。这解决了信息论界几十年的一个猜想。
精确计算： 给出了一个漂亮的数学公式，精确描述了这种混乱系统的极限能力。

一句话总结：
这篇论文就像是在一个被撕得粉碎的拼图盒子里，证明了只要碎片是随机生成的，我们依然能凭借数学规律，奇迹般地拼出原图，而且作者还画出了拼图的“最佳策略图”。

论文概要

本文由 Ryan Jeong 和 Francisco Pernice 撰写，引入了一个新的自旋玻璃模型——随机子序列模型（Random Subsequence Model），用于研究二进制删除信道（Deletion Channel）中均匀随机码的容量问题。文章通过建立该模型与统计物理、信息论及离散概率中经典问题的联系，解决了长期存在的猜想，并给出了删除信道均匀码容量的严格正下界和精确解析上界。

1. 研究背景与核心问题

1.1 删除信道（Deletion Channel）

删除信道是通信理论中同步错误信道的典型代表。输入为长度为 $N$ 的二进制串 $X$ ，每个比特以概率 $p$ 被独立删除，输出为长度随机的串 $Y$ 。

核心难题：计算删除信道的容量（即最大可靠传输速率）是信息论过去几十年未解决的重大难题之一。
均匀码问题：本文关注的是**均匀随机码（Uniformly-random codes）**的容量，即输入 $X$ 服从均匀分布 $\text{Unif}\{0,1\}^N$ 时的互信息极限。这对应于使用随机生成的码本进行通信的情况。

1.2 随机子序列模型

作者定义了一个新的自旋玻璃模型，其配分函数 $Z_{X,Y}$ 统计了将随机串 $Y$ 作为子序列嵌入到随机串 $X$ 中的方式数量。
模型包含两种变体：

零模型（Null Model）： $X$ 和 $Y$ 是相互独立且均匀随机的二进制串。
植入模型（Planted Model）： $X$ 是均匀随机的， $Y$ 是 $X$ 的一个随机长度为 $M$ 的子序列（即 $Y$ 是从 $X$ 中“植入”的）。

设 $N, M \to \infty$ 且 $M/N = \alpha \in (0, 1)$ 。研究的核心在于分析该模型的自由能（Free Energy），特别是退火自由能（Annealed Free Energy）（期望在取对数之前）与淬火自由能（Quenched Free Energy）（取对数之后的期望）之间的差异。

2. 方法论与关键技术

2.1 自由能间隙分析（Quenched-Annealed Gaps）

文章的核心策略是证明在零模型和植入模型中，淬火自由能严格小于退火自由能。

零模型：证明了当 $\alpha < 1/2$ 时，典型的子序列计数远小于其期望值（即存在显著的“自旋玻璃相”）。
植入模型：证明了植入的 $Y$ 与 $X$ 之间存在特殊的结构对齐，使得其配分函数显著高于零模型中的随机情况。

2.2 结构假设检验（Structural Hypothesis Testing）

为了区分零模型和植入模型，作者引入了**对齐（Alignment）**概念：

局部对齐（Local Alignment）：将字符串分块，比较块的多数位（Majority bit）是否一致，并结合随机游走位移（Random walk displacement）进行加权。
诱导总对齐（Induced Total Alignment）：定义了一个集合 $G(x)$ $G (x)$ ，包含那些与 $x$ $x$ 具有高度结构对齐的字符串。
- 植入情况：以高概率， $Y \in G(X)$ 。
- 零模型情况：以高概率， $Y \notin G(X')$ 。
标准化算法（Standardization Algorithm）：为了处理零模型中指数级数量的可能分块方式，作者设计了一种算法，将任意“诱导近等分”映射到数量更少的“标准化近等分”集合，并证明这种映射不会显著改变对齐得分。这克服了直接应用联合界（Union Bound）的困难。

2.3 变分法与解析求解

对于植入模型的退火自由能，作者利用Nishimori 恒等式和**重叠（Overlap）**的矩生成函数，将问题转化为一个关于概率测度的变分问题。

通过拉格朗日乘数法，将组合计数问题转化为有限维的变分优化问题。
利用Vandermonde 恒等式和生成函数技术，求出了配分函数的闭式解。
最终导出了关于密度参数 $\alpha$ 的精确解析公式。

3. 主要贡献与结果

3.1 严格分离零模型与植入模型（Theorem 1.1）

结果：在 $\alpha \in (0, 1)$ 的所有值下，植入模型的淬火自由能 $f_{pl}(\alpha)$ 严格大于零模型的退火自由能 $f_{ann}^{null}(\alpha)$ 。
推论：在零模型中，当 $\alpha < 1/2$ 时，淬火自由能 $f_{null}(\alpha)$ 也严格小于其退火自由能。
意义：这表明模型在整个稠密区域处于零温下的自旋玻璃相（Spin Glass Phase），期望值不能代表典型行为。

3.2 删除信道均匀码的正速率（Corollary 1.2）

结论：对于所有删除概率 $p \in [0, 1)$ ，均匀随机码在删除信道中都能实现严格正速率（即 $C_{unif}(p) > 0$ ）。
突破：
- 解决了 [PIW24] 中的猜想 3。
- 首次证明了在 $p \ge 1/2$ （即删除概率大于保留概率）的极端情况下，均匀码依然有效。此前的结果仅适用于 $p < 1/2$ 。
- 给出了当 $p \to 1$ 时，容量衰减的多项式阶下界： $C_{unif}(p) = \Omega((1-p)^k)$ 。

3.3 植入模型退火自由能的精确公式（Theorem 1.3）

结果：给出了植入模型退火自由能 $f_{ann}_{pl}(\alpha)$ 的精确解析表达式。
$f_{ann}_{pl}(\alpha) = -h(\alpha) - \alpha \log 2 - \log x_\alpha - \alpha \log y_\alpha$
其中 $x_\alpha, y_\alpha$ 是特定代数方程组的解。
意义：
- 这提供了删除信道均匀码容量的解析上界。
- 该上界与之前推导的下界非常接近，远优于目前已知的删除信道容量上下界（尽管是针对均匀码而非全容量）。

3.4 与统计物理的联系

文章将随机子序列模型与**定向聚合物（Directed Polymers）**模型联系起来。
指出随机子序列模型对应于“秩一（Rank-one）”随机环境，而现有的精确解通常仅存在于具有特殊代数结构（如 Gamma 分布条目）的模型中（如 Strict-Weak Polymer Model）。
作者通过数值模拟表明，Strict-Weak Polymer 模型可以作为研究随机子序列模型的有效近似。

4. 论文意义与影响

解决长期猜想：彻底解决了关于均匀码在删除信道中是否能在高删除率下保持正速率的开放问题。
方法论创新：提出了一种结合结构假设检验、标准化算法和自旋玻璃理论的新框架，用于处理具有同步错误的信道编码问题。
精确解析结果：在删除信道容量这一 notoriously difficult（极难）的问题上，首次给出了均匀码容量的精确解析上界，极大地缩小了理论界限。
跨学科桥梁：成功地将信息论中的删除信道问题、离散数学中的最长公共子序列（LCS）问题以及统计物理中的自旋玻璃和聚合物模型统一在一个框架下，为未来研究提供了新的视角。

5. 开放问题（Open Problems）

文章最后提出了几个未来的研究方向：

淬火自由能的精确公式：目前仅得到了退火自由能的精确解，如何推导植入模型的淬火自由能 $f_{pl}(\alpha)$ 的精确公式仍是一个挑战（可能需要复制方法 Replica Method 或腔方法 Cavity Method 的突破）。
可解的类比模型：寻找具有可解代数结构的“植入”随机子序列模型变体，以作为理解原模型的阶梯。
高删除率渐近行为：确定当 $p \to 1$ 时，均匀容量的精确渐近阶数。

总结：这篇论文通过引入随机子序列模型，利用深刻的统计物理工具和组合分析，不仅证明了均匀随机码在删除信道中的鲁棒性（即使在极高删除率下），还给出了该问题最精确的解析界限，是信息论与统计物理交叉领域的里程碑式工作。