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

র্যান্ডম জিওমেট্রিক গ্রাফে বিরল ঘটনার সম্ভাবনা

মৌলিক তথ্য

পেপার আইডি: 2510.09196
শিরোনাম: র্যান্ডম জিওমেট্রিক গ্রাফে বিরল ঘটনার সম্ভাবনা
লেখক: প্রভঙ্কর দেকা (পিকিং বিশ্ববিদ্যালয়, বিজিং আন্তর্জাতিক গণিত গবেষণা কেন্দ্র), ফাংজু লুও (পিকিং বিশ্ববিদ্যালয়, গণিত বিজ্ঞান একাডেমি), বাইচুয়ান উ (পিকিং বিশ্ববিদ্যালয়, গণিত বিজ্ঞান একাডেমি)
শ্রেণীবিভাগ: math.PR (সম্ভাবনা তত্ত্ব)
প্রকাশনার সময়: ২০২৫ সালের ১০ অক্টোবর (arXiv প্রাক-প্রিন্ট)
পেপার লিংক: https://arxiv.org/abs/2510.09196

সারসংক্ষেপ

এই পেপারটি উচ্চ-মাত্রিক গোলক এবং গাউসীয় র্যান্ডম জিওমেট্রিক গ্রাফে বিরল ঘটনা অধ্যয়ন করে। এই মডেলগুলিতে, শীর্ষবিন্দুগুলি $d$ -মাত্রিক একক গোলকের উপর সমানভাবে র্যান্ডমভাবে নমুনা করা বিন্দু বা $d$ -মাত্রিক মান গাউসীয় ভেক্টরের সাথে সামঞ্জস্যপূর্ণ। দুটি শীর্ষবিন্দুর অভ্যন্তরীণ গুণফল $t_p$ থ্রেশহোল্ডের চেয়ে বেশি হলে তাদের মধ্যে একটি প্রান্ত যোগ করা হয়, যেখানে $t_p$ এমনভাবে নির্বাচিত হয় যাতে প্রান্ত বিদ্যমান থাকার সম্ভাবনা $p$ এর সমান হয়। এই পেপারটি দুটি সমস্যার উপর দৃষ্টি নিবদ্ধ করে: (ক) র্যান্ডম জিওমেট্রিক গ্রাফ সম্পূর্ণ গ্রাফ হওয়ার সম্ভাবনা, এবং (খ) অস্বাভাবিকভাবে বড় সংখ্যক প্রান্ত পর্যবেক্ষণ করার সম্ভাবনা। জ্যামিতিক এবং সম্ভাবনাগত যুক্তির সমন্বয়ের মাধ্যমে, এই বিরল ঘটনার সম্ভাবনার অ্যাসিম্পটোটিক সূচকীয় হ্রাসের হার প্রাপ্ত করা হয়েছে, যা শীর্ষবিন্দু সংখ্যা $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$

মূল প্রযুক্তিগত পদ্ধতি

১. মডেল সংযোগ কৌশল

$\tilde{X}/\|\tilde{X}\|$ গোলক প্রজেকশনের মাধ্যমে দুটি মডেলের সম্পর্ক স্থাপন করে, পুনরাবৃত্ত বিশ্লেষণের জটিলতা এড়ায়:

লেম্মা ৩.২: স্থির $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))$

২. প্রতিসাম্য পুনর্বিন্যাস কৌশল

জটিল জ্যামিতিক সীমাবদ্ধতা পরিচালনা করতে গোলকে প্রতিসাম্য পুনর্বিন্যাস ব্যবহার করে:

উপপাদ্য ৩.৪: গোলকে ফাংশন $f_1, \ldots, f_n$ এবং বর্ধনশীল ফাংশন $K_{i,j}$ এর জন্য: $I[f_1, \ldots, f_n] \leq I[f_1^*, \ldots, f_n^*]$ যেখানে $f^*$ হল $f$ এর প্রতিসাম্য পুনর্বিন্যাস।

৩. থ্রেশহোল্ড অ্যাসিম্পটোটিক আচরণ

লেম্মা ৩.১: স্থির $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$ এর বৈশিষ্ট্য ব্যবহার করে
গোলক ক্যাপ প্রক্রিয়া বিশ্লেষণ: প্রতিসাম্য পুনর্বিন্যাসের মাধ্যমে জটিল উত্তল সেট প্রক্রিয়াকে গোলক ক্যাপ প্রক্রিয়ায় রূপান্তরিত করে
মুহূর্ত উৎপাদনকারী ফাংশন পদ্ধতি: প্রান্তের সংখ্যার বিচ্যুতি সমস্যায় সূচকীয় মার্কভ অসমতা ব্যবহার করে

পরীক্ষামূলক ফলাফল

সম্পূর্ণ গ্রাফ সম্ভাবনার প্রধান ফলাফল

উপপাদ্য ২.১ এবং উপপাদ্য ২.२ অনুযায়ী, সম্পূর্ণ গ্রাফ সম্ভাবনা বিভিন্ন মাত্রা অন্তরালে বিভিন্ন হ্রাসের হার রয়েছে:

মাত্রা অন্তরাল	নিচের সীমা	উপরের সীমা
$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$

প্রান্তের সংখ্যার বড় বিচ্যুতির প্রধান ফলাফল

উপপাদ্য ২.३ এবং উপপাদ্য २.४ প্রান্তের সংখ্যার বড় বিচ্যুতির নির্ভুল সীমা প্রদান করে:

ঘটনা $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)}$ এ মিলিত উপরের এবং নিচের সীমা প্রাপ্ত করা হয়েছে

প্রযুক্তিগত উদ্ভাবন বিন্দু

১. সংযোগ কৌশলের উদ্ভাবনী প্রয়োগ

$\tilde{X}/\|\tilde{X}\|$ এর গোলক প্রজেকশনের মাধ্যমে দুটি মডেলের সংযোগ স্থাপন করে, পুনরাবৃত্ত বিশ্লেষণের জটিলতা এড়ায়।

२. জ্যামিতিক সরঞ্জামের সম্ভাবনাগত প্রয়োগ

প্রতিসাম্য পুনর্বিন্যাস এই জ্যামিতিক বিশ্লেষণ সরঞ্জামকে সম্ভাবনা তত্ত্বের সমস্যায় উদ্ভাবনীভাবে প্রয়োগ করে, বিশেষত জটিল প্রান্ত নির্ভরতা সম্পর্ক পরিচালনায়।

३. বহু-স্কেল বিশ্লেষণ কাঠামো

বিভিন্ন $(n,d)$ সম্পর্কের জন্য একটি একীভূত বিশ্লেষণ কাঠামো স্থাপন করে, নিম্ন-মাত্রিক থেকে উচ্চ-মাত্রিক পর্যন্ত রূপান্তর আচরণ প্রকাশ করে।

সীমাবদ্ধতা এবং ভবিষ্যত দিকনির্দেশনা

সীমাবদ্ধতা

প্রযুক্তিগত সীমাবদ্ধতা: মধ্য অন্তরাল $n^{4/3} \lesssim d \lesssim n^2$ এ, উপরের এবং নিচের সীমার মধ্যে ফাঁক রয়েছে
মডেল সীমাবদ্ধতা: প্রধানত $p \leq 1/2$ ক্ষেত্র বিবেচনা করে, $p > 1/2$ এর বিশ্লেষণ তুলনামূলকভাবে সীমিত
পদ্ধতি সীমাবদ্ধতা: প্রতিসাম্য পুনর্বিন্যাস প্রক্রিয়ায় তথ্য হ্রাস কিছু সীমাকে যথেষ্ট কঠোর করতে বাধা দেয়

ভবিষ্যত গবেষণা দিকনির্দেশনা

তাত্ত্বিক সীমা উন্নত করা: মধ্য অন্তরালের উপরের এবং নিচের সীমার ফাঁক কমানো
মডেল সম্প্রসারণ: আরও সাধারণ $p$ মান এবং অন্যান্য জ্যামিতিক পরিমাপ বিবেচনা করা
অ্যালগরিদমিক প্রয়োগ: তাত্ত্বিক ফলাফলকে ব্যবহারিক নেটওয়ার্ক বিশ্লেষণ এবং মেশিন লার্নিং সমস্যায় প্রয়োগ করা
গতিশীল মডেল: সময়-পরিবর্তনশীল র্যান্ডম জিওমেট্রিক গ্রাফের বিরল ঘটনা অধ্যয়ন করা

গভীর মূল্যায়ন

শক্তি

তাত্ত্বিক গভীরতা: জ্যামিতি, সম্ভাবনা তত্ত্ব এবং বিশ্লেষণের গভীর ফলাফল একত্রিত করে একটি সম্পূর্ণ গাণিতিক তাত্ত্বিক কাঠামো স্থাপন করে
প্রযুক্তিগত উদ্ভাবন: র্যান্ডম গ্রাফ তত্ত্বে প্রতিসাম্য পুনর্বিন্যাস কৌশলের প্রয়োগ অগ্রগামী
ফলাফলের সম্পূর্ণতা: একাধিক মাত্রা অন্তরালে নির্ভুল উপরের এবং নিচের সীমা প্রদান করে, সমস্যার জটিলতা প্রদর্শন করে
পদ্ধতির সার্বজনীনতা: বিকশিত প্রযুক্তি অন্যান্য জ্যামিতিক র্যান্ডম গ্রাফ সমস্যায় সাধারণীকরণ করা যেতে পারে

ত্রুটি

সম্পূর্ণতার ত্রুটি: মধ্য অন্তরালের উপরের এবং নিচের সীমার অমিল ফলাফলের সম্পূর্ণতাকে প্রভাবিত করে
ব্যবহারিক প্রয়োগের সীমাবদ্ধতা: প্রধানত তাত্ত্বিক ফলাফল, সংখ্যাগত যাচাইকরণ এবং ব্যবহারিক প্রয়োগ প্রদর্শনের অভাব
প্রযুক্তিগত জটিলতা: প্রমাণ প্রযুক্তি অত্যন্ত জটিল, যা ফলাফলের সাধারণীকরণযোগ্যতা সীমিত করতে পারে

একাডেমিক প্রভাব

তাত্ত্বিক অবদান: উচ্চ-মাত্রিক র্যান্ডম জিওমেট্রিক গ্রাফ তত্ত্বের জন্য গুরুত্বপূর্ণ তাত্ত্বিক ভিত্তি প্রদান করে
পদ্ধতিগত অবদান: প্রতিসাম্য পুনর্বিন্যাস কৌশলের প্রয়োগ সম্পর্কিত সমস্যার জন্য নতুন বিশ্লেষণ সরঞ্জাম প্রদান করে
অনুপ্রেরণামূলক মূল্য: মাত্রার র্যান্ডম জিওমেট্রিক গ্রাফে মূল ভূমিকা প্রকাশ করে, পরবর্তী গবেষণার জন্য দিকনির্দেশনা প্রদান করে

প্রযোজ্য পরিস্থিতি

তাত্ত্বিক গবেষণা: র্যান্ডম গ্রাফ তত্ত্ব, জ্যামিতিক সম্ভাবনা তত্ত্ব, উচ্চ-মাত্রিক ঘটনা গবেষণা
প্রয়োগ ক্ষেত্র: নেটওয়ার্ক বিজ্ঞান, মেশিন লার্নিংয়ে কার্নেল পদ্ধতি, উচ্চ-মাত্রিক পরিসংখ্যান
অ্যালগরিদম ডিজাইন: জ্যামিতিক গ্রাফ-ভিত্তিক অ্যালগরিদম বিশ্লেষণ এবং অপ্টিমাইজেশন

উপসংহার

এই পেপারটি র্যান্ডম জিওমেট্রিক গ্রাফের বিরল ঘটনা বিশ্লেষণে গুরুত্বপূর্ণ তাত্ত্বিক অগ্রগতি অর্জন করেছে। প্রতিসাম্য পুনর্বিন্যাস কৌশল এবং সম্ভাবনাগত পদ্ধতি উদ্ভাবনীভাবে একত্রিত করে, উচ্চ-মাত্রিক গোলক এবং গাউসীয় র্যান্ডম জিওমেট্রিক গ্রাফে সম্পূর্ণ গ্রাফ সম্ভাবনা এবং প্রান্তের সংখ্যার বড় বিচ্যুতি সমস্যার জন্য সিস্টেমেটিক বিশ্লেষণ প্রদান করে। যদিও কিছু প্রযুক্তিগত বিবরণে উন্নতির অবকাশ রয়েছে, তবে এর প্রতিষ্ঠিত তাত্ত্বিক কাঠামো এবং প্রাপ্ত গভীর ফলাফল এই ক্ষেত্রের উন্নয়নের জন্য একটি দৃঢ় ভিত্তি স্থাপন করে, যার গুরুত্বপূর্ণ একাডেমিক মূল্য এবং অনুপ্রেরণামূলক তাৎপর্য রয়েছে।