Stratification and optimal resampling for sequential Monte Carlo¶

作者: Yichao Li, Wenshuo Wang, Ke Deng, Jun S Liu
来源: Biometrika
主题: 统计计算 / 算法
相关性: 3/10
机构绿灯: Tsinghua University（US News 前 50，免分进入精读）
链接: 期刊页 · arXiv

一、领域脉络与小综述¶

这个方向是什么¶

这个子方向是序贯蒙特卡洛（SMC）算法中的重采样步骤。SMC（又称粒子滤波）是一类通过大量加权粒子（样本）来近似复杂动态系统后验分布的算法。其核心循环是：预测（根据系统模型向前传播粒子）→ 更新（根据新观测调整粒子权重）→ 重采样（根据权重重新抽取粒子，淘汰低权重粒子、复制高权重粒子，以缓解“权重退化”问题）。重采样步骤的设计直接决定了SMC算法的方差、收敛速率和计算成本。本文聚焦于：如何设计重采样方案，使得重采样后的粒子集在最小化方差和分布距离的意义上最优，并给出可实现的算法与收敛速率。

当前成熟度：这是一个高度成熟但仍有核心开放问题的方向。重采样方案（multinomial, residual, stratified, systematic）自1990年代起就被广泛使用，其基本性质（如条件方差比较）在2005年左右已被Douc等人厘清。但高维情形下的最优重采样策略及其收敛速率直到2017-2019年才由Gerber等人取得突破，而本文正是该突破的延续与深化。

发展脉络¶

奠基工作（1990s-2005）：SMC算法的基本框架由Gordon等人（1993）提出，其中重采样步骤使用最简单的multinomial resampling（多项分布抽样）。Douc, Cappé & Moulines (2005) [被引4] 系统比较了当时已有的重采样方案，证明residual resampling和stratified resampling的条件方差总是小于multinomial resampling，而systematic resampling则不一定。这奠定了重采样方差比较的基本框架。
主要进展（2012-2017）：两条线索并行发展。
线索A：最优传输视角。Reich (2013) [被引1] 将重采样重新解释为离散最优传输问题——寻找一个将原始粒子集映射到重采样粒子集的“传输方案”，使得某种代价（如Wasserstein距离）最小。这为后续的optimal transport resampling提供了理论基础。Webber (2019) [被引8] 进一步用重采样矩阵统一了各种方案，并识别出使误差最小的矩阵方案。
线索B：排序与分层策略。Gerber, Chopin & Whiteley (2017) [被引2] 是本文最直接的先驱。他们证明了：① 当粒子按其在\(\mathbb{R}\)上的状态排序后，stratified resampling的方差可降至\(O(N^{-(1+1/d)})\)（\(d=1\)时）；② 对于\(d>1\)，若先用Hilbert曲线对粒子排序再进行分层重采样，方差为\(O(N^{-(1+1/d)})\)；③ 他们猜想这个速率可以改进到\(O(N^{-(1+2/d)})\)。同时，He & Owen (2016) [被引3] 研究了Hilbert曲线在拟蒙特卡洛积分中的应用，证明对Lipschitz连续被积函数，均方误差可达\(O(n^{-1-2/d})\)。
当前Frontier：本文（Li, Wang, Deng & Liu, 2024）直接回应了Gerber等人(2019)的猜想，将Hilbert曲线排序后分层重采样的方差从\(O(m^{-(1+1/d)})\)改进到\(O(m^{-(1+2/d)})\)，并证明该速率对有序分层重采样方案是最优的。同时，本文首次给出了Hilbert曲线重采样下Wasserstein距离的几乎必然界，并基于此推导出序贯拟蒙特卡洛（SQMC）的均方误差可达\(O(n^{-1-4/[d(d+4)]})\)——这是首个低于\(o(n^{-1})\)的SQMC收敛速率。

子线索聚类¶

重采样方差分析：Douc et al. (2005) [被引4] → Gerber et al. (2017) [被引2] → 本文。这条线索专注于推导不同重采样方案的条件方差表达式与上界，并寻找最小化方差的方案。
最优传输重采样：Reich (2013) [被引1] → Webber (2019) [被引8] → 本文（在一维情形下证明最优传输重采样与排序后分层重采样等价）。这条线索将重采样视为离散最优传输问题，追求某种分布距离的最小化。
Hilbert曲线与拟蒙特卡洛：He & Owen (2016) [被引3] → Gerber & Chopin (2015) [被引7] → 本文。这条线索利用Hilbert空间填充曲线将高维粒子映射到一维，从而利用一维排序与分层策略的优势，并与拟蒙特卡洛方法结合。
矩阵重采样框架：Hu et al. (2008) [被引9] → Webber (2019) [被引8] → 本文（提及但未深入）。这条线索用重采样矩阵统一描述各种方案，便于理论分析。

这个方向在追问的核心问题¶

重采样方差的最小可能速率是多少？ 对于\(d\)维粒子，是否存在一个重采样方案使得方差以\(O(m^{-(1+2/d)})\)或更快的速率衰减？本文回答了这个问题：对有序分层重采样，\(O(m^{-(1+2/d)})\)是最优的。
重采样后的分布距离（如Wasserstein距离）如何控制？ 这直接关系到SMC算法的整体收敛性。本文给出了Hilbert曲线重采样下Wasserstein距离的几乎必然界。
如何将重采样改进转化为SMC/SQMC的整体收敛速率提升？ 本文首次给出了SQMC低于\(o(n^{-1})\)的均方误差速率。
计算复杂度与统计精度的权衡：最优传输重采样（如Sinkhorn算法）的计算复杂度为\(O(m^2)\)，而分层重采样仅为\(O(m \log m)\)。如何在保持统计精度的同时降低计算成本？

⚠️ 作者的Framing¶

作者把缺口frame成：Gerber等人(2019)证明了Hilbert曲线排序后分层重采样的方差为\(O(m^{-(1+1/d)})\)，并猜想该速率可改进至\(O(m^{-(1+2/d)})\)。本文证实了这个猜想，并进一步给出了Wasserstein距离的几乎必然界和SQMC的改进收敛速率。作者将本文定位为“对Gerber等人猜想的完整解答”以及“SQMC收敛理论的重要推进”。

被淡化或回避的竞争路线： - 最优传输重采样的精确解（而非Sinkhorn近似）：作者承认精确最优传输的计算复杂度为\(O(m^3 \log m)\)，但仅用一句话带过，未深入讨论其与Hilbert曲线分层重采样的实际性能对比。 - 矩阵重采样框架（Webber, 2019）：作者将其归入“matrix resampling methods”并引用，但未在本文中与之进行理论对比（如Webber框架下的最优方案是否也能达到\(O(m^{-(1+2/d)})\)？）。 - 其他空间填充曲线（如Peano曲线、Moore曲线）：作者仅使用Hilbert曲线，未讨论其他曲线是否可能带来更好的速率。

什么明显该被引/该存在、却没出现在intro里？ - Sinkhorn距离的收敛性质：Cuturi (2013) [被引10] 和 Benamou et al. (2015) [被引11] 被引用为“近似最优传输的\(O(m^2)\)算法”，但未讨论这些近似解对重采样方差或Wasserstein距离的影响。这是一个值得研究者去查的缺口：Sinkhorn近似解是否也能达到\(O(m^{-(1+2/d)})\)的方差速率？ - 粒子滤波的均方误差理论：如Del Moral (2004) 的经典结果（粒子滤波的\(L^p\)收敛性），本文未引用。这可能是因为本文聚焦于重采样步骤本身，而非整个SMC算法。

张力¶

未见明显对立引用。所有被引工作基本一致地认为：排序（尤其是Hilbert曲线排序）能降低重采样方差，且分层重采样优于简单多项重采样。Gerber等人(2019)的猜想与本文的证明构成了一个自然的“猜想→证明”链条，而非矛盾。

二、最核心、最简单的例子 / 数学问题¶

第一步：符号、模型、可观测数据交代清楚¶

符号： - \(m\)：重采样后粒子的数量（通常等于原始粒子数\(N\)，但本文允许\(m \neq N\)）。 - \(\{x_i\}_{i=1}^N\)：原始粒子集，每个\(x_i \in \mathbb{R}^d\)。 - \(\{w_i\}_{i=1}^N\)：原始粒子的权重，满足\(w_i \geq 0\)，\(\sum_{i=1}^N w_i = 1\)。 - \(\{n_i\}_{i=1}^N\)：重采样后每个原始粒子被复制的次数，满足\(n_i \in \{0,1,\dots,m\}\)，\(\sum_{i=1}^N n_i = m\)。重采样后的粒子集为\(\{x_i\text{ 被复制 }n_i\text{ 次}\}\)。 - \(\hat{P}_N = \sum_{i=1}^N w_i \delta_{x_i}\)：原始加权经验分布。 - \(\tilde{P}_N = \frac{1}{m} \sum_{i=1}^N n_i \delta_{x_i}\)：重采样后的经验分布（等权重）。 - \(\text{Var}_{\text{resamp}}\)：重采样方差，定义为\(\mathbb{E}\left[\sum_{i=1}^N (n_i - m w_i)^2\right]\)，衡量重采样引入的随机波动。 - \(W_p(\hat{P}_N, \tilde{P}_N)\)：\(p\)-Wasserstein距离，衡量两个分布之间的传输代价。 - \(E(\hat{P}_N, \tilde{P}_N)\)：能量距离（Energy Distance），定义为\(\mathbb{E}\left[2\|\tilde{X} - \tilde{X}'\| - \|\tilde{X} - X\| - \|\tilde{X}' - X'\|\right]\)，其中\(X \sim \hat{P}_N\)，\(\tilde{X}, \tilde{X}' \sim \tilde{P}_N\)独立。

模型： - 数据生成机制：SMC算法在时间\(t\)步产生一组加权粒子\(\{x_i, w_i\}\)。重采样步骤的目标是：给定\(\{x_i, w_i\}\)，产生一个新的等权重粒子集\(\{x_i\text{ 被复制 }n_i\text{ 次}\}\)，使得新粒子集尽可能“接近”原始加权粒子集。 - 已知量：\(\{x_i, w_i\}\)完全已知（由SMC算法前序步骤计算得出）。 - 要估的对象：重采样方案（即如何从\(\{w_i\}\)生成\(\{n_i\}\)），使得某种损失（方差、Wasserstein距离、能量距离）最小。

可观测数据： - 可直接观测：原始粒子位置\(\{x_i\}\)和权重\(\{w_i\}\)。重采样后的粒子位置（即原始粒子的复制）也是直接可观测的。 - 潜在/不可观测：重采样方案本身是一个随机算法，其随机性来源于从多项分布/分层分布/系统分布中抽样。不同方案对应不同的\(\{n_i\}\)的联合分布。我们无法观测到“如果用了另一种方案会得到什么”，只能通过理论分析比较不同方案的期望性质。

第二步：最小内核——一维情形下的最优重采样¶

最简特例：\(d=1\)（一维粒子），\(m=N\)（重采样后粒子数等于原始粒子数），且原始粒子权重相等（\(w_i = 1/N\)）。这个特例剥离了权重不均和维度诅咒，让我们看清重采样问题的核心。

在这个特例下： - 原始粒子集：\(\{x_i\}_{i=1}^N\)，\(x_i \in \mathbb{R}\)，权重均为\(1/N\)。 - 重采样目标：从\(\{x_i\}\)中有放回地抽取\(N\)个粒子，使得每个粒子被抽中的概率为\(1/N\)。最简单的方案是multinomial resampling：独立地从\(\{1,\dots,N\}\)中抽取\(N\)个索引，每个索引被抽中的概率为\(1/N\)。这等价于\(\{n_i\}\)服从多项分布\(\text{Multinomial}(N; 1/N, \dots, 1/N)\)。

核心问题：能否设计一个重采样方案，使得重采样后的经验分布\(\tilde{P}_N\)比multinomial resampling更“接近”原始经验分布\(\hat{P}_N\)？

关键观察：如果粒子\(x_i\)已经按大小排序（\(x_1 \leq x_2 \leq \dots \leq x_N\)），那么stratified resampling（分层重采样）可以大幅降低方差。具体做法： 1. 将区间\([0,1]\)等分为\(N\)个小区间：\([0, 1/N), [1/N, 2/N), \dots, [(N-1)/N, 1)\)。 2. 对每个小区间\(k\)，独立地从均匀分布\(U[(k-1)/N, k/N)\)中抽取一个随机数\(u_k\)。 3. 令\(n_i\)等于\(u_k\)落在第\(i\)个粒子的累积权重区间内的次数（这里由于权重相等，累积权重区间为\([(i-1)/N, i/N)\)）。

为什么这能降低方差？ 在multinomial resampling中，每个粒子被抽中的次数\(n_i\)服从二项分布\(\text{Binomial}(N, 1/N)\)，方差为\(1 - 1/N\)。在stratified resampling中，由于每个小区间恰好贡献一个随机数，\(n_i\)的分布被“强制”为：要么是0（如果该小区间对应的随机数落在其他粒子的区间），要么是1（如果落在自己的区间），要么偶尔是2（如果随机数落在边界附近）。实际上，可以证明：对于等权重情形，stratified resampling保证每个\(n_i \in \{0,1,2\}\)，且\(\text{Var}(n_i) \leq 1/N\)——比multinomial的方差小了一个数量级。

本文的核心发现（在一维情形下）： 1. 最优传输重采样与排序后分层重采样等价：在一维且粒子已排序的条件下，求解最优传输问题（最小化2-Wasserstein距离）得到的重采样方案，恰好就是stratified resampling。这意味着stratified resampling不仅方差小，而且在分布距离的意义上也是最优的。 2. 两者同时最小化重采样方差和期望平方能量距离：在所有无偏重采样方案（即\(\mathbb{E}[n_i] = m w_i\)）中，排序后分层重采样（等价于最优传输重采样）使得\(\text{Var}_{\text{resamp}}\)和\(\mathbb{E}[E(\hat{P}_N, \tilde{P}_N)]\)同时达到最小。

这个特例揭示了整篇论文的核心思路：排序 + 分层 = 最优。对于\(d>1\)，我们无法直接对高维粒子排序，但可以通过Hilbert曲线将粒子映射到一维，然后在一维空间上应用排序+分层策略。这就是本文从一维推广到高维的桥梁。

三、这篇论文做了什么¶

三句话¶

研究了什么问题：序贯蒙特卡洛算法中重采样步骤的最优设计问题，特别是如何通过Hilbert曲线排序与分层重采样达到最优的方差收敛速率和Wasserstein距离控制。
核心工具/方法：Hilbert空间填充曲线（将高维粒子映射到一维）、分层重采样（stratified resampling）、最优传输理论（optimal transport）、能量距离（energy distance）、拟蒙特卡洛（quasi-Monte Carlo）。
主要结论：① 在一维情形下，证明最优传输重采样与排序后分层重采样等价，且两者同时最小化重采样方差和期望平方能量距离；② 对于\(d\)维情形，Hilbert曲线排序后分层重采样的方差为\(O(m^{-(1+2/d)})\)，优于已知的\(O(m^{-(1+1/d)})\)，且该速率对有序分层重采样方案是最优的；③ 给出Hilbert曲线重采样下Wasserstein距离的几乎必然界；④ 基于此，SQMC的均方误差可达\(O(n^{-1-4/[d(d+4)]})\)，首次低于\(o(n^{-1})\)。

关键设定与假设¶

完整记号（在第二节基础上补充）： - \(m\)：重采样后粒子数（一般\(m \leq N\)，但本文主要考虑\(m=N\)）。 - \(\{x_i\}_{i=1}^N \subset \mathbb{R}^d\)：原始粒子。 - \(\{w_i\}_{i=1}^N\)：权重，\(\sum w_i = 1\)。 - \(\{n_i\}_{i=1}^N\)：复制次数，\(\sum n_i = m\)。 - \(\hat{P}_N = \sum w_i \delta_{x_i}\)，\(\tilde{P}_N = \frac{1}{m} \sum n_i \delta_{x_i}\)。 - \(H: [0,1]^d \to [0,1]\)：Hilbert曲线映射（将\(d\)维超立方体连续地映射到一维区间）。 - \(\{\pi(i)\}_{i=1}^N\)：粒子按\(H(x_i)\)排序后的排列（即\(H(x_{\pi(1)}) \leq H(x_{\pi(2)}) \leq \dots \leq H(x_{\pi(N)})\)）。 - \(c_i = \sum_{j=1}^i w_{\pi(j)}\)：排序后粒子的累积权重。

关键假设： 1. 粒子位置有界：所有\(x_i\)位于\([0,1]^d\)内。这是Hilbert曲线定义的前提，也是Wasserstein距离分析的标准假设。实际中可通过缩放满足。 2. Hilbert曲线的Lipschitz性质：Hilbert曲线\(H\)是\(\alpha\)-Hölder连续的，其中\(\alpha = 1/d\)。即\(\|H(x) - H(y)\| \leq C \|x - y\|^{1/d}\)。这是推导方差速率的关键——它保证了在一维排序中“接近”的粒子在原始高维空间中也“接近”。 3. 权重非退化：权重\(w_i\)严格正且\(\sum w_i = 1\)。这是重采样算法可执行的前提。 4. 无偏性：所有考虑的重采样方案满足\(\mathbb{E}[n_i] = m w_i\)（无偏性）。这是比较方差和能量距离的基础。

相比已有文献的强化/放宽： - 强化：Gerber等人(2019)证明了\(O(m^{-(1+1/d)})\)的方差上界，本文将其改进到\(O(m^{-(1+2/d)})\)，并证明最优性。 - 放宽：本文的Wasserstein距离几乎必然界不要求粒子独立同分布，只要求粒子位置有界——这更符合SMC的实际场景（粒子是相关的）。

主要结果¶

定理1（一维情形下的等价性与最优性）： - 陈述：设\(d=1\)，粒子已按\(x_i\)排序。则最优传输重采样（最小化2-Wasserstein距离）与排序后分层重采样等价。两者同时最小化重采样方差\(\text{Var}_{\text{resamp}}\)和期望平方能量距离\(\mathbb{E}[E^2(\hat{P}_N, \tilde{P}_N)]\)。 - 直觉：在一维且排序的条件下，最优传输问题退化为“分位数匹配”——每个重采样粒子应落在原始分布的分位数区间内，这正是分层重采样所做的。能量距离的最小化则源于分层重采样对“配对距离”的最优控制。 - 必要条件：粒子必须已排序。如果粒子未排序，分层重采样可能退化为systematic resampling，其方差可能更大（Douc et al., 2005）。 - 解决的技术难点：将连续最优传输的结论（Brenier定理）推广到离散情形，并证明离散最优传输解恰好对应分层重采样。

定理2（高维情形下的方差速率）： - 陈述：设粒子位于\([0,1]^d\)，权重任意。使用Hilbert曲线排序后分层重采样，重采样方差满足：

\[\text{Var}_{\text{resamp}} = O(m^{-(1+2/d)})\]

且该速率对有序分层重采样方案是最优的（即存在常数\(c>0\)使得方差至少为\(c m^{-(1+2/d)}\)）。 - 直觉：Hilbert曲线的Hölder连续性（\(\alpha = 1/d\)）意味着：在一维排序中，相邻粒子的高维距离最多为\(O(\Delta^{1/d})\)，其中\(\Delta\)是一维排序上的间隔。分层重采样将一维区间等分为\(m\)份，每份长度\(1/m\)，因此每份内粒子的高维“直径”为\(O(m^{-1/d})\)。这导致重采样误差的“有效维度”从\(d\)降低到\(1\)，从而方差从\(O(m^{-1})\)（无排序）提升到\(O(m^{-(1+2/d)})\)。 - 必要条件：粒子位置有界于\([0,1]^d\)；Hilbert曲线的Hölder连续性。 - 解决的技术难点：证明\(O(m^{-(1+2/d)})\)的上界需要对Hilbert曲线的几何性质有精细刻画——特别是Hilbert曲线将\([0,1]^d\)划分为\(m\)个“几乎等体积”的连通区域，每个区域对应一维排序上的一个连续区间。下界（最优性）的证明需要构造一个反例，使得任何有序分层重采样方案都无法超越该速率。

定理3（Wasserstein距离的几乎必然界）： - 陈述：在定理2的设定下，对任意\(p \geq 1\)，存在常数\(C\)（依赖于\(d, p\)）使得：

\[\limsup_{m \to \infty} m^{1/d} W_p(\hat{P}_N, \tilde{P}_N) \leq C \quad \text{几乎必然成立}\]

- 直觉：Wasserstein距离的速率\(O(m^{-1/d})\)比分母速率\(O(m^{-(1+2/d)})\)慢，这是因为Wasserstein距离衡量的是“位置误差”而非“计数误差”。即使每个粒子的复制次数精确等于期望值，粒子位置的离散性也会导致\(O(m^{-1/d})\)的Wasserstein误差。 - 必要条件：同定理2。 - 解决的技术难点：将一维排序上的Wasserstein距离控制（通过分层重采样保证）通过Hilbert曲线的Hölder连续性“提升”到高维空间。

定理4（SQMC的均方误差速率）： - 陈述：对于\(d>1\)，若使用Hilbert曲线重采样并选择特定的低差异序列（如Sobol序列），则SQMC的均方误差（MSE）满足：

\[\text{MSE} = O(n^{-1-4/[d(d+4)]})\]

其中\(n\)是粒子数。这是首个低于\(o(n^{-1})\)的SQMC收敛速率。 - 直觉：SQMC的误差由两部分组成：① 重采样引入的误差（\(O(m^{-(1+2/d)})\)）；② 拟蒙特卡洛积分误差（\(O(n^{-1-2/d})\)，对Lipschitz函数）。两者权衡后得到上述速率。当\(d\)较小时（如\(d=2\)），速率为\(O(n^{-1.33})\)；当\(d\)较大时，速率趋近\(O(n^{-1})\)但始终低于\(o(n^{-1})\)。 - 必要条件：使用Hilbert曲线重采样；使用特定低差异序列（如Sobol序列）；被积函数满足一定的光滑性条件（Lipschitz连续）。 - 解决的技术难点：将重采样误差与拟蒙特卡洛积分误差的联合分析——两者不是独立的，需要精细的耦合论证。

证明路线与技术技巧¶

整体路线（以定理2为核心）：

步骤1：将重采样方差分解为“层内方差”之和。分层重采样将\([0,1]\)（Hilbert曲线映射后的一维空间）等分为\(m\)个区间，每个区间内独立抽样。重采样方差可以写成每个区间内粒子复制次数的方差之和。
步骤2：利用Hilbert曲线的Hölder连续性，将层内粒子数控制与层内粒子高维距离联系起来。每个一维区间\(I_k\)对应高维空间中的一个区域\(H^{-1}(I_k)\)。由于Hilbert曲线是\(1/d\)-Hölder连续的，\(H^{-1}(I_k)\)的直径最多为\(O(m^{-1/d})\)。这意味着每个区间内粒子的高维位置差异很小。
步骤3：证明每个区间内粒子数的方差为\(O(m^{-2/d})\)。关键引理：对于任意区间\(I_k\)，其包含的粒子总权重\(W_k = \sum_{i: H(x_i) \in I_k} w_i\)满足\(W_k = 1/m + O(m^{-1-1/d})\)（即每个区间几乎恰好包含\(1/m\)的总权重）。这个引理的证明依赖于Hilbert曲线的“几乎等体积”性质——它将\([0,1]^d\)映射到\([0,1]\)时，保持体积近似不变（偏差为\(O(m^{-1/d})\)）。
步骤4：将层内方差求和。\(m\)个区间的方差之和为\(m \times O(m^{-2/d}) = O(m^{-(1+2/d)})\)。

关键跳跃点： - 从\(O(m^{-(1+1/d)})\)到\(O(m^{-(1+2/d)})\)的改进：Gerber等人(2019)的证明中，对每个区间内粒子数的方差控制是\(O(m^{-1/d})\)，而本文改进到\(O(m^{-2/d})\)。这个改进来源于对Hilbert曲线“几乎等体积”性质的更精细使用——Gerber等人只用了Hölder连续性，而本文进一步利用了Hilbert曲线的等体积性（即\(H\)的Jacobian几乎处处为1）。 - 最优性的证明：需要构造一个反例分布，使得任何有序分层重采样方案都无法超越\(O(m^{-(1+2/d)})\)。这个反例利用了Hilbert曲线的“最坏情况”几何——当粒子集中在Hilbert曲线的“拐点”附近时，分层重采样无法有效区分这些粒子。

技术技巧点名： - Hilbert曲线的等体积性质：\(H\)的Jacobian几乎处处为1，这意味着\(H\)将\([0,1]^d\)上的Lebesgue测度映射到\([0,1]\)上的Lebesgue测度。这是本文改进方差速率的核心工具。 - 能量距离的解析表达式：用于证明一维情形下的最优性。能量距离可以写成\(\mathbb{E}[\|X - X'\|] - 2\mathbb{E}[\|X - \tilde{X}\|] + \mathbb{E}[\|\tilde{X} - \tilde{X}'\|]\)，其中\(X, X' \sim \hat{P}_N\)，\(\tilde{X}, \tilde{X}' \sim \tilde{P}_N\)。通过交换期望与求和，可以将其表示为复制次数\(\{n_i\}\)的二次型。 - 几乎必然收敛的Borel-Cantelli论证：用于定理3的Wasserstein距离几乎必然界。通过证明\(\sum_{m=1}^\infty \mathbb{P}(m^{1/d} W_p > \epsilon) < \infty\)，然后应用Borel-Cantelli引理。 - SQMC误差的分解与权衡：将SQMC的MSE分解为重采样误差和QMC积分误差，然后通过选择重采样粒子数\(m\)（作为\(n\)的函数）来平衡两者，得到最优速率。

真实例子与应用¶

本文包含一个真实数据例子： - 数据：科罗拉多地区的地形图（topographical map of a Colorado region），来自Givens & Hoeting (2013) [被引5]。 - 场景：使用SMC算法对一个状态空间模型进行滤波，其中状态是二维位置（经度、纬度），观测是地形高度。这是一个典型的非线性非高斯滤波问题。 - 方法应用：将本文提出的Hilbert曲线重采样（Hilbert-curve resampling, HCR）与以下baseline对比： - Multinomial resampling (MNR) - Stratified resampling (STR) - Systematic resampling (SYS) - Residual resampling (RES) - Optimal transport resampling (OTR, 使用Sinkhorn近似) - 结果： - 方差：HCR的估计方差显著低于MNR、SYS和RES，与STR和OTR相当。 - 计算时间：HCR的计算时间与STR、SYS、RES相当（\(O(N \log N)\)），远低于OTR（\(O(N^2)\)）。 - 有效样本量（ESS）：HCR的ESS衰减最慢，表明其粒子多样性保持得最好。 - 这个例子想说明什么：HCR在统计精度上达到了与最优传输重采样（OTR）相当的水平，但计算成本低了一个数量级（\(O(N \log N)\) vs \(O(N^2)\)）。这验证了理论结果：HCR在方差意义上接近最优，同时保持了分层重采样的计算效率。

🔎 结论是否比证明窄¶

定理2的“最优性”声明：本文证明的是“对有序分层重采样方案，\(O(m^{-(1+2/d)})\)是最优的”。这个声明不排除存在非有序分层方案（如基于其他空间填充曲线或完全不同的策略）能达到更快的速率。作者在文中明确写了“for ordered stratified resampling schemes”，但读者可能忽略这个限定。
定理4的SQMC速率：该速率\(O(n^{-1-4/[d(d+4)]})\)是在特定低差异序列（如Sobol序列）和特定光滑性条件（Lipschitz连续）下证明的。作者在文中提到“if a specific low-discrepancy set is chosen”，但未明确说明这个“specific”集合是什么，也未证明对所有低差异序列都成立。这是一个值得注意的窄化。
Wasserstein距离的几乎必然界：定理3给出的是\(m^{1/d} W_p\)的有界性，而非收敛到0的速率。作者在文中提到“这个界可能不是紧的”，暗示可能存在更快的收敛速率（如\(O(m^{-2/d})\)），但未证明。

四、开放问题（扎根具体语句）¶

非有序分层重采样方案能否超越\(O(m^{-(1+2/d)})\)？ 本文证明的是“有序分层重采样”的最优性（定理2）。是否存在基于其他空间填充曲线（如Peano曲线）或完全不同的策略（如自适应网格）的方案能达到更快的方差速率？扎根：定理2的陈述中明确限定“for ordered stratified resampling schemes”。
Wasserstein距离的紧界是多少？ 本文给出的是\(O(m^{-1/d})\)的几乎必然界（定理3），但作者在文中提到“这个界可能不是紧的”。能否证明更快的速率（如\(O(m^{-2/d})\)）？扎根：定理3后的讨论：“This bound may not be tight; a sharper bound is left for future work.”
SQMC的MSE速率能否进一步改进？ 本文给出的\(O(n^{-1-4/[d(d+4)]})\)依赖于重采样误差与QMC积分误差的特定权衡。如果使用更光滑的被积函数（如\(C^2\)而非Lipschitz），或者使用更优的低差异序列，速率能否提升？扎根：定理4的证明中假设被积函数为Lipschitz连续，且低差异序列为Sobol序列。作者在结论中写道：“It remains open whether a better rate can be achieved under stronger smoothness assumptions.”
Hilbert曲线重采样在更一般的SMC算法（如粒子吉布斯、粒子边际似然估计）中的表现如何？ 本文的实证例子仅涉及标准滤波问题。在更复杂的SMC变体（如PMCMC、SMC²）中，Hilbert曲线重采样的方差优势和计算效率是否仍然保持？扎根：本文的结论部分：“Extending the theoretical results to more complex SMC algorithms, such as particle Markov chain Monte Carlo, is an interesting direction for future research.”

提醒：要确认第1条是否是真gap，建议去读Gerber等人(2019)的结论部分，看他们是否也讨论了其他排序策略；同时检索近5年关于“space-filling curve resampling”的论文，看是否有其他曲线被提出。如果多篇论文都指向“Hilbert曲线是最优的”，则这是一个共识（真gap）；如果存在互相矛盾的结论（如Peano曲线在某些设定下更好），则是一个机会。

Maintained by 陈星宇 · Homepage · Source on GitHub