Stability of the Shannon--McMillan--Breiman Theorem under Sublinear Parsings

यहाँ रैफ़ाएल ग्रोंडिन के शोध पत्र "Stability of the Shannon–McMillan–Breiman Theorem under Sublinear Parsings" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

शैनन-मैकमिलन-ब्रिमैन (SMB) प्रमेय सूचना सिद्धांत और एर्गोडिक थ्योरी का एक आधारभूत परिणाम है। यह बताता है कि एक अनुक्रम स्थान $\Omega = A^{\mathbb{N}}$ (जहाँ $A$ एक परिमित वर्णमाला है) पर एक शिफ्ट-इनवेरिएंट प्रायिकता माप $P$ के लिए, एक ब्लॉक $x_1^N$ का सामान्यीकृत ऋणात्मक लॉग-प्रायिकता लगभग निश्चित रूप से (almost surely) एंट्रॉपी दर फलन $h_P(x)$ की ओर अभिसरित होता है:
$$\lim_{N \to \infty} -\frac{1}{N} \log P([x_1^N]) = h_P(x)$$
हालाँकि, कई व्यावहारिक अनुप्रयोगों (जैसे लेम्पेल-ज़िव संपीड़न, क्रॉस-एंट्रॉपी अनुमान, और लार्ज डेविएशन थ्योरी) में, पूरे ब्लॉक $x_1^N$ का सीधे विश्लेषण नहीं किया जाता है। इसके बजाय, अनुक्रम को परिवर्तनशील लंबाई वाले निरंतर ब्लॉकों के एक पार्सिंग (parsing) में विभाजित किया जाता है:
$$x_1^N = w_1^{(N)} \cdot w_2^{(N)} \cdots w_{c_N}^{(N)}$$
जहाँ $c_N$ ब्लॉकों की संख्या है। यह शोध पार्सिंग-आधारित योग (parsing-based sum) के अभिसरण की जांच करता है:
$$S_N = \frac{1}{N} \sum_{i=1}^{c_N} -\log P([w_i^{(N)}])$$
मुख्य प्रश्न: किन शर्तों के तहत $S_N$, मूल SMB प्रमेय की तरह ही समान एंट्रॉपी दर $h_P$ की ओर अभिसरित होता है?
चुनौती: योग $S_N$ ब्लॉकों के साथ इस तरह व्यवहार करता है जैसे वे स्वतंत्र हों (उनकी प्रायिकताओं को गुणा करके), जिससे वे सह-संबंध (correlations) अनदेखे रह जाते हैं जो संयुक्त प्रायिकता $P([x_1^N])$ में मौजूद होते हैं। इसके अतिरिक्त, पार्सिंग डेटा-निर्भर (data-dependent) हो सकती है (ब्लॉक की सीमाएँ देखे गए अनुक्रम $x$ पर निर्भर करती हैं), जिससे पूर्वाग्रह (bias) उत्पन्न हो सकता है।

2. कार्यप्रणाली (Methodology)

लेखक एक मार्टिंगेल अपघटन (martingale decomposition) दृष्टिकोण का उपयोग करते हैं, जो विशेष रूप से बड़े विचलन सिद्धांतों (large-deviation principles) या विशिष्ट गिब्सियन धारणाओं पर निर्भर करने के बजाय, SMB प्रमेय के ब्रेमन के मूल प्रमाण पर आधारित है।

मुख्य तकनीकी उपकरण:

1. मार्टिंगेल अपघटन (Martingale Decomposition): प्रमाण एक मार्टिंगेल अनुक्रम $Z_n(x) = P([x_2^n]) / P([x_1^n])$ का उपयोग करता है। एक ब्लॉक के ऋणात्मक लॉग-प्रायिकता को एक "मुख्य" पद (लॉग-मार्टिंगेल अंतरों का एक योग) और एक "अवशिष्ट" (residual) पद में विभाजित किया जाता है।
   $$-\log P([x_1^N]) = \sum_{k=0}^{N-1} \log Z(T^k x) + \text{Residual}$$
2. ट्रंकेशन (Truncation): शिफ्ट स्पेस की अनंत प्रकृति को संभालने के लिए, लेखक मार्टिंगेल पदों के ट्रंकेटेड संस्करण ($Z_M$) पेश करते हैं ताकि यह सुनिश्चित हो सके कि मात्राएँ केवल परिमित निर्देशांकों (coordinates) पर निर्भर हैं।
3. बर्कहॉफ योग बनाम पार्सिंग योग (Birkhoff Sums vs. Parsing Sums): प्रमाण पूरे अनुक्रम पर मानक बर्कहॉफ योग की तुलना पार्सिंग ब्लॉक्स के योग से करता है। यह दिखाया गया है कि यदि ब्लॉकों की संख्या $c_N$ पर्याप्त रूप से धीमी गति से बढ़ती है, तो अंतर नगण्य होता है।
4. सहायक लेम्मा (Auxiliary Lemmas):
   • लेम्मा 2.4: पार्सिंग द्वारा उत्पन्न त्रुटि को एक "बर्कहॉफ योग" पद (जो एर्गोडिक प्रमेय द्वारा शून्य हो जाता है) और एक "पार्सिंग-निर्भर" सीमा पद में विभाजित करता है।
   • लेम्मा 2.5: यह सिद्ध करता है कि सीमा पद $o(N)$ (नगण्य) है यदि और केवल यदि ब्लॉकों की संख्या $c_N$ उप-रैखिक (sublinear) है ($c_N/N \to 0$)।
   • लेम्मा 2.7: अवशिष्ट पदों के बर्कहॉफ योगों के शून्य की ओर अभिसरण को स्थापित करता है।

3. मुख्य योगदान और परिणाम (Key Contributions and Results)

A. मुख्य प्रमेय (Theorem 1.1)

यह शोध पत्र स्थापित करता है कि किसी भी शिफ्ट-इनवेरिएंट प्रायिकता माप $P$ और किसी भी पार्सिंग (यहाँ तक कि डेटा-निर्भर और अनिश्चित पार्सिंग भी) के लिए, जहाँ ब्लॉकों की संख्या $c_N$ उप-रैखिक स्थिति (sublinear condition) को पूरा करती है:
$$\lim_{N \to \infty} \frac{c_N(x)}{N} = 0 \quad P\text{-a.s.}$$
ऋणात्मक लॉग-लाइकलीहुड का सामान्यीकृत योग एंट्रॉपी दर की ओर अभिसरित होता है:
$$\lim_{N \to \infty} \frac{1}{N} \sum_{i=1}^{c_N} -\log P([w_i^{(N)}]) = h_P(x)$$
यह अभिसरण लगभग निश्चित रूप से (almost surely) और $L^1(P)$ में भी मान्य है।

B. संरचनात्मक पुनर्गठन (Corollary 1.2)

यह परिणाम सिलेंडर प्रायिकताओं के अनुमानित गुणनखंड (approximate factorization) का संकेत देता है। किसी भी उप-रैखिक पार्सिंग के लिए:
$$P([x_1^N]) = \left( \prod_{i=1}^{c_N} P([w_i^{(N)}]) \right) \exp\{r_N(x)\}$$
जहाँ त्रुटि पद $r_N(x)$ लगभग निश्चित रूप से और $L^1$ में $r_N(x)/N \to 0$ को संतुष्ट करता है। इसका अर्थ है कि उप-रैखिक पार्सिंग के तहत, संयुक्त प्रायिकता सह-संबंधों की उपस्थिति के बावजूद, ब्लॉकों की प्रायिकताओं के गुणनफल की तरह ही व्यवहार करती है।

C. स्थिति की तीक्ष्णता (Sharpness of the Condition - Section 2.6)

यह शोध पत्र सिद्ध करता है कि उप-रैखिक स्थिति तीक्ष्ण (sharp) है।

• यदि $c_N$ रैखिक रूप से बढ़ता है (जैसे, $c_N \sim N/K$), तो गैर-मार्कोव मापों के लिए अभिसरण विफल हो सकता है।
• लेखक एक प्रति-उदाहरण (counterexample) निर्मित करते हैं जहाँ एक नियत (deterministic) पार्सिंग और एक डेटा-निर्भर पार्सिंग (दोनों में रैखिक ब्लॉक गणना है) सामान्यीकृत योग के लिए अलग-अलग सीमाएँ प्रदान करते हैं, जिससे यह सिद्ध होता है कि सामान्य मामले में सीमा या तो अस्तित्व में नहीं होती या $h_P$ के बराबर नहीं होती।

D. सुदृढ़ता (Robustness - Section 3.1)

यह परिणाम उप-विस्तारित परिवर्तनों (subextensive perturbations) के तहत सुदृढ़ है। यदि पार्सिंग ब्लॉकों को उप-विस्तारित मात्रा में प्रतीक जोड़कर या हटाकर संशोधित किया जाता है (अर्थात कुल संशोधन $o(N)$ है), तो $h_P$ की ओर अभिसरण अभी भी बना रहता है। इसमें ब्लॉकों को उप-ब्लॉक्स या सुपर-ब्लॉक्स से बदलना शामिल है, बशर्ते कि पड़ोसियों के साथ ओवरलैप नियंत्रित हो।

E. विस्तार (Extensions - Section 3.3)

लेखक बैरन (Barron) के सामान्यीकृत SMB प्रमेय का उपयोग करके गैर-परिमित वर्णमाला (densities) तक इन परिणामों के विस्तार पर चर्चा करते हैं। जबकि मार्टिंगेल अपघटन स्वाभाविक रूप से विस्तारित होता है, सीमा पद नियंत्रण के लिए सावधानीपूर्वक हैंडलिंग की आवश्यकता होती है, जिसे सेट-वैल्यूड फंक्शनों के लिए एर्गोडिक थ्योरम (प्रस्ताव 3.2) के माध्यम से हल किया जा सकता है।

4. महत्व और व्याख्या (Significance and Interpretation)

• सार्वभौमिकता (Universality): यह परिणाम बिना किसी मिक्सिंग स्थितियों, गिब्स गुणों, या पार्सिंग प्रक्रिया पर विशिष्ट संरचनात्मक धारणाओं के, किसी भी शिफ्ट-इनवेरिएंट माप के लिए मान्य है।
• डेटा-निर्भरता (Data-Dependence): यह एंट्रॉपी अनुमान के लिए अनुकूल, डेटा-निर्भर पार्सिंग योजनाओं (जैसे लेम्पेल-ज़िव एल्गोरिदम में उपयोग किए जाने वाले) के उपयोग को वैध बनाता है, बशर्ते कि पार्स किए गए खंडों की संख्या डेटा की लंबाई के सापेक्ष रैखिक रूप से न बढ़े।
• ऊष्मागतिकी सादृश्य (Thermodynamic Analogy): शोध पत्र सांख्यिकीय यांत्रिकी में कोर्स-ग्रेनिंग (coarse-graining) के साथ एक समानता दर्शाता है। पार्सिंग प्रणाली के एक "मेसोस्कोपिक" दृश्य का प्रतिनिधित्व करती है। प्रमेय सिद्ध करता है कि जब तक कोर्स-ग्रेनिंग बहुत सूक्ष्म नहीं है (उप-रैखिक ब्लॉक), मैक्रोस्कोपिक अवलोकन (एंट्रॉपी दर) अपरिवर्तित रहता है और सूक्ष्म सीमा (microscopic limit) के समान ही होता है।
• पद्धतिगत अंतर्दृष्टि (Methodological Insight): ब्रेमन के मार्टिंगेल अपघटन की सुदृढ़ता को अलग करके, यह शोध पत्र SMB प्रमेय की एक नई संरचनात्मक समझ प्रदान करता है, यह दिखाते हुए कि पार्सिंग योगों में निहित "स्वतंत्रता" की धारणा तब तक आसिम्प्टोटिक रूप से मान्य है जब तक कि सीमाओं की संख्या अनुक्रम की लंबाई के सापेक्ष नगण्य है।

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