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

यादृच्छिक ज्यामितीय ग्राफ़ में दुर्लभ घटना की संभावनाएं

मूल जानकारी

पेपर ID: 2510.09196
शीर्षक: यादृच्छिक ज्यामितीय ग्राफ़ में दुर्लभ घटना की संभावनाएं
लेखक: प्रभंक देका (बीजिंग विश्वविद्यालय, बीजिंग अंतर्राष्ट्रीय गणित अनुसंधान केंद्र), फांगझोउ लुओ (बीजिंग विश्वविद्यालय, गणितीय विज्ञान संस्थान), बाइचुआन वू (बीजिंग विश्वविद्यालय, गणितीय विज्ञान संस्थान)
वर्गीकरण: math.PR (संभाव्यता सिद्धांत)
प्रकाशन तिथि: 10 अक्टूबर 2025 (arXiv प्रीप्रिंट)
पेपर लिंक: https://arxiv.org/abs/2510.09196

सारांश

यह पेपर उच्च-आयामी गोलाकार और गॉसियन यादृच्छिक ज्यामितीय ग्राफ़ में दुर्लभ घटनाओं का अध्ययन करता है। इन मॉडलों में, शीर्ष $d$ -आयामी इकाई गोले $S^{d-1}$ पर समान रूप से यादृच्छिक नमूना किए गए बिंदुओं या $d$ -आयामी मानक गॉसियन वेक्टर के अनुरूप हैं। दो शीर्षों के बीच एक किनारा तब जोड़ा जाता है जब संबंधित बिंदुओं का आंतरिक गुणनफल सीमा $t_p$ से अधिक हो, जहां $t_p$ को इस प्रकार चुना जाता है कि किनारे के अस्तित्व की संभावना $p$ के बराबर हो। यह पेपर दो समस्याओं पर केंद्रित है: (a) यादृच्छिक ज्यामितीय ग्राफ़ के पूर्ण ग्राफ़ होने की संभावना, और (b) असामान्य रूप से बड़ी संख्या में किनारों को देखने की संभावना। ज्यामितीय और संभाव्यता तर्कों के संयोजन के माध्यम से, इन दुर्लभ घटना संभावनाओं के स्पर्शोन्मुख घातीय क्षय दर प्राप्त किए गए हैं, जो शीर्षों की संख्या $n$ और आयाम $d$ पर निर्भर करते हैं।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या परिभाषा

इस पेपर में अध्ययन की गई मूल समस्या उच्च-आयामी यादृच्छिक ज्यामितीय ग्राफ़ में दुर्लभ घटनाओं के दो वर्गों का विश्लेषण है:

पूर्ण ग्राफ़ संभावना: यादृच्छिक ज्यामितीय ग्राफ़ के पूर्ण ग्राफ़ (सभी शीर्ष जोड़ों के बीच किनारे) होने की संभावना
किनारों की संख्या में बड़ा विचलन: असामान्य रूप से बड़ी संख्या में किनारों को देखने की संभावना

अनुसंधान का महत्व

सैद्धांतिक महत्व: यादृच्छिक ज्यामितीय ग्राफ़ जटिल प्रणालियों को मॉडल करने के लिए मौलिक उपकरण हैं, जो कंप्यूटर विज्ञान, जीव विज्ञान, समाजशास्त्र और भौतिकी में व्यापक रूप से लागू होते हैं
व्यावहारिक अनुप्रयोग:
- विसंगति पहचान और परिकल्पना परीक्षण
- उच्च-आयामी डेटा में क्लिक संरचना विश्लेषण
- ज्यामितीय नेटवर्क मॉडल की मजबूती विश्लेषण
- तंत्रिका नेटवर्क और कर्नेल विधियों में आंतरिक गुणनफल-आधारित समानता माप

मौजूदा अनुसंधान की सीमाएं

पिछले कार्य मुख्य रूप से आयाम $d$ को निश्चित रखते हैं और शीर्षों की संख्या $n$ को अनंत तक जाने देते हैं
उच्च-आयामी सघन यादृच्छिक ज्यामितीय ग्राफ़ का व्यवस्थित विश्लेषण अभाव है
किनारों के बीच जटिल निर्भरता संबंध विश्लेषण को चुनौतीपूर्ण बनाते हैं

मुख्य योगदान

संपूर्ण सैद्धांतिक ढांचा स्थापित किया: गोलाकार और गॉसियन यादृच्छिक ज्यामितीय ग्राफ़ में दुर्लभ घटनाओं के लिए एकीकृत विश्लेषण विधि प्रदान की
सटीक क्षय दर प्राप्त किए: $n$ और $d$ के विभिन्न संबंधों में, पूर्ण ग्राफ़ संभावना और किनारों की संख्या के बड़े विचलन संभावना के ऊपरी और निचले सीमाएं दीं
नवीन तकनीकी उपकरण विकसित किए:
- गोलाकार सममिति पुनर्व्यवस्था तकनीक का अनुप्रयोग
- दोनों मॉडलों के बीच युग्मन विधि
- ज्यामितीय और संभाव्यता तर्कों का जैविक संयोजन
आयाम प्रभाव का खुलासा किया: उच्च-आयामी मामले में यादृच्छिक ज्यामितीय ग्राफ़ का व्यवहार Erdős-Rényi मॉडल के करीब है, जबकि निम्न-आयामी में विभिन्न विशेषताएं दिखाई देती हैं

विधि विवरण

मॉडल परिभाषा

गोलाकार यादृच्छिक ज्यामितीय ग्राफ़ (SRGG)

शीर्ष: $(X_1, \ldots, X_n)$ स्वतंत्र और समान रूप से $d$ -आयामी इकाई गोले $S^{d-1}$ पर समान रूप से वितरित
किनारे: जब $\langle X_i, X_j \rangle \geq t_p$ हो तो शीर्ष $i$ और $j$ के बीच किनारा
सीमा: $t_p$ को इस प्रकार चुना जाता है कि $P(\langle X_1, X_2 \rangle \geq t_p) = p$

गॉसियन यादृच्छिक ज्यामितीय ग्राफ़ (GRGG)

शीर्ष: $(\tilde{X}_1, \ldots, \tilde{X}_n)$ स्वतंत्र और समान रूप से $d$ -आयामी मानक सामान्य वितरण का पालन करते हैं
किनारे: जब $\langle \tilde{X}_i, \tilde{X}_j \rangle \geq \tilde{t}_p$ हो तो शीर्ष $i$ और $j$ के बीच किनारा
सीमा: $\tilde{t}_p$ को इस प्रकार चुना जाता है कि $P(\langle \tilde{X}_1, \tilde{X}_2 \rangle \geq \tilde{t}_p) = p$

मुख्य तकनीकी विधियां

1. मॉडल युग्मन तकनीक

$\tilde{X}/\|\tilde{X}\|$ के गोले पर समान वितरण का अवलोकन करके दोनों मॉडलों के बीच युग्मन संबंध स्थापित करना:

लेम्मा 3.2: निश्चित $p < 1/2$ और छोटे $\delta > 0$ के लिए, स्थिरांक $c_\delta, \Delta_\delta$ मौजूद हैं, जैसे कि: $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: गोले पर फलनों $f_1, \ldots, f_n$ और बढ़ते फलन $K_{i,j}$ के लिए: $I[f_1, \ldots, f_n] \leq I[f_1^*, \ldots, f_n^*]$ जहां $f^*$ $f$ की सममिति पुनर्व्यवस्था को दर्शाता है।

3. सीमा स्पर्शोन्मुख व्यवहार

लेम्मा 3.1: निश्चित $p \in (0,1)$ के लिए, जब $d \to \infty$ :

$\tilde{t}_p = (\Phi^{-1}(p) + o(1))\sqrt{d}$
$t_p = (\Phi^{-1}(p) + o(1))/\sqrt{d}$

मुख्य प्रमाण रणनीति

निचली सीमा प्रमाण

Erdős-Rényi प्रकार की निचली सीमा: ज्यामितीय तर्क के माध्यम से $P(E) \geq p^{\binom{n}{2}}$ सिद्ध करना
पूर्वाग्रह तर्क: गॉसियन मॉडल में, सभी वेक्टरों के पहले निर्देशांक पर छोटा पूर्वाग्रह लागू करना
आयाम-निर्भर सीमा: जब $\log n < \varepsilon d$ हो तो $P(\tilde{E}) \geq \exp(-Cn\sqrt{d \log n})$

ऊपरी सीमा प्रमाण

बेयस तर्क: सांख्यिकीय $S = \sum_{i \neq j} \langle \tilde{X}_i, \tilde{X}_j \rangle$ के गुणों का उपयोग
गोलाकार टोपी प्रक्रिया विश्लेषण: सममिति पुनर्व्यवस्था के माध्यम से जटिल उत्तल समुच्चय प्रक्रिया को गोलाकार टोपी प्रक्रिया में परिवर्तित करना
आघूर्ण उत्पन्न करने वाली फलन विधि: किनारों की संख्या विचलन समस्या के लिए घातीय मार्कोव असमानता का उपयोग

प्रायोगिक परिणाम

पूर्ण ग्राफ़ संभावना के मुख्य परिणाम

प्रमेय 2.1 और प्रमेय 2.2 के अनुसार, पूर्ण ग्राफ़ संभावना विभिन्न आयाम अंतरालों में विभिन्न क्षय दर रखती है:

आयाम अंतराल	निचली सीमा	ऊपरी सीमा
$d \gtrsim n^2$	$-Cn^2$	$-cn^2$
$n^2/\log n \lesssim d \lesssim n^2$	$-Cn\sqrt{d}$	$-cn^2$
$n^{4/3+o(1)} \lesssim d \lesssim n^2/\log n$	$-Cn\sqrt{d}$	$-cn\sqrt{d \log n}$
$\log n \lesssim d \lesssim n^{4/3+o(1)}$	$-Cn\sqrt{d \log n}$	$-cn\sqrt{d \log n}$
$d \lesssim \log n$	$-Cnd$	$-cnd$

किनारों की संख्या के बड़े विचलन के मुख्य परिणाम

प्रमेय 2.3 और प्रमेय 2.4 किनारों की संख्या के बड़े विचलन की सटीक सीमाएं देते हैं:

घटना $I_\varepsilon := \{|E(G)| \geq (1+\varepsilon)\binom{n}{2}p\}$ के लिए: $\exp(-c\min(n^2, n\sqrt{d})) \leq P(I_\varepsilon) \leq \exp(-C\min(n^2, n\sqrt{d}))$

मुख्य निष्कर्ष

आयाम सीमा प्रभाव: जब $d \gtrsim \sqrt{n}$ हो तो क्षय दर $\exp(-\Omega(n^2))$ है, जो Erdős-Rényi मॉडल के समान है
ज्यामितीय प्रभाव बना रहता है: जब $d \lesssim \sqrt{n}$ हो तो क्षय दर $\exp(-\Omega(n\sqrt{d}))$ है, जो ज्यामितीय संरचना के प्रभाव को दर्शाता है
मिलती-जुलती ऊपरी और निचली सीमाएं: अंतराल $d \geq n^2$ और $d \leq n^{4/3+o(1)}$ में मिलती-जुलती ऊपरी और निचली सीमाएं प्राप्त की गईं

तकनीकी नवाचार बिंदु

1. युग्मन तकनीक का नवीन अनुप्रयोग

$\tilde{X}/\|\tilde{X}\|$ के गोले पर प्रक्षेपण के माध्यम से दोनों मॉडलों के बीच संबंध स्थापित करना, दोहराए गए विश्लेषण की जटिलता से बचना।

2. ज्यामितीय उपकरणों का संभाव्यता अनुप्रयोग

सममिति पुनर्व्यवस्था को एक ज्यामितीय विश्लेषण उपकरण से संभाव्यता समस्याओं में नवीन रूप से लागू करना, विशेष रूप से जटिल किनारे निर्भरता संबंधों को संभालने में।

3. बहु-स्तरीय विश्लेषण ढांचा

विभिन्न $(n,d)$ संबंधों के लिए एकीकृत विश्लेषण ढांचा स्थापित करना, निम्न-आयामी से उच्च-आयामी तक के संक्रमण व्यवहार को प्रकट करना।

सीमाएं और भविष्य की दिशाएं

सीमाएं

तकनीकी सीमा: मध्य अंतराल $n^{4/3} \lesssim d \lesssim n^2$ में ऊपरी और निचली सीमाओं में अंतराल मौजूद है
मॉडल सीमा: मुख्य रूप से $p \leq 1/2$ के मामले पर विचार किया जाता है, $p > 1/2$ के विश्लेषण में सीमा है
विधि सीमा: सममिति पुनर्व्यवस्था प्रक्रिया में सूचना हानि कुछ सीमाओं को पर्याप्त रूप से कसने से रोकती है

भविष्य की अनुसंधान दिशाएं

सैद्धांतिक सीमाओं में सुधार: मध्य अंतराल में ऊपरी और निचली सीमाओं के बीच अंतराल को कम करना
मॉडल विस्तार: अधिक सामान्य $p$ मानों और अन्य ज्यामितीय मेट्रिक्स पर विचार करना
एल्गोरिथ्मिक अनुप्रयोग: सैद्धांतिक परिणामों को व्यावहारिक नेटवर्क विश्लेषण और मशीन लर्निंग समस्याओं में लागू करना
गतिशील मॉडल: समय-परिवर्तनशील यादृच्छिक ज्यामितीय ग्राफ़ में दुर्लभ घटनाओं का अध्ययन

गहन मूल्यांकन

शक्तियां

सैद्धांतिक गहराई: ज्यामिति, संभाव्यता सिद्धांत और विश्लेषण के गहन परिणामों को जोड़ते हुए संपूर्ण गणितीय सैद्धांतिक ढांचा स्थापित किया
तकनीकी नवाचार: यादृच्छिक ग्राफ़ सिद्धांत में सममिति पुनर्व्यवस्था तकनीक का अनुप्रयोग अग्रणी है
परिणाम पूर्णता: कई आयाम अंतरालों में सटीक ऊपरी और निचली सीमाएं, समस्या की जटिलता को प्रदर्शित करती हैं
विधि सामान्यता: विकसित तकनीकें अन्य ज्यामितीय यादृच्छिक ग्राफ़ समस्याओं तक विस्तारित की जा सकती हैं

कमियां

पूर्णता में कमी: मध्य अंतराल में ऊपरी और निचली सीमाओं का मेल न खाना परिणाम की पूर्णता को प्रभावित करता है
व्यावहारिकता सीमा: मुख्य रूप से सैद्धांतिक परिणाम, संख्यात्मक सत्यापन और व्यावहारिक अनुप्रयोग प्रदर्शन की कमी
तकनीकी जटिलता: प्रमाण तकनीकें काफी जटिल हैं, जो परिणामों की सामान्यीकरणीयता को सीमित कर सकती हैं

शैक्षणिक प्रभाव

सैद्धांतिक योगदान: उच्च-आयामी यादृच्छिक ज्यामितीय ग्राफ़ सिद्धांत के लिए महत्वपूर्ण सैद्धांतिक आधार प्रदान किया
पद्धति संबंधी योगदान: सममिति पुनर्व्यवस्था तकनीक का अनुप्रयोग संबंधित समस्याओं के लिए नई विश्लेषण उपकरण प्रदान करता है
प्रेरणा मूल्य: यादृच्छिक ज्यामितीय ग्राफ़ में आयाम की महत्वपूर्ण भूमिका को प्रकट करता है, बाद के अनुसंधान के लिए दिशा प्रदान करता है

लागू परिदृश्य

सैद्धांतिक अनुसंधान: यादृच्छिक ग्राफ़ सिद्धांत, ज्यामितीय संभाव्यता, उच्च-आयामी घटना अनुसंधान
अनुप्रयोग क्षेत्र: नेटवर्क विज्ञान, मशीन लर्निंग में कर्नेल विधियां, उच्च-आयामी सांख्यिकी
एल्गोरिथ्म डिजाइन: ज्यामितीय ग्राफ़-आधारित एल्गोरिथ्म विश्लेषण और अनुकूलन

निष्कर्ष

यह पेपर यादृच्छिक ज्यामितीय ग्राफ़ में दुर्लभ घटना विश्लेषण के क्षेत्र में महत्वपूर्ण सैद्धांतिक सफलता प्राप्त करता है। सममिति पुनर्व्यवस्था तकनीक और संभाव्यता विधियों को नवीन रूप से जोड़कर, उच्च-आयामी गोलाकार और गॉसियन यादृच्छिक ज्यामितीय ग्राफ़ में पूर्ण ग्राफ़ संभावना और किनारों की संख्या के बड़े विचलन समस्याओं के लिए व्यवस्थित विश्लेषण प्रदान किया। हालांकि कुछ तकनीकी विवरणों में सुधार की गुंजाइश है, लेकिन इसके द्वारा स्थापित सैद्धांतिक ढांचा और प्राप्त गहन परिणाम इस क्षेत्र के विकास के लिए एक मजबूत आधार प्रदान करते हैं, जिसका महत्वपूर्ण शैक्षणिक मूल्य और प्रेरणा महत्व है।