युग्‍मानूसार स्वावलंबन

संभाव्यता सिद्धांत में, यादृच्छिक चर का एक जोड़ीदार स्वतंत्र संग्रह यादृच्छिक चर का एक सेट है, जिनमें से कोई भी दो सांख्यिकीय स्वतंत्रता हैं। पारस्परिक स्वतंत्रता यादृच्छिक चर का कोई भी संग्रह जोड़ीदार स्वतंत्र है, लेकिन कुछ जोड़ीदार स्वतंत्र संग्रह परस्पर स्वतंत्र नहीं हैं। परिमित भिन्नता वाले जोड़ीदार स्वतंत्र यादृच्छिक चर असंबद्ध हैं।

यादृच्छिक चर एक्स और वाई की एक जोड़ी 'स्वतंत्र' है अगर और केवल अगर यादृच्छिक वेक्टर (एक्स, वाई) संयुक्त वितरण संचयी वितरण समारोह (सीडीएफ) के साथ $F_{X,Y}(x,y)$ संतुष्ट

$F_{X,Y}(x,y)=F_{X}(x)F_{Y}(y),$

या समकक्ष, उनका संयुक्त घनत्व $f_{X,Y}(x,y)$ संतुष्ट

$f_{X,Y}(x,y)=f_{X}(x)f_{Y}(y).$

अर्थात्, संयुक्त वितरण सीमांत वितरण के उत्पाद के बराबर है। जब तक यह संदर्भ में स्पष्ट न हो, व्यवहार में संशोधक आपसी को आमतौर पर छोड़ दिया जाता है ताकि स्वतंत्रता का अर्थ पारस्परिक स्वतंत्रता हो। X, Y, Z जैसे कथन स्वतंत्र यादृच्छिक चर हैं जिसका अर्थ है कि X, Y, Z परस्पर स्वतंत्र हैं।

उदाहरण

जोड़ीदार स्वतंत्रता का अर्थ पारस्परिक स्वतंत्रता नहीं है, जैसा कि निम्नलिखित उदाहरण द्वारा दिखाया गया है, जिसका श्रेय एस. बर्नस्टीन को दिया जाता है। मान लीजिए X और Y एक निष्पक्ष सिक्के के दो स्वतंत्र टॉस हैं, जहां हम 1 को हेड के लिए और 0 को टेल के लिए नामित करते हैं। मान लें कि तीसरा रैंडम वेरिएबल Z 1 के बराबर है, अगर उन सिक्कों में से एक टॉस के परिणामस्वरूप हेड्स आए, और 0 अन्यथा (यानी, $Z=X\oplus Y$). फिर संयुक्त रूप से ट्रिपल (एक्स, वाई, जेड) में निम्नलिखित संयुक्त संभाव्यता वितरण है:

$(X,Y,Z)=\left\{{\begin{matrix}(0,0,0)&{\text{with probability}}\ 1/4,\\(0,1,1)&{\text{with probability}}\ 1/4,\\(1,0,1)&{\text{with probability}}\ 1/4,\\(1,1,0)&{\text{with probability}}\ 1/4.\end{matrix}}\right.$

यहाँ सीमांत संभाव्यता वितरण समान हैं: $f_{X}(0)=f_{Y}(0)=f_{Z}(0)=1/2,$ और $f_{X}(1)=f_{Y}(1)=f_{Z}(1)=1/2.$ द्विभाजित वितरण भी सहमत हैं: $f_{X,Y}=f_{X,Z}=f_{Y,Z},$ कहाँ $f_{X,Y}(0,0)=f_{X,Y}(0,1)=f_{X,Y}(1,0)=f_{X,Y}(1,1)=1/4.$ चूंकि प्रत्येक जोड़ीवार संयुक्त वितरण उनके संबंधित सीमांत वितरण के उत्पाद के बराबर होता है, इसलिए चर जोड़े में स्वतंत्र होते हैं:

• X और Y स्वतंत्र हैं, और
• एक्स और जेड स्वतंत्र हैं, और
• Y और Z स्वतंत्र हैं।

हालाँकि, X, Y और Z 'नहीं' हैं $f_{X,Y,Z}(x,y,z)\neq f_{X}(x)f_{Y}(y)f_{Z}(z),$ उदाहरण के लिए बाईं ओर बराबर (x, y, z) = (0, 0, 0) के लिए 1/4 जबकि दाईं ओर (x, y, z) = (0, 0, 0) के लिए 1/8 के बराबर है। वास्तव में, कोई भी $\{X,Y,Z\}$ अन्य दो द्वारा पूरी तरह से निर्धारित किया जाता है (एक्स, वाई, जेड में से कोई भी मॉड्यूलर अंकगणितीय है। योग (मॉड्यूलो 2) दूसरों का)। यह स्वतंत्रता से उतना ही दूर है जितना यादृच्छिक चर प्राप्त कर सकते हैं।

जोड़ीदार स्वतंत्र घटनाओं के मिलन की संभावना

बर्नौली वितरण यादृच्छिक चर का योग कम से कम एक होने की प्रायिकता पर सीमा, जिसे आमतौर पर बूले की असमानता के रूप में जाना जाता है, फ्रेचेट असमानताओं द्वारा प्रदान की जाती है। बूले-फ्रेचेट असमानता। जबकि ये सीमाएँ केवल अविभाजित जानकारी मानती हैं, सामान्य संयुक्त संभाव्यता वितरण संभावनाओं के ज्ञान के साथ कई सीमाएँ भी प्रस्तावित की गई हैं। द्वारा निरूपित करें $\{{A}_{i},i\in \{1,2,...,n\}\}$ का एक सेट $n$ घटना की संभावना के साथ Bernoulli वितरण घटनाओं $\mathbb {P} (A_{i})=p_{i}$ प्रत्येक के लिए $i$. मान लीजिए कि संयुक्त प्रायिकता वितरण प्रायिकता द्वारा दिया गया है $\mathbb {P} (A_{i}\cap A_{j})=p_{ij}$ सूचकांकों की प्रत्येक जोड़ी के लिए $(i,j)$. खाट निम्नलिखित ऊपरी और निचली सीमाएँ व्युत्पन्न:

$\mathbb {P} (\displaystyle {\cup }_{i}A_{i})\leq \displaystyle \sum _{i=1}^{n}p_{i}-{\underset {j\in \{1,2,..,n\}}{\max }}\sum _{i\neq j}p_{ij},$

जो एक पूर्ण ग्राफ पर फैले पेड़ के एक स्टार (ग्राफ सिद्धांत) के अधिकतम वजन को घटाता है $n$ नोड्स (जहां बढ़त वजन द्वारा दिया जाता है $p_{ij}$) सीमांत वितरण संभावनाओं के योग से $\sum _{i}p_{i}$.
हंटर-वॉर्स्ले इस ऊपरी और निचले सीमा को अनुकूलित करके कस दिया $\tau \in T$ इस प्रकार है:

$\mathbb {P} (\displaystyle {\cup }_{i}A_{i})\leq \displaystyle \sum _{i=1}^{n}p_{i}-{\underset {\tau \in T}{\max }}\sum _{(i,j)\in \tau }p_{ij},$

कहाँ $T$ ग्राफ पर सभी फैले पेड़ का सेट है। ये सीमाएँ ऊपरी और निचली सीमाएँ नहीं हैं # सामान्य संयुक्त संभाव्यता वितरण के साथ तंग सीमाएँ संभव हैं $p_{ij}$ यहां तक ​​कि जब संभव क्षेत्र की गारंटी दी जाती है जैसा कि बोरोस और अन्य में दिखाया गया है। हालांकि, जब चर #Example ($p_{ij}=p_{i}p_{j}$), रामचंद्र-नटराजन दिखाया गया है कि कौनियास-हंटर-वॉर्स्ली बाउंड ऊपरी और निचली सीमा है # तंग सीमा यह साबित करके कि घटनाओं के मिलन की अधिकतम संभावना एक बंद-रूप अभिव्यक्ति को स्वीकार करती है:

$\max \mathbb {P} (\displaystyle {\cup }_{i}A_{i})=\displaystyle \min \left(\sum _{i=1}^{n}p_{i}-p_{n}\left(\sum _{i=1}^{n-1}p_{i}\right),1\right)$

(1)

जहां संभाव्यता को बढ़ते क्रम में क्रमबद्ध किया जाता है $0\leq p_{1}\leq p_{2}\leq \ldots \leq p_{n}\leq 1$. यह ध्यान रखना दिलचस्प है कि ऊपरी और निचली सीमाएँ # तंग सीमाएँ हैं Eq. 1 केवल सबसे छोटे के योग पर निर्भर करता है $n-1$ संभावना $\sum _{i=1}^{n-1}p_{i}$ और सबसे बड़ी संभावना $p_{n}$. इस प्रकार, जबकि संभाव्यता की छँटाई सीमा की व्युत्पत्ति में एक भूमिका निभाती है, सबसे छोटी छँटाई $n-1$ संभावना $\{p_{1},p_{2},...,p_{n-1}\}$ अप्रासंगिक है क्योंकि केवल उनकी राशि का उपयोग किया जाता है।

फ़्रेचेट असमानताओं के साथ तुलना|बूले–फ़्रेचेट बूले की असमानता

मनमाने ढंग से निर्भर और स्वतंत्र चर और #Example के साथ संघ की संभावना पर सबसे छोटी सीमा की तुलना करना उपयोगी है। ऊपरी और निचली सीमाएं#टाइट बाउंड्स फ्रेचेट असमानताएं|बूले-फ्रेचेट ऊपरी और निचली सीमाएं बूल की असमानता (केवल अविभाजित जानकारी मानते हुए) इस प्रकार दी गई है:

$\displaystyle \max \mathbb {P} (\displaystyle {\cup }_{i}A_{i})=\displaystyle \min \left(\sum _{i=1}^{n}p_{i},1\right)$

(2)

जैसा कि रामचंद्र-नटराजन में दिखाया गया है, यह आसानी से सत्यापित किया जा सकता है कि दो ऊपरी और निचली सीमाओं का अनुपात # तंग सीमा में है Eq. 2 और Eq. 1 द्वारा ऊपरी और निचली सीमा है $4/3$ जहां का अधिकतम मूल्य $4/3$ प्राप्त होता है जब

$\sum _{i=1}^{n-1}p_{i}=1/2$, $p_{n}=1/2$

जहां संभाव्यता को बढ़ते क्रम में क्रमबद्ध किया जाता है $0\leq p_{1}\leq p_{2}\leq \ldots \leq p_{n}\leq 1$. दूसरे शब्दों में, सबसे अच्छी स्थिति में, जोड़ीदार स्वतंत्रता बंधी हुई है Eq. 1 का सुधार प्रदान करता है $25\%$ में बाध्य अविभाज्य पर Eq. 2.

सामान्यीकरण

अधिक आम तौर पर, हम किसी भी k ≥ 2 के लिए k-वार स्वतंत्रता के बारे में बात कर सकते हैं। विचार समान है: यादृच्छिक चर का एक सेट k-वार स्वतंत्र है यदि उन चर के आकार k का प्रत्येक उपसमूह स्वतंत्र है। k-वार स्वतंत्रता का उपयोग सैद्धांतिक कंप्यूटर विज्ञान में किया गया है, जहाँ इसका उपयोग MAXEkSAT समस्या के बारे में एक प्रमेय को सिद्ध करने के लिए किया गया था।

k-वार स्वतंत्रता का उपयोग इस प्रमाण में किया जाता है कि k-स्वतंत्र हैशिंग फ़ंक्शन सुरक्षित अक्षम्य संदेश प्रमाणीकरण कोड हैं।

यह भी देखें

• विकट:जोड़ीदार
• जोड़ो में अलग करना