libc यादृच्छिक संख्या जेनरेटर त्रुटिपूर्ण?

Question

संभावना का परीक्षण करने के लिए एक एल्गोरिदम पर विचार करें कि एक विशिष्ट संख्या को एक विशिष्ट संख्या के प्रयासों के बाद एन अद्वितीय संख्याओं के एक सेट से चुना जाता है (उदाहरण के लिए, एन = 2 के साथ, रूले (0 के बिना) में संभावना क्या है जो एक्स लेता है ब्लैक जीतने की कोशिश करता है?)।

इसके लिए सही वितरण पाउ (1-1/एन, एक्स -1) * (1/एन) है।

हालांकि, जब मैं निम्नलिखित कोड का उपयोग करके इसका परीक्षण करता हूं, तो एक्स = 31 में स्वतंत्र रूप से एन से स्वतंत्र रूप से बीज से एक गहरी खाई होती है।

क्या यह एक अंतर्निहित दोष है जिसे पीआरएनजी के कार्यान्वयन विनिर्देशों के उपयोग से रोका नहीं जा सकता है, क्या यह एक वास्तविक बग है, या क्या मैं कुछ स्पष्ट दिख रहा हूं?

// C 

#include <sys/times.h> 
#include <math.h> 
#include <stdio.h> 

int array[101]; 
void main(){ 

    int nsamples=10000000; 
    double breakVal,diffVal; 
    int i,cnt; 

    // seed, but doesn't change anything 
    struct tms time; 
    srandom(times(&time)); 

    // sample 
    for(i=0;i<nsamples;i++){ 
     cnt=1; 
     do{ 
      if((random()%36)==0) // break if 0 is chosen 
       break; 
      cnt++; 
     }while(cnt<100); 
     array[cnt]++; 
    } 

    // show distribution 
    for(i=1;i<100;i++){ 
     breakVal=array[i]/(double)nsamples; // normalize 
     diffVal=breakVal-pow(1-1/36.,i-1)*1/36.; // difference to expected value 
     printf("%d %.12g %.12g\n",i,breakVal,diffVal); 
    } 
} 

पर परीक्षण किया गया एक अप-टू-डेट Xubuntu 12.10 libc6 पैकेज 2.15-0ubuntu20 और इंटेल कोर SandyBridge i5-2500 साथ है, लेकिन मैं एक पुराने Ubuntu मशीन पर कुछ साल पहले पहले से ही इस खोज की।

मैं भी Unity3D/मोनो (यकीन नहीं जो मोनो संस्करण है, हालांकि) का उपयोग कर विंडोज 7 पर इस परीक्षण किया है, और यहाँ खाई जब, System.Random का उपयोग करते समय एकता के builtin Unity.Random नहीं दिखाई खाई है एक्स = 55 पर होता है (कम से कम एक्स < 100 के लिए नहीं)।

वितरण:

मतभेद:

Answer 1

यह glibc के random() समारोह पर्याप्त यादृच्छिक नहीं किया जा रहा की वजह से है। this page के अनुसार, random() द्वारा दिया यादृच्छिक संख्या के लिए, हमने:

oi = (oi-3 + oi-31) % 2^31

या:

oi = (oi-3 + oi-31 + 1) % 2^31।

अब xi = oi % 36 लें, और मान लें कि उपरोक्त पहला समीकरण एक है (यह प्रत्येक संख्या के लिए 50% मौका होता है)। अब xi-31=0 और xi-3!=0, तो संभावना है कि xi=0 1/36 से कम है। इसका कारण यह है समय oi-31 + oi-3 के 50% कम से कम 2^31 हो जाएगा है, और जब ऐसा होता है,

xi = oi % 36 = (oi-3 + oi-31) % 36 = oi-3 % 36 = xi-3,

जो अशून्य है। इससे 0 नमूने के बाद आपको 31 नमूने मिलते हैं।

Answer 2

इस प्रयोग में जो मापा जा रहा है वह बर्नौली प्रयोग के सफल परीक्षणों के बीच अंतराल है, जहां (ओपी में 36) के लिए सफलता को random() mod k == 0 के रूप में परिभाषित किया गया है। दुर्भाग्यवश, यह इस तथ्य से प्रभावित है कि random() के कार्यान्वयन का अर्थ है कि बर्नौली परीक्षण सांख्यिकीय रूप से स्वतंत्र नहीं हैं।

हम `यादृच्छिक() 'के ith उत्पादन के लिए rndi लिखेंगे और हम ध्यान दें कि:

संभावना 0,75

rndi = rndi-31 + rndi-3 + 1 संभावना 0 के साथ साथ rndi = rndi-31 + rndi-3    ।25

(एक सबूत रूपरेखा के लिए नीचे देखें।)

के rndi-31 mod k == 0 लगता है और हम वर्तमान में rndi देख रहे हैं। तो यह मामला होना चाहिए कि rndi-3 mod k ≠ 0, अन्यथा हम चक्र को k-3 की लंबाई के रूप में गिना होगा।

लेकिन (अधिकांश समय) (mod k): rndi = rndi-31 + rndi-3 = rndi-3 ≠ 0।

तो वर्तमान परीक्षण पिछले परीक्षणों से सांख्यिकीय रूप से स्वतंत्र नहीं है, और सफलता के बाद 31 ^सेंट परीक्षण के बाद परीक्षण सफल होने की संभावना कम होने की संभावना कम है, यह बर्नौली परीक्षणों की निष्पक्ष श्रृंखला में होगा।

रैखिक-संगत जेनरेटर का उपयोग करने में सामान्य सलाह, जो वास्तव में random() एल्गोरिदम पर लागू नहीं होती है, कम ऑर्डर बिट्स के बजाय उच्च-ऑर्डर बिट्स का उपयोग करना है, क्योंकि उच्च-आदेश बिट्स "अधिक यादृच्छिक हैं "(यानी, लगातार मूल्यों से कम सहसंबंधित)। लेकिन यह इस मामले में या तो काम नहीं करेगा, क्योंकि उपर्युक्त पहचान high log k bits फ़ंक्शन mod k == low log k bits के लिए समान रूप से अच्छी तरह से पकड़ती है।

असल में, हम उम्मीद कर सकते हैं कि हम एक रैखिक-संगत जनरेटर को बेहतर काम करने की उम्मीद कर सकते हैं, खासकर यदि हम उत्पादन के उच्च-आदेश बिट्स का उपयोग करते हैं, क्योंकि हालांकि एलसीजी मोंटे कार्लो सिमुलेशन में विशेष रूप से अच्छा नहीं है, लेकिन यह इससे ग्रस्त नहीं है random() की रैखिक प्रतिक्रिया।

---

random एल्गोरिथ्म, डिफ़ॉल्ट मामले के लिए:

state अहस्ताक्षरित देशांतर का एक वेक्टर बनें। एक बीज, कुछ निश्चित मान, और एक मिश्रण एल्गोरिदम का उपयोग कर state0...state30 शुरू करें। सादगी के लिए, हम राज्य वेक्टर को असीमित मान सकते हैं, हालांकि केवल अंतिम 31 मानों का उपयोग किया जाता है, इसलिए इसे वास्तव में रिंग बफर के रूप में लागू किया जाता है।

rndi: (Note: ⊕ उत्पन्न करने के लिए इसके अलावा आधुनिक 2 है)

statei = statei-31 ⊕ statei-3

rndi = (statei - (statei mod 2))/2

अब, ध्यान दें कि:।

(i + j) mod 2 = i mod 2 + j mod 2   i mod 2 == 0 यदि या j mod 2 == 0

(i + j) mod 2 = i mod 2 + j mod 2 - 2i mod 2 == 1 अगर और j mod 2 == 1

तो i और j समान रूप से वितरित कर रहे हैं, पहले मामले समय के 75%, और दूसरे मामले में 25% हो जाएगा।

तो, पीढ़ी सूत्र में प्रतिस्थापन द्वारा:

rndi = rndi-31 ⊕ rndi-3

:

rndi = (statei-31 ⊕ statei-3 - ((statei-31 + statei-3) mod 2))/2

     = ((statei-31 - (statei-31 mod 2)) ⊕ (statei-3 - (statei-3 mod 2)))/2 या

     = ((statei-31 - (statei-31 mod 2)) ⊕ (statei-3 - (statei-3 mod 2)) + 2)/2

दो मामलों आगे को कम किया जा सकता 363,210

rnd मैं = rnd मैं-31 ⊕ rnd मैं-3 + 1

जैसा कि ऊपर, पहले मामले समय का 75% होता है, कि rnd संभालने _मैं-31 और आरएनडी _i-3 स्वतंत्र रूप से एक समान वितरण से खींचे जाते हैं (जो वे नहीं हैं, लेकिन यह एक उचित पहला अनुमान है)।

Answer 3

जैसा कि अन्य ने बताया, random() पर्याप्त यादृच्छिक नहीं है।

निचले लोगों की बजाय उच्च बिट्स का उपयोग इस मामले में मदद नहीं करता है। मैनुअल के अनुसार (man 3 rand), पुरानाrand() के कार्यान्वयन के निचले बिट्स में समस्या थी। यही कारण है कि random() इसके बजाए अनुशंसित है। हालांकि, rand() का वर्तमान कार्यान्वयन उसी जनरेटर का उपयोग random() के रूप में करता है।

मैं पुराने rand() की सिफारिश की सही उपयोग की कोशिश की:

if ((int)(rand()/(RAND_MAX+1.0)*36)==0) 

... और एक्स = 31

Interstingly में एक ही गहरी खाई है, अगर मैं rand() की संख्या मिश्रण एक और अनुक्रम के साथ, मैं खाई से छुटकारा पाने:

unsigned x=0; 
//... 

     x = (179*x + 79) % 997; 
     if(((rand()+x)%36)==0) 

मैं एक पुरानेउपयोग कर रहा हूँ। मैंने प्रिम्स टेबल से यादृच्छिक रूप से 79, 17 9 और 997 का चयन किया। यह लंबाई 997

कहा की एक दोहरा अनुक्रम उत्पन्न करनी चाहिए, इस चाल शायद कुछ गैर अनियमितता, कुछ पदचिह्न शुरू की ... जिसके परिणामस्वरूप मिश्रित अनुक्रम निश्चित रूप से अन्य सांख्यिकीय परीक्षण असफल हो जायेगी। x लगातार पुनरावृत्तियों में एक ही मूल्य नहीं लेता है। वास्तव में, यह हर मूल्य दोहराने के लिए बिल्कुल 997 पुनरावृत्तियों लेता है।

'' [..] यादृच्छिक संख्या यादृच्छिक रूप से चुनी गई विधि के साथ उत्पन्न नहीं की जानी चाहिए। कुछ सिद्धांत इस्तेमाल किया जाना चाहिए। "(DEKnuth," आर्ट ऑफ़ कंप्यूटर प्रोग्रामिंग ", vol.2)

सिमुलेशन लिए, यदि आप सुनिश्चित करना चाहते हैं, का उपयोग Mersenne Twister