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

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

इस बाउंड को आमतौर पर हरमन चेर्नॉफ़ के नाम पर जाना जाता है, जिन्होंने 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}.$