Direct Sampling of Confined Polygons in Linear Time

तकनीकी सारांश: रैखिक समय में सीमित बहुभुजों (Confined Polygons) का प्रत्यक्ष नमूनाकरण (Direct Sampling)

समस्या विवरण
यह शोध पत्र तीन आयामी स्थान ($\mathbb{R}^3$) में यादृच्छिक समबाहु बंद बहुभुजों (equilateral closed polygons) के नमूनाकरण की चुनौती को संबोधित करता है, जो "कठोर सीमितता" (tight confinement) के अंतर्गत आते हैं। विशेष रूप से, लेखक त्रिज्या $R=1$ के मूलबद्ध गोलाकार सीमितता (rooted spherical confinement) के शासन पर ध्यान केंद्रित करते हैं, जहाँ पहला शीर्ष (vertex) मूल बिंदु (origin) पर स्थिर होता है, और सभी आगामी शीर्ष एक त्रिज्या 1 वाले गोले के भीतर होने चाहिए। चूंकि किनारे (edges) इकाई लंबाई के हैं, इसलिए $R=1$ सबसे कठोर संभव सीमितता का प्रतिनिधित्व करता है जहाँ दूसरा और अंतिम शीर्ष गोले की सतह पर स्थित होने के लिए मजबूर होते हैं।

ऐसे सीमित बहुभुजों का नमूनाकरण करना कम्प्यूटेशनल रूप से कठिन है क्योंकि क्लोजर कंडीशन ($\sum e_i = 0$) किनारों की दिशाओं के बीच गहरा सहसंबंध (correlation) उत्पन्न करती है। मौजूदा विधियाँ सीमित बहुभुजों के लिए निम्नलिखित कमियों से ग्रस्त हैं:

• डियाओ (Diao) आदि की विधि: क्रमिक मार्जिनल (successive marginals) उत्पन्न करने पर आधारित यह विधि कम्प्यूटेशनल रूप से महंगी ($\Theta(n^2)$ या उससे अधिक) है, जिससे बड़े एन्सेम्बल (ensembles) बनाना कठिन हो जाता है।
• टोरिक सिम्पलेक्टिक मार्कोव चेन मोंटे कार्लो (TSMCMC): हालांकि यह बड़े एन्सेम्बल बनाने में सक्षम है, लेकिन यह एक मार्कोव चेन पर निर्भर करता है जिसके अभिसरण दर (convergence rates) को समझना कठिन है, जिससे प्रभावी नमूना आकार (effective sample size) का अनुमान लगाना मुश्किल हो जाता है।

कार्यप्रणाली (Methodology)
लेखक कन्फाइंड पॉलिगन्स फ्रॉम ऑर्डर पॉलीटोप्स (CPOP) एल्गोरिदम पेश करते हैं। कार्यप्रणाली तीन मुख्य चरणों में से गुजरती है:

1. सिम्पलेक्टिक रिडक्शन (Symplectic Reduction):
   बहुभुज स्थान की सिम्पलेक्टिक ज्यामिति (विशेष रूप से कपकोविच, मिल्सन, कैंटारेला और शोनक्विलर द्वारा स्थापित एक्शन-एंगल निर्देशांकों) का उपयोग करते हुए, समबाहु $n$-गोंस (n-gons) के नमूनाकरण की समस्या को एक विशिष्ट उत्तल पॉलीटोप $P_n(1) \subset \mathbb{R}^{n-3}$ से एक बिंदु के नमूनाकरण में बदल दिया जाता है। इस पॉलीटोप के निर्देशांक विकर्ण लंबाई (diagonal lengths) $d_i = |v_{i+2} - v_1|$ के अनुरूप होते हैं।

   • $R=1$ के लिए, $P_n(1)$ की परिभाषित असमानताएं सरल होकर $0 \le d_i \le 1$ और $d_i + d_{i+1} \ge 1$ हो जाती हैं।

2. संयोजन संबंधी संबंध (Combinatorial Connection):
   एक एफ़ाइन ट्रांसफॉर्मेशन $\varphi$ के माध्यम से, पॉलीटोप $P_n(1)$ को ज़िग-ज़ैग ऑर्डर पॉलीटोप $O_{n-3}$ में मैप किया जाता है, जो ज़िग-ज़ैग पोसेट (poset) का ऑर्डर पॉलीटोप है।

   • इस पॉलीटोप का आयतन यूलर संख्याओं (या अप-डाउन संख्याओं) से संबंधित है, जो अल्टरनेटिंग परम्यूटेशन (alternating permutations) की गणना करती हैं।
   • यह पॉलीटोप अल्टरनेटिंग परम्यूटेशन द्वारा अनुक्रमित ऑर्थोस्कीम्स (orthoschemes) में एक यूनिमॉडुलर त्रिकोणीकरण (unimodular triangulation) को स्वीकार करता है।

3. रैखिक-समय नमूनाकरण एल्गोरिदम (Linear-Time Sampling Algorithm):
   लेखक मार्शल (Marchal) के एक एल्गोरिदम (जो मूल रूप से अल्टरनेटिंग परम्यूटेशन के नमूनाकरण के लिए डिज़ाइन किया गया था) को $P_n(1)$ पर लेबेग माप (Lebesgue measure) से सीधे $d_1, \dots, d_{n-3}$ विकर्ण लंबाई को नमूना लेने के लिए अनुकूलित करते हैं।

   • एल्गोरिदम एक विशिष्ट सशर्त घनत्व (conditional density) का उपयोग करके एक मार्कोव चेन के माध्यम से $d_1, \dots, d_{n-3}$ विकर्ण लंबाई का निर्माण करता है, जो फलन $h(x) = \sin(\frac{\pi}{2}x)$ से व्युत्पन्न है।
   • एकरूपता (uniformity) सुनिश्चित करने के लिए, एल्गोरिदम एक अनुक्रम उत्पन्न करता है, उसे उलट देता है, और पहले और अंतिम तत्वों के बीच एक प्रायिकता अनुपात के आधार पर परिणाम को स्वीकार करता है।
   • एक बार विकर्ण लंबाई का नमूना लेने के बाद, $[0, 2\pi)$ से स्वतंत्र डायहेड्रल कोणों (dihedral angles) का नमूना लेकर और रिकंस्ट्रक्शन मैप लागू करके बहुभुज का पुनर्निर्माण किया जाता है।

मुख्य योगदान

• CPOP एल्गोरिदम: सीमित समबाहु $n$-गोंस के लिए एक प्रत्यक्ष नमूनाकरण एल्गोरिदम जिसका औसत समय जटिलता $\Theta(n)$ है। यह सैद्धांतिक रूप से इष्टतम है और पिछली विधियों की तुलना में काफी तेज़ है।
• अपेक्षित दूरियों के स्पष्ट सूत्र: ऑर्डर पॉलीटोप की संयोजन संरचना का लाभ उठाते हुए, लेखक मूल बिंदु से $i$-वें शीर्ष की अपेक्षित दूरी के सटीक सूत्र प्राप्त करते हैं। ये अपेक्षाएं एंट्रिंगर संख्याओं (Entringer numbers) और ऑगमेंटेड ज़िग-ज़ैग पोसेट के रैखिक विस्तार (linear extensions) की संख्या के पदों में व्यक्त की गई हैं।
• एसिम्प्टोटिक विश्लेषण (Asymptotic Analysis): शोध पत्र कॉर्ड लंबाई (chord lengths) के अपेक्षित मानों के लिए सटीक एसिम्प्टोटिक सूत्र प्रदान करता है, जो दिखाते हैं कि वे घनत्व $f(t) = 1 - \cos(\pi t)$ वाले एक सीमित वितरण की ओर अभिसरित होते हैं।
• कुल वक्रता (Total Curvature) पर अनुमान: CPOP एल्गोरिदम का उपयोग करके बड़े एन्सेम्बल (20,000 तक $n$) उत्पन्न करते हुए, लेखक अपेक्षित कुल वक्रता की जांच करते हैं। वे औसत टर्निंग एंगल के लिए एक अत्यधिक सटीक एसिम्प्टोटिक अनुमान प्रस्तावित करते हैं।

परिणाम

• प्रदर्शन: एल्गोरिदम एक मानक डेस्कटॉप कंप्यूटर पर लगभग प्रति सेकंड 500 की दर से 20,000-गोंस उत्पन्न करता है। नमूनाकरण चरण की रिजेक्शन प्रायिकता (rejection probability) तेजी से $1 - 8/\pi^2 \approx 0.1894$ की ओर अभिसरित होती है।
• अपेक्षित कॉर्ड लंबाई: मूल बिंदु से $i$-वें शीर्ष की अपेक्षित दूरी $\mathbb{E}[d_i] = \frac{e(Z_{n-3, i})}{(n-2)E_{n-3}}$ द्वारा दी गई है, जहाँ $e(Z)$ एक ऑगमेंटेड ज़िग-ज़ैग पोसेट के रैखिक विस्तारों की संख्या है और $E$ यूलर संख्या है। एसिम्प्टोटिक रूप से, ये मान $\frac{1}{2} + \frac{2}{\pi^2} \approx 0.7026$ की ओर अभिसरित होते हैं।
• कुल वक्रता: संख्यात्मक प्रयोगों से पता चलता है कि बड़े $n$ के लिए अपेक्षित कुल वक्रता $\mathbb{E}[\kappa]$ निम्नलिखित रूप का अनुसरण करती है:
  $$\mathbb{E}[\kappa] \approx \left(\frac{\pi}{2} + 0.57545\right)n - 0.46742$$
  यह दर्शाता है कि औसत टर्निंग एंगल $\approx 2.14625$ की ओर नीचे से बढ़ता है, जिसमें $O(1/n)$ क्रम का एक सुधार पद (correction term) शामिल है। यह परिणाम डियाओ आदि के पिछले मॉडलों के साथ संगत है, लेकिन उससे अधिक सटीक है।

महत्ता और दावे
शोध पत्र का दावा है कि CPOP विशेष रूप से $R=1$ के मामले के लिए एक "बेहतर" (dramatically better) नमूनाकरण उपकरण प्रदान करता है, जो गति और मार्कोव चेन मोंटे कार्लो विधियों में निहित अभिसरण संबंधी चिंताओं के बिना स्वतंत्र, समान रूप से वितरित नमूनों को उत्पन्न करने की क्षमता दोनों प्रदान करता है।

सिम्पलेक्टिक ज्यामिति और संयोजन विज्ञान (विशेष रूप से अल्टरनेटिंग परम्यूटेशन और ऑर्डर पॉलीटोप) के बीच का संबंध उस तंत्र को उजागर करता है जो न केवल तेज़ नमूनाकरण बल्कि स्पष्ट सांख्यिकीय सूत्रों के व्युत्पन्न को भी सक्षम बनाता है। लेखक नोट करते हैं कि जबकि एल्गोरिदम वर्तमान में $R=1$ तक सीमित है, प्राप्त संयोजन संबंधी अंतर्दृष्टि (जैसे कि $P_n(R)$ की संरचना) भविष्य के कार्यों को सूचित कर सकती है। शोध पत्र $R > 1$ के विस्तार और वक्रता स्थिरांकों के विश्लेषणात्मक व्युत्पन्न को भविष्य के अनुसंधान के लिए खुले प्रश्नों के रूप में चिह्नित करते हुए समाप्त होता है।