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

From Vigyanwiki
(Created page with "{{Short description|Exponentially decreasing bounds on tail distributions of random variables}} संभाव्यता सिद्धांत में, एक चे...")
 
No edit summary
 
(10 intermediate revisions by 3 users not shown)
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 में हराल्ड क्रेमर ने अधिकतर इसी धारणा को प्रकाशित किया था, जिसे अब क्रेमर का सिद्धांत के नाम से जाना जाता है।


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


== जेनेरिक चेर्नॉफ़ सीमाएँ ==
== जेनेरिक चेर्नॉफ़ सीमाएँ ==
[[File:Chernoff-bound.svg|thumb|दो-तरफा चेर्नॉफ़ [[ची-वर्ग वितरण]]|ची-वर्ग यादृच्छिक चर के लिए बाध्य है]]जेनेरिक चेर्नॉफ़ एक यादृच्छिक चर के लिए बाध्य है <math>X</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>
और
और


:<math>\operatorname P \left(X \leq a\right) \leq \inf_{t < 0} M(t) e^{-t a}</math>
:<math>\operatorname P \left(X \leq a\right) \leq \inf_{t < 0} M(t) e^{-t a}</math>
मात्रा <math>M(t) e^{-t a}</math> अपेक्षा मूल्य के रूप में व्यक्त किया जा सकता है <math>\operatorname E (e^{t X}) e^{-t a}</math>, या समकक्ष <math>\operatorname E (e^{t (X-a)})</math>.
मात्रा <math>M(t) e^{-t a}</math> अपेक्षा मूल्य के रूप में व्यक्त किया जा सकता है <math>\operatorname E (e^{t X}) e^{-t a}</math>, या समकालिक रूप में लिखा जा सकता है <math>\operatorname E (e^{t (X-a)})</math>


=== गुण ===
=== गुण ===


घातांकीय फलन उत्तल है, इसलिए जेन्सेन की असमानता से <math>\operatorname E (e^{t X}) \ge e^{t \operatorname E (X)}</math>. इसका तात्पर्य यह है कि दाहिनी पूँछ पर बाउंड तुच्छ रूप से 1 के बराबर है <math>a \le \operatorname E (X)</math>; इसी प्रकार, बायीं सीमा भी तुच्छ है <math>a \ge \operatorname E (X)</math>. इसलिए हम दोनों इन्फिमा को जोड़ सकते हैं और दो-तरफा चेर्नॉफ़ बाउंड को परिभाषित कर सकते हैं:<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>इसलिए हम दोनों इंफोमा को संयोजित कर सकते हैं और दो-तरफी चेरनॉफ बाध्य को परिभाषित कर सकते हैं .<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 display="block">I(a) = \sup_{t} at - K(t) </math>
 
 


दो-तरफा चेर्नॉफ़ बाउंड के लघुगणक को [[दर समारोह]] (या क्रैमर ट्रांसफॉर्म) के रूप में जाना जाता है। <math>I = -\log C</math>. यह लेजेन्ड्रे-फेन्चेल ट्रांसफॉर्मेशन के समतुल्य है|लेजेन्ड्रे-फेन्चेल ट्रांसफॉर्म या [[संचयी जनरेटिंग फ़ंक्शन]] का [[उत्तल संयुग्म]] <math>K = \log M</math>, के रूप में परिभाषित: <math display="block">I(a) = \sup_{t} at - K(t) </math>मोमेंट-जेनरेटिंग_फंक्शन#महत्वपूर्ण_प्रॉपर्टीज लॉगरिदमिक रूप से उत्तल फ़ंक्शन|लॉग-उत्तल है, इसलिए उत्तल संयुग्म की एक संपत्ति के अनुसार, चेर्नॉफ बाउंड को लॉगरिदमिक रूप से अवतल फ़ंक्शन|लॉग-अवतल होना चाहिए। चेर्नॉफ़ सीमा माध्य पर अपनी अधिकतम सीमा प्राप्त कर लेती है, <math>C(\operatorname E(X))=1</math>, और अनुवाद के अंतर्गत अपरिवर्तनीय है: <math display="inline">C_{X+k}(a) = C_X(a - k) </math>.
यहां, मायने उत्पन्न करने के लिए कुम्युलेटिव उत्पन्न कारक फ़ंक्शन का लघुकरण अभिप्रेत है, इसलिए चेरनॉफ बाध्य लघुकरण होना चाहिए। चेरनॉफ बाध्य अपनी अधिकतम मान्यता आवश्यकता के समय प्राप्त करता है, <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>. असंबद्ध यादृच्छिक चर के लिए सीमा कहीं भी तंग नहीं है, हालांकि यह उप-घातीय कारकों (घातीय रूप से तंग) तक स्पर्शोन्मुख रूप से तंग है।{{Citation needed|date=February 2023}} व्यक्तिगत क्षण अधिक विश्लेषणात्मक जटिलता की कीमत पर, कड़ी सीमाएं प्रदान कर सकते हैं।<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>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"
|+Exact rate functions and Chernoff bounds for common distributions
|+सामान्य वितरण के लिए त्रुटिहीन दर फ़ंक्शन और चेर्नॉफ़ सीमाएं
!Distribution
!वितरण
!<math>\operatorname E (X)</math>
!<math>\operatorname E (X)</math>
!<math>K(t)</math>
!<math>K(t)</math>
Line 37: Line 46:
!<math>C(a)</math>
!<math>C(a)</math>
|-
|-
|[[Normal distribution]]  
|[[Normal distribution|सामान्य वितरण]]
|<math>0</math>
|<math>0</math>
|<math>\frac{1}{2}\sigma^2t^2</math>
|<math>\frac{1}{2}\sigma^2t^2</math>
Line 43: Line 52:
|<math>\exp \left( {-\frac{a^2}{2\sigma^2}} \right)</math>
|<math>\exp \left( {-\frac{a^2}{2\sigma^2}} \right)</math>
|-
|-
|[[Bernoulli distribution]](detailed below)
|[[Bernoulli distribution|बर्नौली वितरण]] (नीचे विस्तृत)
|<math>p</math>
|<math>p</math>
|<math>\ln \left( 1-p + pe^t \right)</math>
|<math>\ln \left( 1-p + pe^t \right)</math>
Line 49: Line 58:
|<math>\left (\frac{p}{a}\right )^{a} {\left (\frac{1 - p}{1-a}\right )}^{1 - a}</math>
|<math>\left (\frac{p}{a}\right )^{a} {\left (\frac{1 - p}{1-a}\right )}^{1 - a}</math>
|-
|-
|Standard Bernoulli
|मानक बर्नौली
(''H'' is the [[binary entropy function]])
(''H'' [[binary entropy function|बाइनरी एन्ट्रॉपी फ़ंक्शन है]])
|<math>\frac{1}{2}</math>
|<math>\frac{1}{2}</math>
|<math>\ln \left( 1 + e^t \right) - \ln(2)</math>
|<math>\ln \left( 1 + e^t \right) - \ln(2)</math>
Line 56: Line 65:
|<math>\frac{1}{2}a^{-a}(1-a)^{-(1-a)}</math>
|<math>\frac{1}{2}a^{-a}(1-a)^{-(1-a)}</math>
|-
|-
|[[Rademacher distribution]]
|[[Rademacher distribution|रेडमेकर वितरण]]
|<math>0</math>
|<math>0</math>
|<math>\ln \cosh(t)</math>
|<math>\ln \cosh(t)</math>
Line 62: Line 71:
|<math>\sqrt{(1+a)^{-1-a}(1-a)^{-1+a}}</math>
|<math>\sqrt{(1+a)^{-1-a}(1-a)^{-1+a}}</math>
|-
|-
|[[Gamma distribution]]
|[[Gamma distribution|गामा वितरण]]
|<math>\theta k</math>
|<math>\theta k</math>
|<math>-k\ln(1 - \theta t)</math>
|<math>-k\ln(1 - \theta t)</math>
Line 68: Line 77:
|<math>\left(\frac{a}{\theta k}\right)^k e^{k-a/\theta}</math>
|<math>\left(\frac{a}{\theta k}\right)^k e^{k-a/\theta}</math>
|-
|-
|[[Chi-squared distribution]]
|[[Chi-squared distribution|ची-वर्ग वितरण]]
|<math>k</math>
|<math>k</math>
|<math>-\frac{k}{2}\ln (1-2t)</math>
|<math>-\frac{k}{2}\ln (1-2t)</math>
Line 74: Line 83:
|<math>\left( \frac{a}{k} \right)^{k/2} e^{k/2-a/2} </math>
|<math>\left( \frac{a}{k} \right)^{k/2} e^{k/2-a/2} </math>
|-
|-
|[[Poisson distribution]]
|[[Poisson distribution|पोइसन वितरण]]
|<math>\lambda</math>
|<math>\lambda</math>
|<math>\lambda(e^t - 1)</math>
|<math>\lambda(e^t - 1)</math>
Line 80: Line 89:
|<math>(a/\lambda)^{-a} e^{a-\lambda}</math>
|<math>(a/\lambda)^{-a} e^{a-\lambda}</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>). हालाँकि, चेर्नॉफ़ बाउंड के विपरीत, यह परिणाम तेजी से तंग नहीं है।
मात्रात्मक उत्पन्न कारक का उपयोग करके, डेली-जयग्मंद असम्भवता को <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> ने बाध्य का निर्माण किया (जो अधिक) जैसे एक्सपोनेंशियल [[घातीय झुकाव]] प्रक्रिया का उपयोग करके ज्यादा सत्य होता है।


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


== स्वतंत्र यादृच्छिक चर का योग ==
== स्वतंत्र यादृच्छिक चर का योग ==
कब {{mvar|X}} का योग है {{mvar|n}} स्वतंत्र यादृच्छिक चर {{math|''X''<sub>1</sub>, ..., ''X<sub>n</sub>''}}, का क्षण उत्पन्न करने वाला कार्य {{mvar|X}} व्यक्तिगत क्षण उत्पन्न करने वाले कार्यों का उत्पाद है, जो यह देता है:
जब {{mvar|X}}, {{mvar|n}} अलग-अलग औपचारिक क्रमिक चरणिका {{math|''X''<sub>1</sub>, ..., ''X<sub>n</sub>''}}, के {{mvar|n}} निर्दिष्ट निर्देशांकों का योग होता है, तो {{mvar|X}} का उत्पन्न कारक उत्पन्नकों के व्यक्तिगत उत्पन्नकों के गुणक का होता है, जिससे प्राप्त होता है:


{{NumBlk|:|<math>\Pr(X \geq a) \leq \inf_{t > 0} \frac{\operatorname E \left [\prod_i e^{t\cdot X_i}\right]}{e^{t\cdot a}} = \inf_{t > 0} e^{-t\cdot a}\prod_i\operatorname E\left[ e^{t\cdot X_i}\right].</math>|{{EquationRef|1}}}}
{{NumBlk|:|<math>\Pr(X \geq a) \leq \inf_{t > 0} \frac{\operatorname E \left [\prod_i e^{t\cdot X_i}\right]}{e^{t\cdot a}} = \inf_{t > 0} e^{-t\cdot a}\prod_i\operatorname E\left[ e^{t\cdot X_i}\right].</math>|{{EquationRef|1}}}}
Line 99: Line 107:
विशिष्ट चेर्नॉफ़ सीमाएँ क्षण-उत्पन्न करने वाले फ़ंक्शन की गणना करके प्राप्त की जाती हैं <math>\operatorname E \left[e^{-t\cdot X_i} \right ]</math> यादृच्छिक चर के विशिष्ट उदाहरणों के लिए <math>X_i</math>.
विशिष्ट चेर्नॉफ़ सीमाएँ क्षण-उत्पन्न करने वाले फ़ंक्शन की गणना करके प्राप्त की जाती हैं <math>\operatorname E \left[e^{-t\cdot X_i} \right ]</math> यादृच्छिक चर के विशिष्ट उदाहरणों के लिए <math>X_i</math>.


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


== स्वतंत्र परिबद्ध यादृच्छिक चरों का योग ==
== स्वतंत्र परिबद्ध यादृच्छिक चरों का योग ==
{{main|Hoeffding's inequality}}
{{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>
::<math>\Pr (X \ge \mu+t) < e^{-2t^2/(n(b-a)^2)}.</math>
::<math>\Pr (X \ge \mu+t) < e^{-2t^2/(n(b-a)^2)}.</math>
== स्वतंत्र बर्नौली यादृच्छिक चर का योग ==
== स्वतंत्र बर्नौली यादृच्छिक चर का योग ==
बर्नौली यादृच्छिक चर के लिए निम्नलिखित अनुभागों में सीमाएं बर्नौली यादृच्छिक चर के लिए उपयोग करके प्राप्त की जाती हैं <math>X_i</math> 1 के बराबर होने की प्रायिकता p के साथ,
निम्न खंडों में दिए गए बर्नौली यादृच्छिक चरणिकाओं के लिए बाउंड, उस तथ्य का उपयोग करके निर्मित किए गए है कि बर्नौली यादृच्छिक चरणिका <math>X_i</math> के लिए, 1 होने की संभावना p होती है।


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


===गुणात्मक रूप (सापेक्ष त्रुटि)===
===गुणात्मक रूप (सापेक्ष त्रुटि)===
गुणक चेर्नॉफ़ बाध्य। कल्पना करना {{math|''X''<sub>1</sub>, ..., ''X<sub>n</sub>''}} सांख्यिकीय स्वतंत्रता यादृच्छिक चर हैं जो मान लेते हैं {{math|{0, 1}.}} होने देना {{mvar|X}} उनके योग को निरूपित करें और जाने दें {{math|''μ'' {{=}} E[''X'']}} योग के अपेक्षित मूल्य को निरूपित करें। फिर किसी के लिए {{math|''δ'' > 0}},
यदि {{math|''X''<sub>1</sub>, ..., ''X<sub>n</sub>''}} स्वतंत्र यादृच्छिक चरणिका हैं जो {{math|{0, 1}.}} मान लेते हैं, तो {{mvar|X}} को उनके योग का दर्शाता है औ {{math|''μ'' {{=}} E[''X'']}} योग की अपेक्षित मान दर्शाता है। तब किसी भी {{math|''δ'' > 0}} । के लिए,
:<math>\Pr ( X \ge (1+\delta)\mu) < \left(\frac{e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu.</math>
:<math>\Pr ( X \ge (1+\delta)\mu) < \left(\frac{e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu.</math>
यह दिखाने के लिए एक समान प्रमाण रणनीति का उपयोग किया जा सकता है {{math|0 < ''δ'' < 1}}
यह दिखाने के लिए समान प्रमाण रणनीति का उपयोग करके दिखाया जा सकता है कि {{math|0 < ''δ'' < 1}} के लिए,


:<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>
:<math>\Pr( X \le (1-\delta)\mu) \le e^{-\delta^2\mu/2}, \qquad 0 < \delta < 1,</math>
:<math>\Pr( X \le (1-\delta)\mu) \le e^{-\delta^2\mu/2}, \qquad 0 < \delta < 1,</math>
:<math>\Pr( |X - \mu| \ge \delta\mu) \le 2e^{-\delta^2\mu/3}, \qquad 0 < \delta < 1.</math>
:<math>\Pr( |X - \mu| \ge \delta\mu) \le 2e^{-\delta^2\mu/3}, \qquad 0 < \delta < 1.</math>
ध्यान दें कि सीमाएँ तुच्छ हैं <math>\delta = 0</math>.
ध्यान दें कि ये बाध्य जीर्ण होते हैं जब <math>\delta = 0</math>


=== योगात्मक रूप (पूर्ण त्रुटि) ===
=== योगात्मक रूप (पूर्ण त्रुटि) ===
निम्नलिखित प्रमेय [[वासिली होफ़डिंग]] के कारण है<ref>{{cite journal
निम्नलिखित प्रमाण [[वासिली होफ़डिंग]] के द्वारा है और इसलिए इसे चेरनॉफ-हेफोडिंग प्रमाण कहा जाता है।<ref>{{cite journal
  |last1=Hoeffding |first1=W.
  |last1=Hoeffding |first1=W.
  |year=1963
  |year=1963
Line 139: Line 145:
  |jstor=2282952
  |jstor=2282952
|url=http://repository.lib.ncsu.edu/bitstream/1840.4/2170/1/ISMS_1962_326.pdf
|url=http://repository.lib.ncsu.edu/bitstream/1840.4/2170/1/ISMS_1962_326.pdf
  }}</ref> और इसलिए इसे चेर्नॉफ़-होएफ़डिंग प्रमेय कहा जाता है।
  }}</ref>  


:चेर्नॉफ़-होफ़डिंग प्रमेय। कल्पना करना {{math|''X''<sub>1</sub>, ..., ''X<sub>n</sub>''}} आई.आई.डी. हैं यादृच्छिक चर, मान लेते हुए {{math|{0, 1}.}} होने देना {{math|''p'' {{=}} E[''X''<sub>1</sub>]}} और {{math|''ε'' > 0}}.
:चेरनॉफ-हेफोडिंग प्रमाण: मानें {{math|''X''<sub>1</sub>, ..., ''X<sub>n</sub>''}} i.i.d. यादृच्छिक चरणिका हैं, जो{{math|{0, 1}.}} मान लेते हैं। {{math|''p'' {{=}} E[''X''<sub>1</sub>]}} और {{math|''ε'' > 0}} हों।.
 
:<math>\begin{align}
::<math>\begin{align}
\Pr \left (\frac{1}{n} \sum X_i \geq p + \varepsilon \right ) \leq \left (\left (\frac{p}{p + \varepsilon}\right )^{p+\varepsilon} {\left (\frac{1 - p}{1-p- \varepsilon}\right )}^{1 - p- \varepsilon}\right )^n &= e^{-D(p+\varepsilon\parallel p) n} \\
\Pr \left (\frac{1}{n} \sum X_i \geq p + \varepsilon \right ) \leq \left (\left (\frac{p}{p + \varepsilon}\right )^{p+\varepsilon} {\left (\frac{1 - p}{1-p- \varepsilon}\right )}^{1 - p- \varepsilon}\right )^n &= e^{-D(p+\varepsilon\parallel p) n} \\
\Pr \left (\frac{1}{n} \sum X_i \leq p - \varepsilon \right ) \leq \left (\left (\frac{p}{p - \varepsilon}\right )^{p-\varepsilon} {\left (\frac{1 - p}{1-p+ \varepsilon}\right )}^{1 - p+ \varepsilon}\right )^n &= e^{-D(p-\varepsilon\parallel p) n}
\Pr \left (\frac{1}{n} \sum X_i \leq p - \varepsilon \right ) \leq \left (\left (\frac{p}{p - \varepsilon}\right )^{p-\varepsilon} {\left (\frac{1 - p}{1-p+ \varepsilon}\right )}^{1 - p+ \varepsilon}\right )^n &= e^{-D(p-\varepsilon\parallel p) n}
\end{align}</math>
\end{align}</math>जहाँ
:कहाँ
::<math> D(x\parallel y) = x \ln \frac{x}{y} + (1-x) \ln \left (\frac{1-x}{1-y} \right )</math>
::<math> D(x\parallel y) = x \ln \frac{x}{y} + (1-x) \ln \left (\frac{1-x}{1-y} \right )</math>
:क्रमशः पैरामीटर x और y के साथ [[बर्नौली वितरण]] यादृच्छिक चर के बीच कुल्बैक-लीबलर विचलन है। अगर {{math|''p'' ≥ {{sfrac|1|2}},}} तब <math>D(p+\varepsilon\parallel p)\ge \tfrac{\varepsilon^2}{2p(1-p)}</math> मतलब
:क्रमशः पैरामीटर x और y के साथ [[बर्नौली वितरण]] यादृच्छिक चर के बीच कुल्बैक-लीबलर विचलन है। यदि {{math|''p'' ≥ {{sfrac|1|2}},}} है, तो <math>D(p+\varepsilon\parallel p)\ge \tfrac{\varepsilon^2}{2p(1-p)}</math> है, जिसका अर्थ है


::<math> \Pr\left ( \frac{1}{n}\sum X_i>p+x \right ) \leq \exp \left (-\frac{x^2n}{2p(1-p)} \right ).</math>
::<math> \Pr\left ( \frac{1}{n}\sum X_i>p+x \right ) \leq \exp \left (-\frac{x^2n}{2p(1-p)} \right ).</math>
प्रमेय का उपयोग करके आराम करने से एक सरल बंधन बनता है {{math|''D''(''p'' + ''ε'' {{!!}} ''p'') ≥ 2''ε''<sup>2</sup>}}, जो के उत्तल फलन से अनुसरण करता है {{math|''D''(''p'' + ''ε'' {{!!}} ''p'')}} और तथ्य यह है कि
इसके साथ सुगम बाध्य {{math|''D''(''p'' + ''ε'' {{!!}} ''p'') ≥ 2''ε''<sup>2</sup>}}, का उपयोग करके, जो {{math|''D''(''p'' + ''ε'' {{!!}} ''p'')}} की उत्तलता और तथ्य के कारण से होता है


:<math>\frac{d^2}{d\varepsilon^2} D(p+\varepsilon\parallel p) = \frac{1}{(p+\varepsilon)(1-p-\varepsilon) } \geq 4 =\frac{d^2}{d\varepsilon^2}(2\varepsilon^2).</math>
:<math>\frac{d^2}{d\varepsilon^2} D(p+\varepsilon\parallel p) = \frac{1}{(p+\varepsilon)(1-p-\varepsilon) } \geq 4 =\frac{d^2}{d\varepsilon^2}(2\varepsilon^2).</math>
यह परिणाम होफ़डिंग की असमानता का एक विशेष मामला है। कभी-कभी, सीमा
यह परिणाम होफ़डिंग की असमानता का विशेष स्थिति है। कभी-कभी, बाउंड्स


:<math>
:<math>
Line 165: 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>
 
चेर्नॉफ़ बाध्य का उपयोग क्रमपरिवर्तन रूटिंग समस्याओं के लिए तंग बाध्य प्राप्त करने के लिए भी किया जाता है जो विरल नेटवर्क में पैकेट को रूट करते समय [[नेटवर्क संकुलन]] भीड़ को कम करता है।<ref name="0bAYl6d7hvkC" />


सांख्यिकीय प्रयोगों को डिज़ाइन करते समय सेट संतुलन की समस्या उत्पन्न होती है। आम तौर पर एक सांख्यिकीय प्रयोग को डिजाइन करते समय, प्रयोग में प्रत्येक भागीदार की विशेषताओं को देखते हुए, हमें यह जानना होगा कि प्रतिभागियों को 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>{{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="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 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>:
चेर्नॉफ़ बाध्य का सरल और सामान्य उपयोग [[यादृच्छिक एल्गोरिदम]] को बढ़ावा देने के लिए है। यदि किसी के पास एल्गोरिदम है जो अनुमान लगाता है कि संभावना p> 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>




== मैट्रिक्स चेर्नॉफ़ बाउंड ==
== आव्यूह चेर्नॉफ़ बाउंड ==
{{main|Matrix Chernoff bound}}
{{main|मैट्रिक्स चेर्नॉफ़ बाध्य}}


[[रूडोल्फ अहलस्वेड]] और [[एंड्रियास विंटर]] ने मैट्रिक्स-मूल्यवान यादृच्छिक चर के लिए एक चेर्नॉफ़ बाउंड पेश किया।<ref>{{cite journal
[[रूडोल्फ अहलस्वेड]] और [[एंड्रियास विंटर]] ने आव्यूह-मूल्यवान यादृच्छिक चर के लिए चेर्नॉफ़ बाध्य प्रस्तुत किया।<ref>{{cite journal
  |last1=Ahlswede |first1=R.
  |last1=Ahlswede |first1=R.
  |last2=Winter |first2=A.
  |last2=Winter |first2=A.
Line 207: Line 212:
|s2cid=17735965
|s2cid=17735965
  }}</ref>
  }}</ref>
होने देना {{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|''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>\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 स्वतंत्र यादृच्छिक वॉक के बीच अधिकतम विचलन है। निरंतर संभावना के साथ अधिकतम विचलन पर निश्चित बाध्य प्राप्त करने के लिए, यह देखना आसान है कि इस परिदृश्य में 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>
आयामों पर निर्भरता से बचने के लिए, यह मानकर निम्नलिखित प्रमेय प्राप्त किया जा सकता है कि एम की रैंक निम्न है।
 
आयामों पर निर्भरता से बचने के लिए, यह मानकर निम्नलिखित प्रमेय प्राप्त किया जा सकता है कि M की रैंक निम्न है।


===आयामों पर निर्भरता के बिना प्रमेय===
===आयामों पर निर्भरता के बिना प्रमेय===
होने देना {{math|0 < ''ε'' < 1}} और एम एक यादृच्छिक सममित वास्तविक मैट्रिक्स हो <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>
कहाँ {{math|''M''<sub>1</sub>, ..., ''M<sub>t</sub>''}} आई.आई.डी. हैं एम की प्रतियां
यहाँ {{math|''M''<sub>1</sub>, ..., ''M<sub>t</sub>''}} की i.i.d. प्रतिलिपियाँ हैं।


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


चेर्नॉफ़ की सीमा के निम्नलिखित संस्करण का उपयोग इस संभावना को सीमित करने के लिए किया जा सकता है कि किसी नमूने में आबादी का बहुमत अल्पसंख्यक बन जाएगा, या इसके विपरीत।<ref>{{Cite book | doi = 10.1007/3-540-44676-1_35| chapter = Competitive Auctions for Multiple Digital Goods| title = Algorithms — ESA 2001| volume = 2161| pages = 416| series = Lecture Notes in Computer Science| year = 2001| last1 = Goldberg | first1 = A. V. | last2 = Hartline | first2 = J. D. | isbn = 978-3-540-42493-2| citeseerx = 10.1.1.8.5115}}; lemma 6.1</ref>
चेर्नॉफ़ के बाध्य का निम्नलिखित संस्करण प्रयोग किया जा सकता है जो आवदेन परिभाषित करने के लिए उपयुक्त है, जिसमें जनसंख्या में बहुमत नमूने में अल्पसंख्यक बन जाएगा, या इसके विपरीत हो जाता है। ।<ref>{{Cite book | doi = 10.1007/3-540-44676-1_35| chapter = Competitive Auctions for Multiple Digital Goods| title = Algorithms — ESA 2001| volume = 2161| pages = 416| series = Lecture Notes in Computer Science| year = 2001| last1 = Goldberg | first1 = A. V. | last2 = Hartline | first2 = J. D. | isbn = 978-3-540-42493-2| citeseerx = 10.1.1.8.5115}}; lemma 6.1</ref>
मान लीजिए कि एक सामान्य जनसंख्या A और एक उप-जनसंख्या B ⊆ A है। उप-जनसंख्या के सापेक्ष आकार (|B|/|A|) को r से चिह्नित करें।


मान लीजिए कि हम एक पूर्णांक k और आकार k का एक यादृच्छिक नमूना S ⊂ A चुनते हैं। नमूने में उप-जनसंख्या के सापेक्ष आकार को r द्वारा चिह्नित करें (|B∩S|/|S|)<sub>S</sub>.
मान लीजिये कि सामान्य जनसंख्या A है और उप-जनसंख्या B ⊆ A है। उप-जनसंख्या का सापेक्षिक आकार (|''B''|/|''A''|) को r से चिह्नित करता है।
 
मान लीजिए कि हम पूर्णांक k और यादृच्छिक नमूना S ⊂ A चुनते हैं, जिसका आकार k है। नमूने में उप-जनसंख्या का सापेक्षिक आकार (|''B''∩''S''|/|''S''|) को ''r<sub>S</sub>'' से चिह्नित करते है।


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


:<math>\Pr\left(r_S < (1-d)\cdot r\right) < \exp\left(-r\cdot d^2 \cdot \frac k 2\right)</math>
:<math>\Pr\left(r_S < (1-d)\cdot r\right) < \exp\left(-r\cdot d^2 \cdot \frac k 2\right)</math>
विशेष रूप से, यदि बी ए में बहुमत है (यानी आर > 0.5) तो हम इस संभावना को सीमित कर सकते हैं कि बी एस (आर) में बहुमत रहेगा<sub>S</sub>> 0.5) लेकर: d = 1 − 1/(2r):<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 हमें एक तुच्छ बाध्य संभावना > 0 मिलती है।
यह बाध्य बिल्कुल त्रुटिहीन नहीं है। उदाहरण के लिए, जब r = 0.5 ता है, हमें साधारण बाध्य प्राप्त होता है: Prob > 0।


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


===गुणात्मक रूप===
===गुणात्मक रूप===
गुणक चेर्नॉफ़ बाउंड की शर्तों का पालन करते हुए, आइए {{math|''X''<sub>1</sub>, ..., ''X<sub>n</sub>''}} स्वतंत्र बर्नौली यादृच्छिक चर हो, जिसका योग है {{math|''X''}}, प्रत्येक की प्रायिकता p है<sub>i</sub>1 के बराबर होना। बर्नौली चर के लिए:
गुणक चेर्नॉफ़ बाध्य की शर्तों का पालन करते हुए, {{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>
तो, (का उपयोग करते हुए){{EquationNote|1}}) साथ <math>a = (1+\delta)\mu</math> किसी के लिए <math>\delta>0</math> और कहाँ <math>\mu = \operatorname E[X] = \textstyle\sum_{i=1}^n p_i</math>,
इसलिए, ({{EquationNote|1}}) का उपयोग करते हुए, जहाँ <math>a = (1+\delta)\mu</math> और यहाँ <math>\delta>0</math> है, और यहाँ<math>\mu = \operatorname E[X] = \textstyle\sum_{i=1}^n p_i</math> है,


:<math>\begin{align}
:<math>\begin{align}
Line 249: 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>
इससे वांछित परिणाम सिद्ध होता है।
यह हमारी वांछित परिणाम को सिद्ध करता है।


===चेर्नॉफ़-होफ़डिंग प्रमेय (योगात्मक रूप)===
===चेर्नॉफ़-होफ़डिंग प्रमेय (योगात्मक रूप)===
होने देना {{math|''q'' {{=}} ''p'' + ''ε''}}. ले रहा {{math|''a'' {{=}} ''nq''}} में ({{EquationNote|1}}), हमने प्राप्त:
{{math|''q'' {{=}} ''p'' + ''ε''}} मानते हुए ({{EquationNote|1}}) में {{math|''a'' {{=}} ''nq''}} लेते हैं, हम प्राप्त करते हैं:


:<math>\Pr\left ( \frac{1}{n} \sum X_i \ge q\right )\le \inf_{t>0} \frac{E \left[\prod e^{t X_i}\right]}{e^{tnq}} = \inf_{t>0} \left ( \frac{ E\left[e^{tX_i} \right] }{e^{tq}}\right )^n.</math>
:<math>\Pr\left ( \frac{1}{n} \sum X_i \ge q\right )\le \inf_{t>0} \frac{E \left[\prod e^{t X_i}\right]}{e^{tnq}} = \inf_{t>0} \left ( \frac{ E\left[e^{tX_i} \right] }{e^{tq}}\right )^n.</math>
अब, यह जानना {{math|Pr(''X<sub>i</sub>'' {{=}} 1) {{=}} ''p'', Pr(''X<sub>i</sub>'' {{=}} 0) {{=}} 1 − ''p''}}, अपने पास
अब, {{math|Pr(''X<sub>i</sub>'' {{=}} 1) {{=}} ''p'', Pr(''X<sub>i</sub>'' {{=}} 0) {{=}} 1 − ''p''}}, होने के कारण हमें मिलता है


:<math>\left (\frac{\operatorname E\left[e^{tX_i} \right] }{e^{tq}}\right )^n = \left (\frac{p e^t + (1-p)}{e^{tq} }\right )^n = \left ( pe^{(1-q)t} + (1-p)e^{-qt} \right )^n.</math>
:<math>\left (\frac{\operatorname E\left[e^{tX_i} \right] }{e^{tq}}\right )^n = \left (\frac{p e^t + (1-p)}{e^{tq} }\right )^n = \left ( pe^{(1-q)t} + (1-p)e^{-qt} \right )^n.</math>
इसलिए, हम कैलकुलस का उपयोग करके आसानी से अनंत की गणना कर सकते हैं:
इसलिए, हम तुरंत त्रिगणित का उपयोग करके अन्तिम बाध्य की गणना कर सकते हैं:


:<math>\frac{d}{dt} \left (pe^{(1-q)t} + (1-p)e^{-qt} \right) = (1-q)pe^{(1-q)t}-q(1-p)e^{-qt}</math>
:<math>\frac{d}{dt} \left (pe^{(1-q)t} + (1-p)e^{-qt} \right) = (1-q)pe^{(1-q)t}-q(1-p)e^{-qt}</math>
Line 270: 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 276: Line 283:


:<math>t = \log\left(\frac{(1-p)q}{(1-q)p}\right).</math>
:<math>t = \log\left(\frac{(1-p)q}{(1-q)p}\right).</math>
जैसा {{math|''q'' {{=}} ''p'' + ''ε'' > ''p''}}, हमने देखा कि {{math|''t'' > 0}}, इसलिए हमारी सीमा संतुष्ट है {{mvar|t}}. के लिए हल किया जा रहा है {{mvar|t}}, हम इसे खोजने के लिए उपरोक्त समीकरणों को वापस जोड़ सकते हैं
{{math|''q'' {{=}} ''p'' + ''ε'' > ''p''}}, होने के कारण हम देखते हैं कि {{math|''t'' > 0}}, इसलिए हमारा बाध्य {{mvar|t}} पर संतुष्ट होता है। {{mvar|t}} के लिए समीकरणों में वापस प्रविष्ट करने से हम पाते हैं:


:<math>\begin{align}
:<math>\begin{align}
Line 287: 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>''}} को परिभाषित करते हैं , वही समान प्रमाण का उपयोग करते हैं, और हमारे बाध्य में इसे प्लगइन करते हैं।


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


* बर्नस्टीन असमानताएँ (संभावना सिद्धांत)
* बर्नस्टीन असमानताएँ (संभावना सिद्धांत)
*[[एकाग्रता असमानता]] - यादृच्छिक चर पर टेल-बाउंड का सारांश।
*[[एकाग्रता असमानता]] - यादृच्छिक चर पर टेल-बाध्य का सारांश।
*क्रैमर प्रमेय (बड़े विचलन)|क्रैमर प्रमेय
*क्रैमर प्रमेय (बड़े विचलन) क्रैमर प्रमेय
*एंट्रोपिक मूल्य खतरे में है
*एंट्रोपिक मूल्य खतरे में है
* होफ़डिंग की असमानता
* होफ़डिंग की असमानता
*[[मैट्रिक्स चेर्नॉफ़ बाध्य]]
*[[मैट्रिक्स चेर्नॉफ़ बाध्य|आव्यूह चेर्नॉफ़ बाध्य]]
*क्षण उत्पन्न करने वाला कार्य
*क्षण उत्पन्न करने वाला कार्य


Line 353: Line 360:
  }}
  }}


{{DEFAULTSORT:Chernoff Bound}}[[Category: संभाव्य असमानताएँ]]
{{DEFAULTSORT:Chernoff Bound}}
 
 


[[Category: Machine Translated Page]]
[[Category:Articles with hatnote templates targeting a nonexistent page|Chernoff Bound]]
[[Category:Created On 08/07/2023]]
[[Category:CS1 English-language sources (en)]]
[[Category:Created On 08/07/2023|Chernoff Bound]]
[[Category:Lua-based templates|Chernoff Bound]]
[[Category:Machine Translated Page|Chernoff Bound]]
[[Category:Pages with maths render errors|Chernoff Bound]]
[[Category:Pages with script errors|Chernoff Bound]]
[[Category:Templates Vigyan Ready|Chernoff Bound]]
[[Category:Templates that add a tracking category|Chernoff Bound]]
[[Category:Templates that generate short descriptions|Chernoff Bound]]
[[Category:Templates using TemplateData|Chernoff Bound]]
[[Category:संभाव्य असमानताएँ|Chernoff Bound]]

Latest revision as of 12:15, 26 July 2023

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

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

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

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

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

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

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

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

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

और

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

गुण

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

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

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


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

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

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


आव्यूह चेर्नॉफ़ बाउंड

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

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

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

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

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

मान ले 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 के लिए समीकरणों में वापस प्रविष्ट करने से हम पाते हैं: