Asymptotically Optimal Sequential Testing with Markovian Data

तकनीकी सारांश: मार्कोवियन डेटा के साथ स्पर्शोन्मुखी रूप से इष्टतम अनुक्रमिक परीक्षण (Asymptotically Optimal Sequential Testing with Markovian Data)

समस्या का स्वरूप (Problem Formulation)
यह शोधपत्र एक एर्गोडिक (ergodic), परिमित-अवस्था वाले मार्कोव श्रृंखला (finite-state Markov chain) द्वारा उत्पन्न डेटा के लिए एक-पक्षीय, $\alpha$-सटीक, पावर-वन (power-one) अनुक्रमिक परिकल्पना परीक्षण (sequential hypothesis testing) के विषय को संबोधित करता है। इसका उद्देश्य एक मिश्रित शून्य परिकल्पना (composite null hypothesis) $\mathcal{P}$ और एक विलगित मिश्रित वैकल्पिक परिकल्पना (disjoint composite alternative hypothesis) $\mathcal{Q}$ के बीच अंतर करना है, जहाँ दोनों सेट स्टोकेस्टिक ट्रांजिशन मैट्रिसेस (stochastic transition matrices) के बने होते हैं। विशेष रूप से, अज्ञात ट्रांजिशन मैट्रिक्स से प्राप्त अनुक्रमिक प्रेक्षणों $X_1, X_2, \dots$ को देखते हुए, लक्ष्य यह निर्धारित करना है कि क्या मैट्रिक्स $\mathcal{P}$ (शून्य) से संबंधित है या $\mathcal{Q}$ (वैकल्पिक) से। परीक्षण ढांचे के लिए यह आवश्यक है कि जब शून्य सत्य हो, तो उसे अस्वीकार करने की संभावना किसी भी प्रारंभिक वितरण के लिए $\alpha$ से अनियंत्रित रूप से कम हो, जबकि जब वैकल्पिक परिकल्पना सत्य हो, तो उसे अस्वीकार करने की संभावना 1 हो। दक्षता का प्राथमिक मीट्रिक वैकल्पिक परिकल्पना के तहत अपेक्षित रुकने का समय (expected stopping time) है।

कार्यप्रणाली और मुख्य योगदान (Methodology and Key Contributions)
लेखक एक कठोर सैद्धांतिक ढांचा स्थापित करते हैं जो पूर्ववर्ती कार्यों का सामान्यीकरण करता है, जो आमतौर पर सरल परिकल्पनाओं (सिंगलटन नल्स) को मानते थे या स्पर्शोन्मुखी सन्निकटन (asymptotic approximations) पर निर्भर थे। उनके योगदान तीन प्रकार के हैं:

1. गैर-स्पर्शोन्मुखी उदाहरण-निर्भर निचला स्तर (Non-Asymptotic Instance-Dependent Lower Bound): यह शोधपत्र किसी भी वैध अनुक्रमिक परीक्षण के लिए अपेक्षित रुकने के समय $E_Q[\tau_\alpha]$ पर पहला गैर-स्पर्शोन्मुखी, उदाहरण-निर्भर निचला स्तर (lower bound) व्युत्पन्न करता है। यह स्तर एक नए सूचना-सैद्धांतिक परिमाण, $D_M^{\inf}(Q, \mathcal{P})$ द्वारा अभिलक्षित है, जो शून्य सेट $\mathcal{P}$ पर स्टेशनरी-भारित कुलबैक-लीब्लर (KL) डाइवर्जेंस के इन्फिमम (infimum) के रूप में परिभाषित है। यह निचला स्तर वैकल्पिक श्रृंखला $Q$ के संरचनात्मक गुणों पर निर्भर एक सुधार पद (correction term) को शामिल करता है, जिसमें विशेष रूप से पॉइसन समीकरण (Poisson equation) के समाधान का उपयोग किया गया है। यह परिणाम मौजूदा बाउंड्स में सुधार करता है, जो या तो स्पर्शोन्मुखी हैं या इस मिश्रित सेटिंग में सिद्ध रूप से उप-इष्टतम (sub-optimal) हैं।

2. स्पर्शोन्मुखी रूप से इष्टतम परीक्षण (Asymptotically Optimal Test): लेखक एक अनुक्रमिक परीक्षण प्रक्रिया (एल्गोरिदम 1) प्रस्तावित करते हैं जो $\alpha \to 0$ होने पर व्युत्पन्न निचले स्तर से प्रथम क्रम (first order) में मेल खाती है। परीक्षण देखे गए अवस्था-संक्रमण गणनाओं (state-transition counts) से एक अनुभवजन्य संक्रमण कर्नेल (empirical transition kernel) का निर्माण करता है और एक परीक्षण सांख्यिकी (test statistic) की गणना करता है जो अनुभवजन्य कर्नेल और शून्य सेट $\mathcal{P}$ के बीच न्यूनतम KL डाइवर्जेंस पर आधारित होती है। प्रक्रिया तब रुकती है जब यह सांख्यिकी एक सीमा (boundary) को पार कर जाती है जो अवस्था विज़िटेशन गणनाओं (state visitation counts) पर निर्भर करती है। अनुकूलन प्रमाण एक मिश्रण मार्टिंगेल (mixture martingale) के निर्माण और अनुभवजन्य ट्रांजिशन मैट्रिक्स एवं अवस्था आवृत्तियों के अभिसरण (concentration) के विश्लेषण पर आधारित है।

3. तकनीकी उपकरण (Technical Tools): विश्लेषण दो स्वतंत्र रुचि के तकनीकी परिणामों को प्रस्तुत करता है:

   • पॉइसन समीकरण के समाधानों का छद्म-स्पेक्ट्रल गैप (pseudo-spectral gap) और मार्कोव श्रृंखला के स्टेशनरी वितरण के संदर्भ में एक समान नियंत्रण।
   • एक पिंस्कर-प्रकार (Pinsker-type) की असमानता जो दो ट्रांजिशन मैट्रिसेस के बीच स्टेशनरी-भारित KL डाइवर्जेंस को उपयुक्त फलनों के स्टेशनरी माध्यों के वर्ग अंतराल द्वारा निम्नतम स्तर पर बांधती है। यह असमानता गणनात्मक रूप से सुलभ सरोगेट सांख्यिकी (surrogate statistics) के व्युत्पन्न करने में सुविधा प्रदान करती है।

परिणाम (Results)

• निचला स्तर (Lower Bound): किसी भी $\alpha$-सटीक, पावर-वन परीक्षण $\tau_\alpha$ के लिए, और किसी भी एर्गोडिक $Q \in \mathcal{Q}$ के लिए, अपेक्षित रुकने का समय निम्नलिखित होता है:
  $$E_Q[\tau_\alpha] \geq \left( \frac{\log(1/\alpha)}{D_M^{\inf}(Q, \mathcal{P})} - \frac{2C_Q}{\min_i \pi_i} \right)^+$$
  जहाँ $C_Q$ एक स्थिरांक है जो $Q$ के मिक्सिंग गुणों पर निर्भर करता है। स्पर्शोन्मुखी रूप से, $\liminf_{\alpha \to 0} \frac{E_Q[\tau_\alpha]}{\log(1/\alpha)} \geq \frac{1}{D_M^{\inf}(Q, \mathcal{P})}$.
• प्राप्ति क्षमता (Achievability): प्रस्तावित एल्गोरिदम 1 $\alpha$-सटीक है और निम्नलिखित को संतुष्ट करता है:
  $$\limsup_{\alpha \to 0} \frac{E_Q[\tau_\alpha]}{\log(1/\alpha)} \leq \frac{1}{D_M^{\inf}(Q, \mathcal{P})}$$
  यह प्रक्रिया की स्पर्शोन्मुखी अनुकूलता की पुष्टि करता है।
• दो-पक्षीय परीक्षण (Two-Sided Testing): इस ढांचे को दो-पक्षीय परीक्षण (दोनों टाइप-I और टाइप-II त्रुटियों को नियंत्रित करना) के लिए विस्तारित किया गया है, यह दिखाते हुए कि दो एक-पक्षीय परीक्षणों को समानांतर में चलाने से एक स्पर्शोन्मुखी रूप से इष्टतम दो-पक्षीय परीक्षण प्राप्त होता है।
• गणनात्मक सुलभता (Computational Tractability): पिंस्कर-प्रकार की असमानता का लाभ उठाते हुए, लेखक एक गणनात्मक रूप से सुलभ सरोगेट सांख्यिकी व्युत्पन्न करते हैं जो $\alpha$-सटीकता को बनाए रखती है, हालांकि यह इष्टतम सांख्यिकी की तुलना में संभावित रूप से नमूना दक्षता (sample efficiency) की कीमत पर हो सकता है।

अनुप्रयोग और महत्व (Applications and Significance)
यह शोधपत्र दो अनुप्रयोगों के माध्यम से ढांचे की उपयोगिता को प्रदर्शित करता है:

1. MCMC मिसस्पेसिफिकेशन डिटेक्शन (MCMC Misspecification Detection): यह परीक्षण करना कि क्या एक मार्कोव चेन मोंटे कार्लो (MCMC) सैंपलर का ट्रांजिशन मैट्रिक्स एक लक्षित स्टेशनरी वितरण के अनुरूप है। यह ढांचा MCMC अनुमानकों में पूर्वाग्रह (bias) की पहचान करने के लिए इष्टतम पहचान गारंटी प्रदान करता है।
2. MDPs में रैखिकता परीक्षण (Linearity Testing in MDPs): मार्कोव निर्णय प्रक्रियाओं (MDPs) में रैखिक संक्रमण गतिकी (linear transition dynamics) के संरचनात्मक अनुमान का परीक्षण करना, जो सुदृढीकरण aprendizaje (reinforcement learning) में एक सामान्य धारणा है। परीक्षण क्रमवार सत्यापित करता है कि क्या प्रेरित अवस्था-क्रिया (state-action) ट्रांजिशन मैट्रिक्स एक रैखिक गुणनखंड (linear factorization) को स्वीकार करता है।

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