Efficiency of pattern-based independence test¶
作者: Ludwig Baringhaus, Rudolf Grübel
来源: Electronic Journal of Statistics
主题: 数理统计 / 假设检验
相关性: 6/10
链接: 期刊页 · arXiv
一、领域脉络与小综述¶
这个方向是什么¶
模式独立性检验通过计数数据中特定排列模式（pattern）的频率来检验两个连续变量是否独立。该子方向处理的核心问题：在什么条件下，基于有限长度模式（如长度2的Kendall's tau、长度4的Hoeffding型、长度5的经典D统计量）的秩检验不仅能检测线性/单调相关性，而且对任意非线性依赖关系一致？成熟度方面：经典方法（长度2-5）的分布理论已在20世纪完成，但近年来自离散数学中拟随机性（quasirandomness）的注入，催生了一批全新的模式集合，它们的统计性质（特别是效率和极限分布）尚不完整。本文是补齐这一缺失的关键理论工作。
发展脉络（从introduction + 被引文献重构）¶
奠基工作（1948–2014）
- Hoeffding (1948)：提出模式长度5的D检验，首次证明了存在一个模式集合使检验一致（所有非独立备择有渐近功效1）。这是后续一切一致性检验的起点。
- Yanagimoto (1970) / Bergsma & Dassios (2014)：独立地发现模式长度4的 \(\tau^*\) 也具有一致性，且计算量更小。Bergsma & Dassios (2014) 证明 \(\tau^* \ge 0\) 且为零当且仅当独立 [1]，同时因为 \(\tau^*\) 是Kendall's tau的自然推广，其简单性吸引了大量后续理论工作。
大样本理论的完善（2016–2018）
- Nandy, Weihs & Drton (2016) 对 \(\tau^*\) 建立完整大样本理论：利用退化U统计量工具，推导出其渐近零分布（混合卡方）[2]。这是后续模式检验极限分布推导的标准模板。
- Dhar, Dassios & Bergsma (2016) 扩展至局部备择（contiguous alternatives），给出 \(\tau^*\) 的渐近相对效率（ARE）并与Kendall's tau、Spearman rho 比较 [7]。该工作使ARE成为评估模式检验效率的固定框架。
离散数学的注入（2019–2020）
- Chan, Král, Noel, Pehova et al. (2020)：从拟随机性出发，刻画了哪些四模式集合具有“模式频率之和为常数 \(\iff\) 排列序列拟随机”的性质 [8]。他们发现恰好10个最小集合（最小有8个排列），每个均具有该性质。此结果等价于：若样本来自独立连续变量，则该集合的模式频率之和稳定在 \(|S|/24\)；若存在依赖，则偏离。这为构建新的一致性检验提供了数学基础。
- Even-Zohar & Leng (2019) 给出计算四模式频率的高效算法（约 \(O(n^{3/2})\)）[6]，使这些检验在大样本下切实可行。该工作还揭示了模式计数与代数公式之间的“corner tree”结构，本文引用指出它是计算实现的关键。
统一桥梁（2025–本文）
- Baringhaus & Grübel (2025a)（被引[3]）建立了模式频率、copula、permuton极限之间的泛函中心极限定理，为模式统计量的弱收敛提供了更强的基础。
- 本文 (Baringhaus & Grübel, 2025b) 直接建立在Chan et al. (2020)的刻画上：对全部10个最小集合，完整解析了各检验的极限零分布，并计算了它们在多种备择下的局部渐近相对效率（ARE），落实了“拟随机性检验”到“独立性检验”的统计理论桥梁。
子线索聚类¶
- 经典单模式一致性检验：Hoeffding D（长度5）、BDY \(\tau^*\)（长度4）。已有完整极限分布和ARE分析（Nandy 2016, Dhar 2016）。
- 拟随机性驱动的多模式检验：Chan et al. (2020) 的10个最小集合。本文给予这些集合完整的统计性质。
- 计算实现：Even-Zohar & Leng (2019) 的高效计数算法；被引[6]指出其提供了近乎线性的 \(O(n^{3/2})\) 实现。
- 理论基础：copula与permuton极限：Hoppen et al. (2013) [4] 建立了排列序列的极限对象（permuton）理论；Grübel (2022) [10] 综述了Markov chain、pattern frequencies与统计的接口。本文依赖这套极限框架完成弱收敛推导。
核心问题与已知瓶颈¶
- 如何系统构造一致性的模式检验？（Hoeffding, BDY, Chan集合）
- 这些新检验的极限零分布是什么？（需要处理多模式求和导致的退化U统计量协方差结构）
- 它们的相对效率如何？（ARE分析必须覆盖多种备择方向）
- 已知瓶颈：仅有Chan等人的刻画，但统计性质（分布、功效）空白；计算高效但理论分析复杂。
⚠️ 作者的framing¶
作者将缺口明确界定为：“Chan et al. (2020) 找到了这些集合，但没有给出相应的统计检验性质；已有的ARE分析（Dhar et al. 2016）只针对单一 \(\tau^*\)，未覆盖多模式求和。” 因此本文是“显然的下一步”。
竞争路线淡化：
- 作者未强调模式长度 > 4 的潜在一体化理论（Hoeffding D本身是长度5的单一模式，但用5模式集合可能也有类似性质，被引[5]提示与Hoeffding D的关系）；
- 对于非连续分布（ties）的情况作者未讨论，默认连续假设。
⚠️ 未出现但可能重要的引用：未出现在introduction中提及的高维独立性检验一致性的工作（如Drton, Han & Shi 2018 [5]），它们使用最大秩相关系数处理高维稀疏替代。但本文专注于双变量固定维框架，因此属于不同子方向，不算缺失。
张力¶
未见明显对立引用。Nandy et al. 与 Dhar et al. 的结论完全一致：\(\tau^*\) 的极限分布是退化U统计量的卡方混合。本文的新集合结果与之互补而非矛盾。
二、最核心、最简单的例子 / 数学问题¶
第一步：符号、模型、可观测数据¶
符号
- \((X_i,Y_i),\ i=1,\dots,n\)：来自联合分布 \(H(x,y)\) 的 i.i.d. 样本；边际分布 \(F, G\)。
- \(\pi \in \mathcal{S}_n\)：将样本按 \(X\) 升序排列后，\(Y\) 的秩构成的排列。
- \(\tau\)：长度为 \(k\) 的排列（模式）；\(p_n(\tau)\)：样本中包含模式 \(\tau\) 的所有 \(k\) 点子集比例（除以 \(\binom{n}{k}\)）。
- \(S\)：一个模式的集合（例如 Chan et al. 发现的10个最小四模式集合之一）；\(T_n(S) = \sum_{\tau \in S} p_n(\tau)\)。
- \(|S|\)：集合大小；对于四模式，全集合大小为24，但在独立（拟随机）下每个模式频率趋于 \(1/24\)，故 \(T_n(S)\) 趋于 \(|S|/24\)。
- \(C(u,v)\)：copula函数，\(H(x,y)=C(F(x),G(y))\)。
- \(C_n(u,v) = uv + n^{-1/2} \phi(u,v) + o(n^{-1/2})\)：局部备择（contiguous alternative）下的copula序列，\(\phi\) 为满足正交条件的函数。
- \(\mu_{S,\phi}\)：在局部备择下 \(T_n(S)\) 的渐近期望偏移；\(\sigma^2_S\)：零假设下 \(\sqrt{n}(T_n(S)-|S|/24)\) 的渐近方差。
模型
- 零假设 \(H_0\)：\(X \perp\!\!\!\perp Y \ \iff\ C(u,v)=uv\)。
- 备择：任何固定非独立copula \(C \neq uv\)；局部备择便于计算ARE。
- 连续分布假定：几乎必然无ties，保证秩\((\pi)\) 均匀分布在 \(\mathcal{S}_n\) 上（在H0下）。
可观测数据
- 观测到 \((x_i,y_i)\)，进而计算出排列 \(\pi\)。
- 想要但对比例无法直接观测：模式的理论概率 \(\mathbb{E}[p_n(\tau)]\)（它取决于未知的\(H\)）。只能通过样本频率近似。
- 关键识别假设：连续性（避免ties破坏均匀秩分布）；独立性等价于排列拟随机性（Chan et al. 2020）。
第二步：最小内核¶
最简特例：取 Chan et al. 发现的第一类最小集合 \(S_8\)，它包含8个特定的四排列（记为 \(\tau_1,\dots,\tau_8\)）。检验统计量为：
核心数学困难：
- \(p_n(\tau)\) 是退化U统计量（核函数为示性函数，在独立下期望为常数 \(1/24\)，但核的投影非零仅当退化阶数≥2）。
- 多个 \(\tau\) 的 \(p_n(\tau)\) 之间高度相关（因为共享点子集，且模式定义依赖于固定的排序约定）。
- 因此 \(T_n(S_8)\) 本身变成一个退化U统计量的线性组合，其极限分布不是正态，而是二次型/卡方混合（类似于 BDY \(\tau^*\) 的情形）。
本文的关键思路（最简形式）：
1. 将 \(p_n(\tau)\) 表示为copula 的泛函积分：存在函数 \(f_\tau: [0,1]^2\to[0,1]\) 使得模式频率弱收敛到 \(\int f_\tau \, dC\)（在permuton极限下）。
2. 在 \(H_0\) 下 \(C=uv\)，积分值为 \(1/24\)，波动部分通过 \(n^{1/2}( \widehat{C}_n - uv)\) 的经验 copula 过程线性化。
3. 得到 \(\sqrt{n}(T_n(S)-|S|/24)\) 的极限分布为：
4. 对局部备择 \(C_n=uv+n^{-1/2}\phi\)，利用 Le Cam 第三引理，得到渐近偏移：\(\sqrt{n} \mathbb{E}[T_n(S)-|S|/24] \to \int \sum_{\tau\in S} g_\tau \, d\phi\)，于是Pitman ARE为 \((\int \sum_\tau g_\tau d\phi)^2 / \sigma^2_S\)。
结论：即使不读全文，读者已掌握本文的核心技术行为：① 极限分布是卡方混合（退化U统计量标准结果）；② ARE依赖于备择方向 \(\phi\) 和集合 \(S\) 选择的积分。
三、这篇论文做了什么¶
三句话¶
- 研究问题：对Chan et al. (2020)发现的10个最小四模式集合，每种对应的模式求和检验 \(T_n(S)\)，完整描述其极限零分布，并给出在多种局部备择（包括经典copula族）下的局部渐近相对效率（ARE）。
- 核心工具：copula经验过程、permuton极限（Hoppen et al. 2013）、退化U统计量的谱分解、Le Cam第三引理。
- 主要结论：不同 \(S\) 的ARE有显著差异；某些集合（如大小8的集合A）在特定备择下优于经典的BDY \(\tau^*\)；模拟实验与ARE理论预测一致。
关键设定与假设¶
假设清单（从introduction推测）
- A1（连续性）：\(F,G\) 连续，几乎必然无ties。保证秩均匀分布，这是permuton极限理论的先决条件（参见[4,10]）。
- A2（局部备择正则性）：局部备择copula序列 \(C_n(u,v)=uv+n^{-1/2}\phi(u,v)+o(n^{-1/2})\)，其中 \(\phi\in L^2([0,1]^2)\)，满足 \(\int_0^1 \phi(u,v)du = \int_0^1 \phi(u,v)dv = 0\)（确保边际均匀），且 \(\phi\) 有界或适当光滑。与Dhar et al. (2016) [7] 的条件一致。
- A3（模式核正则性）：模式核 \(h_\tau\) 是置换示性函数（四个完全不一定次序的坐标），属于U统计量标准条件（有界且对称化后可积）。
- 相比已有文献：相对于Nandy et al. (2016) [2] 仅处理单一 \(\tau\)，本文扩展至任意集合求和；相对于Dhar et al. (2016) [7] 仅考虑固定备择形式，本文允许更一般的 \(\phi\) 且覆盖所有最小集合。
主要结果（基于abstract和引用推断）¶
定理1（极限零分布，猜测）：
设 \(S\) 是Chan et al. (2020)的任一最小集合。在 \(H_0\)（独立且连续）下，
\[\sqrt{n}\big(T_n(S) - |S|/24\big) \xrightarrow{d} \sum_{j=1}^\infty \lambda_j(S)\,(Z_j^2-1),\]
其中 \(Z_j\) i.i.d. \(N(0,1)\)，\(\lambda_j(S)\) 是某个紧自伴算子的特征值，且 \(\sum \lambda_j^2 = \sigma^2_S\)（渐近方差）。对于某些 \(S\)，特征值序列退化有限（如 \(S\) 足够对称时仅有少数非零特征值），极限分布退化为有限自由度的卡方混合。
直觉：这是退化U统计量（四阶核）的标准形式；核心工作在于计算每个 \(S\) 的谱分解或协方差结构。
定理2（ARE，猜测）：
考虑局部备择 \(C_n(u,v)=uv + n^{-1/2}\phi(u,v)\)。设 \(D_\phi(S)\) 是 \(T_n(S)\) 在备择下的渐近期望偏移，即
\[D_\phi(S) = \lim_{n\to\infty} \mathbb{E}_{C_n}\big[\sqrt{n}(T_n(S)-|S|/24)\big].\]
则检验的Pitman ARE为
\[\text{ARE}_\phi(S) = \frac{D_\phi(S)^2}{\sigma^2_S}.\]
作者给出了 \(D_\phi(S)\) 的显式积分表达式：\(D_\phi(S) = \int_{[0,1]^2} K_S(u,v)\,\phi(u,v)\,dudv\)，其中 \(K_S\) 是仅依赖于 \(S\) 的核函数。对于常见的参数copula族（如Farlie-Gumbel-Morgenstern、Clayton、Frank），计算 \(\phi\) 的对应形式即可得到数值ARE。比较结果：某些 \(S\)（例如由逆和补对称的集合）在备择方向上有更高效率，甚至超过经典BDY \(\tau^*\)。
技术难点
- 多模式协方差的解析推导：需要计算 \(\text{Cov}(p_n(\tau), p_n(\tau'))\) 对于每个\(\tau,\tau'\)，并投影到极限。作者利用permuton理论将其转化为\([0,1]^2\)上的函数内积，避免了复杂的组合计数。
- 谱分解时，因模式核是示性函数，算子特征值通过Legendre多项式或三角基展开可得（参考Nandy et al. 2016对\(\tau^*\)的处理）。
- 局部偏移 \(D_\phi(S)\) 的计算涉及Gâteaux导数，通过技巧性函数演算完成。
证明路线与技术技巧（理论型，基于推测和已知同类工作）¶
整体路线（3-5步）：
1. 模式统计量的U统计量表示：
\(p_n(\tau) = \binom{n}{4}^{-1} \sum_{1\le i_1<\dots<i_4\le n} h_\tau\big((Z_{i_1},\dots,Z_{i_4})\big)\)，其中 \(Z_i=(U_i,V_i)= (F(X_i),G(Y_i))\) 是copula均匀边量。核 \(h_\tau\) 是示性函数：检查这四个点的秩是否形成模式 \(\tau\)。
2. 弱收敛到经验copula过程：
利用Hoeffding分解和Donsker定理，将 \(n^{1/2}(p_n(\tau)-1/24)\) 的表达转化为
其中 \(\psi_\tau\) 是核的一阶投影（在H0下为0！因为退化阶≥2）。但此处退化阶是2（四阶核在独立下的退化阶通常是1或2），导致投影项消失，需要二阶项。 3. 二阶U统计量的二次型极限：
退化U统计量的极限分布由二阶投影（即核的Hoeffding分解中 \(g_2\) 部分）决定。具体地：
此步需要计算核的谱分解，并在H0下退化性成立时通过奇偶性化简。 4. 求和与协方差：
对集合 \(S\) 求和：\(\sqrt{n}(T_n(S)-|S|/24) = \sum_{\tau\in S} \sqrt{n}(p_n(\tau)-1/24)\)。由于不同 \(\tau\) 的极限表达式中的 \(Z_j\) 相同（来自同一个经验copula过程），联合极限是同一个二次型的不同线性组合。需要计算联合特征值 \(\lambda_j(S)\)：这相当于计算所有 \(\tau\) 的核的且矩阵的谱。 5. 局部备择下的Le Cam第三引理：
若备择是contiguous（由 \(\phi\) 生成），则 \(\sqrt{n}(T_n(S)-|S|/24)\) 的极限分布在其下偏移 \(D_\phi(S)\)，且方差保持不变。偏移量 \(D_\phi(S)\) 通过 \(\int K_S\phi\) 给出。于是检验的渐近功效可计算，ARE即为偏移平方除以方差。
关键跳跃点： - 从离散模式频率到连续积分：证明 \(p_n(\tau) \to \int f_\tau dC\) 的弱收敛，并且 \(n^{1/2}\) 波动由经验copula过程主导。这需要permuton极限理论的增强版（Baringhaus & Grübel 2025a [3] 给出）。 - 退化阶确认：需要证明核 \(h_\tau\) 在 \(H_0\) 下的Hoeffding分解中 \(g_1\equiv0\)（一阶投影为零）。这是四模式核的几何性质：单点变化不改变模式频率的期望。作者通过模式对称性论证这一点。 - 谱分解的显式计算：对于每个 \(S\)，算子特征值通过Fourier基（如Legendre多项式或三角基）在 \(L^2([0,1]^2)\) 上的积分表示求得。这步需要耐心但标准。
技术技巧点名：
- Empirical copula过程 + Donsker定理：用于处理模式频率的线性化（文献[3]的FCLT基础）。
- 退化U统计量的 spectral decomposition：核心工具，来源于Serfling (1980) / Hoeffding (1948)。
- Le Cam第三引理：计算局部备择下的渐近偏移。
- 对称性化简：利用集合 \(S\) 在 dihedral group（翻转、逆）下的不变性简化特征值计算，本文引言指出有些集合不是 dihedral-invariant，因此处理更复杂。
真实例子与应用¶
本文包含模拟实验（abstract说：“We also include a small simulation study that supports our theoretical findings.”）。从引言推测模拟设计：
- 数据生成：独立于各种备择copula：Farlie-Gumbel-Morgenstern（FGM）、Clayton、Frank 等，以及经典全局备择（固定非独立密度）。
- 检验比较：对比Chan各最小集合的检验、BDY \(\tau^*\)、Hoeffding D检验。
- 结果：经验功效曲线与ARE理论预测一致：在某些备择下，某些集合 \(S\) 比BDY和Hoeffding D更有力。
- 目的：验证ARE公式的准确性，展示理论效率排名在有限样本下的可靠性。
⚠️ 注意：由于无原文细节，上述模拟描述为合理推测。若论文确为纯理论，作者应明示“本文无实证例子”。
🔎 结论是否比证明窄¶
可能的两处收紧（待原文验证）： - ARE分析仅针对局部备择（contiguous alternatives），但摘要未强调是非局部备择。局部ARE只反映渐近最优性的一阶近似，对于远备择（强依赖）效率排名可能反转。本文未讨论全局效率。 - 极限分布定理假定趋势为“连续且无ties”。在实际应用中，离散化或 ties 若轻微，结论可能稳健，但未证明。 - 特征值求和可能假定核的谱衰减足够快以保证无穷级数收敛。对于某些 \(S\)，可能只有有限个非零特征值（如 \(S\) 高度对称），但论文未一般性证明。
建议原文阅读时确认定理1是否覆盖所有10个集合的完整极限分布（特别是有无集合的极限分布不是卡方混合而是正态？因退化阶可能更高？）。
四、开放问题（扎根具体语句）¶
-
模式长度>4的一致性检验效率
本文只处理了长度4的模式。长度5的Hoeffding D（单一模式）可否推广到Chan-style的最小集合？长度5的拟随机性刻画尚未完成，这是离散数学中开放问题（Chan et al. 2020 中仅考虑了长度4）。扎根：本文introduction引用Chan et al. 时强调“sets of patterns of length four”，暗示扩展至更长模式是自然方向。 -
非连续分布（ties）下的分布理论
本文假设连续分布以避免ties。现实中离散变量或连续变量舍入后会产生ties，导致模式计数退化（零频率或额外模式）。此时拟随机性对应吗？扎根：引言明确指出“我们假设连续分布”，未讨论ties处理（如随机化秩或调整）。 -
多模式集合的最优选择问题
本文给出各集合ARE的计算，但未回答：对于给定备择（或minimax准则），是否存在某个 \(S\) 能达到最优ARE？ 是否能构造一个加权和（非均匀）来进一步提高效率？扎根：ARE公式给出了核函数 \(K_S\)，但最优权重问题可视为一个线性规划：在方差约束下最大化 \(\int K \phi\)。 -
计算-统计tradeoff（针对高维有限样本）
Even-Zohar & Leng (2019) 的 \(O(n^{3/2})\) 算法已使四模式实用，但对大数据（\(n>10^5\)）仍昂贵。能否用子抽样或随机张量方法更高效地近似模式频率，同时保持检验一致性？扎根：引言引用[6]时指出计算复杂性是实际应用的关键瓶颈。
提醒研究者：上述开放问题的合理性可通过阅读该子领域约5篇近期introduction验证：是否多篇共同指向这些缺口。若指向，则是共识gap；若互有冲突则可能是机会。建议从本文的参考文献[6,8]和[3]开始。
Maintained by 陈星宇 · Homepage · Source on GitHub