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

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

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

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

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

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

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

जेनेरिक चेर्नॉफ़ यादृच्छिक चर के लिए बाध्य है $X$ मार्कोव की असमानता को लागू करने से प्राप्त होता है $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)}$. इसका तात्पर्य यह है कि दाहिनी पूँछ पर बाउंड तुच्छ रूप से 1 के बराबर है $a\leq \operatorname {E} (X)$; इसी प्रकार, बायीं सीमा भी तुच्छ है $a\geq \operatorname {E} (X)$. इसलिए हम दोनों इन्फिमा को जोड़ सकते हैं और दो-तरफा चेर्नॉफ़ बाउंड को परिभाषित कर सकते हैं:

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

Exact rate functions and Chernoff bounds for common distributions

वितरण	$\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, का क्षण उत्पन्न करने वाला कार्य 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 iid चर के औसत के लिए बाध्य चेर्नॉफ़ एकल चर पर बंधे चेर्नोफ़ की 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 आई.आई.डी. हैं यादृच्छिक चर, मान लेते हुए {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 और एम यादृच्छिक सममित वास्तविक मैट्रिक्स हो $\|\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 आई.आई.डी. हैं एम की प्रतियां

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

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

मान लीजिये कि सामान्य जनसंख्या 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}.$