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

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

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

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

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

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

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

यादृच्छिक प्रतिसमिष्ट के लिए जनेरिक चेरनॉफ बाउंड को लागू करने के लिए, मार्कोव की असम्भवता को उपयोग करते हुए यह बाउंड मिलता है, इसे आवश्यकतानुसार एक्सपोनेंशियल मार्कोव या एक्सपोनेंशियल मोमेंट्स बाउंड भी कहा जाता है। इसके लिए, धनात्मक $t$ के लिए हम $e^{tX}$ का बाउंड प्राप्त करते हैं (इसी कारण इसे कभी-कभी एक्सपोनेंशियल मार्कोव या एक्सपोनेंशियल मोमेंट्स बाउंड कहा जाता है)। इस बाउंड के लिए, यदि $t$ धनात्मक है, तो यह बाउंड देता है $X$ के दायां खंभे की ओर की सीमा, जिसे मायने के रूप में उसके मोमेंट-उत्पन्न कारक के साथ लिखा जा सकता है $M(t)=\operatorname {E} (e^{tX})$:

$\operatorname {P} \left(X\geq a\right)=\operatorname {P} \left(e^{tX}\geq e^{ta}\right)\leq M(t)e^{-ta}\qquad (t>0)$

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

$\operatorname {P} \left(X\geq a\right)\leq \inf _{t>0}M(t)e^{-ta}$

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

$\operatorname {P} \left(X\leq a\right)=\operatorname {P} \left(e^{tX}\geq e^{ta}\right)\leq M(t)e^{-ta}\qquad (t<0)$

और

$\operatorname {P} \left(X\leq a\right)\leq \inf _{t<0}M(t)e^{-ta}$

मात्रा $M(t)e^{-ta}$ अपेक्षा मूल्य के रूप में व्यक्त किया जा सकता है $\operatorname {E} (e^{tX})e^{-ta}$, या समकालिक रूप में लिखा जा सकता है $\operatorname {E} (e^{t(X-a)})$।

गुण

घाती संख्या के लिए तार्किक समान लिया जा सकता है क्योंकि एक्सपोनेंशियल फ़ंक्शन अभिप्रेत है, इसलिए जेनसेन की असम्भाविता के अनुसार $\operatorname {E} (e^{tX})\geq e^{t\operatorname {E} (X)}$होता है। इससे यह प्राप्त होता है कि दायां खंभे की सीमा अवश्य हैं होता है जब $a\leq \operatorname {E} (X)$; उसी प्रकार, बाएं खंभे के लिए बाउंड उचित होता है जब $a\geq \operatorname {E} (X)$। इसलिए हम दोनों infima को संयोजित कर सकते हैं और दो-तरफी चेरनॉफ बाउंड को परिभाषित कर सकते हैं .

$$C(a)=\inf _{t}M(t)e^{-ta}$$

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

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

$$I(a)=\sup _{t}at-K(t)$$

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

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

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

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

वितरण	$\operatorname {E} (X)$	$K(t)$	$I(a)$	$C(a)$
सामान्य वितरण	$0$	${\frac {1}{2}}\sigma ^{2}t^{2}$	${\frac {1}{2}}\left({\frac {a}{\sigma }}\right)^{2}$	$\exp \left({-{\frac {a^{2}}{2\sigma ^{2}}}}\right)$
बर्नौली वितरण (नीचे विस्तृत)	$p$	$\ln \left(1-p+pe^{t}\right)$	$D_{KL}(a\parallel p)$	$\left({\frac {p}{a}}\right)^{a}{\left({\frac {1-p}{1-a}}\right)}^{1-a}$
मानक बर्नौली (H बाइनरी एन्ट्रॉपी फ़ंक्शन है)	${\frac {1}{2}}$	$\ln \left(1+e^{t}\right)-\ln(2)$	$\ln(2)-H(a)$	${\frac {1}{2}}a^{-a}(1-a)^{-(1-a)}$
रेडमेकर वितरण	$0$	$\ln \cosh(t)$	$\ln(2)-H\left({\frac {1+a}{2}}\right)$	${\sqrt {(1+a)^{-1-a}(1-a)^{-1+a}}}$
गामा वितरण	$\theta k$	$-k\ln(1-\theta t)$	$-k\ln {\frac {a}{\theta k}}-k+{\frac {a}{\theta }}$	$\left({\frac {a}{\theta k}}\right)^{k}e^{k-a/\theta }$
ची-वर्ग वितरण	$k$	$-{\frac {k}{2}}\ln(1-2t)$	${\frac {k}{2}}\left({\frac {a}{k}}-1-\ln {\frac {a}{k}}\right)$	$\left({\frac {a}{k}}\right)^{k/2}e^{k/2-a/2}$
पोइसन वितरण	$\lambda$	$\lambda (e^{t}-1)$	$a\ln(a/\lambda )-a+\lambda$	$(a/\lambda )^{-a}e^{a-\lambda }$

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

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

$$\operatorname {P} \left(X>a\right)\geq \sup _{t>0\land M(t)\geq e^{ta}}\left(1-{\frac {e^{ta}}{M(t)}}\right)^{2}{\frac {M(t)^{2}}{M(2t)}}$$

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

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

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

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

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

$\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].$

(1)

और:

$\Pr(X\leq a)\leq \inf _{t<0}e^{-ta}\prod _{i}\operatorname {E} \left[e^{tX_{i}}\right]$

विशिष्ट चेर्नॉफ़ सीमाएँ क्षण-उत्पन्न करने वाले फ़ंक्शन की गणना करके प्राप्त की जाती हैं $\operatorname {E} \left[e^{-t\cdot X_{i}}\right]$ यादृच्छिक चर के विशिष्ट उदाहरणों के लिए $X_{i}$.

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

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

Main article: होफ़डिंग की असमानता

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

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

$\Pr(X\leq \mu -t)<e^{-2t^{2}/(n(b-a)^{2})},$

$\Pr(X\geq \mu +t)<e^{-2t^{2}/(n(b-a)^{2})}.$

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

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

$\operatorname {E} \left[e^{t\cdot X_{i}}\right]=(1-p)e^{0}+pe^{t}=1+p(e^{t}-1)\leq e^{p(e^{t}-1)}.$

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

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

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

$\Pr(X\geq (1+\delta )\mu )<\left({\frac {e^{\delta }}{(1+\delta )^{1+\delta }}}\right)^{\mu }.$

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

$\Pr(X\leq (1-\delta )\mu )<\left({\frac {e^{-\delta }}{(1-\delta )^{1-\delta }}}\right)^{\mu }.$

उपरोक्त सूत्र अधिकांशतः अव्यवस्थित होता है, इसलिए आधारभूत किन्तु अधिक सुविधाजनक बाउंड उपयोग किए जाते हैं, जो लॉगरिद्धि समानताओं की सूची से अवधारित असमानता $\textstyle {\frac {2\delta }{2+\delta }}\leq \log(1+\delta )$ का पालन करते हैं:

$\Pr(X\geq (1+\delta )\mu )\leq e^{-\delta ^{2}\mu /(2+\delta )},\qquad 0\leq \delta ,$

$\Pr(X\leq (1-\delta )\mu )\leq e^{-\delta ^{2}\mu /2},\qquad 0<\delta <1,$

$\Pr(|X-\mu |\geq \delta \mu )\leq 2e^{-\delta ^{2}\mu /3},\qquad 0<\delta <1.$

ध्यान दें कि ये बाउंड जीर्ण होते हैं जब $\delta =0$।

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

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

चेरनॉफ-हेफोडिंग प्रमाण: मानें X₁, ..., X_n i.i.d. यादृच्छिक चरणिका हैं, जो{0, 1}. मान लेते हैं। p = E[X₁] और ε > 0 हों।.

${\begin{aligned}\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{aligned}}$जहाँ

$D(x\parallel y)=x\ln {\frac {x}{y}}+(1-x)\ln \left({\frac {1-x}{1-y}}\right)$

क्रमशः पैरामीटर x और y के साथ बर्नौली वितरण यादृच्छिक चर के बीच कुल्बैक-लीबलर विचलन है। यदि p ≥ 1/2, है, तो $D(p+\varepsilon \parallel p)\geq {\tfrac {\varepsilon ^{2}}{2p(1-p)}}$ है, जिसका अर्थ है

$\Pr \left({\frac {1}{n}}\sum X_{i}>p+x\right)\leq \exp \left(-{\frac {x^{2}n}{2p(1-p)}}\right).$

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

${\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}).$

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

${\begin{aligned}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{aligned}}$

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

अनुप्रयोग

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

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

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

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

$\Pr \left[X>{n \over 2}\right]\geq 1-e^{-n\left(p-1/2\right)^{2}/(2p)}\geq 1-\delta$

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

Main article: मैट्रिक्स चेर्नॉफ़ बाध्य

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

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

$\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).$

ध्यान दें कि यह निष्कर्ष निकालने के लिए कि 0 से विचलन परिबद्ध है ε उच्च संभावना के साथ, हमें कई नमूने चुनने की आवश्यकता है $t$ के लघुगणक के समानुपाती $d_{1}+d_{2}$. सामान्यतः, दुर्भाग्य से, पर निर्भरता $\log(\min(d_{1},d_{2}))$ अपरिहार्य है: उदाहरण के लिए आयाम का विकर्ण यादृच्छिक संकेत मैट्रिक्स लें $d\times d$. टी स्वतंत्र नमूनों के योग का ऑपरेटर मानदंड त्रुटिहीन रूप से लंबाई टी के डी स्वतंत्र यादृच्छिक वॉक के बीच अधिकतम विचलन है। निरंतर संभावना के साथ अधिकतम विचलन पर निश्चित सीमा प्राप्त करने के लिए, यह देखना आसान है कि इस परिदृश्य में t को d के साथ लघुगणकीय रूप से बढ़ना चाहिए।

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

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

मान ले 0 < ε < 1 हो और M यादृच्छिक सममित वास्तविक मैट्रिक्स हो जिसके लिए $\|\operatorname {E} [M]\|\leq 1$ और $\|M\|\leq \gamma$ होता है अधिकतर निश्चितता के साथ, मान लें कि M के समर्थन में प्रत्येक तत्व मानक r से अधिकतम अवर्ध होता है। सेट करें

$t=\Omega \left({\frac {\gamma \log(\gamma /\varepsilon ^{2})}{\varepsilon ^{2}}}\right).$

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

$\Pr \left(\left\|{\frac {1}{t}}\sum _{i=1}^{t}M_{i}-\operatorname {E} [M]\right\|>\varepsilon \right)\leq {\frac {1}{\mathbf {poly} (t)}}$

यहाँ M₁, ..., M_t की i.i.d. प्रतिलिपियाँ हैं।

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

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

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

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

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

$\Pr \left(r_{S}<(1-d)\cdot r\right)<\exp \left(-r\cdot d^{2}\cdot {\frac {k}{2}}\right)$

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

$\Pr \left(r_{S}>0.5\right)>1-\exp \left(-r\cdot \left(1-{\frac {1}{2r}}\right)^{2}\cdot {\frac {k}{2}}\right)$

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

प्रमाण

गुणात्मक रूप

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

$\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)}$

इसलिए, (1) का उपयोग करते हुए, जहाँ $a=(1+\delta )\mu$ और यहाँ $\delta >0$ है, और यहाँ$\mu =\operatorname {E} [X]=\textstyle \sum _{i=1}^{n}p_{i}$ है,

${\begin{aligned}\Pr(X>(1+\delta )\mu )&\leq \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{aligned}}$

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

$\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 }.$

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

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

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

$\Pr \left({\frac {1}{n}}\sum X_{i}\geq q\right)\leq \inf _{t>0}{\frac {E\left[\prod e^{tX_{i}}\right]}{e^{tnq}}}=\inf _{t>0}\left({\frac {E\left[e^{tX_{i}}\right]}{e^{tq}}}\right)^{n}.$

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

$\left({\frac {\operatorname {E} \left[e^{tX_{i}}\right]}{e^{tq}}}\right)^{n}=\left({\frac {pe^{t}+(1-p)}{e^{tq}}}\right)^{n}=\left(pe^{(1-q)t}+(1-p)e^{-qt}\right)^{n}.$

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

${\frac {d}{dt}}\left(pe^{(1-q)t}+(1-p)e^{-qt}\right)=(1-q)pe^{(1-q)t}-q(1-p)e^{-qt}$

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

${\begin{aligned}(1-q)pe^{(1-q)t}&=q(1-p)e^{-qt}\\(1-q)pe^{t}&=q(1-p)\end{aligned}}$

जिससे

$e^{t}={\frac {(1-p)q}{(1-q)p}}.$

इस प्रकार,

$t=\log \left({\frac {(1-p)q}{(1-q)p}}\right).$

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

$\Pr \left({\tfrac {1}{n}}\sum X_{i}\geq p+\varepsilon \right)\leq e^{-D(p+\varepsilon \parallel p)n}.$