विशिष्ट समुच्चय: Difference between revisions

Latest revision as of 10:36, 11 December 2023

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

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

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

(दुर्बल (वीकली)) विशिष्ट अनुक्रम (दुर्बल विशिष्टता, एन्ट्रॉपी विशिष्टता)

यदि किसी अनुक्रम x₁, ..., x_n को एक आई.आई.डी. वितरण X से निर्धारित एक सीमित वर्णमाला ${\mathcal {X}}$ पर से प्राप्त किया गया है, तो विशिष्ट समुच्चय, A_ε⁽ⁿ⁾ $\in {\mathcal {X}}$ , उन सृष्टियों को परिभाषित करता है जो निम्नलिखित शर्तों को संतुष्ट करते हैं:

2^{-n(H(X)+\varepsilon )}\leqslant p(x_{1},x_{2},\dots ,x_{n})\leqslant 2^{-n(H(X)-\varepsilon )}

जहाँ

H(X)=-\sum _{x\in {\mathcal {X}}}p(x)\log _{2}p(x)

X की सूचना एन्ट्रॉपी है। उपरोक्त प्रायिकता केवल 2^{n ε} के कारक के अंतर्गत होनी चाहिए। सभी पक्षों पर लघुगणक लेने और -n से विभाजित करने पर, इस परिभाषा को समकक्ष रूप से कहा जा सकता है

H(X)-\varepsilon \leq -{\frac {1}{n}}\log _{2}p(x_{1},x_{2},\ldots ,x_{n})\leq H(X)+\varepsilon .

आई.आई.डी. अनुक्रम के लिए, चूँकि

p(x_{1},x_{2},\ldots ,x_{n})=\prod _{i=1}^{n}p(x_{i}),

हमें यह निम्लिखित और प्राप्त होता है

H(X)-\varepsilon \leq -{\frac {1}{n}}\sum _{i=1}^{n}\log _{2}p(x_{i})\leq H(X)+\varepsilon .

बड़ी संख्याओं के नियम के अनुसार, पर्याप्त रूप से बड़े n के लिए

-{\frac {1}{n}}\sum _{i=1}^{n}\log _{2}p(x_{i})\rightarrow H(X).

गुणधर्म

विशिष्ट समुच्चय की एक आवश्यक विशेषता यह है कि यदि कोई व्यक्ति वितरण X से बड़ी संख्या n के स्वतंत्र यादृच्छिक सैंपल प्राप्त करता है, तो परिणाम स्वरूपी अनुक्रम (x₁, x₂, ..., x_n) प्रायिकता से बहुत बड़े होने की प्रायिकता है कि विशिष्ट समुच्चय का घटक हो, हालांकि विशिष्ट समुच्चय सभी संभावित अनुक्रमों का केवल एक छोटा भाग होता है। औपचारिक रूप से, किसी भी $\varepsilon >0$ के लिए ऐसा चयन किया जा सकता है जिस प्रकार:

X(n) से एक अनुक्रम Aε(n) से प्राप्त होने की प्रायिकता 1 - ε, अर्थात $Pr[x^{(n)}\in A_{\epsilon }^{(n)}]\geq 1-\varepsilon$ से अधिक है
$\left|{A_{\varepsilon }}^{(n)}\right|\leqslant 2^{n(H(X)+\varepsilon )}$
$\left|{A_{\varepsilon }}^{(n)}\right|\geqslant (1-\varepsilon )2^{n(H(X)-\varepsilon )}$
यदि ${\mathcal {X}}$ से अधिक वितरण एक समान नहीं है, तो अनुक्रमों का अंश जो सामान्य है

{\frac {|A_{\epsilon }^{(n)}|}{|{\mathcal {X}}^{(n)}|}}\equiv {\frac {2^{nH(X)}}{2^{n\log _{2}|{\mathcal {X}}|}}}=2^{-n(\log _{2}|{\mathcal {X}}|-H(X))}\rightarrow 0

चूँकि n बहुत बड़ा हो जाता है,

H(X)<\log _{2}|{\mathcal {X}}|,

के पश्चात से जहाँ

|{\mathcal {X}}|

,

{\mathcal {X}}

की गणनीयता (कार्डिनैलिटी) होती है।

सामान्य प्रसंभाव्य (स्टोकास्टिक) प्रक्रम {X(t)} के लिए, जिसमें एईपी होता है, (दुर्बल रूप से) विशिष्ट समुच्चय को समरूप रूप से परिभाषित किया जा सकता है, जिसमें p(x₁, x₂, ..., x_n) को p(x₀^τ) से बदला जाता है (अर्थात, सम्पल के प्रायिक काल अंतराल [0, τ] तक सीमित होने की प्रायिकता), n प्रक्रिया की समय अंतराल में की गई स्वतंत्रता होती है और H(X) एन्ट्रॉपी दर होती है। यदि प्रक्रिया सतत मूल्यवान है, तो स्थानीय एन्ट्रॉपी का बजाय अवकल एन्ट्रॉपी का उपयोग किया जाता है।

उदाहरण

प्रति-सहज ज्ञान के विपरीत, सबसे संभावित अनुक्रम प्रायः विशिष्ट समुच्चय का घटक नहीं होता है। उदाहरण के लिए, मान लें कि X, p(0)=0.1 और p(1)=0.9 के साथ आई.आई.डी. बर्नौली यादृच्छिक चर है। n स्वतंत्र परीक्षणों में, चूँकि p(1)>p(0), परिणाम का सबसे संभावित क्रम सभी 1, (1,1,...,1) का अनुक्रम है। यहां X की एन्ट्रॉपी H(X)=0.469 है, जबकि

-{\frac {1}{n}}\log _{2}p\left(x^{(n)}=(1,1,\ldots ,1)\right)=-{\frac {1}{n}}\log _{2}(0.9^{n})=0.152

तो यह अनुक्रम विशिष्ट समुच्चय में नहीं है क्योंकि इसकी औसत लघुगामी प्रायिकता स्वयं की इक्षा अनुसार n की कितना भी बड़ा मान लें, यह कभी भी यादृच्छिक प्रतिस्थान X की एन्ट्रॉपी के निकट नहीं आ सकती है।

बर्नौली यादृच्छिक चर के लिए, विशिष्ट समुच्चय में n स्वतंत्र परीक्षणों में 0 और 1 की औसत संख्या वाले अनुक्रम होते हैं। इसे सरलता से प्रदर्शित किया जा सकता है: यदि p(1) = p और p(0) = 1-p, तो m 1 के साथ n परीक्षणों के लिए, हमें निम्नलिखित प्राप्त होता है

-{\frac {1}{n}}\log _{2}p(x^{(n)})=-{\frac {1}{n}}\log _{2}p^{m}(1-p)^{n-m}=-{\frac {m}{n}}\log _{2}p-\left({\frac {n-m}{n}}\right)\log _{2}(1-p).

बर्नौली परीक्षणों के अनुक्रम में 1 की औसत संख्या m = np है। इस प्रकार, हमें निम्नलिखित प्राप्त होता है

-{\frac {1}{n}}\log _{2}p(x^{(n)})=-p\log _{2}p-(1-p)\log _{2}(1-p)=H(X).

इस उदाहरण के लिए, यदि n=10, तो विशिष्ट समुच्चय में वे सभी अनुक्रम सम्मिलित होते हैं जिनमें संपूर्ण अनुक्रम में एक 0 होता है। यदि p(0)=p(1)=0.5, तो प्रत्येक संभावित बाइनरी अनुक्रम विशिष्ट समुच्चय से संबंधित है।

दृढ़ विशिष्ट अनुक्रम (सशक्त विशिष्टता, अक्षर विशिष्टता)

यदि एक अनुक्रम x₁, ..., x_n एक परिमित या एक अनंत वर्णमाला ${\mathcal {X}}$ पर परिभाषित कुछ निर्दिष्ट संयुक्त वितरण से तैयार किया गया है, तो दृढ़ता से विशिष्ट समुच्चय, A_ε,strong⁽ⁿ⁾ $\in {\mathcal {X}}$ को अनुक्रमों के समुच्चय के रूप में परिभाषित किया गया है जो संतुष्ट करते हैं

\left|{\frac {N(x_{i})}{n}}-p(x_{i})\right|<{\frac {\varepsilon }{\|{\mathcal {X}}\|}}.

जहां ${N(x_{i})}$ अनुक्रम में किसी विशिष्ट प्रतीक की घटनाओं की संख्या है।

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

संयुक्त रूप से विशिष्ट अनुक्रम

दो अनुक्रम $x^{n}$ और $y^{n}$ संयुक्त रूप से ε-विशिष्ट हैं यदि जोड़ी $(x^{n},y^{n})$ संयुक्त बंटन $p(x^{n},y^{n})=\prod _{i=1}^{n}p(x_{i},y_{i})$ के संबंध में ε-विशिष्ट है और $x^{n}$ और $y^{n}$ दोनों अपने सीमांत वितरण $p(x^{n})$ और $p(y^{n})$ के संबंध में ε-विशिष्ट हैं। अनुक्रम $(x^{n},y^{n})$ के ऐसे सभी युग्मों के समुच्चय को $A_{\varepsilon }^{n}(X,Y)$ द्वारा निरूपित किया जाता है। संयुक्त रूप से ε-विशिष्ट n-टपल अनुक्रमों को समान रूप से परिभाषित किया जाता है।

मान लीजिए ${\tilde {X}}^{n}$ और ${\tilde {Y}}^{n}$ समान सीमांत वितरण $p(x^{n})$ और $p(y^{n})$ के साथ यादृच्छिक चर के दो स्वतंत्र अनुक्रम हैं। फिर किसी भी ε>0 के लिए, पर्याप्त रूप से बड़े n के लिए, संयुक्त रूप से विशिष्ट अनुक्रम निम्नलिखित गुणों को संतुष्ट करते हैं:

$P\left[(X^{n},Y^{n})\in A_{\varepsilon }^{n}(X,Y)\right]\geqslant 1-\epsilon$
$\left|A_{\varepsilon }^{n}(X,Y)\right|\leqslant 2^{n(H(X,Y)+\epsilon )}$
$\left|A_{\varepsilon }^{n}(X,Y)\right|\geqslant (1-\epsilon )2^{n(H(X,Y)-\epsilon )}$
$P\left[({\tilde {X}}^{n},{\tilde {Y}}^{n})\in A_{\varepsilon }^{n}(X,Y)\right]\leqslant 2^{-n(I(X;Y)-3\epsilon )}$
$P\left[({\tilde {X}}^{n},{\tilde {Y}}^{n})\in A_{\varepsilon }^{n}(X,Y)\right]\geqslant (1-\epsilon )2^{-n(I(X;Y)+3\epsilon )}$

विशिष्टता के अनुप्रयोग

विशिष्ट समुच्चय एन्कोडिंग

सूचना सिद्धांत में, विशिष्ट समुच्चय एन्कोडिंग निश्चित लंबाई ब्लॉक कोड के साथ स्टोकेस्टिक स्रोत के विशिष्ट समुच्चय में केवल अनुक्रमों को एन्कोड करता है। चूँकि विशिष्ट समुच्चय का आकार लगभग 2^nH(X) है, कोडिंग के लिए केवल nH(X) बिट्स की आवश्यकता होती है, जबकि साथ ही यह सुनिश्चित किया जाता है कि एन्कोडिंग त्रुटि की प्रायिकता ε तक सीमित है। असम्बद्ध रूप से, एईपी द्वारा, यह हानिरहित है और स्रोत की एन्ट्रॉपी दर के बराबर न्यूनतम दर प्राप्त करता है।

विशिष्ट समुच्चय डिकोडिंग

सूचना सिद्धांत में, विशिष्ट समुच्चय डिकोडिंग का उपयोग यादृच्छिक कोडिंग के साथ मिलकर संचरित संदेश का अनुमान लगाने के लिए किया जाता है, जो एक कोडवर्ड के साथ होता है जो अवलोकन के साथ संयुक्त रूप से ε-विशिष्ट होता है। अर्थात

{\hat {w}}=w\iff (\exists w)((x_{1}^{n}(w),y_{1}^{n})\in A_{\varepsilon }^{n}(X,Y))

जहाँ ${\hat {w}},x_{1}^{n}(w),y_{1}^{n}$ क्रमशः संदेश अनुमान, संदेश $w$ का कोडवर्ड और अवलोकन हैं। $A_{\varepsilon }^{n}(X,Y)$ को संयुक्त वितरण $p(x_{1}^{n})p(y_{1}^{n}|x_{1}^{n})$ के संबंध में परिभाषित किया गया है जहां $p(y_{1}^{n}|x_{1}^{n})$ संक्रमण प्रायिकता है जो चैनल आंकड़ों की विशेषता है, और $p(x_{1}^{n})$ कुछ इनपुट वितरण है जो यादृच्छिक कोडबुक में कोडवर्ड उत्पन्न करने के लिए उपयोग किया जाता है।

सार्वभौमिक शून्य (अक्षम)-परिकल्पना परीक्षण

सार्वभौमिक चैनल कोड

यह भी देखें

एसिम्प्टोटिक समविभाजन संपत्ति
स्रोत कोडिंग प्रमेय
नॉइज़ी-चैनल कोडिंग प्रमेय

संदर्भ

C. E. Shannon, "A Mathematical Theory of Communication", Bell System Technical Journal, vol. 27, pp. 379–423, 623-656, July, October, 1948
Cover, Thomas M. (2006). "Chapter 3: Asymptotic Equipartition Property, Chapter 5: Data Compression, Chapter 8: Channel Capacity". Elements of Information Theory. John Wiley & Sons. ISBN 0-471-24195-4.
David J. C. MacKay. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1

@@ Line 1: / Line 1: @@
-[[सूचना सिद्धांत]] में, विशिष्ट सेट अनुक्रमों का एक सेट होता है जिसकी [[संभावना]] उनके स्रोत वितरण की [[सूचना एन्ट्रापी]] की नकारात्मक शक्ति से दो के करीब होती है। इस सेट की कुल संभावना एक के करीब होना [[स्पर्शोन्मुख समविभाजन संपत्ति]] (एईपी) का परिणाम है जो बड़ी संख्या का एक प्रकार का कानून है। विशिष्टता की धारणा केवल अनुक्रम की संभावना से संबंधित है न कि वास्तविक अनुक्रम से।
+[[सूचना सिद्धांत]] में, '''विशिष्ट (टिपिकल) समुच्चय''' अनुक्रमों का एक समुच्चय होता है जिसकी [[संभावना|प्रायिकता]] उनके स्रोत बंटन की [[सूचना एन्ट्रापी|एन्ट्रॉपी]] की ऋणात्मक घात से दो तक बढ़ जाती है। इस समुच्चय की कुल प्रायिकता एक के निकट होना [[स्पर्शोन्मुख समविभाजन संपत्ति|स्पर्शोन्मुख (एसिम्प्टोटिक) समविभाजन गुण]] (एईपी) का परिणाम है जो बड़ी संख्याओं का एक प्रकार का नियम होता है। विशिष्टता की धारणा वास्तविक अनुक्रम से संबंधित नहीं है, जबकि यह केवल अनुक्रम की प्रायिकता से संबंधित होती है।
-डेटा संपीड़न सिद्धांत में इसका बहुत उपयोग है क्योंकि यह डेटा को संपीड़ित करने के लिए एक सैद्धांतिक साधन प्रदान करता है, जिससे हमें किसी भी अनुक्रम ''X'' का प्रतिनिधित्व करने की अनुमति मिलती है।<sup>n</sup> औसतन nH(X) बिट्स का उपयोग करना, और, इसलिए, किसी स्रोत से जानकारी के माप के रूप में एन्ट्रापी के उपयोग को उचित ठहराना।
+यह संपीड़न सिद्धांत में महत्वपूर्ण है क्योंकि यह सूचना को संपीड़ित करने के लिए एक सैद्धान्तिक व्यवस्था प्रदान करता है, जिससे हमें किसी भी अनुक्रम ''X<sup>n</sup>'' को ''nH''(''X'') बिट का औसत से प्रदर्शित करने की प्रायिकता होती है, और, इसलिए, एक स्रोत से सूचना की माप के रूप में एन्ट्रॉपी के उपयोग को स्वीकृति प्राप्त होती है।
-एईपी को [[स्थिर एर्गोडिक प्रक्रिया]]ओं के एक बड़े वर्ग के लिए भी सिद्ध किया जा सकता है, जिससे विशिष्ट सेट को अधिक सामान्य मामलों में परिभाषित किया जा सकता है।
+एईपी को [[स्थिर एर्गोडिक प्रक्रिया|स्थिर अभ्यतिप्राय (एर्गोडिक) प्रक्रम]] बड़े वर्ग के लिए भी सिद्ध किया जा सकता है, जिससे अधिक सामान्य स्थितियों में विशिष्ट समुच्चय को परिभाषित किया जा सकता है।
-==(कमजोर) विशिष्ट अनुक्रम (कमजोर विशिष्टता, एन्ट्रापी विशिष्टता)==
+==(दुर्बल (वीकली)) विशिष्ट अनुक्रम (दुर्बल विशिष्टता, एन्ट्रॉपी विशिष्टता)==
-यदि एक अनुक्रम x<sub>1</sub>, ..., एक्स<sub>''n''</sub> एक स्वतंत्र रूप से वितरित यादृच्छिक चर से तैयार किया गया है|i.i.d. वितरण X को एक परिमित वर्णमाला पर परिभाषित किया गया है <math>\mathcal{X}</math>, फिर विशिष्ट सेट, ए<sub>''ε''</sub><sup>(एन)</sup><math>\in\mathcal{X}</math><sup>(n)</sup> को उन अनुक्रमों के रूप में परिभाषित किया गया है जो संतुष्ट करते हैं:
+यदि किसी अनुक्रम ''x''<sub>1</sub>, ..., ''x<sub>n</sub>'' को एक आई.आई.डी. वितरण ''X'' से निर्धारित एक सीमित वर्णमाला <math>\mathcal{X}</math> पर से प्राप्त किया गया है, तो विशिष्ट समुच्चय,  ''A<sub>ε</sub>''<sup>(''n'')</sup><math>\in\mathcal{X}</math>, उन सृष्टियों को परिभाषित करता है जो निम्नलिखित शर्तों को संतुष्ट करते हैं:
 :<math>
 ^{-n( H(X)+\varepsilon)} \leqslant p(x_1, x_2, \dots , x_n) \leqslant 2^{-n( H(X)-\varepsilon)}
 </math>
-कहाँ
+जहाँ
 : <math>  H(X)  = - \sum_{x \isin \mathcal{X}}p(x)\log_2 p(x)  </math>
-एक्स की सूचना एन्ट्रापी है। उपरोक्त संभावना केवल 2 के कारक के भीतर होनी चाहिए<sup>n ε</sup>. सभी पक्षों पर लघुगणक लेते हुए और -n से विभाजित करने पर, इस परिभाषा को समान रूप से कहा जा सकता है
+''X'' की सूचना एन्ट्रॉपी है। उपरोक्त प्रायिकता केवल 2<sup>''n'' ''ε''</sup> के कारक के अंतर्गत होनी चाहिए। सभी पक्षों पर लघुगणक लेने और ''-n'' से विभाजित करने पर, इस परिभाषा को समकक्ष रूप से कहा जा सकता है
 :<math> H(X) - \varepsilon \leq -\frac{1}{n}\log_2 p(x_1, x_2, \ldots, x_n) \leq H(X) + \varepsilon.</math>
 आई.आई.डी. अनुक्रम के लिए, चूँकि
-:<math>p(x_1, x_2, \ldots, x_n) = \prod_{i=1}^n p(x_i),</math> हमारे पास और भी है
+:<math>p(x_1, x_2, \ldots, x_n) = \prod_{i=1}^n p(x_i),</math>
+हमें यह निम्लिखित और प्राप्त होता है
 :<math> H(X) - \varepsilon \leq -\frac{1}{n} \sum_{i=1}^n \log_2 p(x_i) \leq H(X) + \varepsilon.</math>
-बड़ी संख्या के नियम के अनुसार, पर्याप्त रूप से बड़े n के लिए
+बड़ी संख्याओं के नियम के अनुसार, पर्याप्त रूप से बड़े ''n'' के लिए
 :<math>-\frac{1}{n} \sum_{i=1}^n \log_2 p(x_i)  \rightarrow H(X).</math>
+===गुणधर्म===
+विशिष्ट समुच्चय की एक आवश्यक विशेषता यह है कि यदि कोई व्यक्ति वितरण ''X'' से बड़ी संख्या ''n'' के स्वतंत्र यादृच्छिक सैंपल प्राप्त करता है, तो परिणाम स्वरूपी अनुक्रम  (''x''<sub>1</sub>, ''x''<sub>2</sub>, ..., ''x<sub>n</sub>'') प्रायिकता से बहुत बड़े होने की प्रायिकता है कि विशिष्ट समुच्चय का घटक हो, हालांकि विशिष्ट समुच्चय सभी संभावित अनुक्रमों का केवल एक छोटा भाग होता है। औपचारिक रूप से, किसी भी <math>\varepsilon>0</math> के लिए ऐसा चयन किया जा सकता है जिस प्रकार:
-===गुण===
+#X(n) से एक अनुक्रम Aε(n) से प्राप्त होने की प्रायिकता 1 - ε, अर्थात <math>Pr[x^{(n)} \in A_\epsilon^{(n)}] \geq 1 - \varepsilon </math> से अधिक है
-विशिष्ट सेट की एक आवश्यक विशेषता यह है कि, यदि कोई वितरण एक्स से बड़ी संख्या में स्वतंत्र यादृच्छिक नमूने खींचता है, तो परिणामी अनुक्रम (x)<sub>1</sub>, एक्स<sub>2</sub>, ..., एक्स<sub>''n''</sub>) विशिष्ट सेट का सदस्य होने की बहुत संभावना है, भले ही विशिष्ट सेट में सभी संभावित अनुक्रमों का केवल एक छोटा सा अंश शामिल हो। औपचारिक रूप से, कोई भी दिया गया <math>\varepsilon>0</math>, कोई n को इस प्रकार चुन सकता है कि:
-#X से अनुक्रम की प्रायिकता<sup>(एन)</sup>ए से लिया जा रहा है<sub>''ε''</sub><sup>(n)</sup> 1 − ε से बड़ा है, यानी। <math>Pr[x^{(n)} \in A_\epsilon^{(n)}] \geq 1 - \varepsilon </math>
 #<math>\left| {A_\varepsilon}^{(n)} \right| \leqslant 2^{n(H(X)+\varepsilon)}</math>
 #<math>\left| {A_\varepsilon}^{(n)} \right| \geqslant (1-\varepsilon)2^{n(H(X)-\varepsilon)}</math>
-#अगर वितरण खत्म हो गया <math>\mathcal{X}</math> एक समान नहीं है, तो अनुक्रमों का अंश जो विशिष्ट है वह है
+#यदि <math>\mathcal{X}</math> से अधिक वितरण एक समान नहीं है, तो अनुक्रमों का अंश जो सामान्य है
 ::<math>\frac{|A_\epsilon^{(n)}|}{|\mathcal{X}^{(n)}|} \equiv \frac{2^{nH(X)}}{2^{n\log_2|\mathcal{X}|}} = 2^{-n(\log_2|\mathcal{X}|-H(X))} \rightarrow 0  </math>
-::चूंकि n बहुत बड़ा हो जाता है <math>H(X) < \log_2|\mathcal{X}|,</math> कहाँ <math>|\mathcal{X}|</math> की [[प्रमुखता]] है <math>\mathcal{X}</math>.
+::चूँकि n बहुत बड़ा हो जाता है, <math>H(X) < \log_2|\mathcal{X}|,</math> के पश्चात से जहाँ <math>|\mathcal{X}|</math>, <math>\mathcal{X}</math> की [[प्रमुखता|गणनीयता]] (कार्डिनैलिटी) होती है।
-AEP के साथ एक सामान्य स्टोकेस्टिक प्रक्रिया {X(t)} के लिए, (कमजोर) विशिष्ट सेट को p(x) के साथ समान रूप से परिभाषित किया जा सकता है<sub>1</sub>, एक्स<sub>2</sub>, ..., एक्स<sub>''n''</sub>) को p(x) द्वारा प्रतिस्थापित किया गया<sub>0</sub><sup>τ</sup>) (यानी समय अंतराल [0,τ] तक सीमित नमूने की संभावना), n समय अंतराल में प्रक्रिया की स्वतंत्रता (भौतिकी और रसायन विज्ञान) की डिग्री है और H(X) है [[एन्ट्रापी दर]]. यदि प्रक्रिया निरंतर-मूल्यवान है, तो इसके बजाय [[विभेदक एन्ट्रापी]] का उपयोग किया जाता है।
+सामान्य प्रसंभाव्य (स्टोकास्टिक) प्रक्रम {''X''(''t'')} के लिए, जिसमें एईपी होता है, (दुर्बल रूप से) विशिष्ट समुच्चय को समरूप रूप से परिभाषित किया जा सकता है, जिसमें ''p''(''x''<sub>1</sub>, ''x''<sub>2</sub>, ..., ''x<sub>n</sub>'') को ''p''(''x''<sub>0</sub><sup>''τ''</sup>) से बदला जाता है (अर्थात, सम्पल के प्रायिक काल अंतराल [0, τ] तक सीमित होने की प्रायिकता), ''n'' प्रक्रिया की समय अंतराल में की गई स्वतंत्रता होती है और ''H''(''X'') [[एन्ट्रापी दर|एन्ट्रॉपी दर]] होती है। यदि प्रक्रिया सतत मूल्यवान है, तो स्थानीय एन्ट्रॉपी का बजाय [[विभेदक एन्ट्रापी|अवकल एन्ट्रॉपी]] का उपयोग किया जाता है।
 ===उदाहरण===
-प्रति-सहज ज्ञान से, सबसे संभावित अनुक्रम अक्सर विशिष्ट सेट का सदस्य नहीं होता है। उदाहरण के लिए, मान लीजिए कि X, p(0)=0.1 और p(1)=0.9 के साथ एक i.i.d Bernoulli_distribution है। n स्वतंत्र परीक्षणों में, चूँकि p(1)>p(0), परिणाम का सबसे संभावित क्रम सभी 1 का अनुक्रम है, (1,1,...,1)। यहाँ X की एन्ट्रापी H(X)=0.469 है, जबकि
+प्रति-सहज ज्ञान के विपरीत, सबसे संभावित अनुक्रम प्रायः विशिष्ट समुच्चय का घटक नहीं होता है। उदाहरण के लिए, मान लें कि ''X'', ''p''(0)=0.1 और ''p''(1)=0.9 के साथ आई.आई.डी. बर्नौली यादृच्छिक चर है। ''n'' स्वतंत्र परीक्षणों में, चूँकि ''p''(1)>''p''(0), परिणाम का सबसे संभावित क्रम सभी 1, (1,1,...,1) का अनुक्रम है। यहां ''X'' की एन्ट्रॉपी ''H''(''X'')=0.469 है, जबकि
 :<math> -\frac{1}{n}\log_2 p\left(x^{(n)}=(1,1,\ldots,1)\right) = -\frac{1}{n}\log_2 (0.9^n) = 0.152</math>
-इसलिए यह क्रम विशिष्ट सेट में नहीं है क्योंकि इसकी औसत लघुगणकीय संभावना यादृच्छिक चर
+तो यह अनुक्रम विशिष्ट समुच्चय में नहीं है क्योंकि इसकी औसत लघुगामी प्रायिकता स्वयं की इक्षा अनुसार ''n'' की कितना भी बड़ा मान लें, यह कभी भी यादृच्छिक प्रतिस्थान X की एन्ट्रॉपी के निकट नहीं आ सकती है।
-बर्नौली यादृच्छिक चर के लिए, विशिष्ट सेट में n स्वतंत्र परीक्षणों में 0s और 1s की औसत संख्या वाले अनुक्रम होते हैं। इसे आसानी से प्रदर्शित किया जा सकता है: यदि p(1) = p और p(0) = 1-p, तो m 1 के साथ n परीक्षणों के लिए, हमारे पास है
+बर्नौली यादृच्छिक चर के लिए, विशिष्ट समुच्चय में ''n'' स्वतंत्र परीक्षणों में 0 और 1 की औसत संख्या वाले अनुक्रम होते हैं। इसे सरलता से प्रदर्शित किया जा सकता है: यदि ''p(1) = p'' और ''p(0) = 1-p'', तो m 1 के साथ n परीक्षणों के लिए, हमें निम्नलिखित प्राप्त होता है
 :<math> -\frac{1}{n} \log_2 p(x^{(n)}) = -\frac{1}{n} \log_2 p^m (1-p)^{n-m} = -\frac{m}{n} \log_2 p - \left( \frac{n-m}{n} \right) \log_2 (1-p).</math>
-बर्नौली परीक्षणों के अनुक्रम में 1 की औसत संख्या m = np है। इस प्रकार, हमारे पास है
+बर्नौली परीक्षणों के अनुक्रम में 1 की औसत संख्या m = np है। इस प्रकार, हमें निम्नलिखित प्राप्त होता है
 :<math> -\frac{1}{n} \log_2 p(x^{(n)}) = - p \log_2 p - (1-p) \log_2 (1-p) = H(X).</math>
-इस उदाहरण के लिए, यदि n=10, तो विशिष्ट सेट में सभी अनुक्रम शामिल होते हैं जिनमें पूरे अनुक्रम में एक 0 होता है। यदि p(0)=p(1)=0.5, तो प्रत्येक संभावित बाइनरी अनुक्रम विशिष्ट सेट से संबंधित है।
+इस उदाहरण के लिए, यदि ''n=10'', तो विशिष्ट समुच्चय में वे सभी अनुक्रम सम्मिलित होते हैं जिनमें संपूर्ण अनुक्रम में एक 0 होता है। यदि ''p(0)=p(1)=0.5'', तो प्रत्येक संभावित बाइनरी अनुक्रम विशिष्ट समुच्चय से संबंधित है।
-==दृढ़ विशिष्ट अनुक्रम (मजबूत विशिष्टता, अक्षर विशिष्टता)==
+==दृढ़ विशिष्ट अनुक्रम (सशक्त विशिष्टता, अक्षर विशिष्टता)==
-यदि एक अनुक्रम x<sub>1</sub>, ..., एक्स<sub>''n''</sub> एक परिमित या अनंत वर्णमाला पर परिभाषित कुछ निर्दिष्ट संयुक्त वितरण से लिया गया है <math>\mathcal{X}</math>, फिर दृढ़ता से विशिष्ट सेट, ए<sub>ε,strong</sub><sup>(एन)</sup><math>\in\mathcal{X}</math> संतुष्ट करने वाले अनुक्रमों के समुच्चय के रूप में परिभाषित किया गया है
+यदि एक अनुक्रम ''x''<sub>1</sub>, ..., ''x<sub>n</sub>'' एक परिमित या एक अनंत वर्णमाला <math>\mathcal{X}</math> पर परिभाषित कुछ निर्दिष्ट संयुक्त वितरण से तैयार किया गया है, तो दृढ़ता से विशिष्ट समुच्चय, ''A''<sub>ε,strong</sub><sup>(''n'')</sup><math>\in\mathcal{X}</math> को अनुक्रमों के समुच्चय के रूप में परिभाषित किया गया है जो संतुष्ट करते हैं
 :<math>
 \left|\frac{N(x_i)}{n}-p(x_i)\right| < \frac{\varepsilon}{\|\mathcal{X}\|}.
 </math>
-कहाँ <math>{N(x_i)}</math> अनुक्रम में किसी विशिष्ट प्रतीक के घटित होने की संख्या है।
+जहां <math>{N(x_i)}</math> अनुक्रम में किसी विशिष्ट प्रतीक की घटनाओं की संख्या है।
-यह दिखाया जा सकता है कि दृढ़ता से विशिष्ट अनुक्रम भी कमजोर रूप से विशिष्ट होते हैं (एक अलग स्थिरांक के साथ), और इसलिए नाम। हालाँकि, दोनों रूप समतुल्य नहीं हैं। स्मृतिहीन चैनलों के लिए प्रमेयों को सिद्ध करने में मजबूत विशिष्टता के साथ काम करना अक्सर आसान होता है। हालाँकि, जैसा कि परिभाषा से स्पष्ट है, विशिष्टता का यह रूप केवल सीमित समर्थन वाले यादृच्छिक चर के लिए परिभाषित किया गया है।
+यह दिखाया जा सकता है कि दृढ़ता से विशिष्ट अनुक्रम भी दुर्बल रूप से विशिष्ट होते हैं (एक अलग स्थिरांक के साथ), और अतः इसका नाम दृढ़ विशिष्ट अनुक्रम रखा गया। हालाँकि, दोनों रूप समतुल्य नहीं हैं। स्मृतिहीन चैनलों के लिए प्रमेयों को सिद्ध करने के लिए सशक्त विशिष्टताओं के साथ काम करना प्रायः आसान होता है। हालाँकि, जैसा कि परिभाषा से स्पष्ट है, विशिष्टता का यह रूप केवल सीमित समर्थन वाले यादृच्छिक चर के लिए परिभाषित किया गया है।
 ==संयुक्त रूप से विशिष्ट अनुक्रम==
-दो क्रम <math>x^n</math> और <math>y^n</math> यदि जोड़ी संयुक्त रूप से ε-विशिष्ट है <math>(x^n,y^n)</math> संयुक्त वितरण के संबंध में ε-विशिष्ट है <math>p(x^n,y^n)=\prod_{i=1}^n p(x_i,y_i)</math> और दोनों <math>x^n</math> और <math>y^n</math> उनके सीमांत वितरण के संबंध में ε-विशिष्ट हैं <math>p(x^n)</math> और <math>p(y^n)</math>. अनुक्रमों के ऐसे सभी युग्मों का समुच्चय <math>(x^n,y^n)</math> द्वारा निरूपित किया जाता है <math>A_{\varepsilon}^n(X,Y)</math>. संयुक्त रूप से ε-विशिष्ट n-टुपल अनुक्रमों को समान रूप से परिभाषित किया गया है।
+दो अनुक्रम <math>x^n</math> और <math>y^n</math> संयुक्त रूप से ε-विशिष्ट हैं यदि जोड़ी <math>(x^n,y^n)</math> संयुक्त बंटन <math>p(x^n,y^n)=\prod_{i=1}^n p(x_i,y_i)</math> के संबंध में ε-विशिष्ट है और <math>x^n</math> और <math>y^n</math> दोनों अपने सीमांत वितरण <math>p(x^n)</math> और <math>p(y^n)</math> के संबंध में ε-विशिष्ट हैं। अनुक्रम <math>(x^n,y^n)</math> के ऐसे सभी युग्मों के समुच्चय को <math>A_{\varepsilon}^n(X,Y)</math> द्वारा निरूपित किया जाता है। संयुक्त रूप से ε-विशिष्ट n-टपल अनुक्रमों को समान रूप से परिभाषित किया जाता है।
-होने देना <math>\tilde{X}^n</math> और <math>\tilde{Y}^n</math> समान सीमांत वितरण वाले यादृच्छिक चर के दो स्वतंत्र अनुक्रम हों <math>p(x^n)</math> और <math>p(y^n)</math>. फिर किसी भी ε>0 के लिए, पर्याप्त रूप से बड़े n के लिए, संयुक्त रूप से विशिष्ट अनुक्रम निम्नलिखित गुणों को संतुष्ट करते हैं:
+मान लीजिए <math>\tilde{X}^n</math> और <math>\tilde{Y}^n</math> समान सीमांत वितरण <math>p(x^n)</math> और <math>p(y^n)</math> के साथ यादृच्छिक चर के दो स्वतंत्र अनुक्रम हैं। फिर किसी भी ε>0 के लिए, पर्याप्त रूप से बड़े n के लिए, संयुक्त रूप से विशिष्ट अनुक्रम निम्नलिखित गुणों को संतुष्ट करते हैं:
 #<math> P\left[ (X^n,Y^n) \in A_{\varepsilon}^n(X,Y) \right] \geqslant 1 - \epsilon </math>
 #<math> \left| A_{\varepsilon}^n(X,Y) \right| \leqslant 2^{n (H(X,Y) + \epsilon)} </math>
@@ Line 71: / Line 68: @@
 #<math> P\left[ (\tilde{X}^n,\tilde{Y}^n) \in A_{\varepsilon}^n(X,Y) \right] \leqslant 2^{-n (I(X;Y) - 3 \epsilon)} </math>
 #<math> P\left[ (\tilde{X}^n,\tilde{Y}^n) \in A_{\varepsilon}^n(X,Y) \right] \geqslant (1 - \epsilon) 2^{-n (I(X;Y) + 3 \epsilon)}</math>
-{{Expand section|date=December 2009}}
 ==विशिष्टता के अनुप्रयोग==
-{{Expand section|date=December 2009}}
+===विशिष्ट समुच्चय एन्कोडिंग===
+{{see|शैनन का सोर्स कोडिंग प्रमेय}}
-===विशिष्ट सेट एन्कोडिंग===
-{{see|Shannon's source coding theorem}}
-सूचना सिद्धांत में, विशिष्ट सेट एन्कोडिंग निश्चित लंबाई वाले ब्लॉक कोड वाले स्टोकेस्टिक स्रोत के विशिष्ट सेट में केवल अनुक्रमों को एन्कोड करता है। चूँकि सामान्य सेट का आकार लगभग 2 होता है<sup>nH(X)</sup>, कोडिंग के लिए केवल nH(X) बिट्स की आवश्यकता होती है, जबकि साथ ही यह सुनिश्चित किया जाता है कि एन्कोडिंग त्रुटि की संभावना ε तक सीमित है। असम्बद्ध रूप से, यह, एईपी द्वारा, दोषरहित है और स्रोत की एन्ट्रापी दर के बराबर न्यूनतम दर प्राप्त करता है।
-{{Expand section|date=December 2009}}
+सूचना सिद्धांत में, विशिष्ट समुच्चय एन्कोडिंग निश्चित लंबाई ब्लॉक कोड के साथ स्टोकेस्टिक स्रोत के विशिष्ट समुच्चय में केवल अनुक्रमों को एन्कोड करता है। चूँकि विशिष्ट समुच्चय का आकार लगभग ''2''<sup>nH(X)</sup> है, कोडिंग के लिए केवल ''nH(X)'' बिट्स की आवश्यकता होती है, जबकि साथ ही यह सुनिश्चित किया जाता है कि एन्कोडिंग त्रुटि की प्रायिकता ε तक सीमित है। असम्बद्ध रूप से, एईपी द्वारा, यह हानिरहित है और स्रोत की एन्ट्रॉपी दर के बराबर न्यूनतम दर प्राप्त करता है।
-===विशिष्ट सेट डिकोडिंग===
+===विशिष्ट समुच्चय डिकोडिंग===
-सूचना सिद्धांत में, विशिष्ट सेट डिकोडिंग का उपयोग [[यादृच्छिक कोडिंग]] के साथ मिलकर संचरित संदेश का अनुमान लगाने के लिए किया जाता है, जो एक कोडवर्ड के साथ होता है जो अवलोकन के साथ संयुक्त रूप से ε-विशिष्ट होता है। अर्थात।
+सूचना सिद्धांत में, विशिष्ट समुच्चय डिकोडिंग का उपयोग [[यादृच्छिक कोडिंग]] के साथ मिलकर संचरित संदेश का अनुमान लगाने के लिए किया जाता है, जो एक कोडवर्ड के साथ होता है जो अवलोकन के साथ संयुक्त रूप से ε-विशिष्ट होता है। अर्थात
 :<math>\hat{w}=w \iff (\exists w)( (x_1^n(w),y_1^n)\in A_{\varepsilon}^n(X,Y)) </math>
-कहाँ <math>\hat{w},x_1^n(w),y_1^n</math> संदेश का अनुमान, संदेश का कोडवर्ड हैं <math>w</math> और क्रमशः अवलोकन। <math>A_{\varepsilon}^n(X,Y)</math> संयुक्त वितरण के संबंध में परिभाषित किया गया है <math>p(x_1^n)p(y_1^n|x_1^n)</math> कहाँ <math>p(y_1^n|x_1^n)</math> संक्रमण संभाव्यता है जो चैनल आँकड़ों की विशेषता बताती है, और <math>p(x_1^n)</math> यह कुछ इनपुट वितरण है जिसका उपयोग यादृच्छिक कोडबुक में कोडवर्ड उत्पन्न करने के लिए किया जाता है।
+जहाँ <math>\hat{w},x_1^n(w),y_1^n</math> क्रमशः संदेश अनुमान, संदेश <math>w</math> का कोडवर्ड और अवलोकन हैं। <math>A_{\varepsilon}^n(X,Y)</math> को संयुक्त वितरण <math>p(x_1^n)p(y_1^n|x_1^n)</math> के संबंध में परिभाषित किया गया है जहां <math>p(y_1^n|x_1^n)</math> संक्रमण प्रायिकता है जो चैनल आंकड़ों की विशेषता है, और <math>p(x_1^n)</math> कुछ इनपुट वितरण है जो यादृच्छिक कोडबुक में कोडवर्ड उत्पन्न करने के लिए उपयोग किया जाता है।
-{{Expand section|date=December 2009}}
-===सार्वभौमिक शून्य-परिकल्पना परीक्षण===
-{{Empty section|date=December 2009}}
-===यूनिवर्सल चैनल कोड===
+===सार्वभौमिक शून्य (अक्षम)-परिकल्पना परीक्षण===
-{{Expand section|date=December 2009}}
+===सार्वभौमिक चैनल कोड===
-{{See also|algorithmic complexity theory}}
+{{See also|एल्गोरिदमिक सम्मिश्रता सिद्धांत}}
 ==यह भी देखें==
 * एसिम्प्टोटिक समविभाजन संपत्ति
 * [[स्रोत कोडिंग प्रमेय]]
-* [[शोर-चैनल कोडिंग प्रमेय]]
+* [[शोर-चैनल कोडिंग प्रमेय|नॉइज़ी-चैनल कोडिंग प्रमेय]]
 ==संदर्भ==
@@ Line 120: / Line 107: @@
 [[Category: Machine Translated Page]]
 [[Category:Created On 29/11/2023]]
+[[Category:Vigyan Ready]]

Anonymous

Search

विशिष्ट समुच्चय: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 10:36, 11 December 2023

Contents