📊 statistics

Fast Algorithms for Exact Confidence Intervals in Randomized Experiments with Binary Outcomes

यह शोध पत्र एक नवीन एल्गोरिदम प्रस्तुत करता है जो संतुलित डिजाइनों के तहत केवल $O(\log n)$ रैंडमाइजेशन परीक्षणों का उपयोग करके बाइनरी परिणामों वाले रैंडमाइज्ड प्रयोगों में औसत उपचार प्रभावों (average treatment effects) के लिए सटीक कॉन्फिडेंस इंटरवल का निर्माण करता है, जो ब्रूट-फोर्स विधियों पर एक इष्टतम घातांकीय सुधार प्राप्त करता है और संतुलित पूर्ण रैंडमाइजेशन की तुलना में एक तीक्ष्ण दक्षता अंतराल स्थापित करता है।

मूल लेखक: Peng Zhang

प्रकाशित 2026-02-25

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

CC BY 4.0

मूल लेखक: Peng Zhang

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

कल्पना कीजिए कि आप एक जासूस हैं जो एक रहस्य सुलझाने की कोशिश कर रहे हैं: क्या एक नई दवा वास्तव में काम कर रही थी?

आपने एक प्रयोग चलाया। आपने अपने आधे मरीजों को दवा दी (उपचार समूह - Treatment Group) और दूसरे आधे को चीनी की गोली दी (नियंत्रण समूह - Control Group)। अब, आप जानना चाहते हैं: दवा ने लोगों को कितना बेहतर महसूस कराया?

सांख्यिकी (Statistics) में, यह "कितना बेहतर" को औसत उपचार प्रभाव (Average Treatment Effect - ATE) कहा जाता है। यह सुनिश्चित करने के लिए कि आपका उत्तर वास्तविक है न कि केवल किस्मत, आपको एक कॉन्फिडेंस इंटरवल (Confidence Interval) बनाना होगा। इसे एक "मछली पकड़ने वाले जाल" के रूप में सोचें जिसे आप अपने उत्तर के चारों ओर फेंकते हैं। यदि आप इस जाल को 100 बार फेंकते हैं, तो आप चाहते हैं कि यह कम से कम 95 बार वास्तविक उत्तर को पकड़ ले।

समस्या: "ब्रूट फोर्स" का दुःस्वप्न

पारंपरिक रूप से, इस जाल को पूरी तरह से बनाने के लिए (यह अनुमान लगाए बिना कि दुनिया कैसे काम करती है), सांख्यिकीविद रैंडमाइजेशन टेस्ट (Randomization Tests) नामक एक विधि का उपयोग करते हैं।

कल्पना करें कि आपके पास मरीजों का प्रतिनिधित्व करने वाला ताश का एक डेक है। यह देखने के लिए कि क्या आपका परिणाम केवल भाग्य था, आप डेक को शफल करते हैं और कार्डों को फिर से बांटते हैं, यह मानते हुए कि आपने अलग-अलग लोगों को दवा दी। आप यह बार-बार करते हैं ताकि यह देख सकें कि कितनी बार आपको वैसा ही परिणाम मिलता है जैसा कि आपने वास्तव में देखा था।

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

समाधान: "जादुई शॉर्टकट"

यह शोध पत्र एक सुपर-फास्ट एल्गोरिदम पेश करता है जो हर संभावना की जांच किए बिना एक परफेक्ट जाल (एक "सटीक कॉन्फिडेंस इंटरवल") बनाता है। यह गणित में एक चतुर पैटर्न को खोजकर ऐसा करता है।

लेखक, पेंग झांग (Peng Zhang), इसे दो विशिष्ट परिदृश्यों का उपयोग करके कैसे समझाते हैं, यहाँ दिया गया है:

परिदृश्य A: "स्वतंत्र सिक्का उछालना" (Bernoulli Design)

कल्पना करें कि आप एक ऑनलाइन प्रयोग चला रहे हैं। जब भी कोई उपयोगकर्ता आपकी वेबसाइट पर आता है, आप एक सिक्का उछालते हैं। हेड (Heads) = नया विज्ञापन दिखाएं। टेल्स (Tails) = पुराना विज्ञापन दिखाएं। प्रत्येक उछाल स्वतंत्र है।

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

परिदृश्य B: "मैच्ड पेयर्स" (Matched-Pairs Design)

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

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

यह एक बड़ी बात क्यों है

यह शोध पत्र दो अद्भुत चीजें सिद्ध करता है:

गति (Speed): एक संतुलित प्रयोग (दोनों समूहों में समान संख्या) के लिए, नया एल्गोरिदम एक्सपोनेंशियल रूप से तेज (exponentially faster) है।
- पुराना तरीका: यदि आप मरीजों की संख्या दोगुनी करते हैं, तो काम भी दोगुना (या उससे भी अधिक) हो जाता है।
- नया तरीका: यदि आप मरीजों की संख्या दोगुनी करते हैं, तो काम केवल थोड़ा सा ही बढ़ता है (जैसे सीढ़ी पर एक और कदम जोड़ना)।
- रूपक: पुराना तरीका न्यूयॉर्क से लंदन तक पैदल चलने जैसा है। नया तरीका एक टेलीपोर्टेशन डिवाइस लेने जैसा है जिसमें केवल कुछ सेकंड लगते हैं।
इष्टतमता (Optimality): लेखक ने यह भी सिद्ध किया है कि आप इससे तेज नहीं जा सकते। यह यह सिद्ध करने जैसा है कि आप प्रकाश की गति से तेज नहीं चल सकते। इस विशिष्ट पहेली को हल करने का यह सबसे तेज़ तरीका है।

"सीक्रेट सॉस": FFT

कंप्यूटर इतनी तेजी से संभावना की गणना कैसे करता है? यह फास्ट फूरियर ट्रांसफॉर्म (Fast Fourier Transform - FFT) नामक एक गणितीय उपकरण का उपयोग करता है।

उपमा: कल्पना करें कि आपके पास एक गाना है जिसमें एक साथ 1,000 वाद्य यंत्र बज रहे हैं। बेस लाइन (bass line) सुनने के लिए, आप पूरे गाने को 1,000 बार सुन सकते हैं। या, आप एक "जादुई इक्वलाइज़र" (FFT) का उपयोग कर सकते हैं जो तुरंत केवल बेस लाइन को अलग कर देता है। शोध पत्र इस "जादुिक इक्वलाइज़र" का उपयोग पूरे प्रयोग का अनुकरण किए बिना तुरंत संभावनाओं की गणना करने के लिए करता है।

सारांश

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

संक्षेप में: यह शोध पत्र हमें एक सांख्यिकीय पहेली को हल करने के लिए एक "चीट कोड" देता है जिसे सुलझाने में सुपरकंप्यूटर को वर्षों लग जाते थे, जिससे हमें अपने प्रयोगों पर कम डेटा के साथ, अधिक तेज़ी से और अधिक विश्वास करने की अनुमति मिलती है।

यहाँ पेंग झांग के शोध पत्र "Fast Algorithms for Exact Confidence Intervals in Randomized Experiments with Binary Outcomes" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र बाइनरी परिणामों (binary outcomes) वाले रैंडमाइज्ड प्रयोगों में औसत उपचार प्रभाव (Average Treatment Effect - ATE) के लिए सटीक आत्मविश्वास अंतराल (Exact Confidence Intervals - CIs) के निर्माण में आने वाली कम्प्यूटेशनल बाधाओं को संबोधित करता है।

संदर्भ: परिमित जनसंख्या (finite populations) में, एसिम्प्टोटिक सन्निकटन (जैसे सेंट्रल लिमिट थ्योरम) की तुलना में सटीक CI को प्राथमिकता दी जाती है क्योंकि वे किसी भी नमूना आकार (sample size) के लिए, चाहे वह कितना भी विषम (skewed) या विषम (heterogeneous) क्यों न हो, वैध कवरेज गारंटी प्रदान करते हैं।
कार्यप्रणाली: सटीक CI आमतौर पर रैंडमाइजेशन टेस्ट्स के व्युत्क्रमण (inverting randomization tests) द्वारा निर्मित किए जाते हैं। इसमें सभी संभावित अनदेखे परिणामों (unobserved potential outcomes) के पूर्णता (completions) के विरुद्ध एक उम्मीदवार ATE मान $\tau_0$ की जाँच करना शामिल है।
बाधा (The Bottleneck): अनदेखे संभावित परिणामों का खोज स्थान (search space) तेजी से ( $2^n$ ) बढ़ता है। भले ही इसे संभावित परिणाम प्रकारों की गणना तक सीमित कर दिया जाए, फिर भी यह स्थान $O(n^4)$ होता है। प्रत्येक विन्यास (configuration) का परीक्षण करने के लिए नेइव एन्यूमरेशन (naive enumeration) की आवश्यकता होती है, जिससे मध्यम-से-बड़े नमूना आकारों के लिए सटीक अनुमान (exact inference) कम्प्यूटेशनल रूप से निषेध योग्य (prohibitive) हो जाता है।
लक्ष्य: ऐसे एल्गोरिदम विकसित करना जो सटीक अंतराल (exact intervals) के निर्माण के लिए आवश्यक रैंडमाइजेशन टेस्ट्स की संख्या को काफी कम कर सकें, विशेष रूप से बर्नौली डिज़ाइन्स (Bernoulli designs) और मैच्ड-पेयर्स डिज़ाइन्स (matched-pairs designs) के लिए।

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

लेखक एक ऐसा ढांचा प्रस्तावित करते हैं जो बर्नौली और मैच्ड-पेयर्स डिज़ाइन्स की विशिष्ट स्वतंत्रता संरचनाओं (independence structures) का लाभ उठाकर "वर्स्ट-केस" (worst-case) p-वैल्यू खोजने की अनुकूलन समस्या को निरंतर संख्या में टेस्ट्स तक कम कर देता है।

A. मुख्य एल्गोरिदम रणनीति (Core Algorithmic Strategy)

कॉन्फिडेंस सेट $I_\alpha$ का निर्माण उन $\tau_0$ मानों के सेट को खोजने में शामिल है जहाँ संगत संभावित परिणाम पूर्णताओं (compatible potential outcome completions) पर अधिकतम p-वैल्यू $\geq \alpha$ है।

बाइनरी सर्च (Binary Search): देखे गए टेस्ट स्टैटिस्टिक के आसपास अधिकतम p-वैल्यू फंक्शन ( $p_{max}$ ) की एकदिष्टता (monotonicity) के कारण, लेखक उम्मीदवार सेट के ऊपर बाइनरी सर्च का उपयोग करते हैं। यह $\tau_0$ के मूल्यांकन की संख्या को $O(\log n)$ तक कम कर देता है।
$p_{max}$ का अनुकूलन (Optimization of $p_{max}$ ): एक निश्चित $\tau_0$ $τ_{0}$ के लिए, चुनौती उस संभावित परिणाम पूर्णता को खोजना है जो p-वैल्यू को अधिकतम करता है (अर्थात, देखे गए सांख्यिकी को सबसे कम चरम बनाता है)।
- मुख्य अंतर्दृष्टि (Key Insight): संतुलित बर्नौली और मैच्ड-पेयर्स डिज़ाइन्स के तहत, केंद्रित टेस्ट स्टैटिस्टिक (centered test statistic) का वितरण स्वतंत्र रेडेमेकर (Rademacher) (मान $\pm 1$ ) और हाफ-रेडेमेकर (half-Rademacher) (मान $\pm 1/2$ ) यादृच्छिक चरों के योग के रूप में व्यक्त किया जा सकता है।
- यूनिमोडैलिटी और मोनोटोनिसिटी (Unimodality & Monotonicity): लेखक सिद्ध करते हैं कि इस योग की टेल प्रोबेबिलिटी (p-value) इन यादृच्छिक चरों की गणनाओं के संबंध में यूनिमोडल (unimodal) और एकदिष्ट (monotone) है।
- न्यूनीकरण (Reduction): फलस्वरूप, अधिकतम p-वैल्यू को गणनाओं के पूरे स्थान की खोज करके नहीं पाया जाता है। इसके बजाय, यह व्यवहार्य क्षेत्र (feasible region) के दो सीमा बिंदुओं (boundary points) (लेक्सिकोग्राफिकल रूप से सबसे बड़े व्यवहार्य काउंट वेक्टर्स) में से एक पर प्राप्त होता है।
- परिणाम: $p_{max}(\tau_0)$ की गणना करने के लिए अधिकतम दो विशिष्ट विन्यासों के p-वैल्यू का मूल्यांकन करना पर्याप्त है।

B. कम्प्यूटेशनल कार्यान्वयन (Computational Implementation)

पॉइसन बिनोमियल डिस्ट्रीब्यूशन (Poisson Binomial Distribution): p-वैल्यू की गणना स्वतंत्र गैर-समान बर्नौली ट्रायल्स के योग (पॉइसन बिनोमियल डिस्ट्रीब्यूशन) की टेल प्रोबेबिलिटी की गणना करने में बदल जाती है।
फास्ट फूरियर ट्रांसफॉर्म (FFT): इन टेल प्रोबेबिलिटीज़ की सटीक और कुशलतापूर्वक गणना करने के लिए, लेखक FFT एल्गोरिदम का उपयोग करते हैं, जो $O(n \log n)$ समय में संचयी वितरण फलन (Cumulative Distribution Function - CDF) की गणना करता है। यह धीमी मोंटे कार्लो सिमुलेशन की आवश्यकता को समाप्त करता है।
इंटिजर लीनियर प्रोग्रामिंग (ILP): मैच्ड-पेयर्स डिज़ाइन के लिए, लेक्सिकोग्राफिकल रूप से सबसे बड़ा व्यवहार्य काउंट वेक्टर खोजने के लिए छोटे ILP (स्थिर आयामों के साथ) को हल करना शामिल है, जिसे $O(1)$ समय में किया जा सकता है।

3. प्रमुख योगदान और सैद्धांतिक परिणाम (Key Contributions & Theoretical Results)

प्रमेय 1.1: घातांकीय गति (Exponential Speedup)

संतुलित बर्नौली (balanced Bernoulli) या मैच्ड-पेयर्स (matched-pairs) डिज़ाइन्स के तहत, सटीक कॉन्फिडेंस सेट को अधिकतम $O(\log n)$ रैंडमाइजेशन टेस्ट्स का उपयोग करके बनाया जा सकता है।

तुलना: यह ब्रूट-फोर्स ( $O(n^4)$ ) की तुलना में एक घातांकीय सुधार है और संतुलित पूर्ण रैंडमाइजेशन (balanced complete randomization) के लिए सर्वोत्तम ज्ञात विधियों (Aronow et al., 2023) की तुलना में एक महत्वपूर्ण सुधार है।
महत्व: यह स्वतंत्र यूनिट असाइनमेंट (बर्नौली/मैच्ड) और आश्रित असाइनमेंट (पूर्ण रैंडमाइजेशन) वाले डिज़ाइन्स के बीच एक स्पष्ट अंतर स्थापित करता है।

प्रमेय 1.2: सूचना-सैद्धांतिक निचली सीमा (Information-Theoretic Lower Bound)

लेखक सिद्ध करते हैं कि किसी भी नियतात्मक एल्गोरिथ्म (deterministic algorithm) के लिए सबसे खराब स्थिति में $\Omega(\log n)$ रैंडमाइजेशन टेस्ट्स आवश्यक हैं। यह पुष्टि करता है कि उनका $O(\log n)$ ऊपरी स्तर (upper bound) इष्टतम (optimal) है।

प्रमेय 1.3: कुल समय जटिलता (Total Time Complexity)

कॉन्फिडेंस सेट बनाने की कुल समय जटिलता $O(n \log^2 n)$ है।

यह $O(n \log n)$ FFT-आधारित p-वैल्यू मूल्यांकनों के साथ $O(\log n)$ बाइनरी सर्च चरणों को जोड़कर प्राप्त किया जाता है।
यह नियतात्मक (deterministic) है और मोंटे कार्लो सन्निकटन के विचरण (variance) और कम्प्यूटेशनल लागत से बचता है।

प्रमेय 1.4: सामान्य बर्नौली डिज़ाइन (General Bernoulli Design)

असंतुलित (unbalanced) बर्नौली डिज़ाइन्स (जहाँ $p \neq 0.5$ ) के लिए, लेखक इस पद्धति को $O(n^2)$ रैंडमाइजेशन टेस्ट्स और $O(n^3 \log n)$ समय की आवश्यकता के साथ विस्तारित करते हैं, जो सामान्य पूर्ण रैंडमाइजेशन के लिए सर्वोत्तम ज्ञात प्रक्रियाओं की दक्षता से मेल खाता है।

4. परिणाम और सिमुलेशन (Results & Simulations)

शोध पत्र सैद्धांतिक निष्कर्षों को सिमुलेशन के माध्यम से मान्य करता है:

सटीकता (Accuracy): एल्गोरिदम द्वारा निर्मित सटीक अंतराल सभी संभावित परिणाम सेटिंग्स में समान कवरेज गारंटी प्राप्त करते हैं, जबकि वाल्ड इंटरवल (Wald intervals) स्पार्स (sparse) या विषम डेटा परिदृश्यों में अंडरकवर (undercover) हो सकते हैं।
दक्षता (Efficiency):
- बर्नौली डिज़ाइन: $n=1000$ के लिए, एल्गोरिदम 1.5 मिनट से कम समय में अंतराल बनाता है (10,000 सिमुलेशन), जबकि ब्रूट-फोर्स व्यवहार्य नहीं है।
- मैच्ड-पेयर्स डिज़ाइन: एल्गोरिदम ब्रूट-फोर्स की तुलना में काफी तेज़ है, हालांकि प्रत्येक चरण के लिए छोटे ILP को हल करने के कारण बर्नौली मामले की तुलना में थोड़ा धीमा है।
अंतराल की चौड़ाई (Interval Width): स्पार्स सेटिंग्स में सटीक अंतराल वाल्ड इंटरवल की तुलना में थोड़े अधिक चौड़े होते हैं (सटीक वितरण की असतत प्रकृति के कारण), जो अधिक रूढ़िवादी और सटीक कवरेज गारंटी को दर्शाते हैं।

5. महत्व (Significance)

व्यावहारिकता: यह शोध पत्र सटीक परिमित-नमूना अनुमान (finite-sample inference) को बड़े पैमाने के रैंडमाइज्ड प्रयोगों (जैसे ऑनलाइन A/B टेस्ट, क्लिनिकल ट्रायल) के लिए व्यवहार्य बनाता है जहाँ बाइनरी परिणाम आम हैं।
डिज़ाइन तुलना: यह पूर्ण रैंडमाइजेशन (complete randomization) की तुलना में बर्नौली और मैच्ड-पेयर्स डिज़ाइन्स के एक मौलिक कम्प्यूटेशनल लाभ को उजागर करता है। जबकि पूर्ण रैंडमाइजेशन निर्भरता (dependence) पैदा करता है जो अनुकूलन परिदृश्य (optimization landscape) को जटिल बनाता है, बर्नौली/मैच्ड में स्वतंत्रता कम्प्यूटेशनल जटिलता में भारी कमी की अनुमति देती है।
खुले प्रश्न का समाधान: यह कार्य Aronow et al. (2023) द्वारा उठाए गए एक खुले प्रश्न का उत्तर देता है कि मैच्ड-पेयर्स डिज़ाइन्स के लिए तेज़ रैंडमाइजेशन-आधारित निर्माणों को कैसे सामान्यीकृत किया जाए।
सॉफ्टवेयर: एक पायथन कार्यान्वयन (Python implementation) प्रदान किया गया है, जो इन उन्नत सटीक विधियों को चिकित्सकों (practitioners) के लिए सुलभ बनाता है।

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