चेर्नॉफ़ बाध्य: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{Short description|Exponentially decreasing bounds on tail distributions of random variables}}
{{Short description|Exponentially decreasing bounds on tail distributions of random variables}}
संभाव्यता सिद्धांत में, '''चेर्नॉफ़ बाउंड''' यादृच्छिक चर की पूंछ पर उसके क्षण उत्पन्न करने वाले फ़ंक्शन के आधार पर तेजी से घटती ऊपरी सीमा है। ऐसी सभी घातांकीय सीमाओं का न्यूनतम ''चेर्नॉफ़ या चेर्नॉफ़-क्रैमर बाउंड'' बनाता है, जो घातीय की तुलना में तेजी से क्षय हो सकता है (उदाहरण के लिए उप-गॉसियन वितरण|उप-गॉसियन)<ref name="blm">{{Cite book|last=Boucheron|first=Stéphane|url=https://www.worldcat.org/oclc/837517674|title=Concentration Inequalities: a Nonasymptotic Theory of Independence|date=2013|publisher=Oxford University Press|others=Gábor Lugosi, Pascal Massart|isbn=978-0-19-953525-5|location=Oxford|page=21|oclc=837517674}}</ref><ref>{{Cite web|last=Wainwright|first=M.|date=January 22, 2015|title=मूल पूंछ और एकाग्रता सीमाएँ|url=https://www.stat.berkeley.edu/~mjwain/stat210b/Chap2_TailBounds_Jan22_2015.pdf|url-status=live|archive-url=https://web.archive.org/web/20160508170739/http://www.stat.berkeley.edu:80/~mjwain/stat210b/Chap2_TailBounds_Jan22_2015.pdf |archive-date=2016-05-08 }}</ref> यह विशेष रूप से स्वतंत्र यादृच्छिक चर के योग के लिए उपयोगी है, जैसे [[बर्नौली यादृच्छिक चर]] का योग।<ref>{{Cite book|last=Vershynin|first=Roman|url=https://www.worldcat.org/oclc/1029247498|title=High-dimensional probability : an introduction with applications in data science|date=2018|isbn=978-1-108-41519-4|location=Cambridge, United Kingdom|oclc=1029247498|page=19}}</ref><ref>{{Cite journal|last=Tropp|first=Joel A.|date=2015-05-26|title=मैट्रिक्स एकाग्रता असमानताओं का एक परिचय|url=https://www.nowpublishers.com/article/Details/MAL-048|journal=Foundations and Trends in Machine Learning|language=English|volume=8|issue=1–2|page=60|doi=10.1561/2200000048|arxiv=1501.01571|s2cid=5679583|issn=1935-8237}}</ref>
संभाव्यता सिद्धांत में, '''चेर्नॉफ़ बाउंड''' संयंत्रक संख्या के माध्यम से एक यादृच्छिक प्रारंभिक मुद्रण फल की पुनरावृत्ति पर एक विपरीत लक्ष्य बाउंड होती है। सभी ऐसे घातीय बाउंडों में से कम से कम भारी बाउंड चेर्नॉफ या चेर्नॉफ-क्रामर बाउंड कहलाता है, जो विपरीत या सब-गॉसियन (उदाहरण के लिए अवसादीय) रूप से अधिक घटती है।<ref name="blm">{{Cite book|last=Boucheron|first=Stéphane|url=https://www.worldcat.org/oclc/837517674|title=Concentration Inequalities: a Nonasymptotic Theory of Independence|date=2013|publisher=Oxford University Press|others=Gábor Lugosi, Pascal Massart|isbn=978-0-19-953525-5|location=Oxford|page=21|oclc=837517674}}</ref><ref>{{Cite web|last=Wainwright|first=M.|date=January 22, 2015|title=मूल पूंछ और एकाग्रता सीमाएँ|url=https://www.stat.berkeley.edu/~mjwain/stat210b/Chap2_TailBounds_Jan22_2015.pdf|url-status=live|archive-url=https://web.archive.org/web/20160508170739/http://www.stat.berkeley.edu:80/~mjwain/stat210b/Chap2_TailBounds_Jan22_2015.pdf |archive-date=2016-05-08 }}</ref> यह विशेष रूप से स्वतंत्र यादृच्छिक चर के योग के लिए उपयोगी है, जैसे कि [[बर्नौली यादृच्छिक चर]] का योग।<ref>{{Cite book|last=Vershynin|first=Roman|url=https://www.worldcat.org/oclc/1029247498|title=High-dimensional probability : an introduction with applications in data science|date=2018|isbn=978-1-108-41519-4|location=Cambridge, United Kingdom|oclc=1029247498|page=19}}</ref><ref>{{Cite journal|last=Tropp|first=Joel A.|date=2015-05-26|title=मैट्रिक्स एकाग्रता असमानताओं का एक परिचय|url=https://www.nowpublishers.com/article/Details/MAL-048|journal=Foundations and Trends in Machine Learning|language=English|volume=8|issue=1–2|page=60|doi=10.1561/2200000048|arxiv=1501.01571|s2cid=5679583|issn=1935-8237}}</ref>


इस बाउंड को आमतौर पर [[हरमन चेर्नॉफ़]] के नाम पर जाना जाता है, जिन्होंने 1952 के पेपर में इस विधि का वर्णन किया था,<ref>{{Cite journal|last=Chernoff|first=Herman|date=1952|title=अवलोकनों के योग के आधार पर एक परिकल्पना के परीक्षण के लिए स्पर्शोन्मुख दक्षता का एक उपाय|journal=The Annals of Mathematical Statistics|volume=23|issue=4|pages=493–507|doi=10.1214/aoms/1177729330|jstor=2236576|issn=0003-4851|doi-access=free}}</ref> हालाँकि चेर्नॉफ़ ने इसे स्वयं हरमन रूबिन को समर्पित किया था।<ref>{{cite book | url=http://www.crcpress.com/product/isbn/9781482204964 | title=सांख्यिकी का अतीत, वर्तमान और भविष्य| chapter=A career in statistics | page=35 | publisher=CRC Press | last1=Chernoff | first1=Herman | editor-first1=Xihong | editor-last1=Lin | editor-first2=Christian | editor-last2=Genest | editor-first3=David L. | editor-last3=Banks | editor-first4=Geert | editor-last4=Molenberghs | editor-first5=David W. | editor-last5=Scott | editor-first6=Jane-Ling | editor-last6=Wang  | editor6-link = Jane-Ling Wang| year=2014 | isbn=9781482204964 | archive-url=https://web.archive.org/web/20150211232731/https://nisla05.niss.org/copss/past-present-future-copss.pdf | archive-date=2015-02-11 | chapter-url=https://nisla05.niss.org/copss/past-present-future-copss.pdf}}</ref> 1938 में हराल्ड क्रामर ने लगभग इसी धारणा को प्रकाशित किया था, जिसे अब क्रामर का सिद्धांत के नाम से जाना जाता है।
इस बाउंड को सामान्यतः [[हरमन चेर्नॉफ़]] के नाम पर जाना जाता है, जिन्होंने 1952 के लेख में इस विधि का वर्णन किया था,<ref>{{Cite journal|last=Chernoff|first=Herman|date=1952|title=अवलोकनों के योग के आधार पर एक परिकल्पना के परीक्षण के लिए स्पर्शोन्मुख दक्षता का एक उपाय|journal=The Annals of Mathematical Statistics|volume=23|issue=4|pages=493–507|doi=10.1214/aoms/1177729330|jstor=2236576|issn=0003-4851|doi-access=free}}</ref> चूँकि चेर्नॉफ़ ने इसे स्वयं हरमन रूबिन को समर्पित किया था।<ref>{{cite book | url=http://www.crcpress.com/product/isbn/9781482204964 | title=सांख्यिकी का अतीत, वर्तमान और भविष्य| chapter=A career in statistics | page=35 | publisher=CRC Press | last1=Chernoff | first1=Herman | editor-first1=Xihong | editor-last1=Lin | editor-first2=Christian | editor-last2=Genest | editor-first3=David L. | editor-last3=Banks | editor-first4=Geert | editor-last4=Molenberghs | editor-first5=David W. | editor-last5=Scott | editor-first6=Jane-Ling | editor-last6=Wang  | editor6-link = Jane-Ling Wang| year=2014 | isbn=9781482204964 | archive-url=https://web.archive.org/web/20150211232731/https://nisla05.niss.org/copss/past-present-future-copss.pdf | archive-date=2015-02-11 | chapter-url=https://nisla05.niss.org/copss/past-present-future-copss.pdf}}</ref> 1938 में हराल्ड क्रेमर ने अधिकतर इसी धारणा को प्रकाशित किया था, जिसे अब क्रेमर का सिद्धांत के नाम से जाना जाता है।


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


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


== जेनेरिक चेर्नॉफ़ सीमाएँ ==
== जेनेरिक चेर्नॉफ़ सीमाएँ ==
[[File:Chernoff-bound.svg|thumb|दो-तरफा चेर्नॉफ़ [[ची-वर्ग वितरण]]|ची-वर्ग यादृच्छिक चर के लिए बाध्य है]]यादृच्छिक प्रतिस्थान के लिए जनेरिक चेरनॉफ बाउंड को लागू करने के लिए, मार्कोव की असम्भवता को उपयोग करते हुए यह बाउंड मिलता है, इसे आवश्यकतानुसार एक्सपोनेंशियल मार्कोव या एक्सपोनेंशियल मोमेंट्स बाउंड भी कहा जाता है। इसके लिए, सकारात्मक <math>t</math> के लिए हम <math>e^{tX}</math> का बाउंड प्राप्त करते हैं (इसी कारण इसे कभी-कभी एक्सपोनेंशियल मार्कोव या एक्सपोनेंशियल मोमेंट्स बाउंड कहा जाता है)। इस बाउंड के लिए, यदि <math>t</math> सकारात्मक है, तो यह बाउंड देता है <math>X</math> के दायां खंभे की ओर की सीमा, जिसे मायने के रूप में उसके मोमेंट-उत्पन्न कारक के साथ लिखा जा सकता है <math>M(t) = \operatorname E (e^{t X})</math>:
[[File:Chernoff-bound.svg|thumb|दो-तरफा चेर्नॉफ़ [[ची-वर्ग वितरण]]|ची-वर्ग यादृच्छिक चर के लिए बाध्य है]]यादृच्छिक प्रतिसमिष्ट के लिए जनेरिक चेरनॉफ बाउंड को लागू करने के लिए, मार्कोव की असम्भवता को उपयोग करते हुए यह बाउंड मिलता है, इसे आवश्यकतानुसार एक्सपोनेंशियल मार्कोव या एक्सपोनेंशियल मोमेंट्स बाउंड भी कहा जाता है। इसके लिए, धनात्मक <math>t</math> के लिए हम <math>e^{tX}</math> का बाउंड प्राप्त करते हैं (इसी कारण इसे कभी-कभी एक्सपोनेंशियल मार्कोव या एक्सपोनेंशियल मोमेंट्स बाउंड कहा जाता है)। इस बाउंड के लिए, यदि <math>t</math> धनात्मक है, तो यह बाउंड देता है <math>X</math> के दायां खंभे की ओर की सीमा, जिसे मायने के रूप में उसके मोमेंट-उत्पन्न कारक के साथ लिखा जा सकता है <math>M(t) = \operatorname E (e^{t X})</math>:


<math>\operatorname P \left(X \geq a \right) = \operatorname P \left(e^{t X} \geq e^{t a}\right) \leq M(t) e^{-t a} \qquad (t > 0)</math>
<math>\operatorname P \left(X \geq a \right) = \operatorname P \left(e^{t X} \geq e^{t a}\right) \leq M(t) e^{-t a} \qquad (t > 0)</math>


यह बाउंड हर सकारात्मक <math>t</math>,के लिए सत्य होता है, इसलिए हम [[सबसे निचला और उच्चतम]] को न्यूनतम मान ले सकते हैं:
यह बाउंड हर धनात्मक <math>t</math>,के लिए सत्य होता है, इसलिए हम [[सबसे निचला और उच्चतम]] को न्यूनतम मान ले सकते हैं:


:<math>\operatorname P \left(X \geq a\right) \leq \inf_{t > 0} M(t) e^{-t a}</math>
:<math>\operatorname P \left(X \geq a\right) \leq \inf_{t > 0} M(t) e^{-t a}</math>
इसी तरह के विश्लेषण को नकारात्मक <math>t</math> के साथ करने से हम बाएं खंभे की समान बाउंड प्राप्त करते हैं:
इसी प्रकार के विश्लेषण को ऋणात्मक <math>t</math> के साथ करने से हम बाएं खंभे की समान बाउंड प्राप्त करते हैं:
:<math>\operatorname P \left(X \leq a \right) = \operatorname P \left(e^{t X} \geq e^{t a}\right) \leq M(t) e^{-t a} \qquad (t < 0)</math>
:<math>\operatorname P \left(X \leq a \right) = \operatorname P \left(e^{t X} \geq e^{t a}\right) \leq M(t) e^{-t a} \qquad (t < 0)</math>
और
और
Line 25: Line 25:
=== गुण ===
=== गुण ===


घाती संख्या के लिए तार्किक समान लिया जा सकता है क्योंकि एक्सपोनेंशियल फ़ंक्शन अभिप्रेत है, इसलिए जेनसेन की असम्भाविता के अनुसार <math>\operatorname E (e^{t X}) \ge e^{t \operatorname E (X)}</math>होता है। इससे यह प्राप्त होता है कि दायां खंभे की सीमा अवश्य हैं होता है जब <math>a \le \operatorname E (X)</math>; उसी तरह, बाएं खंभे के लिए बाउंड उचित होता है जब <math>a \ge \operatorname E (X)</math>। इसलिए हम दोनों infima को संयोजित कर सकते हैं और दो-तरफी चेरनॉफ बाउंड को परिभाषित कर सकते हैं .<math display="block">C(a) = \inf_{t} M(t) e^{-t a} </math>जो मुड़े हुए संचयी वितरण फ़ंक्शन पर ऊपरी सीमा प्रदान करता है <math>X</math> (माध्य पर मुड़ा हुआ, माध्यिका पर नहीं)।
घाती संख्या के लिए तार्किक समान लिया जा सकता है क्योंकि एक्सपोनेंशियल फ़ंक्शन अभिप्रेत है, इसलिए जेनसेन की असम्भाविता के अनुसार <math>\operatorname E (e^{t X}) \ge e^{t \operatorname E (X)}</math>होता है। इससे यह प्राप्त होता है कि दायां खंभे की सीमा अवश्य हैं होता है जब <math>a \le \operatorname E (X)</math>; उसी प्रकार, बाएं खंभे के लिए बाउंड उचित होता है जब <math>a \ge \operatorname E (X)</math>। इसलिए हम दोनों infima को संयोजित कर सकते हैं और दो-तरफी चेरनॉफ बाउंड को परिभाषित कर सकते हैं .<math display="block">C(a) = \inf_{t} M(t) e^{-t a} </math>जो मुड़े हुए संचयी वितरण फ़ंक्शन पर ऊपरी सीमा प्रदान करता है <math>X</math> (माध्य पर मुड़ा हुआ, माध्यिका पर नहीं)।
 


दो-तरफी चेर्नॉफ़ बाउंड के लघुगणक को [[दर समारोह|दर फ़ंक्शन]] (या क्रैमर ट्रांसफॉर्म) के रूप में जाना जाता है <math>I = -\log C</math>। यह लेजेन्ड्रे-फेन्चेल ट्रांसफॉर्मेशन के समतुल्य है|लेजेन्ड्रे-फेन्चेल ट्रांसफॉर्म या [[संचयी जनरेटिंग फ़ंक्शन]] का [[उत्तल संयुग्म]] <math>K = \log M</math>, के रूप में परिभाषित:
दो-तरफी चेर्नॉफ़ बाउंड के लघुगणक को [[दर समारोह|दर फ़ंक्शन]] (या क्रैमर ट्रांसफॉर्म) के रूप में जाना जाता है <math>I = -\log C</math>। यह लेजेन्ड्रे-फेन्चेल ट्रांसफॉर्मेशन के समतुल्य है|लेजेन्ड्रे-फेन्चेल ट्रांसफॉर्म या [[संचयी जनरेटिंग फ़ंक्शन]] का [[उत्तल संयुग्म]] <math>K = \log M</math>, के रूप में परिभाषित:
Line 33: Line 32:




यहां, मायने उत्पन्न करने के लिए कुम्युलेटिव उत्पन्न कारक फ़ंक्शन का लघुकरण अभिप्रेत है, इसलिए चेरनॉफ बाउंड लघुकरण होना चाहिए। चेरनॉफ बाउंड अपनी अधिकतम मान्यता आवश्यकता के समय प्राप्त करता है, <math>C(\operatorname E(X))=1</math>, और अनुवर्तन के तहत समान होता है:<math display="inline">C_{X+k}(a) = C_X(a - k) </math>.


चेरनॉफ बाउंड केवल तब सटीक होता है जब <math>X</math> एकल केंद्रित भार (असमवितरित वितरण) होता है। यह बाउंड केवल सीमित संख्यात्मक मानों के परे या उसके सीमाओं में सत्य होता है, जहां अनंत <math>t</math> के लिए निर्धारित होते हैं। असीमित संख्यात्मक मानों के लिए बाउंड कहीं भी सत्य नहीं होता है, हालांकि यह उप-घातीय कारकों (घातीय रूप से तंग) तक स्पर्शोन्मुख रूप से तंग है। व्यक्तिगत क्षण अधिक विश्लेषणात्मक जटिलता की कीमत पर, कड़ी सीमाएं प्रदान कर सकते हैं।<ref>{{Cite journal |last1=Philips |first1=Thomas K. |last2=Nelson |first2=Randolph |date=1995 |title=सकारात्मक पूंछ संभावनाओं के लिए बंधा हुआ क्षण चेर्नॉफ़ के बंधे से भी अधिक कठिन है|url=https://www.jstor.org/stable/2684633 |journal=The American Statistician |volume=49 |issue=2 |pages=175–178 |doi=10.2307/2684633 |jstor=2684633 |issn=0003-1305}}</ref>
यहां, मायने उत्पन्न करने के लिए कुम्युलेटिव उत्पन्न कारक फ़ंक्शन का लघुकरण अभिप्रेत है, इसलिए चेरनॉफ बाउंड लघुकरण होना चाहिए। चेरनॉफ बाउंड अपनी अधिकतम मान्यता आवश्यकता के समय प्राप्त करता है, <math>C(\operatorname E(X))=1</math>, और अनुवर्तन के अनुसार  समान होता है:<math display="inline">C_{X+k}(a) = C_X(a - k) </math>.
 
चेरनॉफ बाउंड केवल तब त्रुटिहीन होता है जब <math>X</math> एकल केंद्रित भार (असमवितरित वितरण) होता है। यह बाउंड केवल सीमित संख्यात्मक मानों के परे या उसके सीमाओं में सत्य होता है, जहां अनंत <math>t</math> के लिए निर्धारित होते हैं। असीमित संख्यात्मक मानों के लिए बाउंड कहीं भी सत्य नहीं होता है, चूंकि यह उप-घातीय कारकों (घातीय रूप से तंग) तक स्पर्शोन्मुख रूप से तंग है। व्यक्तिगत क्षण अधिक विश्लेषणात्मक जटिलता की मूल्य पर, कड़ी सीमाएं प्रदान कर सकते हैं।<ref>{{Cite journal |last1=Philips |first1=Thomas K. |last2=Nelson |first2=Randolph |date=1995 |title=सकारात्मक पूंछ संभावनाओं के लिए बंधा हुआ क्षण चेर्नॉफ़ के बंधे से भी अधिक कठिन है|url=https://www.jstor.org/stable/2684633 |journal=The American Statistician |volume=49 |issue=2 |pages=175–178 |doi=10.2307/2684633 |jstor=2684633 |issn=0003-1305}}</ref>


व्यावहारिक रूप में, सटीक चेरनॉफ बाउंड को असामर्थ्यपूर्ण या विश्लेषणात्मक रूप से मूल्यांकित करना कठिन हो सकता है, जिसके परिणामस्वरूप प्रतीक्षित कुम्युलेटिव वितरण फ़ंक्शन के ऊपरी सीमा (या कुम्युलेटिव उत्पन्न कारक) के लिए उचित ऊपरी बाउंड प्रयोग किया जा सकता है (जैसे कि उप-उपवाकीय सीजीएफ जो उप-गौसिय चेरनॉफ बाउंड देता है)।
व्यावहारिक रूप में, त्रुटिहीन चेरनॉफ बाउंड को असामर्थ्यपूर्ण या विश्लेषणात्मक रूप से मूल्यांकित करना कठिन हो सकता है, जिसके परिणामस्वरूप प्रतीक्षित कुम्युलेटिव वितरण फ़ंक्शन के ऊपरी सीमा (या कुम्युलेटिव उत्पन्न कारक) के लिए उचित ऊपरी बाउंड प्रयोग किया जा सकता है (जैसे कि उप-उपवाकीय सीजीएफ जो उप-गौसिय चेरनॉफ बाउंड देता है)।
{| class="wikitable mw-collapsible"
{| class="wikitable mw-collapsible"
|+सामान्य वितरण के लिए सटीक दर फ़ंक्शन और चेर्नॉफ़ सीमाएं
|+सामान्य वितरण के लिए त्रुटिहीन दर फ़ंक्शन और चेर्नॉफ़ सीमाएं
!वितरण
!वितरण
!<math>\operatorname E (X)</math>
!<math>\operatorname E (X)</math>
Line 91: Line 91:


=== एमजीएफ से निचली सीमा ===
=== एमजीएफ से निचली सीमा ===
मात्रात्मक उत्पन्न कारक का उपयोग करके, डेली-जयग्मंद असम्भवता को <math>e^{tX}</math>, पर लागू करके, पूर्विक को कोण प्राप्त किया जा सकता है, जो खंभे की संभावनाओं पर निचला बाउंड प्रदान करता है: <math display="block">\operatorname P \left(X > a\right) \geq \sup_{t > 0 \and M(t) \geq e^{ta}} \left( 1 - \frac{e^{ta}}{M(t)} \right)^2 \frac{M(t)^2}{M(2t)}</math>(नकारात्मक <math>t</math> के लिए बाईं पूंछ पर बाउंड प्राप्त किया जाता है) हालाँकि, चेर्नॉफ़ बाउंड के विपरीत, यह परिणाम तेजी से तंग नहीं है।
मात्रात्मक उत्पन्न कारक का उपयोग करके, डेली-जयग्मंद असम्भवता को <math>e^{tX}</math>, पर लागू करके, पूर्विक को कोण प्राप्त किया जा सकता है, जो खंभे की संभावनाओं पर निचला बाउंड प्रदान करता है: <math display="block">\operatorname P \left(X > a\right) \geq \sup_{t > 0 \and M(t) \geq e^{ta}} \left( 1 - \frac{e^{ta}}{M(t)} \right)^2 \frac{M(t)^2}{M(2t)}</math>(ऋणात्मक <math>t</math> के लिए बाईं पूंछ पर बाउंड प्राप्त किया जाता है) चूँकि, चेर्नॉफ़ बाउंड के विपरीत, यह परिणाम तेजी से तंग नहीं है।


थियोडोसोपोलोस<ref>{{Cite journal |last=Theodosopoulos |first=Ted |date=2007-03-01 |title=चेर्नॉफ़ बाउंड का प्रत्यावर्तन|url=https://www.sciencedirect.com/science/article/pii/S0167715206002884 |journal=Statistics & Probability Letters |language=en |volume=77 |issue=5 |pages=558–565 |doi=10.1016/j.spl.2006.09.003 |issn=0167-7152}}</ref> ने बाउंड का निर्माण किया (जो अधिक) जैसे एक्सपोनेंशियल[[घातीय झुकाव]] प्रक्रिया का उपयोग करके ज्यादा सत्य होता है।
थियोडोसोपोलोस<ref>{{Cite journal |last=Theodosopoulos |first=Ted |date=2007-03-01 |title=चेर्नॉफ़ बाउंड का प्रत्यावर्तन|url=https://www.sciencedirect.com/science/article/pii/S0167715206002884 |journal=Statistics & Probability Letters |language=en |volume=77 |issue=5 |pages=558–565 |doi=10.1016/j.spl.2006.09.003 |issn=0167-7152}}</ref> ने बाउंड का निर्माण किया (जो अधिक) जैसे एक्सपोनेंशियल[[घातीय झुकाव]] प्रक्रिया का उपयोग करके ज्यादा सत्य होता है।


विशेष (जैसे कि [[द्विपद वितरण]]) वितरणों के लिए, चेरनॉफ बाउंड के समान घातीय क्रम की निचली सीमाएं अक्सर उपलब्ध होती हैं।
विशेष (जैसे कि [[द्विपद वितरण]]) वितरणों के लिए, चेरनॉफ बाउंड के समान घातीय क्रम की निचली सीमाएं अधिकांशतः उपलब्ध होती हैं।


== स्वतंत्र यादृच्छिक चर का योग ==
== स्वतंत्र यादृच्छिक चर का योग ==
Line 112: Line 112:
{{main|होफ़डिंग की असमानता}}
{{main|होफ़डिंग की असमानता}}


चेर्नॉफ़ सीमाएं उनके वितरण की परवाह किए बिना, स्वतंत्र, बंधे हुए यादृच्छिक चर के सामान्य योगों पर भी लागू की जा सकती हैं; इसे होफ़डिंग की असमानता के रूप में जाना जाता है। प्रमाण अन्य चेरनॉफ़ सीमाओं के समान दृष्टिकोण का अनुसरण करता है, लेकिन क्षण उत्पन्न करने वाले कार्यों को बाध्य करने के लिए होएफ़डिंग की लेम्मा को लागू करता है (होएफ़डिंग की असम्भवता देखें)।
चेर्नॉफ़ सीमाएं उनके वितरण की परवाह किए बिना, स्वतंत्र, बंधे हुए यादृच्छिक चर के सामान्य योगों पर भी लागू की जा सकती हैं; इसे होफ़डिंग की असमानता के रूप में जाना जाता है। प्रमाण अन्य चेरनॉफ़ सीमाओं के समान दृष्टिकोण का अनुसरण करता है, किन्तु क्षण उत्पन्न करने वाले कार्यों को बाध्य करने के लिए होएफ़डिंग की लेम्मा को लागू करता है (होएफ़डिंग की असम्भवता देखें)।
:हेफ़ोडिंग की असम्भवता: मानें {{math|''X''<sub>1</sub>, ..., ''X<sub>n</sub>''}} [[सांख्यिकीय स्वतंत्रता]] यादृच्छिक चर हैं जो मान लेते हैं {{math|[a,b].}} होने देना {{mvar|X}} को उनके योग का दर्शाता है और {{math|''μ'' {{=}} E[''X'']}}उनके योग की अपेक्षित मान दर्शाता है। तब किसी भी <math>t>0</math>,
:हेफ़ोडिंग की असम्भवता: मानें {{math|''X''<sub>1</sub>, ..., ''X<sub>n</sub>''}} [[सांख्यिकीय स्वतंत्रता]] यादृच्छिक चर हैं जो मान लेते हैं {{math|[a,b].}} होने देना {{mvar|X}} को उनके योग का दर्शाता है और {{math|''μ'' {{=}} E[''X'']}}उनके योग की अपेक्षित मान दर्शाता है। तब किसी भी <math>t>0</math>,
::<math>\Pr (X \le \mu-t) < e^{-2t^2/(n(b-a)^2)},</math>
::<math>\Pr (X \le \mu-t) < e^{-2t^2/(n(b-a)^2)},</math>
Line 120: Line 120:


:<math>\operatorname E \left[e^{t\cdot X_i} \right] = (1 - p) e^0 + p e^t = 1 + p (e^t -1) \leq e^{p (e^t - 1)}.</math>
:<math>\operatorname E \left[e^{t\cdot X_i} \right] = (1 - p) e^0 + p e^t = 1 + p (e^t -1) \leq e^{p (e^t - 1)}.</math>
चेरनॉफ बाउंड के कई प्रकार हो सकते हैं: मूल्यमान के साथ तुलनात्मक त्रुटि को बाउंड करने वाला मूलभूत जोड़ने का रूप (जो वास्तविक त्रुटि पर बाउंड देता है) या अधिक व्यावहारिक गुणकारी रूप (जो त्रुटि को माध्य के प्रति संबंधित बाउंड करता है)।
चेरनॉफ बाउंड के कई प्रकार हो सकते हैं: मूल्यमान के साथ समानतात्मक त्रुटि को बाउंड करने वाला मूलभूत जोड़ने का रूप (जो वास्तविक त्रुटि पर बाउंड देता है) या अधिक व्यावहारिक गुणकारी रूप (जो त्रुटि को माध्य के प्रति संबंधित बाउंड करता है)।


===गुणात्मक रूप (सापेक्ष त्रुटि)===
===गुणात्मक रूप (सापेक्ष त्रुटि)===
Line 128: Line 128:


:<math>\Pr(X \le (1-\delta)\mu) < \left(\frac{e^{-\delta}}{(1-\delta)^{1-\delta}}\right)^\mu.</math>
:<math>\Pr(X \le (1-\delta)\mu) < \left(\frac{e^{-\delta}}{(1-\delta)^{1-\delta}}\right)^\mu.</math>
उपरोक्त सूत्र अक्सर अव्यवस्थित होता है, इसलिए आधारभूत लेकिन अधिक सुविधाजनक बाउंड<ref name="MitzenmacherUpfal">{{cite book | url=https://books.google.com/books?id=0bAYl6d7hvkC | title=Probability and Computing: Randomized Algorithms and Probabilistic Analysis | publisher=Cambridge University Press |author1=Mitzenmacher, Michael  |author2=Upfal, Eli | year=2005 | isbn=978-0-521-83540-4}}</ref> उपयोग किए जाते हैं, जो लॉगरिद्धि समानताओं की सूची से अवधारित असमानता <math>\textstyle\frac{2\delta}{2+\delta} \le \log(1+\delta)</math> का पालन करते हैं:
उपरोक्त सूत्र अधिकांशतः अव्यवस्थित होता है, इसलिए आधारभूत किन्तु अधिक सुविधाजनक बाउंड<ref name="MitzenmacherUpfal">{{cite book | url=https://books.google.com/books?id=0bAYl6d7hvkC | title=Probability and Computing: Randomized Algorithms and Probabilistic Analysis | publisher=Cambridge University Press |author1=Mitzenmacher, Michael  |author2=Upfal, Eli | year=2005 | isbn=978-0-521-83540-4}}</ref> उपयोग किए जाते हैं, जो लॉगरिद्धि समानताओं की सूची से अवधारित असमानता <math>\textstyle\frac{2\delta}{2+\delta} \le \log(1+\delta)</math> का पालन करते हैं:


:<math>\Pr( X \ge (1+\delta)\mu)\le e^{-\delta^2\mu/(2+\delta)}, \qquad 0 \le \delta,</math>
:<math>\Pr( X \ge (1+\delta)\mu)\le e^{-\delta^2\mu/(2+\delta)}, \qquad 0 \le \delta,</math>
Line 169: Line 169:
\end{align}
\end{align}
</math>
</math>
जो {{math|''p'' < {{sfrac|1|8}},}} के लिए मजबूत हैं, भी इस्तेमाल किए जाते हैं।
जो {{math|''p'' < {{sfrac|1|8}},}} के लिए मजबूत हैं, और उपयोग किए जाते हैं।


==अनुप्रयोग==
==अनुप्रयोग==
[[विरल ग्राफ]] नेटवर्क में सेट संतुलन और [[पैकेट (सूचना प्रौद्योगिकी)]] [[मार्ग]] में चेर्नॉफ़ सीमा के बहुत उपयोगी अनुप्रयोग हैं।
[[विरल ग्राफ]] नेटवर्क में सेट संतुलन और [[पैकेट (सूचना प्रौद्योगिकी)]] [[मार्ग]] में चेर्नॉफ़ सीमा के बहुत उपयोगी अनुप्रयोग हैं।


सांख्यिकीय प्रयोगों को डिज़ाइन करते समय सेट संतुलन की समस्या उत्पन्न होती है। आम तौर पर सांख्यिकीय प्रयोग को डिजाइन करते समय, प्रयोग में प्रत्येक भागीदार की विशेषताओं को देखते हुए, हमें यह जानना होगा कि प्रतिभागियों को 2 असंयुक्त समूहों में कैसे विभाजित किया जाए ताकि प्रत्येक विशेषता दोनों समूहों के बीच यथासंभव संतुलित हो।<ref name="0bAYl6d7hvkC">Refer to this [https://books.google.com/books?id=0bAYl6d7hvkC&pg=PA71 book section] for more info on the problem.</ref>
सांख्यिकीय प्रयोगों को डिज़ाइन करते समय सेट संतुलन की समस्या उत्पन्न होती है। सामान्यतः सांख्यिकीय प्रयोग को डिजाइन करते समय, प्रयोग में प्रत्येक भागीदार की विशेषताओं को देखते हुए, हमें यह जानना होगा कि प्रतिभागियों को 2 असंयुक्त समूहों में कैसे विभाजित किया जाए जिससे प्रत्येक विशेषता दोनों समूहों के बीच यथासंभव संतुलित हो।<ref name="0bAYl6d7hvkC">Refer to this [https://books.google.com/books?id=0bAYl6d7hvkC&pg=PA71 book section] for more info on the problem.</ref>
चेर्नॉफ़ सीमा का उपयोग क्रमपरिवर्तन रूटिंग समस्याओं के लिए तंग सीमा प्राप्त करने के लिए भी किया जाता है जो विरल नेटवर्क में पैकेट को रूट करते समय [[नेटवर्क संकुलन]] भीड़ को कम करता है।<ref name="0bAYl6d7hvkC" />
चेर्नॉफ़ सीमा का उपयोग क्रमपरिवर्तन रूटिंग समस्याओं के लिए तंग सीमा प्राप्त करने के लिए भी किया जाता है जो विरल नेटवर्क में पैकेट को रूट करते समय [[नेटवर्क संकुलन]] भीड़ को कम करता है।<ref name="0bAYl6d7hvkC" />


चेर्नॉफ़ सीमाओं का उपयोग [[कम्प्यूटेशनल शिक्षण सिद्धांत]] में यह साबित करने के लिए किया जाता है कि लर्निंग एल्गोरिदम संभवतः लगभग सही लर्निंग है, अर्थात् उच्च संभावना के साथ एल्गोरिदम में पर्याप्त बड़े प्रशिक्षण डेटा सेट पर छोटी त्रुटि होती है।<ref>{{cite book |first1=M. |last1=Kearns |first2=U. |last2=Vazirani |title=कम्प्यूटेशनल लर्निंग थ्योरी का एक परिचय|at=Chapter 9 (Appendix), pages 190–192 |publisher=MIT Press |year=1994 |isbn=0-262-11193-4 }}</ref>
चेर्नॉफ़ सीमाओं का उपयोग [[कम्प्यूटेशनल शिक्षण सिद्धांत]] में यह सिद्ध करने के लिए किया जाता है कि लर्निंग एल्गोरिदम संभवतः अधिकतर सही लर्निंग है, अर्थात् उच्च संभावना के साथ एल्गोरिदम में पर्याप्त बड़े प्रशिक्षण डेटा सेट पर छोटी त्रुटि होती है।<ref>{{cite book |first1=M. |last1=Kearns |first2=U. |last2=Vazirani |title=कम्प्यूटेशनल लर्निंग थ्योरी का एक परिचय|at=Chapter 9 (Appendix), pages 190–192 |publisher=MIT Press |year=1994 |isbn=0-262-11193-4 }}</ref>
यादृच्छिकरण के साथ इसके गड़बड़ी स्थान की खोज करके किसी एप्लिकेशन/एल्गोरिदम की मजबूती के स्तर का मूल्यांकन करने के लिए चेर्नॉफ़ सीमा का प्रभावी ढंग से उपयोग किया जा सकता है।<ref name="Alippi2014">{{cite book |first=C. |last=Alippi |chapter=Randomized Algorithms |title=एंबेडेड सिस्टम के लिए इंटेलिजेंस|publisher=Springer |year=2014 |isbn=978-3-319-05278-6 }}</ref>
यादृच्छिकरण के साथ इसके गड़बड़ी समिष्ट की अविष्कार करके किसी एप्लिकेशन/एल्गोरिदम की मजबूती के स्तर का मूल्यांकन करने के लिए चेर्नॉफ़ सीमा का प्रभावी ढंग से उपयोग किया जा सकता है।<ref name="Alippi2014">{{cite book |first=C. |last=Alippi |chapter=Randomized Algorithms |title=एंबेडेड सिस्टम के लिए इंटेलिजेंस|publisher=Springer |year=2014 |isbn=978-3-319-05278-6 }}</ref>
चेर्नॉफ़ बाउंड का उपयोग किसी को मजबूत - और अधिकतर अवास्तविक - छोटी गड़बड़ी परिकल्पना (परटर्बेशन परिमाण छोटा है) को त्यागने की अनुमति देता है। मजबूती स्तर का उपयोग, बदले में, किसी विशिष्ट एल्गोरिथम विकल्प, हार्डवेयर कार्यान्वयन या किसी समाधान की उपयुक्तता को मान्य या अस्वीकार करने के लिए किया जा सकता है, जिसके संरचनात्मक पैरामीटर अनिश्चितताओं से प्रभावित होते हैं।
चेर्नॉफ़ बाउंड का उपयोग किसी को मजबूत - और अधिकतर अवास्तविक - छोटी गड़बड़ी परिकल्पना (परटर्बेशन परिमाण छोटा है) को त्यागने की अनुमति देता है। मजबूती स्तर का उपयोग, बदले में, किसी विशिष्ट एल्गोरिथम विकल्प, हार्डवेयर कार्यान्वयन या किसी समाधान की उपयुक्तता को मान्य या अस्वीकार करने के लिए किया जा सकता है, जिसके संरचनात्मक पैरामीटर अनिश्चितताओं से प्रभावित होते हैं।


चेर्नॉफ़ सीमा का सरल और सामान्य उपयोग [[यादृच्छिक एल्गोरिदम]] को बढ़ावा देने के लिए है। यदि किसी के पास एल्गोरिदम है जो अनुमान लगाता है कि संभावना पी> 1/2 के साथ वांछित उत्तर है, तो कोई एल्गोरिदम चलाकर उच्च सफलता दर प्राप्त कर सकता है <math>n = \log(1/\delta) 2p/(p - 1/2)^2</math> समय और अनुमान आउटपुट करना जो एल्गोरिदम के n/2 रन से अधिक आउटपुट है। (पिजनहोल सिद्धांत द्वारा ऐसे से अधिक अनुमान नहीं हो सकते हैं।) यह मानते हुए कि ये एल्गोरिदम रन स्वतंत्र हैं, n/2 से अधिक अनुमानों के सही होने की संभावना इस संभावना के बराबर है कि स्वतंत्र बर्नौली यादृच्छिक चर का योग {{math|''X<sub>k</sub>''}} जो कि 1 है और प्रायिकता p, n/2 से अधिक है। ऐसा कम से कम करके तो दिखाया जा सकता है <math>1-\delta</math> गुणक चेर्नॉफ़ बाउंड के माध्यम से (सिंक्लेयर के क्लास नोट्स में परिणाम 13.3, {{math|''μ'' {{=}} ''np''}}).<ref>{{Cite web|url = http://www.cs.berkeley.edu/~sinclair/cs271/n13.pdf|title = पाठ्यक्रम "यादृच्छिकता और संगणना" के लिए कक्षा नोट्स|date = Fall 2011|access-date = 30 October 2014|last = Sinclair|first = Alistair|archive-url = https://web.archive.org/web/20141031035717/http://www.cs.berkeley.edu/~sinclair/cs271/n13.pdf|archive-date = 31 October 2014|url-status = dead}}</ref>:
चेर्नॉफ़ सीमा का सरल और सामान्य उपयोग [[यादृच्छिक एल्गोरिदम]] को बढ़ावा देने के लिए है। यदि किसी के पास एल्गोरिदम है जो अनुमान लगाता है कि संभावना पी> 1/2 के साथ वांछित उत्तर है, तो कोई एल्गोरिदम चलाकर उच्च सफलता दर प्राप्त कर सकता है <math>n = \log(1/\delta) 2p/(p - 1/2)^2</math> समय और अनुमान आउटपुट करना जो एल्गोरिदम के n/2 रन से अधिक आउटपुट है। (पिजनहोल सिद्धांत द्वारा ऐसे से अधिक अनुमान नहीं हो सकते हैं।) यह मानते हुए कि ये एल्गोरिदम रन स्वतंत्र हैं, n/2 से अधिक अनुमानों के सही होने की संभावना इस संभावना के समान है कि स्वतंत्र बर्नौली यादृच्छिक चर का योग {{math|''X<sub>k</sub>''}} जो कि 1 है और प्रायिकता p, n/2 से अधिक है। ऐसा कम से कम करके तो दिखाया जा सकता है <math>1-\delta</math> गुणक चेर्नॉफ़ बाउंड के माध्यम से (सिंक्लेयर के क्लास नोट्स में परिणाम 13.3, {{math|''μ'' {{=}} ''np''}}).<ref>{{Cite web|url = http://www.cs.berkeley.edu/~sinclair/cs271/n13.pdf|title = पाठ्यक्रम "यादृच्छिकता और संगणना" के लिए कक्षा नोट्स|date = Fall 2011|access-date = 30 October 2014|last = Sinclair|first = Alistair|archive-url = https://web.archive.org/web/20141031035717/http://www.cs.berkeley.edu/~sinclair/cs271/n13.pdf|archive-date = 31 October 2014|url-status = dead}}</ref>:


:<math>\Pr\left[X > {n \over 2}\right] \ge 1 - e^{-n \left(p - 1/2 \right)^2/(2p)} \geq 1-\delta</math>
:<math>\Pr\left[X > {n \over 2}\right] \ge 1 - e^{-n \left(p - 1/2 \right)^2/(2p)} \geq 1-\delta</math>
Line 189: Line 189:
{{main|मैट्रिक्स चेर्नॉफ़ बाध्य}}
{{main|मैट्रिक्स चेर्नॉफ़ बाध्य}}


[[रूडोल्फ अहलस्वेड]] और [[एंड्रियास विंटर]] ने मैट्रिक्स-मूल्यवान यादृच्छिक चर के लिए चेर्नॉफ़ बाउंड पेश किया।<ref>{{cite journal
[[रूडोल्फ अहलस्वेड]] और [[एंड्रियास विंटर]] ने मैट्रिक्स-मूल्यवान यादृच्छिक चर के लिए चेर्नॉफ़ बाउंड प्रस्तुत किया।<ref>{{cite journal
  |last1=Ahlswede |first1=R.
  |last1=Ahlswede |first1=R.
  |last2=Winter |first2=A.
  |last2=Winter |first2=A.
Line 213: Line 213:


होने देना {{math|''M''<sub>1</sub>, ..., ''M<sub>t</sub>''}} स्वतंत्र मैट्रिक्स मान वाले यादृच्छिक चर बनें <math> M_i\in \mathbb{C}^{d_1 \times d_2} </math> और <math> \mathbb{E}[M_i]=0</math>.
होने देना {{math|''M''<sub>1</sub>, ..., ''M<sub>t</sub>''}} स्वतंत्र मैट्रिक्स मान वाले यादृच्छिक चर बनें <math> M_i\in \mathbb{C}^{d_1 \times d_2} </math> और <math> \mathbb{E}[M_i]=0</math>.
आइए हम इसे निरूपित करें <math> \lVert M \rVert </math> मैट्रिक्स का ऑपरेटर मानदंड <math> M </math>. यदि <math> \lVert M_i \rVert \leq \gamma </math> लगभग सभी के लिए निश्चित रूप से धारण करता है <math> i\in\{1,\ldots, t\} </math>, फिर प्रत्येक के लिए {{math|''ε'' > 0}}
आइए हम इसे निरूपित करें <math> \lVert M \rVert </math> मैट्रिक्स का ऑपरेटर मानदंड <math> M </math>. यदि <math> \lVert M_i \rVert \leq \gamma </math> अधिकतर सभी के लिए निश्चित रूप से धारण करता है <math> i\in\{1,\ldots, t\} </math>, फिर प्रत्येक के लिए {{math|''ε'' > 0}}


:<math>\Pr\left( \left\| \frac{1}{t} \sum_{i=1}^t M_i \right\| > \varepsilon \right) \leq (d_1+d_2) \exp \left( -\frac{3\varepsilon^2 t}{8\gamma^2} \right).</math>
:<math>\Pr\left( \left\| \frac{1}{t} \sum_{i=1}^t M_i \right\| > \varepsilon \right) \leq (d_1+d_2) \exp \left( -\frac{3\varepsilon^2 t}{8\gamma^2} \right).</math>
ध्यान दें कि यह निष्कर्ष निकालने के लिए कि 0 से विचलन परिबद्ध है {{math|''ε''}} उच्च संभावना के साथ, हमें कई नमूने चुनने की आवश्यकता है <math>t </math> के लघुगणक के समानुपाती <math> d_1+d_2 </math>. सामान्य तौर पर, दुर्भाग्य से, पर निर्भरता <math> \log(\min(d_1,d_2)) </math> अपरिहार्य है: उदाहरण के लिए आयाम का विकर्ण यादृच्छिक संकेत मैट्रिक्स लें <math>d\times d </math>. टी स्वतंत्र नमूनों के योग का ऑपरेटर मानदंड सटीक रूप से लंबाई टी के डी स्वतंत्र यादृच्छिक वॉक के बीच अधिकतम विचलन है। निरंतर संभावना के साथ अधिकतम विचलन पर निश्चित सीमा प्राप्त करने के लिए, यह देखना आसान है कि इस परिदृश्य में t को d के साथ लघुगणकीय रूप से बढ़ना चाहिए।<ref>{{cite arXiv |last1=Magen |first1=A.|author1-link=Avner Magen |last2=Zouzias |first2=A. |year=2011 |title=निम्न रैंक मैट्रिक्स-मूल्यवान चेर्नॉफ़ बाउंड्स और अनुमानित मैट्रिक्स गुणन|class=cs.DM |eprint=1005.2724 }}</ref>
ध्यान दें कि यह निष्कर्ष निकालने के लिए कि 0 से विचलन परिबद्ध है {{math|''ε''}} उच्च संभावना के साथ, हमें कई नमूने चुनने की आवश्यकता है <math>t </math> के लघुगणक के समानुपाती <math> d_1+d_2 </math>. सामान्यतः, दुर्भाग्य से, पर निर्भरता <math> \log(\min(d_1,d_2)) </math> अपरिहार्य है: उदाहरण के लिए आयाम का विकर्ण यादृच्छिक संकेत मैट्रिक्स लें <math>d\times d </math>. टी स्वतंत्र नमूनों के योग का ऑपरेटर मानदंड त्रुटिहीन रूप से लंबाई टी के डी स्वतंत्र यादृच्छिक वॉक के बीच अधिकतम विचलन है। निरंतर संभावना के साथ अधिकतम विचलन पर निश्चित सीमा प्राप्त करने के लिए, यह देखना आसान है कि इस परिदृश्य में t को d के साथ लघुगणकीय रूप से बढ़ना चाहिए।<ref>{{cite arXiv |last1=Magen |first1=A.|author1-link=Avner Magen |last2=Zouzias |first2=A. |year=2011 |title=निम्न रैंक मैट्रिक्स-मूल्यवान चेर्नॉफ़ बाउंड्स और अनुमानित मैट्रिक्स गुणन|class=cs.DM |eprint=1005.2724 }}</ref>


आयामों पर निर्भरता से बचने के लिए, यह मानकर निम्नलिखित प्रमेय प्राप्त किया जा सकता है कि एम की रैंक निम्न है।
आयामों पर निर्भरता से बचने के लिए, यह मानकर निम्नलिखित प्रमेय प्राप्त किया जा सकता है कि एम की रैंक निम्न है।


===आयामों पर निर्भरता के बिना प्रमेय===
===आयामों पर निर्भरता के बिना प्रमेय===
मान ले {{math|0 < ''ε'' < 1}} हो और M यादृच्छिक सममित वास्तविक मैट्रिक्स हो जिसके लिए <math>\| \operatorname E[M] \| \leq 1 </math> और <math>\| M\| \leq \gamma </math> होता है लगभग निश्चितता के साथ, मान लें कि M के समर्थन में प्रत्येक तत्व मानक r से अधिकतम अवर्ध होता है। सेट करें
मान ले {{math|0 < ''ε'' < 1}} हो और M यादृच्छिक सममित वास्तविक मैट्रिक्स हो जिसके लिए <math>\| \operatorname E[M] \| \leq 1 </math> और <math>\| M\| \leq \gamma </math> होता है अधिकतर निश्चितता के साथ, मान लें कि M के समर्थन में प्रत्येक तत्व मानक r से अधिकतम अवर्ध होता है। सेट करें
:<math> t = \Omega \left( \frac{\gamma\log (\gamma/\varepsilon^2)}{\varepsilon^2} \right).</math>
:<math> t = \Omega \left( \frac{\gamma\log (\gamma/\varepsilon^2)}{\varepsilon^2} \right).</math>
यदि <math> r \leq t </math> लगभग निश्चितता के साथ माना जाता है, तो
यदि <math> r \leq t </math> अधिकतर निश्चितता के साथ माना जाता है, तो


:<math>\Pr\left(\left\| \frac{1}{t} \sum_{i=1}^t M_i - \operatorname E[M] \right\| > \varepsilon \right) \leq \frac{1}{\mathbf{poly}(t)}</math>
:<math>\Pr\left(\left\| \frac{1}{t} \sum_{i=1}^t M_i - \operatorname E[M] \right\| > \varepsilon \right) \leq \frac{1}{\mathbf{poly}(t)}</math>
Line 241: Line 241:
विशेष रूप से, यदि B A में बहुमत है (अर्थात् r > 0.5) तो हम निम्नलिखित लेकर बाउंड कर सकते हैं कि B S में अधिकांश रहेगा ''S''(''r<sub>S</sub>'' > 0.5):''d'' = 1 − 1/(2''r''): <ref>See graphs of: [https://www.desmos.com/calculator/eqvyjug0re the bound as a function of ''r'' when ''k'' changes] and [https://www.desmos.com/calculator/nxurzg7bqj the bound as a function of ''k'' when ''r'' changes].</ref>
विशेष रूप से, यदि B A में बहुमत है (अर्थात् r > 0.5) तो हम निम्नलिखित लेकर बाउंड कर सकते हैं कि B S में अधिकांश रहेगा ''S''(''r<sub>S</sub>'' > 0.5):''d'' = 1 − 1/(2''r''): <ref>See graphs of: [https://www.desmos.com/calculator/eqvyjug0re the bound as a function of ''r'' when ''k'' changes] and [https://www.desmos.com/calculator/nxurzg7bqj the bound as a function of ''k'' when ''r'' changes].</ref>
:<math>\Pr\left(r_S > 0.5\right) > 1 - \exp\left(-r\cdot \left(1 - \frac{1}{2 r}\right)^2 \cdot \frac k 2 \right)</math>
:<math>\Pr\left(r_S > 0.5\right) > 1 - \exp\left(-r\cdot \left(1 - \frac{1}{2 r}\right)^2 \cdot \frac k 2 \right)</math>
यह बाउंड बिल्कुल सटीक नहीं है। उदाहरण के लिए, जब r = 0.5 ता है, हमें साधारण बाउंड प्राप्त होता है: Prob > 0।
यह बाउंड बिल्कुल त्रुटिहीन नहीं है। उदाहरण के लिए, जब r = 0.5 ता है, हमें साधारण बाउंड प्राप्त होता है: Prob > 0।


==प्रमाण==
==प्रमाण==


===गुणात्मक रूप===
===गुणात्मक रूप===
गुणक चेर्नॉफ़ बाउंड की शर्तों का पालन करते हुए, {{math|''X''<sub>1</sub>, ..., ''X<sub>n</sub>''}} स्वतंत्र बर्नौली यादृच्छिक चर है, जिसका योग {{math|''X''}} है, जहाँ प्रत्येक घटक को 1 होने की की प्रायिकता ''p<sub>i</sub>'' के बराबर होती है। बर्नौली चर के लिए:
गुणक चेर्नॉफ़ बाउंड की शर्तों का पालन करते हुए, {{math|''X''<sub>1</sub>, ..., ''X<sub>n</sub>''}} स्वतंत्र बर्नौली यादृच्छिक चर है, जिसका योग {{math|''X''}} है, जहाँ प्रत्येक घटक को 1 होने की की प्रायिकता ''p<sub>i</sub>'' के समान होती है। बर्नौली चर के लिए:


:<math>\operatorname E \left[e^{t\cdot X_i} \right] = (1 - p_i) e^0 + p_i e^t = 1 + p_i (e^t -1) \leq e^{p_i (e^t - 1)}</math>
:<math>\operatorname E \left[e^{t\cdot X_i} \right] = (1 - p_i) e^0 + p_i e^t = 1 + p_i (e^t -1) \leq e^{p_i (e^t - 1)}</math>
Line 256: Line 256:
& = \inf_{t \geq 0} \exp\Big(-t(1+\delta)\mu + (e^t - 1)\mu\Big).
& = \inf_{t \geq 0} \exp\Big(-t(1+\delta)\mu + (e^t - 1)\mu\Big).
\end{align}</math>
\end{align}</math>
यदि हम {{math|''t'' {{=}} log(1 + ''δ'')}} सेट करें ताकि {{math|''t'' > 0}} हो (जब {{math|''δ'' > 0}} हो), तो हम स्थानापन्न सकते हैं और प्राप्त करते हैं
यदि हम {{math|''t'' {{=}} log(1 + ''δ'')}} सेट करें जिससे {{math|''t'' > 0}} हो (जब {{math|''δ'' > 0}} हो), तो हम स्थानापन्न सकते हैं और प्राप्त करते हैं


:<math>\exp\Big(-t(1+\delta)\mu + (e^t - 1)\mu\Big) = \frac{\exp((1+\delta - 1)\mu)}{(1+\delta)^{(1+\delta)\mu}} = \left[\frac{e^\delta}{(1+\delta)^{(1+\delta)}}\right]^\mu.</math>
:<math>\exp\Big(-t(1+\delta)\mu + (e^t - 1)\mu\Big) = \frac{\exp((1+\delta - 1)\mu)}{(1+\delta)^{(1+\delta)\mu}} = \left[\frac{e^\delta}{(1+\delta)^{(1+\delta)}}\right]^\mu.</math>
Line 277: Line 277:
(1-q)pe^{t} &= q(1-p)
(1-q)pe^{t} &= q(1-p)
\end{align}</math>
\end{align}</math>
ताकि
जिससे


:<math>e^t = \frac{(1-p)q}{(1-q)p}.</math>
:<math>e^t = \frac{(1-p)q}{(1-q)p}.</math>
Line 294: Line 294:
&= -D(q \parallel p).
&= -D(q \parallel p).
\end{align}</math>
\end{align}</math>
अब हमारे पास अपना वांछित परिणाम है, यानी
अब हमारे पास अपना वांछित परिणाम है, अर्थात


:<math>\Pr \left (\tfrac{1}{n}\sum X_i \ge p + \varepsilon\right ) \le e^{-D(p+\varepsilon\parallel p) n}.</math>
:<math>\Pr \left (\tfrac{1}{n}\sum X_i \ge p + \varepsilon\right ) \le e^{-D(p+\varepsilon\parallel p) n}.</math>
व्यास्तिगत मामले के लिए प्रमाण को पूरा करने के लिए, हम सदर्भीय चर {{math|''Y<sub>i</sub>'' {{=}} 1 − ''X<sub>i</sub>''}} को परिभाषित करते हैं , वही समान प्रमाण का इस्तेमाल करते हैं, और हमारे बाउंड में इसे प्लगइन करते हैं।
व्यास्तिगत स्थितियों के लिए प्रमाण को पूर्ण करने के लिए, हम सदर्भीय चर {{math|''Y<sub>i</sub>'' {{=}} 1 − ''X<sub>i</sub>''}} को परिभाषित करते हैं , वही समान प्रमाण का उपयोग करते हैं, और हमारे बाउंड में इसे प्लगइन करते हैं।


==यह भी देखें==
==यह भी देखें==

Revision as of 00:09, 14 July 2023

संभाव्यता सिद्धांत में, चेर्नॉफ़ बाउंड संयंत्रक संख्या के माध्यम से एक यादृच्छिक प्रारंभिक मुद्रण फल की पुनरावृत्ति पर एक विपरीत लक्ष्य बाउंड होती है। सभी ऐसे घातीय बाउंडों में से कम से कम भारी बाउंड चेर्नॉफ या चेर्नॉफ-क्रामर बाउंड कहलाता है, जो विपरीत या सब-गॉसियन (उदाहरण के लिए अवसादीय) रूप से अधिक घटती है।[1][2] यह विशेष रूप से स्वतंत्र यादृच्छिक चर के योग के लिए उपयोगी है, जैसे कि बर्नौली यादृच्छिक चर का योग।[3][4]

इस बाउंड को सामान्यतः हरमन चेर्नॉफ़ के नाम पर जाना जाता है, जिन्होंने 1952 के लेख में इस विधि का वर्णन किया था,[5] चूँकि चेर्नॉफ़ ने इसे स्वयं हरमन रूबिन को समर्पित किया था।[6] 1938 में हराल्ड क्रेमर ने अधिकतर इसी धारणा को प्रकाशित किया था, जिसे अब क्रेमर का सिद्धांत के नाम से जाना जाता है।

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

चेरनॉफ बाउंड बर्नस्टीन असम्भवताओं से संबंधित है। इसका उपयोग भी होफ्डिंग के असम्भवता, बेनेट के असम्भवता और मैकडॉनाल्ड के असम्भवता को सिद्ध करने के लिए किया जाता है।

जेनेरिक चेर्नॉफ़ सीमाएँ

ची-वर्ग यादृच्छिक चर के लिए बाध्य है

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

यह बाउंड हर धनात्मक ,के लिए सत्य होता है, इसलिए हम सबसे निचला और उच्चतम को न्यूनतम मान ले सकते हैं:

इसी प्रकार के विश्लेषण को ऋणात्मक के साथ करने से हम बाएं खंभे की समान बाउंड प्राप्त करते हैं:

और

मात्रा अपेक्षा मूल्य के रूप में व्यक्त किया जा सकता है , या समकालिक रूप में लिखा जा सकता है

गुण

घाती संख्या के लिए तार्किक समान लिया जा सकता है क्योंकि एक्सपोनेंशियल फ़ंक्शन अभिप्रेत है, इसलिए जेनसेन की असम्भाविता के अनुसार होता है। इससे यह प्राप्त होता है कि दायां खंभे की सीमा अवश्य हैं होता है जब ; उसी प्रकार, बाएं खंभे के लिए बाउंड उचित होता है जब । इसलिए हम दोनों infima को संयोजित कर सकते हैं और दो-तरफी चेरनॉफ बाउंड को परिभाषित कर सकते हैं .

जो मुड़े हुए संचयी वितरण फ़ंक्शन पर ऊपरी सीमा प्रदान करता है (माध्य पर मुड़ा हुआ, माध्यिका पर नहीं)।

दो-तरफी चेर्नॉफ़ बाउंड के लघुगणक को दर फ़ंक्शन (या क्रैमर ट्रांसफॉर्म) के रूप में जाना जाता है । यह लेजेन्ड्रे-फेन्चेल ट्रांसफॉर्मेशन के समतुल्य है|लेजेन्ड्रे-फेन्चेल ट्रांसफॉर्म या संचयी जनरेटिंग फ़ंक्शन का उत्तल संयुग्म , के रूप में परिभाषित:


यहां, मायने उत्पन्न करने के लिए कुम्युलेटिव उत्पन्न कारक फ़ंक्शन का लघुकरण अभिप्रेत है, इसलिए चेरनॉफ बाउंड लघुकरण होना चाहिए। चेरनॉफ बाउंड अपनी अधिकतम मान्यता आवश्यकता के समय प्राप्त करता है, , और अनुवर्तन के अनुसार समान होता है:.

चेरनॉफ बाउंड केवल तब त्रुटिहीन होता है जब एकल केंद्रित भार (असमवितरित वितरण) होता है। यह बाउंड केवल सीमित संख्यात्मक मानों के परे या उसके सीमाओं में सत्य होता है, जहां अनंत के लिए निर्धारित होते हैं। असीमित संख्यात्मक मानों के लिए बाउंड कहीं भी सत्य नहीं होता है, चूंकि यह उप-घातीय कारकों (घातीय रूप से तंग) तक स्पर्शोन्मुख रूप से तंग है। व्यक्तिगत क्षण अधिक विश्लेषणात्मक जटिलता की मूल्य पर, कड़ी सीमाएं प्रदान कर सकते हैं।[7]

व्यावहारिक रूप में, त्रुटिहीन चेरनॉफ बाउंड को असामर्थ्यपूर्ण या विश्लेषणात्मक रूप से मूल्यांकित करना कठिन हो सकता है, जिसके परिणामस्वरूप प्रतीक्षित कुम्युलेटिव वितरण फ़ंक्शन के ऊपरी सीमा (या कुम्युलेटिव उत्पन्न कारक) के लिए उचित ऊपरी बाउंड प्रयोग किया जा सकता है (जैसे कि उप-उपवाकीय सीजीएफ जो उप-गौसिय चेरनॉफ बाउंड देता है)।

सामान्य वितरण के लिए त्रुटिहीन दर फ़ंक्शन और चेर्नॉफ़ सीमाएं
वितरण
सामान्य वितरण
बर्नौली वितरण (नीचे विस्तृत)
मानक बर्नौली

(H बाइनरी एन्ट्रॉपी फ़ंक्शन है)

रेडमेकर वितरण
गामा वितरण
ची-वर्ग वितरण [8]
पोइसन वितरण

एमजीएफ से निचली सीमा

मात्रात्मक उत्पन्न कारक का उपयोग करके, डेली-जयग्मंद असम्भवता को , पर लागू करके, पूर्विक को कोण प्राप्त किया जा सकता है, जो खंभे की संभावनाओं पर निचला बाउंड प्रदान करता है:

(ऋणात्मक के लिए बाईं पूंछ पर बाउंड प्राप्त किया जाता है) चूँकि, चेर्नॉफ़ बाउंड के विपरीत, यह परिणाम तेजी से तंग नहीं है।

थियोडोसोपोलोस[9] ने बाउंड का निर्माण किया (जो अधिक) जैसे एक्सपोनेंशियलघातीय झुकाव प्रक्रिया का उपयोग करके ज्यादा सत्य होता है।

विशेष (जैसे कि द्विपद वितरण) वितरणों के लिए, चेरनॉफ बाउंड के समान घातीय क्रम की निचली सीमाएं अधिकांशतः उपलब्ध होती हैं।

स्वतंत्र यादृच्छिक चर का योग

जब X, n अलग-अलग औपचारिक क्रमिक चरणिका X1, ..., Xn, के n निर्दिष्ट निर्देशांकों का योग होता है, तो X का उत्पन्न कारक उत्पन्नकों के व्यक्तिगत उत्पन्नकों के गुणक का होता है, जिससे प्राप्त होता है:

 

 

 

 

(1)

और:

विशिष्ट चेर्नॉफ़ सीमाएँ क्षण-उत्पन्न करने वाले फ़ंक्शन की गणना करके प्राप्त की जाती हैं यादृच्छिक चर के विशिष्ट उदाहरणों के लिए .

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

स्वतंत्र परिबद्ध यादृच्छिक चरों का योग

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

हेफ़ोडिंग की असम्भवता: मानें X1, ..., Xn सांख्यिकीय स्वतंत्रता यादृच्छिक चर हैं जो मान लेते हैं [a,b]. होने देना X को उनके योग का दर्शाता है और μ = E[X]उनके योग की अपेक्षित मान दर्शाता है। तब किसी भी ,

स्वतंत्र बर्नौली यादृच्छिक चर का योग

निम्न खंडों में दिए गए बर्नौली यादृच्छिक चरणिकाओं के लिए बाउंड, उस तथ्य का उपयोग करके निर्मित किए गए है कि बर्नौली यादृच्छिक चरणिका के लिए, 1 होने की संभावना p होती है।

चेरनॉफ बाउंड के कई प्रकार हो सकते हैं: मूल्यमान के साथ समानतात्मक त्रुटि को बाउंड करने वाला मूलभूत जोड़ने का रूप (जो वास्तविक त्रुटि पर बाउंड देता है) या अधिक व्यावहारिक गुणकारी रूप (जो त्रुटि को माध्य के प्रति संबंधित बाउंड करता है)।

गुणात्मक रूप (सापेक्ष त्रुटि)

यदि X1, ..., Xn स्वतंत्र यादृच्छिक चरणिका हैं जो {0, 1}. मान लेते हैं, तो X को उनके योग का दर्शाता है औ μ = E[X] योग की अपेक्षित मान दर्शाता है। तब किसी भी δ > 0 । के लिए,

यह दिखाने के लिए समान प्रमाण रणनीति का उपयोग करके दिखाया जा सकता है कि 0 < δ < 1 के लिए,

उपरोक्त सूत्र अधिकांशतः अव्यवस्थित होता है, इसलिए आधारभूत किन्तु अधिक सुविधाजनक बाउंड[10] उपयोग किए जाते हैं, जो लॉगरिद्धि समानताओं की सूची से अवधारित असमानता का पालन करते हैं:

ध्यान दें कि ये बाउंड जीर्ण होते हैं जब

योगात्मक रूप (पूर्ण त्रुटि)

निम्नलिखित प्रमाण वासिली होफ़डिंग के द्वारा है और इसलिए इसे चेरनॉफ-हेफोडिंग प्रमाण कहा जाता है।[11]

चेरनॉफ-हेफोडिंग प्रमाण: मानें X1, ..., Xn i.i.d. यादृच्छिक चरणिका हैं, जो{0, 1}. मान लेते हैं। p = E[X1] और ε > 0 हों।.
जहाँ
क्रमशः पैरामीटर x और y के साथ बर्नौली वितरण यादृच्छिक चर के बीच कुल्बैक-लीबलर विचलन है। यदि p1/2, है, तो है, जिसका अर्थ है

इसके साथ सुगम बाउंड D(p + ε || p) ≥ 2ε2, का उपयोग करके, जो D(p + ε || p) की उत्तलता और तथ्य के कारण से होता है

यह परिणाम होफ़डिंग की असमानता का विशेष मामला है। कभी-कभी, बाउंड्स

जो p < 1/8, के लिए मजबूत हैं, और उपयोग किए जाते हैं।

अनुप्रयोग

विरल ग्राफ नेटवर्क में सेट संतुलन और पैकेट (सूचना प्रौद्योगिकी) मार्ग में चेर्नॉफ़ सीमा के बहुत उपयोगी अनुप्रयोग हैं।

सांख्यिकीय प्रयोगों को डिज़ाइन करते समय सेट संतुलन की समस्या उत्पन्न होती है। सामान्यतः सांख्यिकीय प्रयोग को डिजाइन करते समय, प्रयोग में प्रत्येक भागीदार की विशेषताओं को देखते हुए, हमें यह जानना होगा कि प्रतिभागियों को 2 असंयुक्त समूहों में कैसे विभाजित किया जाए जिससे प्रत्येक विशेषता दोनों समूहों के बीच यथासंभव संतुलित हो।[12] चेर्नॉफ़ सीमा का उपयोग क्रमपरिवर्तन रूटिंग समस्याओं के लिए तंग सीमा प्राप्त करने के लिए भी किया जाता है जो विरल नेटवर्क में पैकेट को रूट करते समय नेटवर्क संकुलन भीड़ को कम करता है।[12]

चेर्नॉफ़ सीमाओं का उपयोग कम्प्यूटेशनल शिक्षण सिद्धांत में यह सिद्ध करने के लिए किया जाता है कि लर्निंग एल्गोरिदम संभवतः अधिकतर सही लर्निंग है, अर्थात् उच्च संभावना के साथ एल्गोरिदम में पर्याप्त बड़े प्रशिक्षण डेटा सेट पर छोटी त्रुटि होती है।[13] यादृच्छिकरण के साथ इसके गड़बड़ी समिष्ट की अविष्कार करके किसी एप्लिकेशन/एल्गोरिदम की मजबूती के स्तर का मूल्यांकन करने के लिए चेर्नॉफ़ सीमा का प्रभावी ढंग से उपयोग किया जा सकता है।[14] चेर्नॉफ़ बाउंड का उपयोग किसी को मजबूत - और अधिकतर अवास्तविक - छोटी गड़बड़ी परिकल्पना (परटर्बेशन परिमाण छोटा है) को त्यागने की अनुमति देता है। मजबूती स्तर का उपयोग, बदले में, किसी विशिष्ट एल्गोरिथम विकल्प, हार्डवेयर कार्यान्वयन या किसी समाधान की उपयुक्तता को मान्य या अस्वीकार करने के लिए किया जा सकता है, जिसके संरचनात्मक पैरामीटर अनिश्चितताओं से प्रभावित होते हैं।

चेर्नॉफ़ सीमा का सरल और सामान्य उपयोग यादृच्छिक एल्गोरिदम को बढ़ावा देने के लिए है। यदि किसी के पास एल्गोरिदम है जो अनुमान लगाता है कि संभावना पी> 1/2 के साथ वांछित उत्तर है, तो कोई एल्गोरिदम चलाकर उच्च सफलता दर प्राप्त कर सकता है समय और अनुमान आउटपुट करना जो एल्गोरिदम के n/2 रन से अधिक आउटपुट है। (पिजनहोल सिद्धांत द्वारा ऐसे से अधिक अनुमान नहीं हो सकते हैं।) यह मानते हुए कि ये एल्गोरिदम रन स्वतंत्र हैं, n/2 से अधिक अनुमानों के सही होने की संभावना इस संभावना के समान है कि स्वतंत्र बर्नौली यादृच्छिक चर का योग Xk जो कि 1 है और प्रायिकता p, n/2 से अधिक है। ऐसा कम से कम करके तो दिखाया जा सकता है गुणक चेर्नॉफ़ बाउंड के माध्यम से (सिंक्लेयर के क्लास नोट्स में परिणाम 13.3, μ = np).[15]:


मैट्रिक्स चेर्नॉफ़ बाउंड

रूडोल्फ अहलस्वेड और एंड्रियास विंटर ने मैट्रिक्स-मूल्यवान यादृच्छिक चर के लिए चेर्नॉफ़ बाउंड प्रस्तुत किया।[16] असमानता का निम्नलिखित संस्करण ट्रॉप के काम में पाया जा सकता है।[17]

होने देना M1, ..., Mt स्वतंत्र मैट्रिक्स मान वाले यादृच्छिक चर बनें और . आइए हम इसे निरूपित करें मैट्रिक्स का ऑपरेटर मानदंड . यदि अधिकतर सभी के लिए निश्चित रूप से धारण करता है , फिर प्रत्येक के लिए ε > 0

ध्यान दें कि यह निष्कर्ष निकालने के लिए कि 0 से विचलन परिबद्ध है ε उच्च संभावना के साथ, हमें कई नमूने चुनने की आवश्यकता है के लघुगणक के समानुपाती . सामान्यतः, दुर्भाग्य से, पर निर्भरता अपरिहार्य है: उदाहरण के लिए आयाम का विकर्ण यादृच्छिक संकेत मैट्रिक्स लें . टी स्वतंत्र नमूनों के योग का ऑपरेटर मानदंड त्रुटिहीन रूप से लंबाई टी के डी स्वतंत्र यादृच्छिक वॉक के बीच अधिकतम विचलन है। निरंतर संभावना के साथ अधिकतम विचलन पर निश्चित सीमा प्राप्त करने के लिए, यह देखना आसान है कि इस परिदृश्य में t को d के साथ लघुगणकीय रूप से बढ़ना चाहिए।[18]

आयामों पर निर्भरता से बचने के लिए, यह मानकर निम्नलिखित प्रमेय प्राप्त किया जा सकता है कि एम की रैंक निम्न है।

आयामों पर निर्भरता के बिना प्रमेय

मान ले 0 < ε < 1 हो और M यादृच्छिक सममित वास्तविक मैट्रिक्स हो जिसके लिए और होता है अधिकतर निश्चितता के साथ, मान लें कि M के समर्थन में प्रत्येक तत्व मानक r से अधिकतम अवर्ध होता है। सेट करें

यदि अधिकतर निश्चितता के साथ माना जाता है, तो

यहाँ M1, ..., Mt की i.i.d. प्रतिलिपियाँ हैं।

नमूना संस्करण

चेर्नॉफ़ के बाउंड का निम्नलिखित संस्करण प्रयोग किया जा सकता है जो आवदेन परिभाषित करने के लिए उपयुक्त है, जिसमें जनसंख्या में बहुमत नमूने में अल्पसंख्यक बन जाएगा, या इसके विपरीत।[19]

मान लीजिये कि सामान्य जनसंख्या A है और उप-जनसंख्या B ⊆ A है। उप-जनसंख्या का सापेक्षिक आकार (|B|/|A|) को r से चिह्नित करता है।

मान लीजिए कि हम पूर्णांक k और यादृच्छिक नमूना S ⊂ A चुनते हैं, जिसका आकार k है। नमूने में उप-जनसंख्या का सापेक्षिक आकार (|BS|/|S|) को rS से चिह्नित करते है।

फिर, प्रत्येक भिन्न d ∈ [0,1] के लिए:

विशेष रूप से, यदि B A में बहुमत है (अर्थात् r > 0.5) तो हम निम्नलिखित लेकर बाउंड कर सकते हैं कि B S में अधिकांश रहेगा S(rS > 0.5):d = 1 − 1/(2r): [20]

यह बाउंड बिल्कुल त्रुटिहीन नहीं है। उदाहरण के लिए, जब r = 0.5 ता है, हमें साधारण बाउंड प्राप्त होता है: Prob > 0।

प्रमाण

गुणात्मक रूप

गुणक चेर्नॉफ़ बाउंड की शर्तों का पालन करते हुए, X1, ..., Xn स्वतंत्र बर्नौली यादृच्छिक चर है, जिसका योग X है, जहाँ प्रत्येक घटक को 1 होने की की प्रायिकता pi के समान होती है। बर्नौली चर के लिए:

इसलिए, (1) का उपयोग करते हुए, जहाँ और यहाँ है, और यहाँ है,

यदि हम t = log(1 + δ) सेट करें जिससे t > 0 हो (जब δ > 0 हो), तो हम स्थानापन्न सकते हैं और प्राप्त करते हैं

यह हमारी वांछित परिणाम को सिद्ध करता है।

चेर्नॉफ़-होफ़डिंग प्रमेय (योगात्मक रूप)

q = p + ε मानते हुए (1) में a = nq लेते हैं, हम प्राप्त करते हैं:

अब, Pr(Xi = 1) = p, Pr(Xi = 0) = 1 − p, होने के कारण हमें मिलता है

इसलिए, हम तुरंत त्रिगणित का उपयोग करके अन्तिम सीमा की गणना कर सकते हैं:

समीकरण को शून्य पर सेट करना और हल करना, हमारे पास है

जिससे

इस प्रकार,

q = p + ε > p, होने के कारण हम देखते हैं कि t > 0, इसलिए हमारा बाउंड t पर संतुष्ट होता है। t के लिए समीकरणों में वापस प्रविष्ट करने से हम पाते हैं: