2025-11-16T21:22:11.887650

Rare event probabilities in Random Geometric Graphs

Deka, Luo, Wu
In this paper, we study rare events in spherical and Gaussian random geometric graphs in high dimensions. In these models, the vertices correspond to points sampled uniformly at random on the $d$ dimensional unit sphere or correspond to $d$ dimensional standard Gaussian vectors, and edges are added between two vertices if the inner-product between their corresponding points are greater than a threshold $t_p$, chosen such that the probability of having an edge is equal to $p$. We focus on two problems: (a) the probability that the RGG is a complete graph, and (b) the probability of observing an atypically large number of edges. We obtain asymptotically exponential decay rates depending on $n$ and $d$ of the probabilities of these rare events through a combination of geometric and probabilistic arguments.
academic

Rare event probabilities in Random Geometric Graphs

基本信息

  • 论文ID: 2510.09196
  • 标题: Rare event probabilities in Random Geometric Graphs
  • 作者: Prabhanka Deka (北京大学北京国际数学研究中心), Fangzhou Luo (北京大学数学科学学院), Baichuan Wu (北京大学数学科学学院)
  • 分类: math.PR (概率论)
  • 发表时间: 2025年10月10日 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2510.09196

摘要

本文研究高维球面和高斯随机几何图中的稀有事件。在这些模型中，顶点对应于d维单位球面上的均匀随机采样点或d维标准高斯向量，当两个顶点对应点的内积大于阈值tpt_p时在它们之间添加边，其中tpt_p的选择使得边存在的概率等于pp。本文专注于两个问题：(a) 随机几何图为完全图的概率，以及 (b) 观察到异常大量边数的概率。通过几何和概率论证的结合，获得了这些稀有事件概率的渐近指数衰减率，该衰减率依赖于顶点数nn和维数dd。

研究背景与动机

问题定义

本文研究的核心问题是在高维随机几何图中分析两类稀有事件：

  1. 完全图概率：随机几何图成为完全图（所有顶点对之间都有边）的概率
  2. 边数大偏差：观察到异常大量边数的概率

研究重要性

  1. 理论意义：随机几何图是建模复杂系统的基础工具，在计算机科学、生物学、社会学和物理学等领域广泛应用
  2. 实际应用：
    • 异常检测和假设检验
    • 高维数据中的团结构分析
    • 几何网络模型的鲁棒性分析
    • 神经网络和核方法中基于内积的相似性度量

现有研究局限性

  • 以往工作主要固定维数dd，让顶点数nn趋于无穷
  • 缺乏对高维稠密随机几何图的系统分析
  • 边之间的复杂依赖关系使得分析具有挑战性

核心贡献

  1. 建立了完整的理论框架：为球面和高斯随机几何图中的稀有事件提供了统一的分析方法
  2. 获得了精确的衰减率：在不同的nn和dd关系下，给出了完全图概率和边数大偏差概率的上下界
  3. 开发了创新的技术工具：
    • 球面对称重排技术的应用
    • 两种模型之间的耦合方法
    • 几何和概率论证的有机结合
  4. 揭示了维数效应：发现在高维情况下，随机几何图的行为接近Erdős-Rényi模型，而在低维时表现出不同特性

方法详解

模型定义

球面随机几何图 (SRGG)

  • 顶点：(X1,…,Xn)(X_1, \ldots, X_n)独立同分布地均匀分布在dd维单位球面Sd−1S^{d-1}上
  • 边：当⟨Xi,Xj⟩≥tp\langle X_i, X_j \rangle \geq t_p时，顶点ii和jj之间有边
  • 阈值：tpt_p选择使得P(⟨X1,X2⟩≥tp)=pP(\langle X_1, X_2 \rangle \geq t_p) = p

高斯随机几何图 (GRGG)

  • 顶点：(X~1,…,X~n)(\tilde{X}_1, \ldots, \tilde{X}_n)独立同分布地服从dd维标准正态分布
  • 边：当⟨X~i,X~j⟩≥t~p\langle \tilde{X}_i, \tilde{X}_j \rangle \geq \tilde{t}_p时，顶点ii和jj之间有边
  • 阈值：t~p\tilde{t}_p选择使得P(⟨X~1,X~2⟩≥t~p)=pP(\langle \tilde{X}_1, \tilde{X}_2 \rangle \geq \tilde{t}_p) = p

核心技术方法

1. 模型耦合技术

通过观察到X~/∥X~∥\tilde{X}/\|\tilde{X}\|在球面上均匀分布，建立两种模型的耦合关系：

引理 3.2：对于固定p<1/2p < 1/2和小的δ>0\delta > 0，存在常数cδ,Δδc_\delta, \Delta_\delta，使得： Pn,d(E~(n,d,p))≤exp⁡(−cδdn)+2nPn,d(E((1−δ)n,d,q))P_{n,d}(\tilde{E}(n,d,p)) \leq \exp(-c_\delta dn) + 2^n P_{n,d}(E((1-\delta)n, d, q))

2. 对称重排技术

利用球面上的对称重排来处理复杂的几何约束：

定理 3.4：对于球面上的函数f1,…,fnf_1, \ldots, f_n和增函数Ki,jK_{i,j}，有： I[f1,…,fn]≤I[f1∗,…,fn∗]I[f_1, \ldots, f_n] \leq I[f_1^*, \ldots, f_n^*] 其中f∗f^*表示ff的对称重排。

3. 阈值渐近行为

引理 3.1：对于固定p∈(0,1)p \in (0,1)，当d→∞d \to \infty时：

  • t~p=(Φ−1(p)+o(1))d\tilde{t}_p = (\Phi^{-1}(p) + o(1))\sqrt{d}
  • tp=(Φ−1(p)+o(1))/dt_p = (\Phi^{-1}(p) + o(1))/\sqrt{d}

主要证明策略

下界证明

  1. Erdős-Rényi类型下界：通过几何论证证明P(E)≥p(n2)P(E) \geq p^{\binom{n}{2}}
  2. 偏置论证：在高斯模型中，对所有向量的第一个坐标施加小的偏置
  3. 维数依赖界：当log⁡n<εd\log n < \varepsilon d时，P(E~)≥exp⁡(−Cndlog⁡n)P(\tilde{E}) \geq \exp(-Cn\sqrt{d \log n})

上界证明

  1. 贝叶斯论证：利用统计量S=∑i≠j⟨X~i,X~j⟩S = \sum_{i \neq j} \langle \tilde{X}_i, \tilde{X}_j \rangle的性质
  2. 球帽过程分析：通过对称重排将复杂的凸集过程转化为球帽过程
  3. 矩生成函数方法：对边数偏差问题使用指数马尔可夫不等式

实验结果

完全图概率的主要结果

根据定理 2.1和定理 2.2，完全图概率在不同维数区间有不同的衰减率：

维数区间下界上界
d≳n2d \gtrsim n^2−Cn2-Cn^2−cn2-cn^2
n2/log⁡n≲d≲n2n^2/\log n \lesssim d \lesssim n^2−Cnd-Cn\sqrt{d}−cn2-cn^2
n4/3+o(1)≲d≲n2/log⁡nn^{4/3+o(1)} \lesssim d \lesssim n^2/\log n−Cnd-Cn\sqrt{d}−cndlog⁡n-cn\sqrt{d \log n}
log⁡n≲d≲n4/3+o(1)\log n \lesssim d \lesssim n^{4/3+o(1)}−Cndlog⁡n-Cn\sqrt{d \log n}−cndlog⁡n-cn\sqrt{d \log n}
d≲log⁡nd \lesssim \log n−Cnd-Cnd−cnd-cnd

边数大偏差的主要结果

定理 2.3和定理 2.4给出了边数大偏差的精确界：

对于事件Iε:={∣E(G)∣≥(1+ε)(n2)p}I_\varepsilon := \{|E(G)| \geq (1+\varepsilon)\binom{n}{2}p\}，有： exp⁡(−cmin⁡(n2,nd))≤P(Iε)≤exp⁡(−Cmin⁡(n2,nd))\exp(-c\min(n^2, n\sqrt{d})) \leq P(I_\varepsilon) \leq \exp(-C\min(n^2, n\sqrt{d}))

关键发现

  1. 维数阈值效应：当d≳nd \gtrsim \sqrt{n}时，衰减率为exp⁡(−Ω(n2))\exp(-\Omega(n^2))，类似于Erdős-Rényi模型
  2. 几何效应保持：当d≲nd \lesssim \sqrt{n}时，衰减率为exp⁡(−Ω(nd))\exp(-\Omega(n\sqrt{d}))，体现了几何结构的影响
  3. 匹配上下界：在区间d≥n2d \geq n^2和d≤n4/3+o(1)d \leq n^{4/3+o(1)}获得了匹配的上下界

相关工作

高维随机几何图研究

  • Devroye等 (2011)：研究了d≫log⁡(n)d \gg \log(n)情况下的团数问题
  • Bubeck等 (2016)：建立了几何可检测性的相变：d≪n3d \ll n^3时几何可检测，d≫n3d \gg n^3时不可检测

大偏差理论

  • Chatterjee & Harel (2020)：研究了泊松点过程生成的随机几何图中边数的大偏差
  • Schreiber & Yukich (2005)：建立了空间点过程泛函的大偏差原理

对称重排技术

  • Draghici (2005)：发展了球面上的重排不等式理论，为本文的核心技术工具提供了基础

技术创新点

1. 耦合技术的创新应用

通过X~/∥X~∥\tilde{X}/\|\tilde{X}\|的球面投影建立两种模型的联系，避免了重复分析的复杂性。

2. 几何工具的概率应用

将对称重排这一几何分析工具创新性地应用于概率论问题，特别是在处理复杂的边依赖关系方面。

3. 多尺度分析框架

针对不同的(n,d)(n,d)关系建立了统一的分析框架，揭示了从低维到高维的过渡行为。

局限性与未来方向

局限性

  1. 技术限制：在中间区间n4/3≲d≲n2n^{4/3} \lesssim d \lesssim n^2，上下界存在gap
  2. 模型限制：主要考虑p≤1/2p \leq 1/2的情况，对于p>1/2p > 1/2的分析相对有限
  3. 方法限制：对称重排过程中信息损失导致某些界不够紧

未来研究方向

  1. 完善理论界：缩小中间区间的上下界gap
  2. 扩展模型：考虑更一般的pp值和其他几何度量
  3. 算法应用：将理论结果应用于实际的网络分析和机器学习问题
  4. 动态模型：研究时变随机几何图的稀有事件

深度评价

优点

  1. 理论深度：建立了完整的数学理论框架，结合了几何学、概率论和分析学的深刻结果
  2. 技术创新：对称重排技术在随机图理论中的应用具有开创性
  3. 结果完整性：在多个维数区间给出了精确的上下界，展现了问题的复杂性
  4. 方法通用性：所develop的技术可以推广到其他几何随机图问题

不足

  1. 完整性缺陷：中间区间的上下界不匹配影响了结果的完整性
  2. 实用性限制：主要是理论结果，缺乏数值验证和实际应用展示
  3. 技术复杂性：证明技术较为复杂，可能限制了结果的可推广性

学术影响

  1. 理论贡献：为高维随机几何图理论提供了重要的理论基础
  2. 方法论贡献：对称重排技术的应用为相关问题提供了新的分析工具
  3. 启发价值：揭示了维数在随机几何图中的关键作用，为后续研究提供了方向

适用场景

  1. 理论研究：随机图理论、几何概率论、高维现象研究
  2. 应用领域：网络科学、机器学习中的核方法、高维统计
  3. 算法设计：基于几何图的算法分析和优化

结论

本文在随机几何图的稀有事件分析方面取得了重要的理论突破。通过创新性地结合对称重排技术和概率论方法，为高维球面和高斯随机几何图中的完全图概率和边数大偏差问题提供了系统性的分析。虽然在某些技术细节上还有改进空间，但其建立的理论框架和获得的深刻结果为该领域的发展奠定了坚实基础，具有重要的学术价值和启发意义。