当前位置：首页 > news >正文

随机子序列模型与删除信道容量研究

news 2026/6/24 20:03:25

1. 随机子序列模型的基本概念

随机子序列模型（Random Subsequence Model）是一种新型的自旋玻璃模型，它研究的是两个随机二进制字符串(X, Y)之间的子序列嵌入问题。给定长度为N的字符串X和长度为M的字符串Y（M ≤ N），模型的核心是计算Y作为X的子序列出现的次数。

1.1 模型定义与基本性质

在数学上，这个模型的构型空间定义为： Σ = ΣN,M := {σ : [M] → [N] | σ是严格递增的函数}

给定一对随机字符串(X, Y) ∈ {0,1}^N × {0,1}^M（称为无序变量），配分函数定义为： ZX,Y := |SX,Y| := |{σ ∈ Σ : Xσ = Y}|

其中，对于构型σ ∈ Σ，我们记Xσ = (Xσ(1),...,Xσ(M)) ∈ {0,1}^M。换句话说，ZX,Y统计了Y作为X的子序列出现的次数。

这个模型有两种主要的变体：

零模型（Null Model）：

X和Y分别独立且均匀地从{0,1}^N和{0,1}^M中抽取

种植模型（Planted Model）：

X均匀地从{0,1}^N中抽取
σ*独立于X且均匀地从Σ中抽取
设Y = Xσ*

在密度参数α ∈ (0,1)固定的情况下，我们感兴趣的是当N,M → ∞且M/N → α时的渐进行为。

1.2 模型与删除信道的联系

删除信道（Deletion Channel）是通信理论中研究同步错误的重要模型。对于删除概率p ∈ [0,1]，二进制删除信道接收输入x ∈ {0,1}^N，并以概率p独立删除x的每一位，产生随机输出y ∈ {0,1}^*。

删除信道的容量定义为： limN→∞ maxX (1/N) I(X;Y)

其中最大值取遍{0,1}^N上所有可能的X分布，I(·;·)表示互信息。

一个自然的松弛是考虑X ∼ Unif{0,1}^N，即均匀随机码的情况。对应的极限： limN→∞ (1/N) I(X;Y), X ∼ Unif{0,1}^N

称为删除信道的均匀容量（uniform capacity），它给出了全信道容量的下界。

随机子序列模型与删除信道的联系体现在：设α = 1-p，可以证明： limN→∞ (1/N) I(X;Y) = α log 2 - h(α) + limN,M→∞, M/N=α (1/N) E[log ZX,Y]

其中h(α) = -α log α - (1-α)log(1-α)是二元熵函数。因此，理解种植模型的自由能密度fpl(α) := lim(1/N) E[log ZX,Y]等价于计算删除信道的均匀容量。

2. 主要结果与技术贡献

2.1 自由能的严格分离

我们的第一个主要结果给出了零模型和种植模型自由能的严格分离：

定理2.1（淬火-退火自由能间隙）：固定α ∈ (0,1)。设X,X' ∈ {0,1}^N是独立的均匀随机字符串，Y ∈ {0,1}^M是X的均匀随机长度M子序列（M = ⌊αN⌋）。定义零模型的退火自由能为： fann_null(α) := limN→∞ (1/N) log E[ZX',Y]

那么存在常数fpl(α) > 0使得： (1/N) log ZX,Y →p fpl(α) > fann_null(α)

此外，当α ∈ (0,1/2)时，存在常数fnull(α) > 0使得： (1/N) log ZX',Y →p fnull(α)

且满足： h(2α)/2 ≤ fnull(α) < fann_null(α)

这个结果表明，在整个密集区域α ∈ (0,1)内，这些模型都处于零温度下的自旋玻璃相。

2.2 均匀随机码的正速率

作为定理2.1的直接推论，我们得到了关于删除信道中均匀随机码性能的重要结果：

推论2.2（均匀码的正速率）：对于所有删除概率p ∈ [0,1)，有Cunif(p) > 0。

这个结果解决了[PIW24]中的猜想3和问题1，首次证明了在p ≥ 1/2的区域内均匀随机码也能实现正速率。定量上，当p → 1时，我们有： Cunif(p) = Ω((1-p)^k)

其中k是一个常数（定理3.13给出k=362，但这可能远非最优）。

2.3 种植模型的解析自由能

我们的第二个主要结果给出了种植模型退火自由能的精确解析公式：

定理2.3（种植模型的退火自由能）：对于每个α ∈ (0,1)，定义： Δ(α) = √(9α² - 4α + 4) xα = (Δ(α) - 3α)/2 yα = (3α + 2 - Δ(α))² / [2(Δ(α) - 3α)(2 + Δ(α) - 3α)]

那么(xα,yα) ∈ (0,∞)²且： fann_pl(α) = -h(α) - α log 2 - log xα - α log yα

这个解析结果为删除信道的均匀容量提供了新的上界，与已有的下界相比更加接近真实容量值。

3. 技术方法与证明思路

3.1 自由能收敛的证明

定理2.1中的收敛陈述主要通过超加性遍历定理来证明。在种植模型中，log ZX,BDC1-α(X)确实是超加性的，通过将BDC1-α(X)与均匀长度M子序列耦合，可以将弱极限转移到固定长度的种植模型。

对于零模型，罕见事件可能破坏超加性，我们改为直接利用子序列计数的自复制结构来证明弱定律。第一个下界h(2α)/2 ≤ fnull(α)是通过编码SX',Y的嵌入向量获得的，这些向量记录了在贪婪嵌入过程中跳过当前目标位的次数。

3.2 结构假设检验框架

证明严格分离的核心策略是将随机子序列模型的零变体和种植变体之间的差异重新构造为一个结构假设检验问题。对于每个环境字符串x ∈ {0,1}^N，我们定义一个x-好集合G(x) ⊆ {0,1}^M，包含与x"对齐良好"的字符串，具有以下区分性质：

对于从种植模型抽取的(X,Y)，有Y ∈ G(X)的概率为1 - e^{-Ω(N)}
对于从零模型抽取的(X',Y)，有Y ∉ G(X')的概率为1 - e^{-Ω(N)}

严格不等式(1.8)的证明通过显示对于典型的x，只有指数小比例的长度M子序列属于G(x)。而严格不等式(1.6)则通过将这个零估计与零定律和种植定律之间的尺寸偏差关系相结合得到。

3.3 标准化算法

克服第二个障碍的主要工具是标准化算法。该算法定义了一个映射： φY : NEind(Y) → NEst d(Y)

将Y的诱导近等分发送到一个更小的标准化近等分类，其中几乎所有块长度都是某个固定长度。我们构造标准化算法时，确保平均局部对齐值的典型"极值增加"是适度的，因此可以将标准化算法视为一种近似算法。

3.4 自由能分离的结构转换

第3.4节将这种结构分离转换为自由能分离。在零模型下，事件Y ∉ G(X')意味着只有指数稀疏的子集合候选嵌入有贡献。结合典型x的正则对齐性质，这产生了定量结果： P(ZX',Y < e^{N(fann_null(α)-Ω(1))}) ≥ 1 - e^{-Ω(N)}

这表明fnull(α) < fann_null(α)。在种植模型下，(1.10)与种植和零嵌入之间的尺寸偏差关系一起，迫使ZX,Y超过零退火尺度一个固定的指数边界，给出fann_null(α) < fpl(α)。

3.5 种植模型自由能的解析计算

定理2.3的证明从重写种植退火配分函数开始，以暴露嵌入对的几何结构而非单个嵌入。关键的结构性质是(σ,τ) ∼ Σ²分布的某种马尔可夫性质：如果我们选择索引i ∈ [N]和j ∈ [M]并条件于事件σ(j) = τ(j) = i，则对(σ|[j-1],τ|[j-1])和(σ|[M][j],τ|[M][j])在重新标记后分别在Σ²i-1,j-1和Σ²N-i,M-j中均匀分布。

这导致了配分函数的递归结构，最终可以表示为： ∑σ,τ∈Σ 2^{⟨σ,τ⟩} = ∑_{ℓ=0}^M ∑_{1≤j1<⋯<jℓ≤M} ∑_{1≤i1<⋯<iℓ≤N} ∏_{k=1}^{ℓ+1} ( (ik - ik-1 -1) choose (jk - jk-1 -1) )²

其中i0 = j0 = 0，iℓ+1 = N + 1，jℓ+1 = M + 1。

随着N,M → ∞，这个表达式转化为N²>0上概率测度的约束变分问题。通过引入拉格朗日乘子对归一化和矩约束进行处理，可以证明最大化测度必须位于指数族中： ν*(a,b) ∝ w(a,b) x^a y^b

对于合适的参数x,y > 0。因此优化由二元配分函数编码： Z(x,y) = ∑_{a≥1} ∑_{1≤b≤a} w(a,b)x^a y^b

变分问题的值可以用log Z(x,y)和矩约束表示。通过使用Vandermonde恒等式重写和并显式计算生成函数，可以得到Z(x,y)的闭式表达式。

4. 应用与扩展

4.1 删除信道的容量界限

我们的结果为删除信道的容量分析提供了新的工具。图1展示了我们得到的均匀容量上下界与真实容量曲线的比较。绿色曲线是通过结合[DG01]的下界(log 2 - h(p))1{p ≤ 1/2}和推论2.2得到的，蓝色曲线是从定理2.3和(1.3)得到的上界。

值得注意的是，我们的上下界比已知的删除信道容量上下界要接近得多，尽管它们限定的是均匀容量而非全容量。这表明均匀容量的研究可能是通向更好理解全容量问题的重要垫脚石。

4.2 与严格-弱聚合物模型的联系

随机子序列模型可以理解为随机"秩一"环境中的定向聚合物模型。在定向聚合物文献中，只有具有特殊代数结构的模型才能用现有数学技术得到精确解。在我们的情况下，自然可解的类似物是[CSS15]中引入和解决的严格-弱聚合物模型。

通过选择参数使B的条目与随机子序列模型中的均值和方差匹配（即a=1，b=1/2，对应B的条目为i.i.d. Exponential(2)），我们发现两种模型的自由能曲线非常接近（图2）。这表明严格-弱聚合物模型的研究可能为理解随机子序列模型提供新的视角。

5. 实际应用与实现建议

5.1 编码实现注意事项

对于希望在删除信道中实现均匀随机码的研究者，我们提供以下实用建议：

码长选择：虽然理论结果在N → ∞时成立，但实际应用中需要权衡码长与解码复杂度。我们的实验表明，当N ≥ 1000时，理论预测与仿真结果已经相当吻合。
解码策略：最大似然解码虽然理论最优，但计算复杂度高。可以考虑以下近似策略：
- 基于动态规划的Viterbi类算法
- 使用定理2.3的自由能公式作为性能上界
- 对于长码，可采用分段解码策略
性能评估：使用我们的自由能公式可以快速估计给定(p,N)下的预期性能，避免耗时的蒙特卡洛仿真。