View source for चेर्नॉफ़ बाध्य

{{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>

इस बाध्य को सामान्यतः [[हरमन चेर्नॉफ़]] के नाम पर जाना जाता है, जिन्होंने 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>:

<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>\operatorname P \left(X \geq a\right) \leq \inf_{t > 0} M(t) e^{-t a}</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) \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>\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>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"
|+सामान्य वितरण के लिए त्रुटिहीन दर फ़ंक्शन और चेर्नॉफ़ सीमाएं
!वितरण
!<math>\operatorname E (X)</math>
!<math>K(t)</math>
!<math>I(a)</math>
!<math>C(a)</math>
|-
|[[Normal distribution|सामान्य वितरण]]
|<math>0</math>
|<math>\frac{1}{2}\sigma^2t^2</math>
|<math>\frac{1}{2} \left( \frac{a}{\sigma} \right)^2</math>
|<math>\exp \left( {-\frac{a^2}{2\sigma^2}} \right)</math>
|-
|[[Bernoulli distribution|बर्नौली वितरण]] (नीचे विस्तृत)
|<math>p</math>
|<math>\ln \left( 1-p + pe^t \right)</math>
|<math>D_{KL}(a \parallel p)</math>
|<math>\left (\frac{p}{a}\right )^{a} {\left (\frac{1 - p}{1-a}\right )}^{1 - a}</math>
|-
|मानक बर्नौली 
(''H'' [[binary entropy function|बाइनरी एन्ट्रॉपी फ़ंक्शन है]])
|<math>\frac{1}{2}</math>
|<math>\ln \left( 1 + e^t \right) - \ln(2)</math>
|<math>\ln(2) - H(a)</math>
|<math>\frac{1}{2}a^{-a}(1-a)^{-(1-a)}</math>
|-
|[[Rademacher distribution|रेडमेकर वितरण]]
|<math>0</math>
|<math>\ln \cosh(t)</math>
|<math>\ln(2) - H\left(\frac{1+a}{2}\right)</math>
|<math>\sqrt{(1+a)^{-1-a}(1-a)^{-1+a}}</math>
|-
|[[Gamma distribution|गामा वितरण]]
|<math>\theta k</math>
|<math>-k\ln(1 - \theta t)</math>
|<math>-k\ln\frac{a}{\theta k} -k + \frac{a}{\theta} </math>
|<math>\left(\frac{a}{\theta k}\right)^k e^{k-a/\theta}</math>
|-
|[[Chi-squared distribution|ची-वर्ग वितरण]]
|<math>k</math>
|<math>-\frac{k}{2}\ln (1-2t)</math>
|<math>\frac{k}{2} \left(\frac{a}{k} - 1 - \ln \frac{a}{k} \right)</math><ref>{{Cite journal |last=Ghosh |first=Malay |date=2021-03-04 |title=Exponential Tail Bounds for Chisquared Random Variables |url=https://doi.org/10.1007/s42519-020-00156-x |journal=Journal of Statistical Theory and Practice |language=en |volume=15 |issue=2 |pages=35 |doi=10.1007/s42519-020-00156-x |issn=1559-8616}}</ref>
|<math>\left( \frac{a}{k} \right)^{k/2} e^{k/2-a/2} </math>
|-
|[[Poisson distribution|पोइसन वितरण]]
|<math>\lambda</math>
|<math>\lambda(e^t - 1)</math>
|<math>a \ln (a/\lambda) - 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> के लिए बाईं पूंछ पर बाध्य प्राप्त किया जाता है) चूँकि, चेर्नॉफ़ बाध्य के विपरीत, यह परिणाम तेजी से तंग नहीं है।

थियोडोसोपोलोस<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|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}}}}

और:

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

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

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

चेर्नॉफ़ सीमाएं उनके वितरण की परवाह किए बिना, स्वतंत्र, बंधे हुए यादृच्छिक चर के सामान्य योगों पर भी लागू की जा सकती हैं; इसे होफ़डिंग की असमानता के रूप में जाना जाता है। प्रमाण अन्य चेरनॉफ़ सीमाओं के समान दृष्टिकोण का अनुसरण करता है, किन्तु क्षण उत्पन्न करने वाले कार्यों को बाध्य करने के लिए होएफ़डिंग की लेम्मा को लागू करता है (होएफ़डिंग की असम्भवता देखें)।
:हेफ़ोडिंग की असम्भवता: मानें {{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 \ge \mu+t) < e^{-2t^2/(n(b-a)^2)}.</math>
== स्वतंत्र बर्नौली यादृच्छिक चर का योग ==
निम्न खंडों में दिए गए बर्नौली यादृच्छिक चरणिकाओं के लिए बाउंड, उस तथ्य का उपयोग करके निर्मित किए गए है कि बर्नौली यादृच्छिक चरणिका <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|''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|0 < ''δ'' < 1}} के लिए,

:<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> का पालन करते हैं:

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

=== योगात्मक रूप (पूर्ण त्रुटि) ===
निम्नलिखित प्रमाण [[वासिली होफ़डिंग]] के द्वारा है और इसलिए इसे चेरनॉफ-हेफोडिंग प्रमाण कहा जाता है।<ref>{{cite journal
 |last1=Hoeffding |first1=W.
 |year=1963
 |title=Probability Inequalities for Sums of Bounded Random Variables
 |journal=[[Journal of the American Statistical Association]]
 |volume=58 |issue=301 |pages=13–30
 |doi=10.2307/2282952
 |jstor=2282952
|url=http://repository.lib.ncsu.edu/bitstream/1840.4/2170/1/ISMS_1962_326.pdf
 }}</ref> 

:चेरनॉफ-हेफोडिंग प्रमाण: मानें {{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}
\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}
\end{align}</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> है, जिसका अर्थ है

::<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>\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>
\begin{align}
D( (1+x) p \parallel p) \geq \frac{1}{4} x^2 p, & & & {-\tfrac{1}{2}} \leq x \leq \tfrac{1}{2},\\[6pt]
D(x \parallel y) \geq \frac{3(x-y)^2}{2(2y+x)}, \\[6pt]
D(x \parallel y) \geq \frac{(x-y)^2}{2y}, & & & x \leq y,\\[6pt]
D(x \parallel y) \geq \frac{(x-y)^2}{2x}, & & & x \geq y
\end{align}
</math>
जो {{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" />

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

चेर्नॉफ़ बाध्य का सरल और सामान्य उपयोग [[यादृच्छिक एल्गोरिदम]] को बढ़ावा देने के लिए है। यदि किसी के पास एल्गोरिदम है जो अनुमान लगाता है कि संभावना 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>


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

[[रूडोल्फ अहलस्वेड]] और [[एंड्रियास विंटर]] ने आव्यूह-मूल्यवान यादृच्छिक चर के लिए चेर्नॉफ़ बाध्य प्रस्तुत किया।<ref>{{cite journal
 |last1=Ahlswede |first1=R.
 |last2=Winter |first2=A.
 |year=2003
 |title=Strong Converse for Identification via Quantum Channels
 |volume=48 |issue=3 |pages=569–579
 |journal=[[IEEE Transactions on Information Theory]]
 |arxiv=quant-ph/0012127
 |doi=10.1109/18.985947
|s2cid=523176
 }}</ref> असमानता का निम्नलिखित संस्करण ट्रॉप के काम में पाया जा सकता है।<ref>{{cite journal
 |last1=Tropp |first1=J.
 |year=2010
 |title=User-friendly tail bounds for sums of random matrices
 |arxiv=1004.4389
 |doi=10.1007/s10208-011-9099-z
 |volume=12
 |issue=4
 |journal=Foundations of Computational Mathematics
 |pages=389–434
|s2cid=17735965
 }}</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>\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 स्वतंत्र यादृच्छिक वॉक के बीच अधिकतम विचलन है। निरंतर संभावना के साथ अधिकतम विचलन पर निश्चित बाध्य प्राप्त करने के लिए, यह देखना आसान है कि इस परिदृश्य में 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}} हो और 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> 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|''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>

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

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

फिर, प्रत्येक भिन्न 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>
विशेष रूप से, यदि 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>
यह बाध्य बिल्कुल त्रुटिहीन नहीं है। उदाहरण के लिए, जब r = 0.5 ता है, हमें साधारण बाध्य प्राप्त होता है: Prob > 0।

==प्रमाण==

===गुणात्मक रूप===
गुणक चेर्नॉफ़ बाध्य की शर्तों का पालन करते हुए, {{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>
इसलिए, ({{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}
\Pr (X > (1 + \delta)\mu) &\le \inf_{t \geq 0} \exp(-t(1+\delta)\mu)\prod_{i=1}^n\operatorname{E}[\exp(tX_i)]\\[4pt]
& \leq \inf_{t \geq 0} \exp\Big(-t(1+\delta)\mu + \sum_{i=1}^n p_i(e^t - 1)\Big) \\[4pt]
& = \inf_{t \geq 0} \exp\Big(-t(1+\delta)\mu + (e^t - 1)\mu\Big).
\end{align}</math>
यदि हम {{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|''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(''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>\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>\begin{align}
(1-q)pe^{(1-q)t} &= q(1-p)e^{-qt} \\
(1-q)pe^{t} &= q(1-p)
\end{align}</math>
जिससे

:<math>e^t = \frac{(1-p)q}{(1-q)p}.</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>\begin{align}
\log \left (pe^{(1-q)t} + (1-p)e^{-qt} \right ) &= \log \left ( e^{-qt}(1-p+pe^t) \right ) \\
&= \log\left (e^{-q \log\left(\frac{(1-p)q}{(1-q)p}\right)}\right) + \log\left(1-p+pe^{\log\left(\frac{1-p}{1-q}\right)}e^{\log\frac{q}{p}}\right ) \\
&= -q\log\frac{1-p}{1-q} -q \log\frac{q}{p} + \log\left(1-p+ p\left(\frac{1-p}{1-q}\right)\frac{q}{p}\right) \\
&= -q\log\frac{1-p}{1-q} -q \log\frac{q}{p} + \log\left(\frac{(1-p)(1-q)}{1-q}+\frac{(1-p)q}{1-q}\right) \\
&= -q \log\frac{q}{p} + \left ( -q\log\frac{1-p}{1-q} + \log\frac{1-p}{1-q} \right ) \\
&= -q\log\frac{q}{p} + (1-q)\log\frac{1-p}{1-q} \\
&= -D(q \parallel p).
\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|''Y<sub>i</sub>'' {{=}} 1 − ''X<sub>i</sub>''}} को परिभाषित करते हैं , वही समान प्रमाण का उपयोग करते हैं, और हमारे बाध्य में इसे प्लगइन करते हैं।

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

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

== संदर्भ ==
{{Reflist}}


==अग्रिम पठन==
* {{cite journal
 |last1=Chernoff |first1=H.
 |year=1952
 |title=A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
 |journal=[[Annals of Mathematical Statistics]]
 |volume=23 |issue=4 |pages=493&ndash;507
 |doi=10.1214/aoms/1177729330
 |jstor=2236576
 |mr=57518
 |zbl=0048.11804
|doi-access=free
 }}
* {{cite journal
 |last1=Chernoff |first1=H.
 |year=1981
 |title=A Note on an Inequality Involving the Normal Distribution
 |journal=[[Annals of Probability]]
 |volume=9 |issue=3 |pages=533–535
 |doi=10.1214/aop/1176994428
 |jstor=2243541
 |mr=614640
 |zbl=0457.60014
|doi-access=free
 }}
* {{cite journal
 |last1=Hagerup |first1=T.
 |last2=Rüb |first2=C.
 |year=1990
 |title=A guided tour of Chernoff bounds
 |journal=[[Information Processing Letters]]
 |volume=33 |issue=6 |pages=305
 |doi=10.1016/0020-0190(90)90214-I
}}
* {{cite journal
 |last=Nielsen |first=F.
 |year=2011
 |title=An Information-Geometric Characterization of Chernoff Information
 |journal=IEEE Signal Processing Letters
 |volume=20
 |issue=3
 |pages=269–272
 |doi=10.1109/LSP.2013.2243726
 |arxiv=1102.2684
|s2cid=15034953
 }}

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



[[Category: Machine Translated Page]]
[[Category:Created On 08/07/2023]]