यादृच्छिकता परीक्षण
डेटा मूल्यांकन में एक यादृच्छिकता परीक्षण (या यादृच्छिकता के लिए परीक्षण), डेटा के एक सेट के वितरण का विश्लेषण करने के लिए उपयोग किया जाने वाला एक परीक्षण है, यह देखने के लिए कि क्या इसे यादृच्छिक (पैटर्न रहित) के रूप में वर्णित किया जा सकता है। स्टोकेस्टिक मॉडलिंग में, कुछ कंप्यूटर सिमुलेशन के रूप में, संभावित इनपुट डेटा की यादृच्छिकता के लिए आशा की जा सकती है, यादृच्छिकता के लिए एक औपचारिक परीक्षण द्वारा सत्यापित किया जा सकता है, यह दिखाने के लिए कि सिमुलेशन रन में उपयोग के लिए डेटा मान्य हैं। कुछ मामलों में, डेटा एक स्पष्ट गैर-यादृच्छिक पैटर्न प्रकट करता है, जैसा कि डेटा में तथाकथित रन के साथ होता है (जैसे कि यादृच्छिक 0–9 की उम्मीद करना लेकिन 4 3 2 1 0 4 3 2 1 ... और शायद ही कभी 4 से ऊपर जाना) . यदि डेटा का एक चयनित सेट परीक्षणों में विफल रहता है, तो मापदंडों को बदला जा सकता है या अन्य यादृच्छिक डेटा का उपयोग किया जा सकता है जो यादृच्छिकता के लिए परीक्षण पास करता है।
पृष्ठभूमि
यादृच्छिकता का मुद्दा एक महत्वपूर्ण दार्शनिक और सैद्धांतिक प्रश्न है। यादृच्छिकता के लिए टेस्ट का उपयोग यह निर्धारित करने के लिए किया जा सकता है कि डेटा सेट में पहचानने योग्य पैटर्न है या नहीं, जो इंगित करेगा कि जिस प्रक्रिया ने इसे उत्पन्न किया है वह काफी गैर-यादृच्छिक है। अधिकांश भाग के लिए, सांख्यिकीय विश्लेषण, व्यवहार में, यादृच्छिकता के परीक्षण के विपरीत डेटा में नियमितता खोजने के लिए अधिक चिंतित रहा है। आज उपयोग में आने वाले कई यादृच्छिक संख्या जेनरेटर एल्गोरिदम द्वारा परिभाषित किए जाते हैं, और वास्तव में छद्म-यादृच्छिक संख्या जेनरेटर भी हैं। वे जो अनुक्रम उत्पन्न करते हैं उन्हें छद्म-यादृच्छिक अनुक्रम कहा जाता है। ये जनरेटर हमेशा अनुक्रम उत्पन्न नहीं करते हैं जो पर्याप्त रूप से यादृच्छिक होते हैं, बल्कि इसके बजाय ऐसे अनुक्रम उत्पन्न कर सकते हैं जिनमें पैटर्न होते हैं। उदाहरण के लिए, कुख्यात RANDU दिनचर्या वर्णक्रमीय परीक्षण सहित कई यादृच्छिकता परीक्षणों को नाटकीय रूप से विफल करती है।
स्टीफन वोल्फ्राम ने यादृच्छिक संख्या उत्पन्न करने की अपनी क्षमता की जांच करने के लिए नियम 30 के आउटपुट पर यादृच्छिकता परीक्षण का इस्तेमाल किया,[1] हालांकि यह दिखाया गया था कि इसका प्रभावी कुंजी आकार इसके वास्तविक आकार से बहुत छोटा है[2] और ची-चुकता परीक्षण में खराब प्रदर्शन करने के लिए।[3] एक अकल्पनीय यादृच्छिक संख्या जनरेटर का उपयोग सांख्यिकीय मान्यताओं का उल्लंघन करके एक प्रयोग की वैधता को संदेह में डाल सकता है। हालांकि आमतौर पर एनआईएसटी मानकों जैसे सांख्यिकीय परीक्षण तकनीकों का उपयोग किया जाता है, योंगगे वांग ने दिखाया कि एनआईएसटी मानक पर्याप्त नहीं हैं। इसके अलावा, योंगगे वैंग[4] डिजाइन किए गए सांख्यिकीय-दूरी-आधारित और कानून-के-पुनरावृत्त-लघुगणक-आधारित परीक्षण तकनीकें। इस तकनीक का उपयोग करते हुए, योंगगे वैंग और टोनी निकोल[5] आमतौर पर उपयोग किए जाने वाले छद्म यादृच्छिक जनरेटर जैसे प्रसिद्ध रैंडम नंबर जनरेटर अटैक # डेबियन ओपनएसएसएल में कमजोरी का पता लगाया गया था जिसे 2008 में तय किया गया था।
यादृच्छिकता के लिए विशिष्ट परीक्षण
व्यवहार में उपयोग किए जाने वाले विभिन्न प्रकार के (छद्म-) यादृच्छिक संख्या जनरेटर की काफी कम संख्या रही है। वे यादृच्छिक संख्या जनरेटर की सूची में पाए जा सकते हैं, और इसमें शामिल हैं:
- रैखिक सर्वांगसम जनरेटर और लीनियर-फीडबैक शिफ्ट रजिस्टर
- सामान्यीकृत फाइबोनैचि जनरेटर
- क्रिप्टोग्राफिक जनरेटर
- द्विघात सर्वांगसम जनरेटर
- सेलुलर automaton जनरेटर
- [[छद्म आयामी द्विआधारी अनुक्रम]]
स्वीकृत टेस्ट सूट को पास करने में इन अलग-अलग जनरेटर के पास अलग-अलग डिग्री की सफलता है। कई व्यापक रूप से उपयोग किए जाने वाले जेनरेटर परीक्षणों को अधिक या कम बुरी तरह विफल करते हैं, जबकि अन्य 'बेहतर' और पूर्व जेनरेटर (इस अर्थ में कि वे परीक्षणों की सभी मौजूदा बैटरी पास कर चुके हैं और वे पहले से मौजूद हैं) को काफी हद तक नजरअंदाज कर दिया गया है।
एक द्विआधारी अनुक्रम के लिए यादृच्छिकता के कई व्यावहारिक उपाय हैं। इनमें सांख्यिकीय परीक्षण, हैडमार्ड परिवर्तन, और जटिलता या इनके मिश्रण के आधार पर उपाय शामिल हैं। परीक्षणों का एक प्रसिद्ध और व्यापक रूप से उपयोग किया जाने वाला संग्रह डाईहार्ड परीक्षण था, जिसे मार्सग्लिया द्वारा प्रस्तुत किया गया था; इसे L'Ecuyer और Simard द्वारा TestU01 सुइट तक बढ़ाया गया था। यादृच्छिकता को मापने के लिए हैडमार्ड रूपांतरण का उपयोग सुभाष काक | एस द्वारा प्रस्तावित किया गया था। काक और फिलिप्स, यूएन, हॉपकिंस, बेथ और दाई, मुंड और जॉर्ज मार्सग्लिया और ज़मान द्वारा विकसित किया गया।[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
