🔢 mathematics

The Insertion List-Decoding Capacity and an Improved Bound on the Deletion List-Decoding Capacity

यह शोध पत्र सममित 2-स्टेट मार्कोव श्रृंखलाओं (symmetric 2-state Markov chains) का उपयोग करते हुए $\delta$ -हिस्से के इंसर्शन (insertions) से बाइनरी कोड्स की लिस्ट-डिकोडिंग के लिए सटीक क्षमता को $(1+\delta)(1-h(\frac{\delta}{1+\delta}))$ के रूप में स्थापित करता है, और साथ ही यह भी प्रदर्शित करता है कि यह दृष्टिकोण डिलीशन (deletions) के लिए रैंडम कोडिंग में सुधार नहीं करता है और डिलीशन लिस्ट-डिकोडिंग क्षमता पर एक अधिक सटीक ऊपरी सीमा प्रदान करता है जो बाइनरी डिलीशन चैनल के एसिम्प्टोटिक व्यवहार (asymptotic behavior) से मेल खाती है।

मूल लेखक: Roni Con, Dean Doron, João Ribeiro

प्रकाशित 2026-07-07

📖 7 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Roni Con, Dean Doron, João Ribeiro

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप कागज की एक लंबी पट्टी पर एक गुप्त संदेश भेज रहे हैं। आपका संदेश केवल 0 और 1 की एक स्ट्रिंग है। अब, कल्पना कीजिए कि एक शरारती 'ग्रेमलिन' (gremlin) आपके संदेश के साथ छेड़छाड़ कर रहा है क्योंकि वह यात्रा के दौरान आपके संदेश में घुसपैठ कर रहा है। इस ग्रेमलिन के पास आपके संदेश को बिगाड़ने के दो तरीके हैं:

इंसर्शन (Insertions - जोड़ना): ग्रेमलिन अतिरिक्त 0 या 1 डाल देता है, जिससे संदेश लंबा हो जाता है।
डिलीशन (Deletions - हटाना): ग्रेमलिन कुछ 0 या 1 को फाड़कर निकाल देता है, जिससे संदेश छोटा हो जाता है।

यह सिंक्रोनाइज़ेशन एरर (synchronization errors) की दुनिया है। साधारण टाइपो (जैसे 'A' का 'B' हो जाना) के विपरीत, यहाँ पूरा संदेश का तालमेल ही बिगड़ जाता है। प्राप्तकर्ता को यह नहीं पता होता कि त्रुटियाँ कहाँ हुईं, उसे केवल इतना पता होता है कि लंबाई बदल गई है।

कोडिंग थ्योरी की दुनिया में, हम जानना चाहते हैं: हम एक संदेश में कितनी जानकारी भर सकते हैं ताकि, ग्रेमलिन द्वारा गड़बड़ी करने के बाद भी, हम मूल संदेश का पता लगा सकें?

आमतौर पर, हम एक ही मूल संदेश खोजने की कोशिश करते हैं। लेकिन कभी-कभी, नुकसान इतना अधिक होता है कि हम सौ प्रतिशत निश्चित नहीं हो सकते कि वह क्या था। इसलिए, हम लिस्ट-डिकोडिंग (List-Decoding) नामक रणनीति का उपयोग करते हैं। एक एकल उत्तर की मांग करने के बजाय, हम कहते हैं, "मुझे संभावित मूल संदेशों की एक छोटी सूची दें। जब तक वास्तविक संदेश उस सूची में है, हम ठीक हैं।"

रोनी कॉन, डीन डोरोन और जोआओ रिबेरो का शोध पत्र, "The Insertion List-Decoding Capacity and an Improved Bound on the Deletion List-Decoding Capacity," इस पहेली को हल करता है कि उस सूची को कितना बड़ा होना चाहिए और हम कितनी जानकारी भेज सकते हैं।

यहाँ उनके निष्कर्षों का सरल उपमाओं (analogies) का उपयोग करके विवरण दिया गया है:

1. "इंसर्शन" पहेली: अतिरिक्त बिट्स के रहस्य को सुलझाना

समस्या: जब ग्रेमलिन बिट्स (bits) जोड़ता है (insertions), तो हम कितना डेटा भेज सकते हैं?
पुरानी सोच: लंबे समय तक, वैज्ञानिकों के पास पूरी तरह से रैंडम (यादृच्छिक) संदेश चुनने पर आधारित एक "सबसे अच्छा अनुमान" (lower bound) था। उनके पास एक "सबसे खराब स्थिति की सीमा" (upper bound) भी थी जो सरल गणित पर आधारित थी। लेकिन उच्च त्रुटि दर (जब ग्रेमलिन बहुत अधिक बिट्स जोड़ देता है) के लिए, अनुमान और सीमा एक-दूसरे से बहुत दूर थे। यह ऐसा था जैसे यह जानना कि खजाना एक विशाल जंगल में कहीं है, लेकिन यह नहीं जानना कि वह उत्तर में है या दक्षिण में।

नई खोज:
लेखकों ने सटीक उत्तर खोज लिया। उन्होंने सिद्ध किया कि आप अधिकतम कितनी डेटा भेज सकते हैं (क्षमता/capacity) वह बिल्कुल उस "सबसे खराब स्थिति की सीमा" के बराबर है जिसे सभी पहले से जानते थे।

उपमा: कल्पना कीजिए कि आप एक लंबी रस्सी को एक डिब्बे में फिट करने की कोशिश कर रहे हैं। आपको लगा कि आप केवल एक छोटा टुकड़ा ही फिट कर सकते हैं। लेखकों ने सिद्ध किया, "नहीं, आप वास्तव में डिब्बे की पूरी क्षमता के बराबर रस्सी फिट कर सकते हैं, उससे अधिक नहीं, और न ही कम।"
उन्होंने यह कैसे किया: उन्होंने केवल रैंडम संदेश नहीं चुने। उन्होंने ऐसे संदेश चुने जो एक विशिष्ट पैटर्न का पालन करते हैं, जैसे कि एक "मार्कोव चेन" (Markov chain)। इसे एक ऐसे संदेश के रूप में सोचें जहाँ अगला बिट पिछले बिट पर निर्भर करता है (जैसे एक बातचीत जहाँ अगला शब्द पिछले शब्द पर निर्भर करता है)। उन्होंने दिखाया कि यदि आप इन विशिष्ट "लयबद्ध" (rhythmic) पैटर्न का उपयोग करके अपने संदेश उत्पन्न करते हैं, तो आप उस सैद्धांतिक सीमा तक पूरी तरह से पहुँच सकते हैं।

2. "डिलीशन" पहेली: वह ग्रेमलिन जो बिट्स को फाड़ देता है

समस्या: जब ग्रेमलिन बिट्स को हटा देता है (deletions), तो हम कितना डेटा भेज सकते हैं?
पुरानी सोच: वैज्ञानिक जानते थे कि रैंडम संदेश एक निश्चित बिंदु तक ठीक काम करते हैं। वे यह भी जानते थे कि "इंसर्शन" त्रुटियों के लिए, उन लयबद्ध "मार्कोव" पैटर्न का उपयोग करना एक महाशक्ति (superpower) की तरह था। इसलिए, उन्होंने स्वाभाविक रूप से पूछा: "यदि लयबद्ध पैटर्न इंसर्शन में मदद करते हैं, तो क्या वे डिलीशन में भी मदद कर सकते हैं?"

नई खोज (ट्विस्ट):
लेखकों ने इस विचार का परीक्षण किया और एक आश्चर्यजनक द्वैत (dichotomy) पाया।

परिणाम: डिलीशन के लिए, उन लयबद्ध "मार्कोव" पैटर्न का उपयोग करने से चीजों में कोई सुधार नहीं होता है, जो केवल रैंडम संदेश चुनने के बराबर ही है।
उपमा: कल्पना कीजिए कि आप एक बिखरे हुए कमरे में खोई हुई चाबी खोजने की कोशिश कर रहे हैं।
- इंसर्शन (अतिरिक्त कचरा जोड़ा गया) के लिए, एक विशिष्ट टॉर्च (मार्कोव पैटर्न) का उपयोग करना आपको चाबी खोजने में रैंडम स्कैन की तुलना में बहुत बेहतर मदद करता है।
- डिलीशन (टुकड़े गायब हैं) के लिए, वही विशेष टॉर्च बेकार है। एक रैंडम स्कैन भी उतना ही अच्छा काम करता है। लेखकों ने गणितीय रूप से सिद्ध किया कि आप अपने "मार्कोव" पैटर्न को चाहे कितनी भी बारीकी से ट्यून करें, आप शुद्ध यादृच्छिकता (randomness) के प्रदर्शन से बेहतर प्रदर्शन नहीं कर सकते।

3. "छोटा डिलीशन" सीमा: एक सटीक पैमाना

समस्या: क्या होता है जब ग्रेमलिन बहुत कम मात्रा में बिट्स निकाल देता है?
पुरानी सोच: हम उत्तर का सामान्य आकार तो जानते थे, लेकिन बहुत कम त्रुटियों के विवरण धुंधले थे।

नई खोज:
लेखकों ने इस विशिष्ट परिदृश्य के लिए एक नया, अधिक सटीक "पैमाना" (upper bound) बनाया।

परिणाम: उन्होंने दिखाया कि जब त्रुटि दर बहुत कम होती है, तो क्षमता लगभग 1940 के दशक के एक प्रसिद्ध फॉर्मूले (बिट फ्लिप के लिए शैनन की क्षमता) के समान व्यवहार करती है।
उपमा: यदि आप कार पर एक छोटे से खरोंच को माप रहे हैं, तो एक मोटा अनुमान पर्याप्त नहीं है। लेखकों ने एक माइक्रोमीटर बनाया। उन्होंने सिद्ध किया कि बहुत कम डिलीशन के लिए, सीमा वही है जिसकी हम मानक शोर (standard noise) के लिए अपेक्षा करते हैं, जो केवल एक सूक्ष्म, लगभग अदृश्य अंतर से भिन्न है।

"बड़ी तस्वीर" का सारांश

यह शोध पत्र एक मानचित्रकार (cartographer) की तरह है जो अंततः एक खतरनाक क्षेत्र का सटीक नक्शा बना रहा है।

इंसर्शन के लिए: उन्होंने सटीक सीमा खोज ली। आप एक विशिष्ट सीमा तक डेटा भेज सकते हैं, और उन्होंने दिखाया कि आप उस सीमा तक पहुँचने के लिए अपने संदेशों को कैसे उत्पन्न कर सकते हैं (लयबद्ध पैटर्न का उपयोग करके)।
डिलीशन के लिए: उन्होंने सिद्ध किया कि "लयबद्ध पैटर्न" वाला तरीका यहाँ काम नहीं करता है। यादृच्छिकता (Randomness) किसी भी फैंसी पैटर्न जितनी ही अच्छी है।
छोटे डिलीशन के लिए: उन्होंने मानचित्र को और अधिक सटीक बनाया ताकि यह दिखाया जा सके कि सीमाएं बहुत कम त्रुटियों के लिए जो हम पहले से ही संदिग्ध मानते थे, उसके बहुत करीब हैं।

यह क्यों मायने रखता है?
कोडिंग की दुनिया में, सटीक सीमा जानना महत्वपूर्ण है। यह इंजीनियरों को बताता है, "इस विशिष्ट समस्या के लिए बेहतर कोड बनाने की कोशिश करना बंद करें; आपने सैद्धांतिक छत (theoretical ceiling) को छू लिया है।" यह पुष्टि करके समय और प्रयास बचाता है कि वर्तमान सर्वोत्तम विधियाँ वास्तव में सर्वोत्तम संभव विधियाँ हैं।

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

तकनीकी सारांश: इंसर्शन लिस्ट-डिकोडिंग क्षमता और डिलीशन लिस्ट-डिकोडिंग क्षमता पर एक बेहतर बाउंड

समस्या विवरण

यह शोध पत्र बाइनरी कोड्स के लिए एडवर्सरियल सिंक्रोनाइज़ेशन एरर्स (adversarial synchronization errors), विशेष रूप से इंसर्शन (insertions) और डिलीशन (deletions) के तहत लिस्ट-डिकोडिंग क्षमता (list-decoding capacity) की जांच करता है। बिट-फ्लिप या इरेज़र चैनल्स के विपरीत, जहाँ लिस्ट-डिकोडिंग क्षमता सुस्पष्ट है और संबंधित प्रोबेबिलिस्टिक चैनल की शैनन क्षमता (Shannon capacity) के समान होती है, सिंक्रोनाइज़ेशन एरर्स के लिए क्षमता का ज्ञान बहुत सीमित है।

केंद्रीय प्रश्न यह है: वह सबसे बड़ी दर $R$ क्या है जिस पर बाइनरी कोड्स का एक परिवार, $L$ लिस्ट साइज (जो ब्लॉक लेंथ $n$ में पॉलीनोमियल है) के साथ, $\delta$ -फ्रैक्शन इंसर्शन या डिलीशन से लिस्ट-डिकोड किया जा सके?

इस कार्य से पूर्व, ज्ञान की स्थिति सीमित थी:

डिलीशन (Deletions): सर्वोत्तम ज्ञात निचला बाउंड (lower bound) $1 - h(\delta)$ था, जो यूनिफॉर्मली रैंडम कोड्स द्वारा प्राप्त किया गया था। ऊपरी बाउंड (upper bound) $1 - 2\delta$ था, जो काफी ढीला (loose) था।
इंसर्शन (Insertions): $\delta \leq 1/2$ के लिए, निचला बाउंड भी $1 - h(\delta)$ था। $\delta > 1/2$ के लिए, केवल एक बहुत छोटा धनात्मक निचला बाउंड ज्ञात था, जबकि ऊपरी बाउंड $(1+\delta)(1 - h(\frac{\delta}{1+\delta}))$ था।
अंतराल (Gap): निचली और ऊपरी बाउंड्स के बीच एक महत्वपूर्ण अंतराल था, विशेष रूप से इंसर्शन के लिए जहाँ $\delta > 1/2$ है, और यह अज्ञात था कि क्या स्ट्रक्चर्ड रैंडम कोड्स (जैसे कि मार्कोव चेन्स) यूनिफॉर्मली रैंडम कोड्स से बेहतर प्रदर्शन कर सकते हैं।

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

लेखक संभाव्य विधियों (probabilistic methods) का उपयोग करते हैं, विशेष रूप से मेमोरी के साथ सैंपल किए गए रैंडम कोड्स (मार्कोव चेन्स) बनाम यूनिफॉर्मली रैंडम कोड्स के प्रदर्शन का विश्लेषण करते हैं।

मार्कोव चेन सैंपलिंग (Markov Chain Sampling): बिट-दर-बिट स्वतंत्र रूप से (यूनिफॉर्मली रैंडम) सैंपल करने के बजाय, लेखक कोडवर्ड्स को एक सिमेट्रिक ऑर्डर-1 मार्कोव चेन के अनुसार सैंपल करते हैं। यह आस-पास के बिट्स के बीच सहसंबंध (correlation) पेश करता है, जिसे एक पैरामीटर $\alpha$ (संभावना कि $X_i = X_{i-1}$ ) द्वारा नियंत्रित किया जाता है।
लार्ज डेविएशन थ्योरी (Large Deviations Theory): यह विश्लेषण करने के लिए कि एक रैंडम कोडवर्ड में एक विशिष्ट प्राप्त स्ट्रिंग (received string) एक सबसीक्वेंस (subsequence) के रूप में या सुपरसीक्वेंस (supersequence) के रूप में मौजूद है, लेखक क्रैमर के प्रमेय (Cramér's theorem) और मोमेंट-जेनरेटिंग फंक्शन्स के लैग्रेंज-फेंचेल ट्रांसफॉर्म (Lagrange-Fenchel transform) का उपयोग करते हैं। यह उन्हें "बुरे" इवेंट्स (अर्थात, एक प्राप्त स्ट्रिंग बहुत से कोडवर्ड्स का सबसीक्वेंस होना) की संभावना पर सटीक एसिम्प्टोटिक बाउंड्स प्राप्त करने की अनुमति देता है।
कॉम्बिनेटरियल काउंटिंग (रन्स - Runs): डिलीशन क्षमता के ऊपरी बाउंड के लिए, लेखक कोडवर्ड्स में "रन्स" (समान प्रतीकों के अधिकतम निरंतर ब्लॉक) के विश्लेषण का उपयोग करते हैं। वे लेवेनस्टीन बाउंड्स (Levenshtein bounds) के साथ पिजनहोल सिद्धांत (pigeonhole principle) के तर्क का उपयोग करके यह दिखाते हैं कि उच्च-दर वाले कोड्स में ऐसे कोडवर्ड्स होने चाहिए जिनमें कई रन्स हों, जो बदले में प्राप्त स्ट्रिंग्स के बड़े लिस्ट साइज को मजबूर करते हैं।

मुख्य योगदान और परिणाम

1. इंसर्शन से लिस्ट-डिकोडिंग की सटीक क्षमता

यह शोध पत्र सभी $\delta \in [0, 1]$ के लिए इंसर्शन के लिए सटीक लिस्ट-डिकोडिंग क्षमता, $C_{ins}(\delta)$ स्थापित करता है।

परिणाम:
$C_{ins}(\delta) = (1 + \delta) \left( 1 - h\left( \frac{\delta}{1 + \delta} \right) \right)$
उपलब्धता (Achievability): यह क्षमता एक सावधानीपूर्वक चुने गए ट्रांजिशन प्रोबेबिलिटी $\alpha = \frac{1+\delta}{2}$ के साथ एक सिमेट्रिक ऑर्डर-1 मार्कोव चेन से सैंपल किए गए कोड द्वारा उच्च संभावना के साथ प्राप्त की जाती है।
महत्व: यह परिणाम इंसर्शन के लिए गैप को समाप्त करता है। यह पिछले निचले बाउंड $1-h(\delta)$ (जो केवल $\delta \leq 1/2$ के लिए मान्य है) में सुधार करता है और $\delta > 1/2$ के लिए केवल एक छोटे धनात्मक निचले बाउंड को भी बेहतर बनाता है। यह पहले से ज्ञात एवरेजिंग-आधारित ऊपरी बाउंड से मेल खाता है, जो सिद्ध करता है कि यह टाइट (tight) है। यह निर्माण क्षमता से नीचे की दरों के लिए एक स्थिर लिस्ट साइज $L = O(1/\epsilon)$ की गारंटी देता है।

2. डिलीशन के लिए मार्कोव कोड्स की सीमाएं

लेखक यह जांचते हैं कि क्या इंसर्शन के लिए मार्कोव चेन्स की सफलता डिलीशन के लिए भी विस्तारित होती है।

परिणाम: ऑर्डर-1 मार्कोव कोड्स डिलीशन से लिस्ट-डिकोडिंग के लिए यूनिफॉर्मली रैंडम कोड्स से बेहतर प्रदर्शन नहीं करते हैं।
प्रमेय (Theorem): डिलीशन के किसी भी अंश $\delta \in [0, 1/2]$ और किसी भी दर $R > 1 - h(\delta)$ के लिए, एक कोड जो ऑर्डर-1 मार्कोव चेन से सैंपल किया गया है, उसमें उच्च संभावना के साथ एक प्राप्त स्ट्रिंग $y$ होगी जो घातांकीय (exponential) संख्या में कोडवर्ड्स का सबसीक्वेंस है ( $2^{\Omega(\epsilon n)}$ )।
महत्व: यह इंसर्शन और डिलीशन के बीच एक द्वैत (dichotomy) को प्रकट करता है। जबकि मेमोरी (मार्कोव संरचना) इंसर्शन क्षमता प्राप्त करने में मदद करती है, यह डिलीशन के लिए यूनिफॉर्म रैंडमनेस की तुलना में कोई लाभ प्रदान नहीं करती है।

3. डिलीशन क्षमता के लिए बेहतर ऊपरी बाउंड

यह शोध पत्र डिलीशन के लिए लिस्ट-डिकोडिंग क्षमता, $C_{del}(\delta)$ , के लिए एक नया, अधिक सटीक ऊपरी बाउंड प्रदान करता है, विशेष रूप से छोटे $\delta$ के लिए।

परिणाम:
$C_{del}(\delta) \leq 1 - \delta - (\gamma - \delta)h\left( \frac{\delta}{\gamma - \delta} \right) = 1 - h(\delta) + o(\delta)$
जहाँ $\gamma = \frac{1}{2} - \sqrt{\frac{h(\delta) \ln 2}{2}}$ ।
एसिम्प्टोटिक व्यवहार: जैसे-जैसे $\delta \to 0$ , क्षमता $1 - h(\delta) + o(\delta)$ के रूप में व्यवहार करती है।
महत्व: यह प्रोबेबिलिस्टिक डिलीशन चैनल (जहाँ बिट्स $\delta$ प्रायिकता के साथ डिलीट होते हैं) की क्षमता के एसिम्प्टोटिक व्यवहार से मेल खाता है। यह सुझाव देता है कि, कम शोर वाले (low-noise) शासन में, एडवर्सरियल लिस्ट-डिकोडिंग क्षमता और प्रोबेबिलिस्टिक चैनल क्षमता समान अग्रणी-क्रम (leading-order) व्यवहार साझा करते हैं, भले ही त्रुटियां एडवर्सरियल प्रकृति की हों।

महत्व और दावे

यह शोध पत्र सिंक्रोनाइज़ेशन एरर करेक्शन की सीमाओं को समझने में मौलिक प्रगति करने का दावा करता है:

इंसर्शन समस्या का समाधान: इंसर्शन के लिए सटीक क्षमता निर्धारित करके, लेखक एक लंबे समय से खुले प्रश्न को हल करते हैं। वे प्रदर्शित करते हैं कि "एवरेजिंग बाउंड" टाइट है और मार्कोवियन रैंडम कोडिंग के माध्यम से प्राप्त किया जा सकता है।
मॉडल्स का पृथक्करण: यह कार्य इंसर्शन और डिलीशन एरर्स के बीच एक मौलिक अंतर को उजागर करता है। वे तकनीकें जो इंसर्शन क्षमता को अनुकूलित करती हैं (मार्कोव चेन्स के माध्यम से मेमोरी पेश करना), डिलीशन के लिए अप्रभावी हैं, जहाँ यूनिफॉर्म रैंडमनेस ऑर्डर-1 मार्कोव कोड्स के वर्ग में इष्टतम बनी रहती है।
प्रोबेबिलिस्टिक चैनल्स के साथ संबंध: डिलीशन के लिए बेहतर ऊपरी बाउंड, एडवर्सरियल लिस्ट-डिकोडिंग क्षमता को प्रोबेबिलिस्टिक डिलीशन चैनल क्षमता के साथ संरेखित करता है, जो लो-नॉइज़ रिजीम में एडवर्सरियल और प्रोबेबिलिस्टिक एरर मॉडल्स के बीच एक गहरा सैद्धांतिक लिंक प्रदान करता है।

लेखक इस बात पर जोर देते हैं कि उनके इंसर्शन के परिणाम नॉन-कंस्ट्रक्टिव (रैंडम कोड्स के अस्तित्व पर आधारित) हैं, लेकिन वे यह पहला प्रमाण प्रदान करते हैं कि क्षमता $\delta > 1/2$ के लिए $1-h(\delta)$ से स्पष्ट रूप से अधिक है। डिलीशन के लिए, कार्य मुख्य रूप से ऊपरी बाउंड को परिष्कृत करता है और विशिष्ट रैंडम कोडिंग रणनीतियों की सीमाओं को स्पष्ट करता है।