Limiting partition function for the Mallows model: a conjecture and partial evidence

本文推测，当标签数量趋于无穷大时，Mallows 模型的一个子族的精确极限配分函数由一个与薛定谔桥分布相关的积分算子的 Fredholm 行列式给出，并且尽管由于缺乏完整证明所需的完整误差界限而未能提供完整的证明，但本文仍为这一主张提供了部分证据。

要点

想象一下，你有一副由 $n$ 张牌组成的牌组，牌面编号从 1 到 $n$。现在，想象你在对它们进行洗牌。共有 $n!$（即 $n$ 的阶乘）种不同的排列方式。

在这篇论文中，作者 Soumik Pal 正在研究一种特定的洗牌方式。在完全随机的洗牌中（即每种顺序出现的概率相等），情况并非如此，他考虑的是一种“加权”洗牌。某些排列被认为是“更好”或“更便宜”的。排列的“成本”取决于卡片偏离其原始位置的距离。如果一张牌移动得很小，成本就很低；如果移动很大，成本就会很高。

论文提出了一个非常具体的问题：当牌组变得无限大时，所有可能洗牌的总“权重”是多少？

在物理学和统计学中，这个总权重被称为配分函数（Partition Function）。它就像是这个系统的“总能量预算”。了解这个数字有助于科学家理解该系统在大规模尺度下的行为。

两步解谜

作者解释说，我们已经知道了第一部分的答案。之前的研究人员已经发现，如果取这个总权重的对数并除以牌组的大小，它会趋于一个特定的数值（我们称之为 $\Gamma_0$）。

你可以这样理解：如果你有一大堆沙子，你确切知道它占据的体积。但作者想要知道的是这个堆积物的精确形状，而不仅仅是它的体积。他想要知道之前计算中遗漏掉的那些“细节说明”。

他为这部分剩余的内容提出了一个新的公式。他猜测答案与所谓的**Fredholm 行列式（Fredholm Determinant）**有关。

类比：“洗牌的幽灵”

为了理解他的猜想，请想象一种“理想”的洗牌。在这个理想世界里，卡片的排列方式完美地平衡了移动成本与洗牌的自然随机性。这种理想的排列被称为薛定谔桥（Schrödinger Bridge）。

作者建议，总权重的“细节说明”是由实际洗牌围绕这种理想排列的“摆动（wiggle）”程度决定的。

他使用了一个叫做**积分算子（Integral Operator）**的数学工具（可以把它想象成一台能够接收某种模式并对其进行转换的巨型机器）来测量这些摆动。Fredholm 行列式是一个能够总结这台机器行为的单一数值。

猜想：
作者声称，如果你取所有洗牌的总权重，乘以一个特定的修正因子（与理想排列相关），结果将恰好等于这个 Fredolem 行列式的平方根的倒数。

简单来说：

总权重 $\approx$ (修正因子) $\times$ (1 / “摆动机器”数值的平方根)

“部分证明”（侦探工作）

作者承认他还没有 100% 地证明这一点。他称之为“带有部分证据的猜想”。

他是这样尝试证明的：

1. 分解问题： 他将计算所有洗牌这个庞大的问题分解成了更小、更易处理的部分。他观察了卡片组是如何相互作用的。
2. “无放回”问题： 通常在数学中，抽取物品有放回（比如抽一张牌，看一眼，再放回去）会更容易。但洗牌是无放回的（一旦一张牌被使用，它就不在了）。这使得数学处理变得更加困难，因为所有的选择都是相互关联的。
3. 结果： 他成功地证明了，如果暂时忽略“无放回”带来的难度，他的公式会完美运作。他证明了这些碎片能够完美地组合成他所预测的 Fredholm 行列式。
4. 缺失的一环： 最后一步需要证明，当牌组变得无限大时，“无放回”带来的难度并不会破坏最终答案。他相信事实确实如此，但他无法找到精确的数学“误差界限（error bound）”来进行严谨的证明。

总结

• 目标： 寻找当项目数量趋于无穷大时，一种特定随机洗牌的总权重的精确极限。
• 已知： 我们知道“大局观”层面的体积（对数配分函数）。
• 猜想： 剩余的细节恰好是来自“理想”洗牌模式的一个特定数学数值（Fredholm 行列式）的平方根倒数。
• 现状： 作者拥有强有力的证据和部分证明，表明这些碎片是可以拼凑在一起的，但他还缺少最后的一点数学“胶水”（误差界限），无法将他的猜想转化为一个完整且无懈可击的证明。

这篇论文本质上是一个侦探故事：侦探已经找到了嫌疑人的指纹和证人证词，但仍在等待最后的法医学证据来结案。

技术摘要

技术摘要：Mallows 模型中限制配分函数的极限

问题陈述
本文研究了定义在置换集 $S_n$ 上的特定类 Gibbs 概率模型的配分函数的渐近行为。这些模型是著名的 Mallows 模型的一个子族，其特征在于其 Gibbs 能量源自 $S_n$ 上的右不变散度（right-invariant divergence）。该能量函数涉及一个代价函数 $c: [0, 1]^2 \to [0, \infty)$，假设该函数是二阶连续可微的、对称的、在对角线上为零，并满足特定的反射对称性 $c(x, y) = c(1-x, 1-y)$。

所关注的量是序列：
$$L_n = \frac{1}{n!} \sum_{\sigma \in S_n} \exp\left( -\sum_{i=1}^n c\left(\frac{i}{n}, \frac{\sigma_i}{n}\right) \right)$$
前人的工作 [Muk16] 确立了缩放对数配分函数的拉德曼大偏差极限：$\lim_{n \to \infty} \frac{1}{n} \log L_n = -\Gamma_0$，其中 $\Gamma_0$ 是一个具有均匀边际分布的熵正则化最优传输问题的解。本文的目标是确定无缩放、经过指数修正后的序列的精确极限：
$$\lim_{n \to \infty} e^{n\Gamma_0} L_n$$

方法论与理论框架
作者运用了最优传输理论、谱理论和组合分析的工具。

1. 薛定谔桥与熵正则化最优传输：
   分析依赖于 $[0, 1]$ 上均匀分布 $\mu$ 与其自身之间的熵正则化最优传输问题的解。已知最优耦合（称为静态薛定谔桥）$\rho(x, y)$ 具有如下形式的密度：
   $$\rho(x, y) = \exp(-c(x, y) - a(x) - a(y))$$
   其中 $a(x)$ 满足由边际约束导出的特定积分方程。$\Gamma_0$ 被证明为 $-2 \int_0^1 a(x) dx$。

2. 谱分解：
   论文定义了一个在 $L^2[0, 1]$ 上以核函数 $\rho(x, y)$ 为算子的积分算子 $T$。由于 $\rho$ 是对称的且边际分布是均匀的，因此 $T$ 是一个自伴、紧的 Hilbert-Schmidt 算子。$T$ 的特征值为 $\lambda_n$，它们是实数且位于 $[-1, 1]$ 之间，其中最大的特征值为 $\lambda_1 = 1$，对应的特征函数为常数函数。该核函数分解为 $\rho(x, y) = 1 + \sum_{n=1}^\infty \lambda_n \phi_n(x)\phi_n(y)$。

3. 组合展开：
   序列 $D_n = e^{n\Gamma_0} L_n$ 使用核函数 $\rho$ 进行重写。通过展开乘积 $\prod \rho(i/n, \sigma_i/n)$ 并利用特征函数的正交性（特别是它们与常数函数的正交性），作者将 $D_n$ 表示为对下标子集的求和。证明策略涉及将核函数截断为有限秩 $L$，并将展开式截断至有限阶 $K$，分析在固定 $K$ 和 $L$ 时 $n \to \infty$ 的极限，并尝试令 $K, L \to \infty$。

关键结果与猜想
论文提出了关于配分函数精确极限的一个猜想。

• 猜想： 在假设存在正谱隙（即 $\sigma^2 = 1 - \max_{i \ge 2} \lambda_i^2 > 0$）且特征函数是 Lipschitz 连续的条件下，极限由算子 $I - T^2$ 的 Fredholm 行列式的平方根的倒数给出：
  $$\lim_{n \to \infty} e^{n\Gamma_0} L_n = \frac{1}{\sqrt{\det_F(I - T^2)}} = \prod_{n=1}^\infty (1 - \lambda_n^2)^{-1/2}$$

• 部分证据： 作者提供了一个部分证明，表明：
  $$\lim_{K, L \to \infty} \lim_{n \to \infty} D_n^{(L)} = \frac{1}{\sqrt{\det_F(I - T^2)}}$$
  其中 $D_n^{(L)}$ 是 $D_n$ 的截断近似。证明过程利用了 Hermite 多项式的性质以及完全图中完美匹配的组合学，来评估截断和的极限。具体而言，它表明除非指标构成完美匹配，否则展开项将消失，这导致了与在零点处求值的 Hermite 多项式的矩相关的乘积。

局限性与声明
论文明确承认其证明是不完整的。关键缺陷在于极限交换问题：作者展示了当在 $n \to \infty$ 之后 令 $K, L \to \infty$ 时极限成立，但猜想要求在 $K, L \to \infty$ 之后 令 $n \to \infty$。建立这一点需要为离散化和截断误差提供一致的误差界限，而目前的论证无法提供。

作者将这一困难归因于不放回抽样（置换结构）与有放回抽样（独立随机变量）之间的组合复杂性，后者是相关结果 [HLP20] 中的设定。虽然直觉表明该猜想是正确的（通过假设在确定性置换情况下极限高斯波动的方差为零），但目前仍缺乏严格的误差界限。

意义
本文旨在完善对具有固定模式的大型随机置换缩放极限的理解。通过对配分函数的亚指数修正项提出精确公式的猜想，它将 Mallows 模型的组合结构与源自最优传输（薛定谔桥）的积分算子的谱性质联系起来。若该猜想被证明，它将为这类模型的完整配分函数表征提供依据，从而架起统计估计、随机置换与最优传输理论之间的桥梁。