पुनः उपयोग जलाशय नमूने में यादृच्छिक संख्या

Question

यह हाल ही में एक और सवाल के संबंध में पूछा गया था: Given an unknown length list, return a random item in it by scanning it only 1 time

मुझे पता है तुम नहीं करना चाहिए, मैं सिर्फ क्यों नहीं की एक विहित स्पष्टीकरण पर मेरी उंगली नहीं डाल सकते हैं। उदाहरण के कोड पर

देखो:

import random, sys 

def rnd(): # a function that returns a random number each call 
    return int(random.getrandbits(32)) 

class fixed: # a functor that returns the same random number each call 
    def __init__(self): 
     self._ret = rnd() 
    def __call__(self): 
     return self._ret 

def sample(rnd,seq_size): 
    choice = 0 
    for item in xrange(1,seq_size): 
     if (rnd() % (item+1)) == 0: 
      choice = item 
    return choice 

dist = [0 for i in xrange(500)] 
for i in xrange(1000): 
    dist[sample(rnd,len(dist))] += 1 
print "real",dist 
print 

dist = [0 for i in xrange(500)] 
for i in xrange(1000): 
    dist[sample(fixed(),len(dist))] += 1 
print "reuse",dist 

उचित जलाशय नमूने उत्पन्न करता है कि आइटम प्रति एक नई यादृच्छिक संख्या अच्छी तरह से समान रूप से वितरित किया जाता है के रूप में यह होना चाहिए के लिए विकल्पों

:

real [1, 3, 0, 1, 2, 3, 2, 3, 1, 2, 2, 2, 2, 0, 0, 1, 3, 3, 4, 0, 2, 1, 2, 1, 1, 4, 0, 3, 1, 1, 2, 0, 0, 0, 1, 4, 6, 2, 3, 1, 1, 3, 2, 1, 3, 3, 1, 4, 1, 1, 2, 2, 5, 1, 2, 1, 0, 3, 1, 0, 2, 6, 1, 2, 2, 1, 1, 1, 1, 3, 2, 1, 5, 4, 0, 3, 3, 4, 0, 0, 2, 1, 3, 2, 3, 0, 2, 4, 6, 3, 0, 1, 3, 0, 2, 2, 4, 3, 2, 1, 2, 1, 2, 2, 1, 4, 2, 0, 0, 1, 1, 0, 1, 4, 2, 2, 2, 1, 0, 3, 1, 2, 1, 0, 2, 2, 1, 5, 1, 5, 3, 3, 1, 0, 2, 2, 0, 3, 2, 3, 0, 1, 1, 3, 0, 1, 2, 2, 0, 1, 2, 2, 3, 2, 3, 1, 1, 0, 1, 2, 2, 2, 2, 2, 3, 2, 1, 2, 2, 2, 1, 3, 3, 1, 0, 1, 1, 0, 1, 3, 2, 1, 4, 3, 4, 1, 1, 1, 2, 1, 2, 0, 0, 0, 1, 1, 2, 6, 0, 1, 1, 0, 1, 0, 1, 2, 2, 3, 0, 1, 2, 2, 1, 0, 4, 2, 1, 2, 2, 0, 4, 4, 0, 3, 2, 2, 1, 2, 4, 1, 2, 1, 0, 2, 1, 1, 5, 1, 2, 2, 3, 2, 3, 0, 1, 2, 3, 2, 5, 2, 3, 0, 1, 1, 1, 1, 3, 4, 2, 4, 1, 2, 3, 2, 5, 2, 1, 0, 1, 1, 2, 2, 3, 1, 1, 1, 2, 1, 2, 0, 4, 1, 1, 2, 3, 4, 3, 1, 2, 3, 3, 3, 2, 1, 2, 0, 0, 4, 3, 2, 2, 5, 5, 3, 3, 3, 1, 0, 1, 3, 1, 1, 2, 4, 3, 1, 4, 4, 2, 5, 0, 5, 4, 2, 1, 0, 4, 1, 3, 3, 2, 4, 2, 3, 3, 1, 3, 3, 4, 2, 2, 1, 1, 1, 1, 3, 3, 5, 3, 2, 4, 0, 1, 3, 2, 2, 4, 2, 2, 3, 4, 5, 3, 2, 1, 2, 3, 2, 2, 2, 4, 4, 0, 1, 3, 3, 3, 4, 1, 2, 4, 0, 4, 0, 3, 2, 1, 1, 4, 2, 1, 0, 0, 0, 4, 2, 2, 1, 4, 3, 1, 1, 3, 2, 4, 3, 4, 2, 1, 1, 2, 2, 3, 3, 1, 2, 2, 1, 1, 2, 3, 1, 9, 1, 3, 4, 2, 4, 4, 0, 1, 0, 1, 0, 2, 1, 0, 1, 2, 3, 3, 6, 2, 2, 1, 2, 4, 3, 3, 3, 2, 1, 2, 1, 2, 8, 2, 3, 1, 5, 3, 0, 2, 1, 1, 4, 2, 2, 1, 2, 3, 2, 1, 0, 4, 3, 4, 3, 1, 3, 2, 3, 2, 2, 1, 0, 1, 2, 5, 3, 0, 3, 1, 2, 2, 2, 1, 0, 1, 4] 

जबकि जब आप सभी वस्तुओं के लिए एक ही यादृच्छिक संख्या का पुनः उपयोग करते हैं, तो आपको बहुत कम संख्या में एक वितरण मिलता है:

reuse [92, 50, 34, 19, 23, 16, 13, 9, 9, 9, 11, 10, 6, 7, 8, 5, 5, 6, 4, 2, 2, 3, 2, 3, 3, 6, 6, 1, 4, 3, 5, 2, 2, 1, 1, 2, 3, 4, 3, 4, 1, 3, 1, 0, 0, 1, 5, 3, 1, 2, 0, 2, 0, 1, 1, 6, 2, 0, 2, 2, 4, 2, 2, 0, 2, 2, 2, 0, 3, 0, 4, 1, 2, 1, 4, 2, 2, 0, 1, 0, 1, 1, 0, 0, 0, 2, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 2, 0, 0, 1, 2, 1, 3, 1, 0, 1, 2, 0, 4, 3, 0, 0, 2, 0, 0, 1, 0, 0, 2, 0, 2, 1, 0, 1, 0, 0, 1, 1, 3, 0, 1, 1, 0, 2, 0, 1, 2, 0, 1, 1, 4, 1, 1, 1, 2, 1, 0, 1, 2, 0, 2, 1, 1, 2, 0, 1, 1, 0, 2, 0, 2, 0, 0, 2, 0, 1, 0, 2, 1, 1, 0, 0, 1, 2, 4, 1, 0, 2, 0, 1, 2, 1, 3, 0, 1, 0, 0, 1, 0, 0, 2, 1, 0, 0, 0, 3, 2, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 4, 1, 0, 2, 1, 0, 0, 2, 1, 1, 3, 3, 2, 0, 1, 0, 2, 0, 1, 1, 0, 0, 3, 1, 0, 0, 1, 0, 3, 2, 2, 0, 0, 0, 0, 0, 2, 0, 1, 0, 2, 0, 4, 1, 0, 0, 2, 0, 1, 1, 0, 0, 3, 1, 3, 2, 2, 1, 3, 1, 2, 0, 1, 1, 3, 0, 3, 1, 2, 0, 2, 0, 2, 0, 3, 0, 3, 0, 3, 1, 0, 2, 3, 1, 1, 0, 1, 3, 3, 1, 1, 1, 0, 2, 1, 1, 4, 1, 1, 1, 2, 0, 3, 1, 1, 0, 4, 1, 1, 0, 1, 3, 1, 0, 1, 1, 0, 3, 3, 0, 2, 4, 0, 1, 2, 1, 6, 1, 0, 0, 0, 0, 1, 2, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 4, 2, 0, 1, 2, 0, 1, 4, 1, 2, 0, 5, 2, 2, 0, 6, 2, 2, 1, 3, 0, 3, 1, 1, 0, 3, 1, 4, 2, 0, 1, 0, 1, 2, 3, 1, 1, 3, 0, 0, 0, 1, 1, 4, 3, 3, 0, 0, 1, 0, 1, 1, 2, 1, 0, 2, 1, 4, 5, 1, 1, 3, 0, 1, 1, 1, 3, 1, 1, 0, 3, 3, 1, 3, 0, 1, 0, 0, 1, 1, 3, 2, 1, 0, 3, 1, 1, 3, 1, 3, 1, 2, 2, 2, 0, 0, 5, 1, 3, 0, 1, 4, 1, 1, 1, 3, 2, 1, 3, 2, 1, 3, 1, 2, 2, 3, 2, 2, 1, 0, 3, 3, 1, 3, 3, 3, 2, 1, 2, 3, 3, 3, 1, 2, 2, 2, 4, 2, 1, 5, 2, 2, 0] 

यहां गणित क्या है? आप एक ही यादृच्छिक संख्या का पुनः उपयोग क्यों नहीं कर सकते?

Answer 1

संपादित करें, जवाब में टिप्पणी करने के लिए:

रास्ता जलाशय नमूना चाहिए काम है: आप के साथ एक अतिरिक्त बिन बनाने के लिए में मौजूदा डिब्बे में से प्रत्येक से नमूनों की बिल्कुल सही अनुपात का चयन करना चाहते एक ही संभावना है। आपके sample() लूप में, यह देखते हुए कि आपने item डिब्बे में से किसी एक को यादृच्छिक रूप से नमूना दिया है, आपको प्रत्येक बिन से संभाव्यता 1/(item + 1) के नमूने चुनने की आवश्यकता है।

हालांकि, fixed() के साथ, चयन निर्णय और पिछला बिन नंबर दोनों एक ही निश्चित 32-बिट संख्या पर निर्भर करता है। इसका मतलब यह है कि प्रत्येक डिब्बे से एक नमूना हटा दिया गया संभावना समान नहीं होगी।

---

पर विचार करें क्या sample() पाश की तीसरी यात्रा के दौरान होता है। आपके पास तीन मौजूदा डिब्बे (0, 1, और 2) हैं, और आप प्रत्येक में नमूने के 1/4 को चुनना चाहते हैं और उन्हें नए बनाए गए बिन में जोड़ना चाहते हैं 3.

ध्यान दें कि सभी 32-बिट fixed() संख्याएं बिन 1 में भी होगा (क्योंकि पहले पास सभी संख्याओं को 2 से विभाजित किया गया है), और बिन 0 में सभी संख्याएं विषम होंगी (क्योंकि यहां तक ​​कि किसी को भी बिन 1 में ले जाया गया था)। दूसरा पास सभी संख्याओं को तीन से बिन 2 तक विभाजित करता है (जो अब तक ठीक होना चाहिए, और डिब्बे 0 और 1 में भी विषम विभाजन को नहीं बदलता है)।

तीसरा पास तब सभी fixed() संख्या 4 को 4 बिन में विभाजित करता है। लेकिन, यह बिन 1 से आधे संख्याओं का चयन करेगा (क्योंकि सभी का आधा भी संख्या 4 से विभाजित है), और बिन से कोई भी संख्या नहीं 0 (क्योंकि वे सभी विषम हैं)। तो, भले ही नए बिन का अपेक्षित आकार सही होना चाहिए, पुराने डिब्बे के अपेक्षित आकार अब समान नहीं हैं।

इस प्रकार fixed() एक असमान वितरण उत्पन्न करता है: अंतर्निहित धारणा, कि आप एक यादृच्छिक संख्या चुनकर प्रत्येक बिन का सटीक अंश चुन सकते हैं, उल्लंघन किया जाता है यदि वह संख्या चुनने के लिए उपयोग की जाने वाली संख्याओं पर अनुमानित तरीके से निर्भर करती है मूल बिन

---

यादृच्छिक संख्याओं की मूल संपत्ति यह है कि प्रत्येक नमूना को पहले के नमूने से स्वतंत्र रूप से वितरित किया जाना चाहिए, सांख्यिकीय अर्थ में। यादृच्छिक संख्याओं के आधार पर एल्गोरिदम इस संपत्ति पर निर्भर करते हैं।

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

वही यादृच्छिक संख्या दोबारा उपयोग करके आप यहां क्या प्रयास कर रहे हैं, एक खराब पीआरएनजी बना रहा है। वास्तविक परिणाम कैसे आवेदन यादृच्छिक संख्या का उपयोग करता है के विवरण पर निर्भर करती है ...

हालांकि fixed() एक जानबूझकर टूट PRNG, है कई वाणिज्यिक लाइब्रेरी की PRNG "कमज़ोर" कर रहे हैं, और इसी तरह की अजीब संबंधों के साथ खत्म हो सकता है कुछ अनुप्रयोगों के साथ। एक व्यावहारिक मामले के रूप में, "कमजोरी" आवेदन के सापेक्ष है - और, जबकि सांख्यिकीय परीक्षण हैं जो कमजोर पीआरएनजी का पर्दाफाश करने की कोशिश करने के लिए व्यापक रूप से उपयोग किए जाते हैं, इस बात की कोई गारंटी नहीं है कि आपका आवेदन कुछ अजीब सहसंबंध पर भी ठोकर नहीं लगाएगा एक "मजबूत" पीआरएनजी।

Answer 2

इस बारे में सोचें: क्या होता है जब आपका निश्चित नंबर वास्तव में छोटा होता है?

Answer 3

यदि आप हर बार यादृच्छिक संख्या चुनते हैं, तो स्ट्रीम के अगले आइटम में पिछले चुने हुए आइटम को मारने का 1/CURRENTSIZE मौका होता है।

तो एक यादृच्छिक संख्या प्रति स्ट्रीम के साथ समस्या क्या है? यह वितरण क्यों छोड़ता है?

मुझे अभी तक कोई पूरा जवाब नहीं मिला है, लेकिन मुझे एक विचार है।

उदाहरण के लिए, 100 संख्याओं की एक धारा लें और यादृच्छिक संख्या 0 चुनें ... 999। अब हम इसे दूसरे आइटम के दृष्टिकोण से देखते हैं।

यह कब जीतता है? खैर, सबसे पहले, इसे एन% 2 == 0 होना चाहिए। तो यह भी एक संख्या होनी चाहिए। इसके अलावा, यह स्ट्रीम में 2 के प्रत्येक बहुमत के प्रत्येक अन्य एकाधिक द्वारा भी हराया जाता है, 4 ... 6 ... 8 .... 10 आदि। लेकिन यह 106 पर उदाहरण के लिए जीतता है।

सभी संख्याओं की गणना करना यह 0..9 99 के साथ जीतता है और हमें 81 बार मिलता है!

अब 4 लेते हैं, इसे एन% 4 == 0 होना चाहिए और यह 4 से एन (8 ... 12 .... 16) के सभी गुणकों द्वारा हराया जाता है। अगर हम गणना करते हैं कि कितनी बार 4 जीत सकते हैं, तो हमें 45 गुना मिलता है ...! तो वितरण उचित नहीं है।

यह तय किया जा सकता है कि यदि आप यादृच्छिक संख्या स्ट्रीम के अधिकतम आकार को बनाते हैं, तो सभी को जीतने का एक मौका होता है, जिससे इसे फिर से वितरण भी मिल जाता है।

उदाहरण के लिए, यदि हमारे पास 100 का स्ट्रीम आकार है, और हम यादृच्छिक संख्या 0..199 चुनते हैं। हम जानते हैं कि पहले 100 यादृच्छिक संख्याएं सभी के पास 1 मैच है, इसलिए उन्हें समान रूप से वितरित किया जाता है। लेकिन यादृच्छिक संख्या 99 के साथ क्या होता है ... 199? वितरण भी नहीं है! उदाहरण के लिए 101 केवल 101% एक्स == 0 के लिए 1 देगा। यह सभी प्रमुख संख्याओं (101, 103, 107, 109, 113, 127, 131, 137, 13 9, 14 9, 151, 157, 163, 167, 173, 17 9, 181, 1 9 1, 1 9 3, 1 9 7, 199)। इसलिए आइटम के पास दूसरों की तुलना में जीतने का बहुत बड़ा मौका है।

यह मामला नहीं है यदि आप प्रत्येक आइटम के लिए एक नया यादृच्छिक संख्या चुनते हैं, तो उस मामले में संभावनाएं शामिल की जा सकती हैं। उदाहरण के लिए जब आइटम के साथ आता है तो उसे जीतने का मौका होता है:

नहीं (1/2 + 1/3 + 1/4 + 1/5 + 1/6 (... आदि))