Concentration inequality
संभाव्यता सिद्धांत में, एकाग्रता असमानताएँ इस बात की सीमा प्रदान करती हैं कि कैसे एक यादृच्छिक चर कुछ मूल्य (आमतौर पर, इसका अपेक्षित मूल्य) से विचलित होता है। शास्त्रीय संभाव्यता सिद्धांत की बड़ी संख्या के नियम में कहा गया है कि स्वतंत्र यादृच्छिक चर का योग, बहुत हल्की परिस्थितियों में, एक बड़ी संभावना के साथ उनकी अपेक्षा के करीब है। इस तरह के योग यादृच्छिक चर के सबसे बुनियादी उदाहरण हैं जो उनके माध्य के आसपास केंद्रित हैं। हाल के परिणाम बताते हैं कि इस तरह का व्यवहार स्वतंत्र यादृच्छिक चर के अन्य कार्यों द्वारा साझा किया जाता है। एकाग्रता असमानताओं को इस आधार पर क्रमबद्ध किया जा सकता है कि उनका उपयोग करने के लिए यादृच्छिक चर के बारे में कितनी जानकारी की आवश्यकता है। मार्कोव की असमानता एक यादृच्छिक चर है जो गैर-नकारात्मक (लगभग निश्चित रूप से) है। फिर, प्रत्येक स्थिरांक के लिए, मार्कोव की असमानता के निम्नलिखित विस्तार पर ध्यान देंः यदि यह सख्ती से बढ़ता हुआ और गैर-नकारात्मक कार्य है, तो चेबीशेव की असमानता के लिए एक यादृच्छिक चर पर निम्नलिखित जानकारी की आवश्यकता होती हैः अपेक्षित मूल्य सीमित है। भिन्नता सीमित है। फिर, प्रत्येक स्थिरांक, या समतुल्य के लिए, का मानक विचलन कहाँ है। चेबिशेव की असमानता को यादृच्छिक चर पर लागू सामान्यीकृत मार्कोव की असमानता के एक विशेष मामले के रूप में देखा जा सकता है। Vysochanskij-Petunin असमानता मान लीजिए कि X एक यादृच्छिक चर है जिसमें एक-आयामी वितरण, माध्य μ और परिमित, गैर-शून्य विचरण σ2 है। फिर, किसी के लिए (अपेक्षाकृत प्राथमिक प्रमाण के लिए देखें। )। एक तरफा विसोचान्स्कीज-पेटुनिन असमानता एक एकरूप यादृच्छिक चर के लिए और, एकतरफा विसोचान्स्कीज-पेटुनिन असमानता इस प्रकार हैः पाले-ज़िग्मंड असमानता कैंटेली की असमानता गॉस की असमानता चेरनोफ सीमा सामान्य चेरनोफ सीमा के लिए क्षण उत्पन्न करने वाले कार्य की आवश्यकता होती है, जैसा कि परिभाषित किया गया है कि यह हमेशा मौजूद है, लेकिन अनंत हो सकता है। मार्कोव की असमानता से, प्रत्येक के लिए और प्रत्येक के लिएः विभिन्न वितरणों और मापदंड के विभिन्न मूल्यों के लिए विभिन्न चेरनोफ़ सीमाएँ हैं। अधिक एकाग्रता असमानताओं के संकलन के लिए देखें। स्वतंत्र बंधे हुए चरों के योग पर सीमाएँ आइए स्वतंत्र यादृच्छिक चर हों जैसे कि, सभी के लिए i: लगभग निश्चित रूप से। मान लीजिए कि उनका योग, इसका अपेक्षित मूल्य और इसका विचलनः योग और इसके अपेक्षित मूल्य के बीच के अंतर को बांधना अक्सर दिलचस्प होता है। कई असमानताओं का उपयोग किया जा सकता है। 1. होफडिंग की असमानता कहती है किः 2. यादृच्छिक चर एक मार्टिंगेल का एक विशेष मामला है, और। इसलिए, अज़ुमा की असमानता के सामान्य रूप का भी उपयोग किया जा सकता है और यह एक समान सीमा उत्पन्न करता हैः यह होफ़्डिंग का एक सामान्यीकरण है क्योंकि यह अन्य प्रकार के मार्टिंगल्स के साथ-साथ सुपरमार्टिंगल्स और सबमार्टिंगल्स को भी संभाल सकता है। फैन एट अल देखें। (2015)। ध्यान दें कि यदि अज़ुमा की असमानता के सरल रूप का उपयोग किया जाता है, तो सीमा में घातांक 4 के कारक से बदतर होता है। 3. योग फलन,, n चर के फलन का एक विशेष मामला है। यह फलन एक सीमित तरीके से बदलता हैः यदि चर i को बदल दिया जाता है, तो f का मान अधिक से अधिक बदल जाता है। इसलिए, मैक्डियारमिड की असमानता का भी उपयोग किया जा सकता है और यह एक समान सीमा उत्पन्न करता हैः यह होफडिंग का एक अलग सामान्यीकरण है क्योंकि यह योग फलन के अलावा अन्य कार्यों को संभाल सकता है, जब तक कि वे एक सीमित तरीके से बदलते हैं। 4. बेनेट की असमानता होफडिंग की तुलना में कुछ सुधार प्रदान करती है जब योगों के विचलन उनकी लगभग निश्चित सीमा सी की तुलना में छोटे होते हैं। बर्नस्टीन की असमानताओं में से पहला यह कहता है किः यह होफडिंग का एक सामान्यीकरण है क्योंकि यह यादृच्छिक चर को न केवल लगभग-निश्चित बाध्य के साथ संभाल सकता है, बल्कि दोनों लगभग-निश्चित बाध्य और भिन्नता बाध्य हैं। 6. स्वतंत्र चरों के योग के मामले में चेरनोफ सीमा का एक विशेष रूप से सरल रूप है। उदाहरण के लिए, मान लीजिए कि चर संतुष्ट करते हैं। फिर हमारे पास निचली पूंछ की असमानता हैः यदि संतुष्ट करता है, तो हमारे पास ऊपरी पूंछ की असमानता हैः यदि है, तो चेरनोफ असमानता का एक विशिष्ट संस्करण हैः 7। इसी तरह की सीमाएँ निम्नलिखित में पाई जा सकती हैंः राडेमाकर distribution#Bounds राशि पर एफ्रॉन-स्टीन असमानता एफ्रॉन-स्टीन असमानता (या प्रभाव असमानता, या भिन्नता पर बाध्य एमजी) एक सामान्य फलन के विचलन को सीमित करती है। मान लीजिए कि, सभी के लिए समान वितरण के साथ स्वतंत्र हैं। मान लीजिए कि एक प्रमाण उदाहरण के लिए पाया जा सकता है। ब्रेटैग्नोल-ह्यूबर-कैरोल असमानता ब्रेटैग्नोल-ह्यूबर-कैरोल असमानता बहुआयामी रूप से वितरित यादृच्छिक चर के वेक्टर और अपेक्षित मूल्यों के वेक्टर के बीच के अंतर को सीमित करती है। (परिशिष्ट अनुभाग) में एक सरल प्रमाण दिखाई देता है। यदि एक यादृच्छिक वेक्टर बहुआयामी रूप से मापदंडों के साथ वितरित किया जाता है और संतुष्ट होता है तो इस असमानता का उपयोग कुल भिन्नता दूरी को बांधने के लिए किया जाता है। मेसन और वैन ज़्वेट असमानता बहुपद यादृच्छिक वैक्टरों के लिए मेसन और वैन ज़्वेट असमानता शास्त्रीय ची-वर्ग सांख्यिकीय के मामूली संशोधन से संबंधित है। मान लीजिए कि यादृच्छिक सदिश को बहुआयामी रूप से मापदंडों के साथ वितरित किया जाए और जैसे कि प्रत्येक के लिए और ऐसे स्थिरांक मौजूद हैं जैसे कि सभी के लिए और संतोषजनक और हमारे पास ड्वोरेटज़की-कीफर-वोल्फोविट्ज़ असमानता है। एक प्राकृतिक संख्या को देखते हुए, संचयी वितरण फलन F (·) के साथ वास्तविक-मूल्य स्वतंत्र और समान रूप से वितरित यादृच्छिक चर होने दें। तो यह संभावना है कि एक एकल यादृच्छिक चर उससे छोटा है, और यादृच्छिक चर की औसत संख्या है जो उससे छोटे हैं। फिर एकाग्रता-विरोधी असमानताएँ दूसरी ओर, एकाग्रता-विरोधी असमानताएँ इस बात की एक ऊपरी सीमा प्रदान करती हैं कि एक यादृच्छिक चर एक मात्रा के आसपास कितना ध्यान केंद्रित कर सकता है। उदाहरण के लिए, राव और येहूदयॉफ बताते हैं कि कुछ ऐसे मौजूद हैं जो, हाइपरक्यूब की अधिकांश दिशाओं के लिए, निम्नलिखित सच हैः जहां काफी बड़े आकार के सबसेट से समान रूप से खींचा जाता है। इस तरह की असमानताएँ कई क्षेत्रों में महत्वपूर्ण हैं, जिनमें संचार जटिलता (जैसे, अंतराल हैमिंग समस्या के प्रमाण में) और ग्राफ सिद्धांत शामिल हैं। स्वतंत्र राडेमाकर यादृच्छिक चर के भारित योग के लिए एक दिलचस्प एकाग्रता-विरोधी असमानता को पाले-ज़िगमंड और खिंटचिन असमानताओं का उपयोग करके प्राप्त किया जा सकता है। संदर्भ बाहरी लिंक कार्तिक श्रीधरन, "एकाग्रता असमानताओं का एक कोमल परिचय"-कॉर्नेल विश्वविद्यालय संभावित असमानताएँ