跳转至

Gaussian fluctuations of generalized \(U\)-statistics and subgraph counting in the binomial random-connection model

讲者: Nicolas Privault
会场: Probability and Asymptotic Theory
报告题目: Gaussian Fluctuations of Generalized U-Statistics and Subgraph Counting in the Binomial Random-Connection Model
链接: arXiv
来源: JCSDS 2026 · 返回会议总览

一、领域脉络与小综述

这个方向是什么

这个子方向研究的是广义U-统计量（generalized U-statistics）的渐近分布理论，特别是其正态近似的收敛速度与中偏差原理。广义U-统计量是经典U-统计量的推广，其核函数不仅依赖于k个独立同分布的主随机变量（如顶点位置），还依赖于一组独立的辅助随机变量（如边指示变量）。这类统计量是研究非齐次随机图（inhomogeneous random graphs）中子图计数（subgraph counts）渐近行为的核心工具。当前该方向已从奠基性的渐近正态性结果，发展到对收敛速率（Berry-Esseen界）、中偏差原理、以及不同图模型（Erdős-Rényi、graphon、随机连接模型）下子图计数波动行为的精细刻画。

发展脉络（history）

  1. 奠基工作：U-统计量与广义U-统计量的渐近理论

    • Hoeffding (1961)：建立了经典U-统计量的强大数律和渐近正态性，其核心工具是Hoeffding分解。
    • Janson & Nowicki (1991)：引入了广义U-统计量（论文中的[JN91]），并证明了其渐近正态性依赖于正交分解中“最小”分量的退化阶数。这是将U-统计量理论应用于随机图子图计数的开创性工作。作者引用其“Lemma 2”和“Theorem 11.3”来说明这一点。
    • Janson (1997)：在《Gaussian Hilbert spaces》一书中系统总结了广义U-统计量的理论，包括其在随机图中的应用。

  2. 主要进展：从渐近正态到收敛速率与中偏差

    • 累积量方法（Cumulant Method）：Saulis & Statulevičius (1991) 的“main lemmas”提供了通过累积量增长条件（Statulevičius条件）来推导正态近似Kolmogorov距离界、中偏差原理和浓度不等式的通用框架。这是本文的核心技术工具。
    • Erdős-Rényi模型中的子图计数：
      • Janson, Łuczak & Ruciński (2000) 的专著《Random graphs》中，系统总结了子图计数的渐近分布，包括正态、泊松等极限，并引入了凸包分析（convex analysis of planar diagrams）来研究方差和累积量的增长阶数（论文引用[JLR00]）。
      • Féray, Mélior & Nikeghbali (2016) 的专著《Mod-φ Convergence》中，利用累积量方法得到了Erdős-Rényi模型中一般子图计数的中偏差原理（论文引用[FMN16]）。
      • Privault & Serafin (2018) 和 Eichelsbacher & Rednoß (2023) 分别利用Stein方法和Stein-Tikhomirov方法，得到了Erdős-Rényi模型中子图计数正态近似的Kolmogorov距离界（论文引用[PS18]和[ER23]）。本文的目标之一是将这些结果推广到二项随机连接模型。
    • 随机连接模型（RCM）中的子图计数：
      • Penrose (2018)、Last, Nestmann & Schulte (2021)、Can & Trinh (2022) 等研究了基于Poisson点过程的RCM中顶点计数、连通分支计数等统计量的分布近似（论文引用[Pen18], [LNS21], [CT22]）。
      • Liu & Privault (2024a, 2024b) 是本文作者的前期工作，分别研究了Poisson RCM中子图计数的正态近似（[LP24a]）和正态到泊松的相变（[LP24b]）。本文是这些工作在二项RCM中的延续。
    • 广义U-统计量的Berry-Esseen界：
      • Zhang (2022) 利用Stein方法的交换对（exchangeable pair）技术，得到了广义U-统计量的最优Berry-Esseen界，并应用于graphon随机图（论文引用[Zha22]）。作者指出，Zhang的工作以及[JN91]和[KR21]都依赖于L2空间上的正交分解，而本文的方法（累积量方法）可以处理连接概率趋于零的情况，这是Zhang的工作未能覆盖的。

  3. 当前Frontier与本文位置

    • 当前frontier在于：对于连接概率可以随n趋于零的稀疏随机图模型（如Erdős-Rényi模型、二项RCM），推导子图计数正态近似的收敛速率和中偏差原理。已有的工作（如[Zha22]）主要针对稠密图（连接概率为常数）或graphon模型。
    • 本文的位置：本文填补了二项RCM中，当连接概率p_n可以趋于零时，子图计数正态近似收敛速率和中偏差原理的空白。它通过累积量方法，将Erdős-Rényi模型中的相关结果（[PS18], [ER23], [FMN16]）推广到了更一般的二项RCM。

子线索聚类

  1. 广义U-统计量的渐近理论：[JN91], [Jan97], [Zha22], [BDMM24]。这一簇关注广义U-统计量本身的正交分解、渐近分布和Berry-Esseen界。
  2. 随机图模型中的子图计数：[JLR00], [FMN16], [BCJ23], [KR21], [PS18], [ER23]。这一簇关注不同随机图模型（Erdős-Rényi, graphon, RCM）中特定子图计数的渐近行为。
  3. 累积量方法与Statulevičius条件：[SS91], [DE09], [DE13], [DJS22], [ST24]。这一簇提供推导正态近似、中偏差和浓度不等式的通用技术工具。
  4. Poisson点过程上的RCM：[Pen18], [LNS21], [CT22], [LP24a], [LP24b]。这一簇研究顶点由Poisson点过程生成的RCM，与本文的二项RCM（顶点数固定）形成对比。

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

  1. 子图计数何时服从正态分布？ 其渐近分布由正交分解中的最小非退化分量决定。对于强平衡图（strongly balanced graph），存在一个临界连接概率阈值n^{-(v-1)/e}，在该阈值两侧，方差和累积量的增长阶数不同，从而影响正态近似的有效性。
  2. 正态近似的收敛速率是多少？ 在Kolmogorov距离下，能否得到最优的n^{-1/2}阶速率？目前对于广义U-统计量，Zhang (2022) 得到了最优速率，但仅限于稠密图。本文得到的速率是n^{-1/(2+4v)}，远非最优。
  3. 中偏差原理（MDP）是否成立？ 在什么条件下，归一化的子图计数满足MDP？其速率函数是什么？本文和[FMN16]等给出了部分答案。
  4. 不同图模型（Erdős-Rényi, graphon, RCM）下的结果如何统一？ 连接函数H(x,y)的引入使得模型更加灵活，但同时也增加了分析的复杂性。本文的工作是向统一理论迈进的一步。

⚠️ 作者的framing

  • 作者把缺口frame成什么？ 作者在引言中明确指出，已有的关于广义U-统计量正态近似的工作（如[Zha22]）依赖于L2正交分解，无法处理连接概率p_n趋于零的稀疏情形。同时，已有的关于二项RCM中子图计数的工作（如[BCJ23]）主要关注渐近分布本身，而非收敛速率。因此，作者将本文定位为：利用累积量方法，填补二项RCM中当p_n = o(1)时子图计数正态近似收敛速率和中偏差原理的空白。这是一个非常清晰的“显然的下一步”。
  • 哪些竞争路线被他淡化或回避了？ 作者明确提到了[Zha22]的Berry-Esseen界是最优的，但指出其方法不适用于p_n = o(1)的情形。作者没有尝试去改进自己的收敛速率以匹配[Zha22]的最优速率，而是满足于得到一个更慢但适用范围更广的速率。这暗示了在稀疏情形下，获得最优速率可能是一个更难的问题。
  • 什么明显该被引/该存在、却没出现在intro里？ 作者引用了大量关于Erdős-Rényi模型和Poisson RCM的工作，但似乎没有引用关于二项点过程（binomial point process）上函数估计的Berry-Esseen界的工作，例如Lachièze-Rey & Peccati (2017) ([LRP17])。作者在引言中提到了这篇论文，但只是作为“其他方法”的一个例子，并没有将其作为主要竞争路线进行对比。这可能是因为[LRP17]处理的是更一般的泛函，而本文专注于广义U-统计量这一特定结构。

张力

未见明显对立引用。所有被引工作都在各自的设定下（稠密/稀疏、不同图模型）推进对子图计数渐近行为的理解，彼此之间是互补而非矛盾的关系。

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

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

  • 符号：

    • n: 顶点总数（样本量）。
    • k: 子图G的顶点数，也是广义U-统计量的阶数。
    • X_1, ..., X_n: i.i.d. 随机变量，代表顶点的位置（或标签），取值于Borel空间S（通常是R^d）。它们是可观测的。
    • Y_{i,j} (1 ≤ i < j ≤ n): i.i.d. 随机变量，代表连接顶点i和j的潜在边指示变量，取值于可测空间M（通常是[0,1]上的均匀分布）。它们是可观测的。
    • f: 核函数，f: S^k × M^{k(k-1)/2} → R。它定义了如何从一组k个顶点及其之间的边来“打分”。对于子图计数，f是一个指示函数，判断这k个顶点是否构成一个与G同构的子图。
    • S_{n,k}(f): 广义U-统计量，即对所有k个不同顶点的有序组合，对f求和。这是要研究的统计量。
    • κ_j(S): 随机变量S的j阶累积量。
    • G = (V_G, E_G): 一个固定的连通图，v(G) = |V_G| = k，e(G) = |E_G|。
    • N_G: 随机图G_H(X_n)中与G同构的注入子图（injective subgraph）的个数。这是本文应用的核心统计量。
    • p_n: 连接概率的全局缩放因子，0 < p_n < 1。它可以随n趋于0。
    • H(x, y): 连接函数，H: R^d × R^d → [0,1]，是一个对称的可测函数。它定义了位置x和y之间连接的相对概率。
    • a(G): 图G的自同构群的大小。

  • 模型：

    • 数据生成机制：首先，独立生成n个顶点位置X_1, ..., X_n，服从分布µ。然后，对于每一对不同的顶点(i, j)，独立地以概率p_n H(X_i, X_j)生成一条边。边指示变量可以表示为1{Y_{i,j} ≤ p_n H(X_i, X_j)}，其中Y_{i,j}是[0,1]上的均匀随机变量。
    • 统计模型：这是一个非参数模型。µ和H是未知的，但假设µ是连续的，H是已知的（或至少是光滑的）。p_n是已知的或需要估计的。本文主要关注p_n已知的情形。
    • 要估的对象：本文不直接估计参数，而是研究统计量N_G（或S_{n,k}(f)）的分布，特别是其渐近正态性。

  • 可观测数据：

    • 可观测：顶点位置X_1, ..., X_n和所有边指示变量1{X_i ∼ X_j}（或等价的Y_{i,j}）。因此，整个随机图G_H(X_n)是完全可观测的。
    • 潜在/不可观测：没有不可观测的潜在变量。所有随机性都来自X_i和Y_{i,j}，它们都是可观测的。这与因果推断中的反事实不同。

第二步：讲最小内核

本文的核心数学困难在于：当连接概率p_n很小时，如何控制广义U-统计量S_{n,k}(f)的累积量增长，并利用Statulevičius条件得到正态近似？

最简特例：考虑一个最简单的子图——边（edge），即k=2，G是一条边。此时v(G)=2, e(G)=1。广义U-统计量S_{n,2}(f)退化为： S_{n,2}(f) = Σ_{1 ≤ i ≠ j ≤ n} 1{X_i ∼ X_j} 这其实就是随机图的总边数（乘以某个常数，因为a(G)=2，但这里忽略自同构）。

在这个特例下： * 要证的命题：归一化的边计数(S_{n,2} - E[S_{n,2}]) / sqrt(Var[S_{n,2}])的分布收敛到标准正态，并给出收敛速率。 * 证明怎么走： 1. 计算累积量：对于边计数，其j阶累积量κ_j可以通过组合论证直接计算。由于边是独立的，κ_j的非零项只来自于那些共享顶点的边集合（即“连通”的边集合）。这个连通性由分区图ρ的连通性来刻画。 2. 累积量上界：通过枚举所有可能的连通分区ρ，可以得到|κ_j| ≤ C_j * n^{1+(j-1)} * p_n^j。这里n^{1+(j-1)}来自顶点数的组合计数，p_n^j来自j条边同时存在的概率。 3. 方差下界：Var[S_{n,2}]的主要贡献来自共享一个顶点的两条边（即“V”形结构），其数量级为n^3 p_n^2。当p_n不是太小时，这个下界是有效的。 4. 归一化：将累积量上界除以(Var)^{j/2}，得到归一化后的累积量|κ_j(Normalized)| ≤ (j!)^{1+γ} / (Δ_n)^{j-2}。这里γ和Δ_n取决于p_n和n的关系。 5. 应用Statulevičius条件：如果Δ_n足够大（例如，当p_n ≫ n^{-1/2}时，Δ_n ~ sqrt(n p_n^2)），则满足条件，从而得到Kolmogorov距离下的收敛速率。

一般情形（k>2）的推广：对于一般的子图G，核心思路完全一样，但组合计数变得更加复杂。需要引入“强平衡图”的概念来保证方差的主要贡献来自某个特定的“最小”结构，从而得到清晰的累积量增长阶数。分区图ρ和凸包分析就是用来处理这种复杂组合计数的工具。

三、这篇论文做了什么

三句话

  1. 研究了什么问题：研究了广义U-统计量S_{n,k}(f)在Kolmogorov距离下的正态近似收敛速率和中偏差原理，并将其应用于二项随机连接模型（binomial RCM）中强平衡连通子图的计数问题。
  2. 核心工具/方法：核心工具是累积量方法（cumulant method），通过分区图（partition diagrams）论证推导累积量上界，并结合方差下界和Statulevičius条件得到最终结果。
  3. 主要结论：对于满足一定条件的广义U-统计量，得到了O(n^{-1/(2+4k)})的Kolmogorov距离界。对于二项RCM中的强平衡连通子图G，在连接概率p_n的不同渐近区域（p_n ≫ n^{-(v-1)/e} 和 p_n ≪ n^{-(v-1)/e}），分别得到了不同形式的Kolmogorov距离界和中偏差原理。

关键设定与假设

  • 设定：X_i和Y_{i,j}是独立的i.i.d.序列。f是有界可测函数。对于子图计数，f由(5.2)式定义，Y_{i,j}是[0,1]上的均匀分布。
  • 核心假设：
    • Assumption 4.1：Var[Σ_{ℓ=1}^k f^{(ℓ)}(X_1)] > 0。这里f^{(ℓ)}是f对第ℓ个位置变量的边缘积分。这个假设保证了广义U-统计量的Hoeffding分解中，一阶项（线性项）是非退化的，从而其渐近分布是正态的。作者指出，这个假设在二项RCM中成立，但在Erdős-Rényi模型中不成立（因为Erdős-Rényi模型中H是常数，导致一阶项退化）。
    • 图G是强平衡的（Definition 7.4）：对于G的任何真子图H，有e(H)/(v(H)-1) ≤ e(G)/(v(G)-1)。这个条件是保证凸包分析中上边界是一条直线段的关键，从而可以精确控制累积量的增长阶数。

主要结果

  1. 定理4.1（广义U-统计量的累积量界）：给出了κ_j(S_{n,k}(f))的上界|κ_j| ≤ n^{1+(k-1)j} ||f||_∞^j j^{j-1} (j!)^k (k!)^{j-1}。在Assumption 4.1下，还给出了方差下界κ_2 ≥ C n!/(n-2k+1)!。
  2. 推论4.3（广义U-统计量的Kolmogorov界）：在Assumption 4.1下，归一化后的S_{n,k}(f)满足sup_x |P(S_{n,k} ≤ x) - Φ(x)| ≤ C / n^{1/(2+4k)}。这个速率依赖于阶数k，且远慢于n^{-1/2}。
  3. 定理5.2（子图计数累积量上界）：给出了κ_j(N_G)的上界，形式为|κ_j| ≤ (j^{j-1}/a(G)^j) Σ_{r=k}^{1+(k-1)j} |C(j,k,r)| n^r p_n^{d(j,k,r)}，其中d(j,k,r)是某个依赖于分区图ρ的最小边数。
  4. 定理7.5（强平衡图累积量增长阶数）：对于强平衡图G，利用凸包分析，将定理5.2中的上界简化为两种情形：
    • 当p_n ≫ n^{-(v-1)/e}时，|κ_j| ≤ C n^{1+(v-1)j} p_n^{j e}。
    • 当p_n ≪ n^{-(v-1)/e}时，|κ_j| ≤ C n^v p_n^e。
  5. 推论7.9（子图计数的Kolmogorov界）：对于强平衡图G，归一化后的N_G满足：
    • 当p_n ≫ n^{-(v-1)/e}时，sup_x |P(N_G ≤ x) - Φ(x)| ≤ C / n^{1/(2+4v)}。
    • 当p_n ≪ n^{-(v-1)/e}时，sup_x |P(N_G ≤ x) - Φ(x)| ≤ C / (n^v p_n^e)^{1/(2+4v)}。
  6. 推论7.11（子图包含的阈值现象）：对于强平衡图G，p_n ≪ n^{-v/e}时，P(N_G = 0) → 1；p_n ≫ n^{-v/e}时，P(N_G = 0) → 0。这给出了子图出现的相变阈值。

证明路线与技术技巧

  • 整体路线：

    1. 矩恒等式（Theorem 3.2）：利用分区图ρ，将E[(S_{n,k}(f))^j]表示为对ρ求和，每个ρ对应一个积分。这是所有后续推导的基础。
    2. 累积量上界（Theorem 4.1 & 5.2）：利用累积量-矩关系（A.1）和“不连通则累积量为零”的性质，将κ_j的求和限制在连通非平坦（connected non-flat）的分区ρ上。然后通过枚举这些分区，并利用|f| ≤ ||f||_∞和E[I_β] ≤ p_n^{e(G)}等平凡上界，得到累积量的上界。
    3. 方差下界（Theorem 4.1 & Proposition 6.1）：利用Assumption 4.1，证明方差的主要贡献来自|ρ| = 2k-1的分区，这些分区对应两个子图共享一个顶点。通过计算这些分区的贡献，得到方差下界。
    4. 归一化与Statulevičius条件（Corollary 4.2 & 7.8）：将累积量上界除以(κ_2)^{j/2}，得到归一化后统计量的累积量界。验证这个界满足Statulevičius条件（A.2），即|κ_j| ≤ (j!)^{1+γ} / Δ_n^{j-2}。
    5. 应用Statulevičius引理（Corollary 4.3, 4.4, 7.9, 7.10）：直接引用[SS91]和[DE13]中的结论，从Statulevičius条件推出Kolmogorov距离界和中偏差原理。

  • 关键跳跃点：

    • 从矩恒等式到累积量上界：需要处理累积量-矩关系中的符号和组合计数。作者通过|κ| ≤ j^{j-1} ||f||_∞^j这个引理（4.5式）来绕过这个困难，这个引理本身依赖于Stirling数的上界。
    • 从一般累积量上界到强平衡图的精确阶数（Theorem 7.5）：这是最核心的跳跃。定理5.2的上界是一个复杂的求和，需要找出主导项。作者利用凸包分析（convex analysis of planar diagrams），将每个分区ρ映射到平面上的一个点(x, y) = (jk - |ρ|, je(G) - d(j,k,r))。对于强平衡图，这些点的凸包的上边界是一条直线段。通过比较不同点与这条直线的位置关系，可以判断出n^r p_n^{d(j,k,r)}项中哪个是最大的，从而得到(7.3)和(7.4)的简洁上界。

  • 技术技巧点名：

    • 分区图（Partition diagrams）：用于表示和枚举广义U-统计量中重复的随机变量，是推导矩恒等式和累积量上界的核心组合工具。
    • 累积量方法（Cumulant method）：通过控制累积量增长来推导正态近似、中偏差和浓度不等式的通用框架。
    • 凸包分析（Convex analysis of planar diagrams）：由Łuczak & Ruciński (1992) 引入，用于分析Erdős-Rényi模型中子图计数方差和累积量的增长阶数。本文将其应用于二项RCM。
    • Statulevičius条件：连接累积量界与最终概率不等式（Kolmogorov界、MDP）的桥梁。
    • Stirling数上界：用于控制累积量-矩关系中的组合系数。

真实例子与应用

本文为纯理论论文，没有包含任何真实数据例子或模拟实验。所有结果都是数学定理和推论。

🔎 结论是否比证明窄

  • 是的，结论比证明窄。推论4.3和7.9给出的Kolmogorov距离界是O(n^{-1/(2+4k)})或O((n^v p_n^e)^{-1/(2+4v)})。作者在引言中明确提到，这个速率“do not match the optimal rate obtained in [Zha22]”。证明中得到的累积量界（Corollary 4.2 & 7.8）是满足Statulevičius条件的，但Statulevičius引理本身给出的Kolmogorov界就是O(Δ_n^{-1/(1+2γ)})，这个速率通常不是最优的。因此，结论的速率受限于所使用的技术工具（Statulevičius引理），而非问题本身的信息论下界。作者没有声称自己的速率是最优的，这是一个诚实的表述。
  • 另一个窄化：定理7.5和推论7.9的结论只适用于强平衡连通图。对于非强平衡图，凸包的上边界可能不是一条直线，累积量的增长阶数会更加复杂，本文的方法无法直接处理。作者在引言中提到了“strongly balanced connected graphs”，但没有讨论非强平衡图的情况。

四、开放问题

  1. 最优收敛速率：能否得到二项RCM中强平衡子图计数正态近似的最优Berry-Esseen界（即n^{-1/2}阶）？这需要发展不依赖于Statulevičius条件的新技术，例如将Stein方法（如[Zha22]中的交换对方法）推广到p_n = o(1)的稀疏情形。扎根点：引言中“Although the convergence rates in the Kolmogorov distance obtained in do not match the optimal rate obtained in [Zha22]”。
  2. 非强平衡图：对于非强平衡的连通图，其子图计数的渐近分布是什么？正态近似是否仍然成立？如果成立，收敛速率如何？凸包分析可能给出更复杂的相图。扎根点：定理7.5的证明依赖于“G is strongly balanced”这一条件。
  3. 广义U-统计量的更一般结果：本文的推论4.3给出了O(n^{-1/(2+4k)})的速率，这个速率依赖于阶数k。能否得到不依赖于k的速率？或者，对于更一般的核函数f（不限于子图计数），能否得到更好的速率？扎根点：推论4.3的证明。
  4. 与计算复杂度的联系：本文研究的广义U-统计量S_{n,k}(f)的计算复杂度是O(n^k)，当k很大时是不可行的。是否存在计算上可行（例如，基于子采样或张量网络收缩）的近似方法，其统计性质（如渐近分布）可以与原始的S_{n,k}(f)相匹配？这与研究者对“统计-计算权衡”的兴趣相关。扎根点：本文没有讨论计算问题，但这是一个自然的延伸。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论