Exact bounds of Spearman’s footrule in the presence of missing data with applications to independence testing¶
作者: Yijin Zeng, Niall Adams, Dean Bodenham
来源: Electronic Journal of Statistics
主题: 数理统计 / 假设检验
相关性: 6/10
链接: 期刊页 · arXiv
一、领域脉络与小综述¶
这个方向是什么： 这个子方向要解决的根本统计问题是：当多维随机变量的部分分量缺失时，如何在不引入不可验证的分布假设的前提下，对基于完整数据定义的统计量（如秩相关系数）进行有效的推断与检验。当前该方向的成熟度处于"有大量经验性插补方法，但严格非参数无分布推断的理论工具稀缺"的阶段——多数方法依赖 MAR（Missing At Random）假设，一旦缺失机制偏离 MAR，第一类错误与估计偏差往往无法控制。
发展脉络： 从 introduction 与参考文献串出的线索如下： - 奠基与问题意识：经典缺失数据文献（Dong & Peng 2013; Heymans & Twisk 2022）确立了 MCAR / MAR / MNAR 的三分法，并指出多重插补与最大似然在 MAR 下可恢复无偏性与效率，但在 MNAR 下失效。这是所有后续工作的起点。 - 主要进展与瓶颈：近年应用领域（如 mHealth RCT、临床试验）反复实证表明，真实数据极可能为 MNAR（Goldberg et al. 2021; Cook & Zea 2019）。Madley-Dowd et al. (2019) 通过模拟指出，缺失比例本身不应作为是否使用 MI 的判据，FMI（Fraction of Missing Information）才是效率的更好指标——但这依然停留在 MAR 框架内。Raykov et al. (2014) 尝试在相关系数检验中引入辅助变量以放宽 MAR，但本质上仍是似然框架的延伸。瓶颈在于：这些主流方法要么要求 MAR，要么要求正确指定缺失模型，无法在"对缺失机制完全无知"时给出有保证的推断。 - 当前 frontier 与本文位置：作者将本文定位为跳出 MAR / 模型指定依赖的路线。他们不试图估计缺失值的期望或分布，而是计算目标统计量（Spearman's footrule）在所有可能插补值下的精确上下界，并基于界构造在任意缺失机制下控制第一类错误的检验。本文处于"非参数最坏情况推断"的 frontier，与敏感性分析（如 Cook & Zea 2019 提出的固定值替换与模型敏感性）形成对照——本文的界是精确的、无需扫描参数的。
子线索聚类： 被引文献大致落在三条子线索上： 1. 似然 / MI 框架下的缺失推断（Dong & Peng 2013; Madley-Dowd et al. 2019; Heymans & Twisk 2022）：在 MAR 下追求无偏与效率，核心工具是 EM / MI，承认 MNAR 下失效。 2. MNAR 下的敏感性分析（Goldberg et al. 2021; Cook & Zea 2019）：不假设 MAR，而是对缺失模型参数做网格扫描或固定值替换，看结论是否翻转。核心瓶颈是计算代价与参数空间的任意性。 3. 缺失下的相关性检验与估计（Raykov et al. 2014）：在 MAR 或辅助变量下做相关系数的估计与检验，仍依赖分布假设。
这个方向在追问的核心问题： 1. 在对缺失机制完全无知的设定下，能否为秩相关系数等非参数统计量给出精确的（而非渐近的、保守的）可能取值范围？ 2. 基于该范围，能否构造在任意缺失机制下严格控制第一类错误的检验？ 3. 精确界的计算代价是否可接受（多项式时间），且在缺失比例达到何种阈值时检验仍有实际功效？
当前主流方法（MI / FIML）的已知瓶颈是：在 MNAR 下既不控制偏差也不控制第一类错误；敏感性分析的瓶颈是缺乏精确界、依赖模型参数扫描。
⚠️ 作者的 framing： - 作者把缺口 frame 为：现有缺失数据下的独立性检验方法均依赖 MAR 或分布假设，无法在任意缺失下控制第一类错误；而本文的界是精确的、检验是无分布的、第一类错误是严格控制的。这让本文成为"显然的下一步"——从依赖假设走向无假设保证。 - 被淡化或回避的竞争路线：半参数效率界 / Debiasing 路线（如基于 Influence Function 的部分缺失推断）、M-估计的鲁棒界路线（如部分观测下 M-估计的 minimax 界）。这些路线同样追求对缺失机制的某种鲁棒性，但 intro 中未出现。 - 明显该被引却未出现的：秩统计量在部分观测下的渐近理论（如 Bhattacharya & Bickel 等关于部分缺失下 U-统计量的工作）、缺失下 minimax 界的文献（如 Robins et al. 关于 MNAR 下效率界的工作）。这是研究者值得去查的缺口——作者选择了一条纯组合 / 算法的路线，可能有意回避了与半参数理论的对话。
张力： 未见明显对立引用。Madley-Dowd et al. (2019) 强调"缺失比例大时 MI 仍可用（若 MAR）"，而 Cook & Zea (2019) 与 Goldberg et al. (2021) 强调"MNAR 下 MI 完全失效"——这两条在条件不同下结论相反，但作者并未正面讨论 MAR 与 MNAR 的分界，而是直接取最坏情况（任意缺失），绕过了这一张力。
二、最核心、最简单的例子 / 数学问题¶
第一步：符号、模型、可观测数据
- \(n\)：向量维度 / 样本量（对数个数）。
- \(X = (X_1, \dots, X_n)\)：\(n\) 维实值随机向量，分量互不相同（无结值假设）。
- \(Y = (Y_1, \dots, Y_n)\)：另一个 \(n\) 维实值随机向量，分量互不相同。
- \(R^X_i\)：\(X_i\) 的缺失指示变量，\(R^X_i = 1\) 表示 \(X_i\) 被观测到，\(R^X_i = 0\) 表示缺失。\(R^Y_i\) 同理。
- \(R_i = (R^X_i, R^Y_i)\)：第 \(i\) 对的缺失指示向量。\(R_i = (1,1)\) 表示第 \(i\) 对完全观测，其余三种组合为部分或完全缺失。
- \(O = \{(i, X_i, Y_i) : R_i = (1,1)\}\)：可观测的完整对集合，包含索引与观测值。
- \(M_X = \{i : R^X_i = 0\}\)：\(X\) 缺失的索引集；\(M_Y\) 同理；\(M_{XY} = \{i : R_i = (0,0)\}\) 为双缺失索引集。
- \(m\)：缺失对的总数，\(m = n - |O|\)。
- \(r(\cdot)\)：秩函数。对无结值向量 \(Z\)，\(r(Z_i)\) 为 \(Z_i\) 在 \(Z\) 所有分量中的排序位置（1 到 \(n\)）。
- Spearman's footrule \(D(X, Y)\)：要估的参数 / estimand，定义为 \(D(X, Y) = \sum_{i=1}^n |r(X_i) - r(Y_i)|\)。这是基于完整数据定义的总体量。
- 可观测数据：研究者实际能观测到的是 \(O\)（完整对的索引与值）以及 \(M_X, M_Y, M_{XY}\)（缺失位置的索引）。观测不到的是 \(M_X\) 中 \(X\) 的真实值、\(M_Y\) 中 \(Y\) 的真实值、\(M_{XY}\) 中 \(X\) 与 \(Y\) 的真实值——这些只能靠假设识别，本文不假设任何缺失机制，因此这些值可取任意实数（只要保持无结值）。
模型： 数据生成机制为：\((X, Y, R)\) 联合分布任意，唯一结构假设是 \(X\) 与 \(Y\) 的分量无结值（连续分布或几乎必然无结值）。缺失机制 \(R\) 的分布完全未知——可以是 MCAR、MAR、MNAR 或任意依赖 \((X, Y)\) 的机制。要估的对象是 \(D(X, Y)\)，但由于 \(m\) 个对的值缺失，\(D(X, Y)\) 的真实值无法计算。
第二步：最小内核
本文的最小内核是一个组合优化问题：给定 \(n\) 个位置中 \(m\) 个的秩未知（但已知它们必须取 \(1\) 到 \(n\) 中尚未被观测秩占据的那些值，且互不相同），求 \(\sum_{i=1}^n |r(X_i) - r(Y_i)|\) 在所有合法秩赋值下的最小值与最大值。
最简特例：\(n=3\)，仅第 3 对双缺失（\(R_3 = (0,0)\)），第 1、2 对完全观测。 - 观测到：\((X_1, Y_1)\) 与 \((X_2, Y_2)\)，由此可算出 \(r(X_1), r(Y_1), r(X_2), r(Y_2)\)。假设 \(r(X_1)=1, r(Y_1)=2, r(X_2)=2, r(Y_2)=1\)。 - 缺失：\(r(X_3)\) 与 \(r(Y_3)\)。已知它们必须取剩余秩 \(\{3\}\)（因为 1, 2 已被观测对占据）。 - 因此 \(r(X_3) = 3, r(Y_3) = 3\) 是唯一合法赋值。 - Footrule 值：\(|1-2| + |2-1| + |3-3| = 2\)。此时上下界重合，缺失无影响。
稍复杂的特例：\(n=4\)，第 3 对缺 \(X\)（\(R_3=(0,1)\)），第 4 对缺 \(Y\)（\(R_4=(1,0)\)），第 1、2 对完全观测。 - 观测到：\(r(X_1), r(Y_1), r(X_2), r(Y_2), r(Y_3), r(X_4)\)。假设观测秩为 \(r(X_1)=1, r(Y_1)=1, r(X_2)=2, r(Y_2)=3, r(Y_3)=4, r(X_4)=3\)。 - 已被占据的 \(X\) 秩：\(\{1, 2, 3\}\)；剩余 \(X\) 秩：\(\{4\}\)。因此 \(r(X_3)=4\)（唯一选择）。 - 已被占据的 \(Y\) 秩：\(\{1, 3, 4\}\)；剩余 \(Y\) 秩：\(\{2\}\)。因此 \(r(Y_4)=2\)（唯一选择）。 - Footrule 值完全确定：\(|1-1| + |2-3| + |4-4| + |3-2| = 0 + 1 + 0 + 1 = 2\)。
真正体现困难的最简例子：\(n=4\)，第 3、4 对双缺失（\(R_3=R_4=(0,0)\)），第 1、2 对完全观测。 - 观测到：\(r(X_1)=1, r(Y_1)=2, r(X_2)=2, r(Y_2)=1\)。 - 已被占据的 \(X\) 秩：\(\{1,2\}\)；剩余 \(X\) 秩：\(\{3,4\}\)。\(r(X_3)\) 与 \(r(X_4)\) 必须取 3 与 4 的某种排列（2 种选择）。 - 已被占据的 \(Y\) 秩：\(\{1,2\}\)；剩余 \(Y\) 秩：\(\{3,4\}\)。\(r(Y_3)\) 与 \(r(Y_4)\) 必须取 3 与 4 的某种排列（2 种选择）。 - 合法赋值共 \(2 \times 2 = 4\) 种。Footrule 值为： - \((r(X_3)=3, r(X_4)=4, r(Y_3)=3, r(Y_4)=4)\)：\(|1-2|+|2-1|+|3-3|+|4-4| = 2\) - \((3, 4, 4, 3)\)：\(|1-2|+|2-1|+|3-4|+|4-3| = 4\) - \((4, 3, 3, 4)\)：\(|1-2|+|2-1|+|4-3|+|3-4| = 4\) - \((4, 3, 4, 3)\)：\(|1-2|+|2-1|+|4-4|+|3-3| = 2\) - 下界 = 2，上界 = 4。这就是本文要算的东西：在所有合法秩赋值下，footrule 的精确最小值与最大值。
核心数学困难：当 \(m\) 较大时，合法赋值的数量是 \((m!)^2\) 级别（若全为双缺失），穷举不可行。本文的核心贡献是给出 \(O(n^2)\) 与 \(O(n^3)\) 的算法精确计算下界与上界，而非渐近近似或保守界。
三、这篇论文做了什么¶
三句话： ① 研究了在部分观测向量下 Spearman's footrule 的精确上下界计算问题，并基于界构造任意缺失机制下控制第一类错误的独立性检验。 ② 核心工具是组合优化与贪心 / 约束传播算法：下界通过顺序贪心插补使得 footrule 非增，上界通过逐步施加秩一致性约束缩小合法赋值集。 ③ 主要结论是：下界与上界可在 \(O(n^2)\) 与 \(O(n^3)\) 时间内精确计算，且基于下界的检验在任意缺失机制下严格控制第一类错误，模拟显示缺失对比例低于 15% 时检验有良好功效。
关键设定与假设： - 无结值假设：\(X\) 与 \(Y\) 的分量几乎必然互不相同。这是 Spearman's footrule 定义的基础，也是秩赋值唯一性的保证。相比已有文献（如经典秩相关理论），这是标准假设，未放宽。 - 任意缺失机制：\(R\) 的分布完全未知，可以是任意依赖 \((X, Y)\) 的机制。这是本文相比 MAR / MI 文献的核心放宽——不要求 MAR，也不要求可忽略性。 - 部分观测结构：允许 \(R_i\) 取 \((0,0), (0,1), (1,0), (1,1)\) 四种值，即允许单变量缺失与双变量缺失并存。相比只考虑双缺失或只考虑单缺失的工作，设定更一般。 - 独立性检验的原假设：\(H_0: X \perp Y\)。在此原假设下，\(X\) 的秩与 \(Y\) 的秩的联合分布为均匀分布上的独立排列，这是检验设计的分布基础。
主要结果：
定理 1（下界算法与精确性）： - 陈述：给定部分观测的 \(X\) 与 \(Y\)，存在 \(O(n^2)\) 算法计算 \(D(X, Y)\) 在所有合法插补下的精确下界 \(D_{\min}\)。 - 直觉：下界通过贪心策略达到——每次选择一个缺失位置，赋予使其对当前 footrule 增量最小的秩值。由于 footrule 是绝对值之和，局部最小赋值不会使后续赋值的增量更小，因此贪心顺序构造保证全局最小。 - 必要条件：无结值假设确保秩赋值无冲突；贪心策略的正确性依赖 footrule 的可加结构与绝对值的单调性。 - 技术难点：证明贪心策略确实达到全局最小，而非仅局部最小。作者通过交换论证证明：任何非贪心赋值可通过交换秩值转化为贪心赋值，且转化过程中 footrule 值非增。
定理 2（上界算法与精确性）： - 陈述：给定部分观测的 \(X\) 与 \(Y\)，存在 \(O(n^3)\) 算法计算 \(D(X, Y)\) 在所有合法插补下的精确上界 \(D_{\max}\)。 - 直觉：上界通过约束传播达到——初始合法赋值集为所有排列组合，然后逐步施加三类约束：（1）已观测秩不可再被赋值；（2）同一变量的缺失位置必须赋不同秩；（3）footrule 的分量约束（每个缺失对的绝对值差受已观测秩的上下界限制）。每施加一层约束，合法赋值集缩小，最终可精确计算最大值。 - 必要条件：约束传播的完整性依赖秩赋值的离散结构与绝对值的三角不等式性质。 - 技术难点：如何在多项式时间内遍历约束缩小后的合法赋值集并找到最大值。作者将上界问题转化为一个带约束的分配问题，利用匈牙利算法的变体在 \(O(n^3)\) 内求解。
定理 3（检验的第一类错误控制）： - 陈述：基于 \(D_{\min}\) 构造的独立性检验（拒绝规则为 \(D_{\min} < c_\alpha\)，其中 \(c_\alpha\) 为 \(H_0\) 下 footrule 的分布的分位数），在任意缺失机制下严格控制第一类错误 \(\leq \alpha\)。 - 直觉：在 \(H_0\) 下，\(D(X, Y)\) 的真实值（基于完整数据）服从已知分布。\(D_{\min} \leq D(X, Y)\) 恒成立（下界性质），因此 \(P(D_{\min} < c_\alpha) \leq P(D(X, Y) < c_\alpha) = \alpha\)。第一类错误被下界"保守化"——下界比真实值更小，因此更难拒绝，但保证了不超过 \(\alpha\)。 - 必要条件：\(H_0\) 下 footrule 的分布可精确计算或近似（无结值 + 独立排列假设下，footrule 的分布有已知表或渐近正态）。 - 技术难点：确保 \(D_{\min}\) 的计算不依赖任何缺失机制假设，且 \(D_{\min} \leq D(X, Y)\) 在所有合法插补下严格成立。
证明路线与技术技巧：
下界证明路线： 1. 定义贪心插补序列：按某个顺序逐个填补缺失位置，每次选择使当前 footrule 增量最小的合法秩值。 2. 证明贪心序列的 footrule 值非增：每次插补的增量 \(\leq 0\)（因为选择了最小增量）。 3. 交换论证：对任意非贪心合法插补，构造一系列秩交换操作，每步交换使 footrule 值非增，最终到达贪心插补。因此贪心插补的 footrule 值 \(\leq\) 任意合法插补的值，即为精确下界。 4. 计算复杂度分析：每步贪心选择需 \(O(n)\) 搜索（遍历剩余合法秩），共 \(m \leq n\) 步，总 \(O(n^2)\)。
上界证明路线： 1. 初始化合法赋值集：所有缺失位置的秩排列组合。 2. 施加约束层 1：已观测秩不可赋给缺失位置——将合法赋值集缩小为剩余秩的排列。 3. 施加约束层 2：同一变量的缺失位置赋不同秩——进一步缩小为无冲突排列。 4. 施加约束层 3：对每个缺失对 \((i)\)，\(|r(X_i) - r(Y_i)|\) 的上界受已观测秩的三角不等式约束——即 \(|r(X_i) - r(Y_i)| \leq |r(X_i) - r_{\text{obs}}| + |r_{\text{obs}} - r(Y_i)|\)，其中 \(r_{\text{obs}}\) 为已观测秩的极值。这给出每个缺失对绝对值差的上界。 5. 将约束后的最大值问题转化为带权分配问题：缺失位置为任务，剩余秩为资源，权重为绝对值差的上界。用匈牙利算法变体求解，复杂度 \(O(n^3)\)。 6. 证明该分配问题的解即为精确上界：约束传播已穷尽所有合法限制，因此分配问题的可行域等于合法插补集。
关键跳跃点： - 下界的交换论证：如何构造交换序列使得每步 footrule 非增。这是证明贪心全局最优的核心，作者利用了绝对值函数的凸性与秩的离散性质。 - 上界的约束传播完整性：如何确保三层约束已穷尽所有合法限制，没有遗漏。作者通过反证法证明：若存在合法插补不在约束传播后的可行域内，则它必违反某层约束，因此不合法。
技术技巧点名： - 贪心算法与交换论证：用于下界，保证局部最优即全局最优。 - 约束传播：用于上界，逐步缩小搜索空间。 - 匈牙利算法 / 分配问题：用于上界的最终求解，将组合优化转化为经典图论问题。 - 三角不等式：用于上界约束层 3，给出绝对值差的上界。 - 秩分布的精确 / 渐近计算：用于检验的临界值确定，依赖 \(H_0\) 下排列的均匀分布。
真实例子与应用： - 气候数据应用：论文使用 CRU TS 气候数据集（Harris et al. 2020），选取温度与降水量的网格时间序列。该数据集天然存在缺失（某些网格某些月份无观测），且缺失机制可能非随机（如偏远地区观测更易缺失）。 - 如何用上去：将温度与降水量的网格序列视为 \(X\) 与 \(Y\)，对每个网格计算部分观测下的 footrule 下界，然后执行独立性检验。 - 得到什么结果：在缺失对比例约 10% 的网格上，检验成功检测到温度与降水的依赖关系（拒绝 \(H_0\)）；在缺失比例超过 20% 的网格上，检验功效显著下降，无法拒绝。这与模拟结论（15% 阈值）一致。 - 想说明什么：验证理论（第一类错误控制 + 功效随缺失比例的变化），并展示在真实缺失机制（可能 MNAR）下方法的实用性。
模拟实验： - 设定：\(n=50, 100, 200\)，缺失比例从 5% 到 30%，缺失机制包括 MCAR、MAR（缺失依赖另一变量）、MNAR（缺失依赖自身值）。 - 结果：第一类错误在所有缺失机制下均 \(\leq \alpha\)（严格控制）；功效在 MCAR 下最高，MNAR 下最低，但差异不大；缺失对比例 \(\leq 15%\) 时功效 \(> 0.8\)（\(n=100, \alpha=0.05\)），超过 20% 时功效 \(< 0.5\)。 - 与 baseline 对比：对比了完全对分析（只用 \(O\)）与 MI 后计算 footrule。完全对分析在 MNAR 下第一类错误失控（可达 0.15），MI 在 MNAR 下同样失控；本文方法在所有机制下第一类错误 \(\leq 0.05\)。
🔎 结论是否比证明窄： - 作者在摘要与 intro 中泛泛 claim"improving on all existing approaches, our method controls Type I error under arbitrary missingness"，但严格证明仅覆盖无结值、footrule 统计量、基于下界的拒绝规则这一特定组合。对其他秩相关系数（如 Kendall's tau）或其他拒绝规则（如基于上界），第一类错误控制未证明。 - 模拟中"15% 阈值"是经验观察，非理论保证——论文未给出功效随缺失比例的理论界，仅说"typically below 15%"，这是一个未严格化的 claim。
四、开放问题（点到为止，扎根具体语句）¶
- 其他秩相关系数的精确界：本文仅处理 Spearman's footrule（绝对值之和）。Kendall's tau 或 Spearman's rho（平方之和）的精确界是否可在多项式时间内计算？扎根点：摘要"This work studies exact bounds of Spearman's footrule"，未提其他系数；intro 无相关讨论。
- 功效的理论界：本文仅给出模拟中的 15% 经验阈值，未给出"缺失比例达到多少时检验功效必然低于某阈值"的理论结果。扎根点：摘要"Simulation results demonstrate our method has good power, typically when the proportion of pairs containing missing data is below 15%"——"typically"非严格陈述。
- 高维 / 多变量扩展：本文限于两个向量的独立性检验。当有 \(p > 2\) 个变量且部分缺失时，如何计算多变量秩相关量的精确界？扎根点：全文仅讨论 \(X\) 与 \(Y\) 二元情形，无 \(p>2\) 的设定或讨论。
- 与半参数效率界的对话：本文的界是组合 / 算法界，未与缺失下独立性检验的半参数效率界（如 Robins et al. 的 MNAR 效率界）比较。下界检验是否达到某种 minimax 效率？扎根点：intro 未引用任何半参数效率界文献，也未讨论检验的渐近效率。
提醒：要确认第 4 条是否真 gap，去读缺失数据下独立性检验的半参数理论近期 5 篇 intro——若都指向"MNAR 下无分布检验的效率界未知"，则为共识真 gap；若已有解决方案但本文未引，则为被回避的竞争路线。
Maintained by 陈星宇 · Homepage · Source on GitHub