यादृच्छिकता का परीक्षण कैसे करें (बिंदु में मामले - शफलिंग)

Question

सबसे पहले, यह प्रश्न this प्रश्न से बाहर निकला है। मैंने ऐसा इसलिए किया क्योंकि मुझे लगता है कि यह हिस्सा लंबे प्रश्न के उप-भाग से बड़ा है। अगर यह अपमानित करता है, तो कृपया मुझे माफ़ कर दो।

मान लें कि आपके पास एक एल्गोरिदम है जो यादृच्छिकता उत्पन्न करता है। अब आप इसका परीक्षण कैसे करते हैं? या अधिक प्रत्यक्ष होने के लिए - मान लें कि आपके पास एक एल्गोरिदम है जो कार्ड के डेक को घुमाता है, आप कैसे परीक्षण करते हैं कि यह एक बिल्कुल यादृच्छिक एल्गोरिदम है?

समस्या के लिए कुछ सिद्धांत जोड़ने के लिए - 52 में कार्ड का एक डेक शफल किया जा सकता है! (52 फैक्टोरियल) विभिन्न तरीकों से। कार्ड का एक डेक लें, इसे हाथ से घुमाएं और सभी कार्डों का ऑर्डर लिखें। संभावना क्या है कि आप वास्तव में उस शफल को प्राप्त कर लेते? उत्तर: 1/52!

शफल होने के बाद, आपको एक अनुक्रम में प्रत्येक सूट के ए, के, क्यू, जे ... प्राप्त करने का मौका क्या है? उत्तर 1/52!

तो, केवल एक बार झुकाव और नतीजे देखने से आपको अपने शफलिंग एल्गोरिदम यादृच्छिकता के बारे में बिल्कुल कोई जानकारी नहीं मिलेगी। दो बार और आपके पास अधिक जानकारी है, तीन और भी ...

आप ब्लैक बॉक्स को यादृच्छिकता के लिए एक शफलिंग एल्गोरिदम का परीक्षण कैसे करेंगे?

Answer 1

सांख्यिकी। आरएनजी परीक्षण के लिए वास्तविक तथ्य Diehard suite है। वैकल्पिक रूप से, Ent program उन परीक्षणों को प्रदान करता है जो व्याख्या करने के लिए सरल हैं लेकिन कम व्यापक हैं।

एल्गोरिदम को शफल करने के लिए, Fisher-Yates (a.k.a "Knuth Shuffle") जैसे एक प्रसिद्ध एल्गोरिदम का उपयोग करें। शफल एक समान रूप से यादृच्छिक होगा जब तक अंतर्निहित आरएनजी समान रूप से यादृच्छिक नहीं है। यदि आप जावा का उपयोग कर रहे हैं, तो यह एल्गोरिदम मानक पुस्तकालय में उपलब्ध है (Collections.shuffle देखें)।

यह शायद सबसे अनुप्रयोगों के लिए कोई फर्क नहीं पड़ता है, लेकिन ध्यान रखें कि अधिकांश RNGs स्वतंत्रता एक 52 पत्तों का डेक के हर संभव परिवर्तन का उत्पादन करने के लिए पर्याप्त डिग्री प्रदान नहीं करते हो (here समझाया गया है)।

Answer 2

बहुत कुछ शफल करें, और फिर परिणामों को रिकॉर्ड करें (यदि मैं इसे सही ढंग से पढ़ रहा हूं)। मुझे यादृच्छिक संख्या जनरेटर की तुलना देखना याद है। वे बस इसे और अधिक परीक्षण करते हैं, फिर परिणामों को ग्राफ़ करते हैं।

यदि यह वास्तव में यादृच्छिक है तो ग्राफ अधिकतर होगा।

Answer 3

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

बेशक, यदि आप ऐसा करते हैं, तो आप वास्तव में अपने इच्छित डेटा को बनाने के लिए अपने मॉडल सामान्य रूप से का उपयोग कर सकते हैं। और यदि आप ऐसा करते हैं, तो आप स्क्वायर वन पर वापस आ गए हैं।

Answer 4

मैं आपके प्रश्न का पूरी तरह से पालन नहीं कर रहा हूं।आप कहते हैं

मान लें कि आपके पास एक एल्गोरिदम है जो यादृच्छिकता उत्पन्न करता है। अब आप इसका परीक्षण कैसे करते हैं?

आपका क्या मतलब है? यदि आप मानते हैं कि आप यादृच्छिकता उत्पन्न कर सकते हैं, तो इसका परीक्षण करने की कोई आवश्यकता नहीं है।

एक बार आपके पास एक यादृच्छिक क्रम जनरेटर बनने के बाद, एक यादृच्छिक क्रमपरिवर्तन बनाना आसान है (उदाहरण के लिए अपने कार्ड 1-52 पर कॉल करें। 52 यादृच्छिक संख्याएं प्रत्येक को कार्ड में आवंटित करें, और फिर अपने 52 रैंडोम के अनुसार क्रमबद्ध करें) । आप अपने क्रमपरिवर्तन उत्पन्न करके अपने अच्छे आरएनजी की यादृच्छिकता को नष्ट नहीं करेंगे।

कठिन प्रश्न आप अपने RNG भरोसा कर सकते हैं कि क्या है। Here's किसी विशिष्ट संदर्भ में उस मुद्दे पर चर्चा करने वाले लोगों के लिए एक नमूना लिंक।

Answer 5

सबसे पहले, यह, any output is possible निश्चित रूप से जानना असंभव है "सही मायने में यादृच्छिक", अगर एक निश्चित परिमित उत्पादन होता है के बाद से के रूप में आप का कहना है।

क्या किया जा सकता, आउटपुट का एक अनुक्रम लेने के लिए और क्या अधिक होने की संभावना है के खिलाफ इस क्रम के विभिन्न माप की जांच करने के लिए है। आप आत्मविश्वास स्कोर प्राप्त कर सकते हैं कि उत्पन्न एल्गोरिदम एक अच्छा काम कर रहा है।

उदाहरण के लिए, आप 10 विभिन्न शफ़ल के उत्पादन में जांच कर सकता है। प्रत्येक कार्ड में 0-51 नंबर असाइन करें, और शफ़ल में स्थिति 6 में कार्ड का औसत लें। अभिसरण औसत 25.5 है, इसलिए आप यहां 1 का मान देखने के लिए आश्चर्यचकित होंगे। आप केंद्रीय सीमा प्रमेय का उपयोग अनुमान लगा सकते हैं कि प्रत्येक औसत किसी दिए गए स्थान के लिए कितना संभव है।

लेकिन हम यहीं समाप्त नहीं करना चाहिए! चूंकि इस एल्गोरिदम को एक सिस्टम द्वारा बेवकूफ बनाया जा सकता है जो केवल दो शफल के बीच वैकल्पिक होता है जो प्रत्येक स्थिति में 25.5 के सटीक औसत देने के लिए डिज़ाइन किए जाते हैं। हम कैसे बेहतर कर सकते हैं?

हम एक स्थिति में एक समान वितरण (किसी भी कार्ड के लिए बराबर संभावना), विभिन्न शफ़ल भर की उम्मीद है। तो 10 शफलों में से, हम यह सत्यापित करने का प्रयास कर सकते हैं कि विकल्प 'समान दिखें।' यह मूल रूप से मूल समस्या का एक कम संस्करण है। आप जांच सकते हैं कि मानक विचलन उचित दिखता है, कि न्यूनतम उचित है, और अधिकतम मूल्य भी है। आप अन्य मूल्यों को भी देख सकते हैं, जैसे कि निकटतम दो कार्ड्स (हमारे असाइन किए गए नंबरों से), भी समझ में आते हैं।

लेकिन हम इस विज्ञापन infinitum जैसे विभिन्न माप भी नहीं जोड़ सकते हैं, क्योंकि पर्याप्त आंकड़े दिए गए हैं, किसी भी विशेष शफल किसी कारण से अत्यधिक संभावना नहीं दिखाई देगा (उदाहरण के लिए यह बहुत कम शफल है जिसमें कार्ड एक्स, वाई , जेड क्रम में दिखाई देते हैं)। तो बड़ा सवाल यह है कि लेने के लिए माप का सही सेट कौन सा है? यहां मुझे यह मानना ​​है कि मुझे सबसे अच्छा जवाब नहीं पता है। हालांकि, यदि आपके पास एक निश्चित अनुप्रयोग है, तो आप परीक्षण करने के लिए गुणों/मापों का एक अच्छा सेट चुन सकते हैं, और उन लोगों के साथ काम कर सकते हैं - ऐसा लगता है कि क्रिप्टोग्राफ़रों ने चीजों को संभाला है।

Answer 6

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

नूथ के कंप्यूटर प्रोग्रामिंग के वॉल्यूम 2 ​​में कई परीक्षण दिए गए हैं जिन्हें आप अनुभाग 3.3.2 (अनुभवजन्य परीक्षण) और 3.3.4 (स्पेक्ट्रल टेस्ट) और उनके पीछे सिद्धांत में उपयोग कर सकते हैं।

Answer 7

परीक्षण 52! संभावनाएं बिल्कुल असंभव है।इसके बजाए, 3, 5, और 10 जैसे कार्डों की छोटी संख्याओं पर अपना शफल प्रयास करें। फिर आप अरबों शफल का परीक्षण कर सकते हैं और एक हिस्टोग्राम और ची-स्क्वायर सांख्यिकीय परीक्षण का उपयोग करके साबित कर सकते हैं कि प्रत्येक क्रमपरिवर्तन "यहां तक ​​कि" संख्या आ रहा है कई बार

Answer 8

अब तक कोई कोड नहीं है, इसलिए मैं मूल प्रश्न में my answer से एक परीक्षण भाग कॉपी-पेस्ट करता हूं।

// ... 
    int main() { 
    typedef std::map<std::pair<size_t, Deck::value_type>, size_t> Map; 
    Map freqs;  
    Deck d; 
    const size_t ntests = 100000; 

    // compute frequencies of events: card at position 
    for (size_t i = 0; i < ntests; ++i) { 
     d.shuffle(); 
     size_t pos = 0; 
     for(Deck::const_iterator j = d.begin(); j != d.end(); ++j, ++pos) 
     ++freqs[std::make_pair(pos, *j)]; 
    } 

    // if Deck.shuffle() is correct then all frequencies must be similar 
    for (Map::const_iterator j = freqs.begin(); j != freqs.end(); ++j) 
     std::cout << "pos=" << j->first.first << " card=" << j->first.second 
       << " freq=" << j->second << std::endl;  
    } 

यह कोड अंतर्निहित छद्म यादृच्छिक संख्या जेनरेटर की यादृच्छिकता का परीक्षण नहीं करता है। परीक्षण पीआरएनजी यादृच्छिकता विज्ञान की एक पूरी शाखा है।

Answer 9

यहां एक सरल जांच है जिसे आप कर सकते हैं। यह पीआई अनुमान लगाने के लिए उत्पन्न यादृच्छिक संख्या का उपयोग करता है। यह यादृच्छिकता का सबूत नहीं है, लेकिन गरीब आरएनजी आमतौर पर इस पर अच्छा प्रदर्शन नहीं करते हैं (वे 2.5 या 3.8 की बजाय कुछ वापस करेंगे ~ 3.14)।

आदर्श रूप से यह केवल कई परीक्षणों में से एक होगा जो आप यादृच्छिकता की जांच के लिए दौड़ेंगे।

कुछ और जो आप जांच सकते हैं आउटपुट के standard deviation है। 0/एन दृष्टिकोण एन/वर्ग (12) में मूल्यों की समान रूप से वितरित आबादी के लिए अपेक्षित मानक विचलन।

/** 
* This is a rudimentary check to ensure that the output of a given RNG 
* is approximately uniformly distributed. If the RNG output is not 
* uniformly distributed, this method will return a poor estimate for the 
* value of pi. 
* @param rng The RNG to test. 
* @param iterations The number of random points to generate for use in the 
* calculation. This value needs to be sufficiently large in order to 
* produce a reasonably accurate result (assuming the RNG is uniform). 
* Less than 10,000 is not particularly useful. 100,000 should be sufficient. 
* @return An approximation of pi generated using the provided RNG. 
*/ 
public static double calculateMonteCarloValueForPi(Random rng, 
                int iterations) 
{ 
    // Assumes a quadrant of a circle of radius 1, bounded by a box with 
    // sides of length 1. The area of the square is therefore 1 square unit 
    // and the area of the quadrant is (pi * r^2)/4. 
    int totalInsideQuadrant = 0; 
    // Generate the specified number of random points and count how many fall 
    // within the quadrant and how many do not. We expect the number of points 
    // in the quadrant (expressed as a fraction of the total number of points) 
    // to be pi/4. Therefore pi = 4 * ratio. 
    for (int i = 0; i < iterations; i++) 
    { 
     double x = rng.nextDouble(); 
     double y = rng.nextDouble(); 
     if (isInQuadrant(x, y)) 
     { 
      ++totalInsideQuadrant; 
     } 
    } 
    // From these figures we can deduce an approximate value for Pi. 
    return 4 * ((double) totalInsideQuadrant/iterations); 
} 

/** 
* Uses Pythagoras' theorem to determine whether the specified coordinates 
* fall within the area of the quadrant of a circle of radius 1 that is 
* centered on the origin. 
* @param x The x-coordinate of the point (must be between 0 and 1). 
* @param y The y-coordinate of the point (must be between 0 and 1). 
* @return True if the point is within the quadrant, false otherwise. 
*/ 
private static boolean isInQuadrant(double x, double y) 
{ 
    double distance = Math.sqrt((x * x) + (y * y)); 
    return distance <= 1; 
} 

Answer 10

इसे अपने आप को विचार है, मैं क्या होता है की तरह कुछ:

सेटअप (छद्म कोड)

// A card has a Number 0-51 and a position 0-51 
int[][] StatMatrix = new int[52][52]; // Assume all are set to 0 as starting values 
ShuffleCards(); 
ForEach (card in Cards) { 
    StatMatrix[Card.Position][Card.Number]++; 
} 

यह हमें एक मैट्रिक्स 52x52 यह दर्शाता है कि कितनी बार एक कार्ड समाप्त हो गया है देता है एक निश्चित स्थिति में। इसे बड़ी संख्या में दोहराएं (मैं 1000 से शुरू करूंगा, लेकिन मेरे आंकड़ों से बेहतर लोग बेहतर संख्या दे सकते हैं)।

मैट्रिक्स

विश्लेषण हम सही अनियमितता है और फेरबदल के समय की एक अनंत संख्या तो प्रत्येक कार्ड के लिए और समय की संख्या कार्ड उस स्थिति में समाप्त हो गया प्रत्येक स्थिति के लिए अच्छा प्रदर्शन करते हैं किसी के लिए के रूप में ही है अन्य कार्ड एक ही बात को एक अलग तरीके से कहकर:

statMatrix[position][card]/numberOfShuffle = 1/52. 

तो मैं गणना करूंगा कि हम उस संख्या से कितने दूर हैं।

Answer 11

यादृच्छिक चीज़ों से पहले अपने आउटपुट की तुलना में बस अपना आउटपुट देखें। यहां मैंने जो किया है उसका एक उदाहरण है।

public void testShuffleRemainingDeck() 
{ 
    System.out.println("ShuffleRemainingDeck"); 
    Deck instance = new Deck(true);    //create new deck 
    System.out.println(instance.toString()); //print unshuffled deck. 
    instance.ShuffleRemainingDeck();   //shuffle the deck. 
    System.out.println(instance.toString()); //print shuffled deck. 
               //now visually compare the outputs. 
} 

Answer 12

त्वरित परीक्षण के लिए, आप हमेशा इसे संपीड़ित करने का प्रयास कर सकते हैं। एक बार यह संपीड़ित नहीं हो जाता है, तो आप अन्य परीक्षणों पर जा सकते हैं।

मैंने मरने की कोशिश की है लेकिन यह एक शफल के लिए काम करने से इंकार कर देता है। सभी परीक्षण विफल यह भी वास्तव में stodgy है, यह आपको इच्छित मूल्यों की श्रेणी या उस तरह की कुछ निर्दिष्ट करने नहीं देगा।