विशिष्ट समुच्चय

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

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

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

(कमजोर) विशिष्ट अनुक्रम (कमजोर विशिष्टता, एन्ट्रापी विशिष्टता)

यदि एक अनुक्रम x₁, ..., एक्स_n एक स्वतंत्र रूप से वितरित यादृच्छिक चर से तैयार किया गया है|i.i.d. वितरण X को एक परिमित वर्णमाला पर परिभाषित किया गया है ${\mathcal {X}}$, फिर विशिष्ट सेट, ए_ε^(एन)$\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)$

एक्स की सूचना एन्ट्रापी है। उपरोक्त संभावना केवल 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) विशिष्ट सेट का सदस्य होने की बहुत संभावना है, भले ही विशिष्ट सेट में सभी संभावित अनुक्रमों का केवल एक छोटा सा अंश शामिल हो। औपचारिक रूप से, कोई भी दिया गया $\varepsilon >0$, कोई n को इस प्रकार चुन सकता है कि:

1. X से अनुक्रम की प्रायिकता^(एन)ए से लिया जा रहा है_ε⁽ⁿ⁾ 1 − ε से बड़ा है, यानी। $Pr[x^{(n)}\in A_{\epsilon }^{(n)}]\geq 1-\varepsilon$
2. $\left|{A_{\varepsilon }}^{(n)}\right|\leqslant 2^{n(H(X)+\varepsilon )}$
3. $\left|{A_{\varepsilon }}^{(n)}\right|\geqslant (1-\varepsilon )2^{n(H(X)-\varepsilon )}$
4. अगर वितरण खत्म हो गया ${\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}}$.

AEP के साथ एक सामान्य स्टोकेस्टिक प्रक्रिया {X(t)} के लिए, (कमजोर) विशिष्ट सेट को p(x) के साथ समान रूप से परिभाषित किया जा सकता है₁, एक्स₂, ..., एक्स_n) को p(x) द्वारा प्रतिस्थापित किया गया₀^τ) (यानी समय अंतराल [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 है, जबकि

$-{\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 स्वतंत्र परीक्षणों में 0s और 1s की औसत संख्या वाले अनुक्रम होते हैं। इसे आसानी से प्रदर्शित किया जा सकता है: यदि 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₁, ..., एक्स_n एक परिमित या अनंत वर्णमाला पर परिभाषित कुछ निर्दिष्ट संयुक्त वितरण से लिया गया है ${\mathcal {X}}$, फिर दृढ़ता से विशिष्ट सेट, ए_ε,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 के लिए, संयुक्त रूप से विशिष्ट अनुक्रम निम्नलिखित गुणों को संतुष्ट करते हैं:

1. $P\left[(X^{n},Y^{n})\in A_{\varepsilon }^{n}(X,Y)\right]\geqslant 1-\epsilon$
2. $\left|A_{\varepsilon }^{n}(X,Y)\right|\leqslant 2^{n(H(X,Y)+\epsilon )}$
3. $\left|A_{\varepsilon }^{n}(X,Y)\right|\geqslant (1-\epsilon )2^{n(H(X,Y)-\epsilon )}$
4. $P\left[({\tilde {X}}^{n},{\tilde {Y}}^{n})\in A_{\varepsilon }^{n}(X,Y)\right]\leqslant 2^{-n(I(X;Y)-3\epsilon )}$
5. $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 )}$

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

विशिष्ट सेट एन्कोडिंग

Further information: Shannon's source coding theorem

सूचना सिद्धांत में, विशिष्ट सेट एन्कोडिंग निश्चित लंबाई वाले ब्लॉक कोड वाले स्टोकेस्टिक स्रोत के विशिष्ट सेट में केवल अनुक्रमों को एन्कोड करता है। चूँकि सामान्य सेट का आकार लगभग 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})$ यह कुछ इनपुट वितरण है जिसका उपयोग यादृच्छिक कोडबुक में कोडवर्ड उत्पन्न करने के लिए किया जाता है।

यूनिवर्सल चैनल कोड

See also: algorithmic complexity theory

यह भी देखें

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

संदर्भ

• 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