यादृच्छिकता परीक्षण
डेटा मूल्यांकन में यादृच्छिकता परीक्षण (या यादृच्छिकता के लिए परीक्षण) डेटा के सेट के वितरण का विश्लेषण करने के लिए उपयोग किया जाने वाला परीक्षण है एवं यह देखने के लिए कि क्या इसे यादृच्छिक (पैटर्न रहित) के रूप में वर्णित किया जा सकता है। स्टोकेस्टिक मॉडलिंग में कुछ कंप्यूटर सिमुलेशन के रूप में संभावित इनपुट डेटा की यादृच्छिकता हेतु अपेक्षा की जा सकती है तथा यादृच्छिकता के लिए औपचारिक परीक्षण द्वारा सत्यापित किया जा सकता है एवं यह दिखाने के लिए कि सिमुलेशन रन में उपयोग के लिए डेटा मान्य हैं। कुछ स्थितियों में डेटा स्पष्ट गैर-यादृच्छिक बनावट प्रकट करता है जैसा कि डेटा में तथाकथित रन के साथ होता है (जैसे कि यादृच्छिक 0–9 की अपेक्षा करना परन्तु 4 3 2 1 0 4 3 2 1 ... और संभवतः ही कभी 4 से ऊपर जाना)। यदि डेटा का चयनित सेट परीक्षणों में विफल रहता है तो मापदंडों को परिवर्तित किया जा सकता है या अन्य यादृच्छिक डेटा का उपयोग किया जा सकता है जो यादृच्छिकता के लिए परीक्षण में सफल होता है।
पृष्ठभूमि
यादृच्छिकता का विवाद महत्वपूर्ण दार्शनिक और सैद्धांतिक प्रश्न है। यादृच्छिकता के लिए परीक्षण का उपयोग यह निर्धारित करने के लिए किया जा सकता है कि डेटा सेट में पहचानने योग्य पैटर्न है या नहीं जो इंगित करेगा कि जिस प्रक्रिया ने इसे उत्पन्न किया है वह अधिक गैर-यादृच्छिक है। अधिकांश भाग के लिए सांख्यिकीय विश्लेषण व्यवहार में यादृच्छिकता के परीक्षण के विपरीत डेटा में नियमितता खोजने के लिए अधिक चिंतित रहा है। आज उपयोग में आने वाले कई यादृच्छिक संख्या जेनरेटर एल्गोरिदम द्वारा परिभाषित किए जाते हैं और वास्तव में छद्म-यादृच्छिक संख्या जेनरेटर भी हैं। वे जो अनुक्रम उत्पन्न करते हैं उन्हें छद्म-यादृच्छिक अनुक्रम कहा जाता है। ये जनरेटर सदैव अनुक्रम उत्पन्न नहीं करते हैं जो पर्याप्त रूप से यादृच्छिक होते हैं बल्कि इसके स्थान पर ऐसे अनुक्रम उत्पन्न कर सकते हैं जिनमें पैटर्न होते हैं। उदाहरण के लिए कुख्यात RANDU नियमित वर्णक्रमीय परीक्षण सहित कई यादृच्छिकता परीक्षणों को नाटकीय रूप से विफल करती है।
स्टीफन वोल्फ्राम ने यादृच्छिक संख्या उत्पन्न करने की अपनी क्षमता की जांच करने के लिए नियम 30 के आउटपुट पर यादृच्छिकता परीक्षण का उपयोग किया[1] तथा इसके माध्यम से यह प्रदर्शित किया गया था कि इसका प्रभावी कुंजी आकार इसके वास्तविक आकार से बहुत छोटा है[2] और ची-वर्ग परीक्षण में अनुपयुक्त प्रदर्शन करता है।[3] अकल्पनीय यादृच्छिक संख्या जनरेटर का उपयोग सांख्यिकीय मान्यताओं का उल्लंघन करके एक प्रयोग की वैधता को संदेह में डाल सकता है। जबकि सामान्य रूप से NIST मानकों जैसे सांख्यिकीय परीक्षण तकनीकों का उपयोग किया जाता है तथा योंगगे वांग ने दिखाया कि NIST मानक पर्याप्त नहीं हैं। इसके अतिरिक्त योंगगे वैंग[4] रूपित किए गए सांख्यिकीय-दूरी-आधारित और नियम-के-पुनरावृत्त-लघुगणक-आधारित परीक्षण तकनीकें। इस तकनीक का उपयोग करते हुए योंगगे वैंग और टोनी निकोल[5] ने सामान्य रूप से उपयोग किए जाने वाले छद्म यादृच्छिक जनरेटर में कमी का पता लगाया जैसे कि ओपनएसएसएल छद्म यादृच्छिक जनरेटर का प्रसिद्ध डेबियन संस्करण जिसे 2008 में ठीक किया गया था।
यादृच्छिकता के लिए विशिष्ट परीक्षण
व्यवहार में उपयोग किए जाने वाले विभिन्न प्रकार के (छद्म-) यादृच्छिक संख्या जनरेटर की बहुत कम संख्या रही है। वे यादृच्छिक संख्या जनरेटर की सूची में प्राप्त किये जा सकते हैं और इसमें सम्मिलित हैं:
- रैखिक सर्वांगसम जनरेटर और लीनियर-फीडबैक शिफ्ट रजिस्टर
- सामान्यीकृत फाइबोनैचि जनरेटर
- क्रिप्टोग्राफिक जनरेटर
- द्विघात सर्वांगसम जनरेटर
- सेलुलर स्वचालन जनरेटर
- [[छद्म आयामी द्विआधारी अनुक्रम]]
स्वीकृत परीक्षण सूट को पास करने में इन भिन्न-भिन्न जनरेटर के पास भिन्न-भिन्न डिग्री की सफलता है। कई व्यापक रूप से उपयोग किए जाने वाले जेनरेटर परीक्षणों को अधिक या कम बुरी तरह विफल करते हैं, जबकि अन्य 'बेहतर' और पूर्व जेनरेटर (इस अर्थ में कि वे परीक्षणों की सभी मौजूदा बैटरी पास कर चुके हैं और वे पहले से मौजूद हैं) को काफी हद तक नजरअंदाज कर दिया गया है।
द्विआधारी अनुक्रम के लिए यादृच्छिकता के कई व्यावहारिक उपाय हैं। इनमें सांख्यिकीय परीक्षण, हैडमार्ड परिवर्तन, और जटिलता या इनके मिश्रण के आधार पर उपाय सम्मिलित हैं। परीक्षणों का एक प्रसिद्ध और व्यापक रूप से उपयोग किया जाने वाला संग्रह डाईहार्ड परीक्षण था जिसे मार्सग्लिया द्वारा प्रस्तुत किया गया था तथा इसे एल'इक्यूयर और सीमार्ड द्वारा U01परीक्षण तक बढ़ाया गया था। यादृच्छिकता को मापने के लिए हैडमार्ड रूपांतरण का उपयोग सुभाष काक द्वारा प्रस्तावित किया गया था। काक और फिलिप्स, यूएन, हॉपकिंस, बेथ और दाई, मुंड और जॉर्ज मार्सग्लिया और ज़मान द्वारा विकसित किया गया।[6]
इनमें से कई परीक्षण जो रैखिक जटिलता के हैं, यादृच्छिकता के वर्णक्रमीय उपाय प्रदान करते हैं। टी. बेथ और जेड-डी. दाई ने प्रदर्शित किया कि कोल्मोगोरोव जटिलता और रैखिक जटिलता व्यावहारिक रूप से समान हैं[7] जबकि वाई. वांग ने इसके पश्चात दिखाया कि उनके कथन गलत हैं।[8] इसके पश्चात भी वांग ने यह भी प्रदर्शित किया कि मार्टिन-लोफ यादृच्छिक अनुक्रमों के लिए कोल्मोगोरोव जटिलता अनिवार्य रूप से रैखिक जटिलता के समान है।
ये व्यावहारिक परीक्षण स्ट्रिंग (कंप्यूटर विज्ञान) की यादृच्छिकता की तुलना करना संभव बनाते हैं। संभाव्य आधार पर दी गई लंबाई के सभी स्ट्रिंग में समान यादृच्छिकता होती है। जबकि भिन्न-भिन्न स्ट्रिंग में एक अलग कोलमोगोरोव जटिलता है। उदाहरण के लिए निम्नलिखित दो स्ट्रिंग पर विचार करें।
- स्ट्रिंग 1:
0101010101010101010101010101010101010101010101010101010101010101 - स्ट्रिंग 2:
1100100001100001110111101110110011111010010000100101011110010110
स्ट्रिंग 1 संक्षिप्त भाषाई विवरण स्वीकार करता है: '01' के 32 दोहराव। इस विवरण में 22 अक्षर हैं और इसे कुछ आधार अनुक्रमों से कुशलतापूर्वक बनाया जा सकता है।[clarification needed] स्ट्रिंग 2 में स्वयं स्ट्रिंग लिखने के अतिरिक्त कोई स्पष्ट सरल विवरण नहीं है जिसमें 64 वर्ण हैं[clarification needed] और इसका कोई तुलनात्मक रूप से कुशल आधार फ़ंक्शन प्रतिनिधित्व नहीं है। लीनियर हैडमार्ड स्पेक्ट्रल परीक्षण (हैडमार्ड ट्रांसफ़ॉर्म देखें) का उपयोग करते हुए इनमें से पहला क्रम दूसरे की तुलना में बहुत कम यादृच्छिकता वाला पाया जाएगा जो सहज ज्ञान से सहमत है।
उल्लेखनीय सॉफ्टवेयर कार्यान्वयन
यह भी देखें
- यादृच्छिकता
- सांख्यिकीय यादृच्छिकता
- एल्गोरिथम यादृच्छिक अनुक्रम
- यादृच्छिकता की सात अवस्थाएँ
- वाल्ड–वोल्फोवित्ज़ परीक्षण चलाता है
टिप्पणियाँ
- ↑ Wolfram, Stephen (2002). एक नए तरह का विज्ञान. Wolfram Media, Inc. pp. 975–976. ISBN 978-1-57955-008-0.
- ↑ Willi Meier; Othmar Staffelbach (1991), "Analysis of pseudo random sequences generated by cellular automata", Advances in Cryptology: Proc. Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT '91. Lecture Notes in Computer Science 547: 186
- ↑ Moshe Sipper; Marco Tomassini (1996), "Generating parallel random number generators by cellular programming", International Journal of Modern Physics C, 7 (2): 181–190, Bibcode:1996IJMPC...7..181S, CiteSeerX 10.1.1.21.870, doi:10.1142/S012918319600017X.
- ↑ Yongge Wang. On the Design of LIL Tests for (Pseudo) Random Generators and Some Experimental Results, http://webpages.uncc.edu/yonwang/, 2014
- ↑ Yongge Wang; Tony Nicol (2014), "Statistical Properties of Pseudo Random Sequences and Experiments with PHP and Debian OpenSSL", Esorics 2014, LNCS 8712: 454–471
- ↑ Terry Ritter, "Randomness tests: a literature survey", webpage: CBR-rand.
- ↑ Beth, T. and Z-D. Dai. 1989. On the Complexity of Pseudo-Random Sequences -- or: If You Can Describe a Sequence It Can't be Random. Advances in Cryptology -- EUROCRYPT '89. 533-543. Springer-Verlag
- ↑ Yongge Wang 1999. Linear complexity versus pseudorandomness: on Beth and Dai's result. In: Proc. Asiacrypt 99, pages 288--298. LNCS 1716, Springer Verlag
- ↑ ENT: A Pseudorandom Number Sequence Test Program, Fourmilab, 2008.
- ↑ A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications, Special Publication 800-22 Revision 1a, National Institute of Standards and Technology, 2010.
- ↑ Implementation of the NIST Statistical Test Suite
बाहरी संबंध
- Randomness tests included in the Cryptographic Toolkit from NIST
- George Marsaglia, Wai Wan Tsang (2002), "Some Difficult-to-pass Tests of Randomness", Journal of Statistical Software, Volume 7, Issue 3
- DieHarder: A Random Number Test Suite by Robert G. Brown, Duke University
- Online Random Number Generator Analysis from CAcert.org
