True Self-Avoiding Walk for Accelerating Markov-Chain Monte Carlo Integration

तकनीकी सारांश: मार्कोव-चेन मोंटे कार्लो एकीकरण को त्वरित करने के लिए ट्रू सेल्फ-अवॉइडिंग वॉक (True Self-Avoiding Walk)

समस्या विवरण
यह शोध पत्र मार्कोव चेन मोंटे कार्लो (MCMC) विधियों में अनुभवजन्य समाकल अनुमान (empirical integral estimation) की परिमित-समय गुणवत्ता (finite-time quality) को संबोधित करता है। एक परिमित अवस्था स्थान $V$, एक अपरिवर्तनीय (irreducible) मार्कोव कर्नेल $P$, और एक स्थिर वितरण (stationary distribution) $\pi$ दिए जाने पर, लक्ष्य एक प्रक्षेपवक्र (trajectory) $(X_t)_{t \geq 0}$ के अनुभवजन्य औसत का उपयोग करके स्थिर समाकल $\pi(f) = \sum_{x \in V} \pi(x)f(x)$ का अनुमान लगाना है।

मानक रैंडम-वॉक-आधारित MCMC विधियाँ "स्थानीय अति-नमूनाकरण" (local oversampling) से ग्रस्त होती हैं, जहाँ प्रक्षेपवक्र हाल ही में खोजे गए क्षेत्रों में बार-बार लौट आता है, जिससे अधिभोग असंतुलन (occupation imbalances) का सुधार धीमा हो जाता है। इसके परिणामस्वरूप, अनुभवजन्य औसत का त्रुटि आमतौर पर लगभग निश्चित रूप से (almost surely) $O(t^{-1/2})$ के रूप में स्केल करती है। जबकि स्व-विकर्षक (self-repellent) रैंडम वॉक (SRRW) पर हालिया कार्य ने विषम विचरण स्थिरांक (asymptotic variance constant) में सुधार किया है, त्रुटि स्केलिंग अभी भी मानक $O(t^{-1/2})$ स्तर पर बनी हुई है। लेखक नमूना आकार $t$ के लिए अनुभवजन्य समाकल त्रुटि हेतु एक तीक्ष्ण निर्भरता (sharper dependence) प्राप्त करने के लिए एक तंत्र की खोज कर रहे हैं।

कार्यप्रणाली
लेखक एक ट्रू सेल्फ-अवॉइडिंग वॉक (TSAW) गतिकी प्रस्तावित करते हैं जहाँ संक्रमण प्रायिकताएं (transition probabilities) अनुभवजन्य अति-उपयोग के आधार पर दंडित की जाती हैं। कार्यप्रणाली तीन विशिष्ट चरणों में आगे बढ़ती है:

1. स्टार ग्राफ पर वॉर्म-अप (Warm-up on the Star Graph): लेखक पहले एक स्टार ग्राफ (एक हब जो $n$ पत्तियों से जुड़ा है) पर एक सरलीकृत मॉडल का विश्लेषण करते हैं। एक एक्सपोनेंशियल-रेस एम्बेडिंग (exponential-race embedding) का उपयोग करके, वे विविक्त (discrete) TSAW गतिकी को निरंतर-समय जन्म प्रक्रिया (continuous-time birth process) में मैप करते हैं। यह कवर टाइम (cover time) के विस्तृत विश्लेषण की अनुमति देता है, जिससे यह प्रदर्शित होता है कि एक्सपोनेंशियल स्व-परहेज (self-avoidance) अन्वेषण पैमाने को शास्त्रीय कूपन-कलेक्टर क्रम $O(n \log n)$ से घटाकर $O(n \log \log n)$ कर देता है।

2. परिमित-वर्णमाला स्व-संतुलन मॉडल (Finite-Alphabet Self-Balancing Model): लेखक एक लक्षित वितरण $p$ वाले परिमित वर्णमाला $[d]$ के लिए एक स्थानीय नमूनाकरण नियम का निर्माण करते हैं। समय $t$ पर अवस्था $i$ के लिए संक्रमण प्रायिकता को लक्ष्य गणना से "अतिरेक" (excess) या "कमी" (deficit) द्वारा दंडित किए गए सॉफ्टमैक्स फलन के माध्यम से परिभाषित किया जाता है:
   $$P(X_{t+1} = i \mid \mathcal{F}_t) \propto \exp\left(-\lambda \Delta_i(t)\right),$$
   जहाँ $\Delta_i(t) = L_t(i) - t p_i$ लक्ष्य गणना से विचलन है।
   एक लयापुनोव फलन (Lyapunov function) $V(t) = e^{\alpha M(t)}$ (जहाँ $M(t)$ अधिकतम अतिरेक है) का उपयोग करते हुए, वे एक एक्सपोनेंशियल ड्रिफ्ट इनइक्वालिटी (exponential drift inequality) सिद्ध करते हैं। यह स्थापित करता है कि अधिकतम अतिरेक लगभग निश्चित रूप से $O(\sqrt{\log t})$ के भीतर सीमित रहता है, जिसमें समान घातीय क्षण सीमाएँ (uniform exponential moment bounds) मौजूद हैं।

3. सामान्य परिमित-अवस्था मार्कोव कर्नेल तक विस्तार (Lifting to General Finite-State Markov Kernels): इस स्थानीय तंत्र को एक सामान्य अपरिवर्तनीय मार्कोव कर्नेल $P$ पर एक सामान्य परिमित सेट $V$ के लिए विस्तारित किया जाता है। संक्रमण नियम अनुभवजन्य संक्रमण गणना $N_t(i, j)$ और अपेक्षित प्रवाह $L_t(i)P_{ij}$ के बीच विसंगति के आधार पर निर्देशित किनारों (directed edges) $(i, j)$ को दंडित करता है:
   $$P(X_{t+1} = j \mid X_t = i, \mathcal{F}_t) \propto P_{ij} \exp\left(-\lambda \epsilon_t(i, j)\right),$$
   जहाँ $\epsilon_t(i, j) = N_t(i, j) - L_t(i)P_{ij}$ है।
   विश्लेषण में शामिल हैं:

   • रो-वाइज रिडक्शन (Row-wise Reduction): प्रत्येक अवस्था $i$ से प्रस्थान के समयों पर प्रक्रिया को अलग करना, जिससे वैश्विक गतिकी को स्थानीय परिमित-वर्णमाला प्रक्रियाओं के संग्रह में बदल दिया जाता है।
   • वैश्विक विसंगति सीमाएँ (Global Discrepancy Bounds): वैश्विक टेल बाउंड (tail bound) के लिए स्थानीय घातीय क्षण सीमाओं को लागू करना, जिससे अधिकतम किनारा विसंगति $M(t)$ प्राप्त होती है।
   • पॉइसन समीकरण (Poisson Equation): ऑपरेटर $(I - P^\top)$ के ग्रुप इनवर्स का उपयोग करके $\epsilon_t$ को वर्टेक्स अधिभोग विसंगति $L_t - t\pi$ से जोड़ना। यह किनारा सीमाओं को अधिभोग गणनाओं में परिवर्तित करता है।

प्रमुख योगदान और परिणाम
लेखक TSAW-आधारित वॉक के लिए निम्नलिखित लगभग निश्चित (almost-sure) सीमाएं स्थापित करते हैं:

• अधिभोग और संक्रमण गणनाएँ: प्रत्येक अवस्था $i$ और किनारे $(i, j)$ के लिए जहाँ $P_{ij} > 0$, विसंगतियाँ संतुष्ट करती हैं:
  $$L_t(i) - t\pi_i = O(\sqrt{\log t})$$
  $$N_t(i, j) - t\pi_i P_{ij} = O(\sqrt{\log t})$$
  लगभग निश्चित रूप से।

• समाकल अनुमान त्रुटि: प्रत्येक सीमित फलन $f: V \to \mathbb{R}$ के लिए, समाकल का त्रुटि अनुमान निम्नलिखित रूप में अभिसरित होता है:
  $$\left| \frac{1}{t} \sum_{s=0}^{t-1} f(X_s) - \sum_{i \in V} \pi_i f(i) \right| = O\left(\frac{\sqrt{\log t}}{t}\right)$$
  लगभग निश्चित रूप से।

• पुनरावृत्ति (Recurrence): लेखक सिद्ध करते हैं कि इस गतिकी के तहत, प्रत्येक अवस्था और प्रत्येक निर्देशित किनारा जिसकी सकारात्मक संक्रमण प्रायिकता है, लगभग निश्चित रूप से अनंत बार विज़िट किया जाता है।

महत्व और दावे
यह शोध पत्र दावा करता है कि TSAW-आधारित अनुमानक मानक रैंडम-वॉक-आधारित विधियों और मौजूदा स्व-विकर्षक वॉक अनुमानकों की तुलना में नमूना आकार $t$ पर काफी तीक्ष्ण निर्भरता प्राप्त करता है। विशेष रूप से:

• मानक विधियाँ और SRRW (जैसा कि डोशी, हू, और यून [1] द्वारा विश्लेषित किया गया है) $O(t^{-1/2})$ की त्रुटि स्केलिंग प्रदर्शित करते हैं।
• प्रस्तावित TSAW अनुमानक $O(\sqrt{\log t}/t)$ प्राप्त करता है, जो $O(\sqrt{t/\log t})$ का सुधार कारक है।

लेखक अपने कार्य को स्व-परहेज रैंडम वॉक, गैर-रेखीय मार्कोव श्रृंखलाओं और MCMC विचरण न्यूनीकरण (variance reduction) के संगम पर रखते हैं। वे इस बात पर जोर देते हैं कि उनकी प्राथमिक नवीनता केवल विषम विचरण न्यूनीकरण के बजाय स्पष्ट परिमित-समय पथवार नियंत्रण (explicit finite-time pathwise control) प्रदान करने में निहित है। यह शोध पत्र निष्कर्ष निकालता है कि यह निर्माण अनुभवजन्य अनुमान में सुधार के लिए एक कठोर तंत्र प्रदान करता है और स्व-परहेज स्थानीय संतुलन नियमों से गैर-मार्कोवियन रैंडम वॉक बनाने के लिए एक सामान्य डिजाइन प्रतिमान प्रदान करता है।