निष्पक्ष 26-पक्षीय मरने के अनुकरण के लिए यादृच्छिक बिट्स का उपयोग कैसे करें?

Question

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

Answer 1

आपके मामले में सबसे आसान तरीका 5 बिट्स फेंकना है, जो 32 (0-31) equiprobable परिणाम देता है। आप अपनी सीमा के बाहर एक मूल्य लेते हैं (एक से अधिक 25) आप फिर से कोशिश (और फिर ...)

"सिक्के" (बिट्स) प्रत्येक अक्षर के लिए इस मामले में फेंकने के लिए की औसत संख्या होगी

5 x 32/26 = 6.15 

Answer 2

आप बिट्स की एक सीमित संख्या के लिए अपने आप को प्रतिबंधित करने और अपने मरने 26 पक्षों विधि हमेशा पक्षपातपूर्ण हो जाएगा नहीं हैं (संदर्भ के लिए, geometric distribution देखें)। आपको इस संभावना की अनुमति देनी होगी कि आपको यह सुनिश्चित करने के लिए संभावित असीमित संख्या में बिट्स देखना होगा कि यह निष्पक्ष है।

एक साधारण एल्गोरिदम(इस मामले में 31) के बीच सबसे यादृच्छिक संख्या चुनने के लिए एक यादृच्छिक संख्या चुनना है। यदि आप जिस नंबर को यादृच्छिक रूप से चुनते हैं वह बहुत बड़ा है, इसे छोड़ दें और जब तक आपको सीमा में कोई संख्या न मिल जाए तब तक प्रतिकृति करें।

स्पष्ट रूप से यह एक इष्टतम एल्गोरिदम नहीं है क्योंकि आप कुछ जानकारी "अपशिष्ट" करते हैं, लेकिन यह अधिकांश उद्देश्यों के लिए पर्याप्त होना चाहिए। यह सबसे अपर्याप्त है अगर मरने के पक्षों की संख्या 2^m से ऊपर m के लिए है, उदाहरण के लिए: 33 पक्ष। इस मामले में आपको उस समय के लगभग 50% मूल्य को त्यागना होगा।

Answer 3

एक बेवकूफ कार्यान्वयन बिट्स की एक निश्चित संख्या (एक पूर्णांक प्राप्त करने के लिए 4 बाइट्स) का उपयोग करके दशमलव या पूर्णांक मान प्राप्त करने के लिए यादृच्छिक बिट्स को गठबंधन करना होगा। परिणामों को विभाजित बिट्स की संख्या के लिए अधिकतम संभव मूल्य से विभाजित करें, जो मुझे लगता है कि आपको 0-1 की श्रेणी में समान रूप से वितरित दशमलव देना चाहिए। (अनिवार्य रूप से एक रैंड() समारोह)। फिर 26 * रैंड()

Answer 4

26 बाइनरी में 11010 है।
पाँच बिट्स उत्पन्न करें, अगर वे 26 से अधिक है, या तो:

1. वापसी मान आधुनिक 26 (कम मूल्यों के पक्ष में होगा)
2. परिणाम त्यागें और फिर से जाना (संभावना खत्म कभी नहीं करने के लिए है)

या इसे सामान्यीकृत:
जेनरेट करें (बेस 2 में लॉग एन) + 1 बिट्स। यदि वे एन से अधिक हो जाते हैं, तो मान mod n वापस करें, या & को फिर से छोड़ दें।

Answer 5

मूलभूत उत्तर यहां सही लगता है - यदि आपका यादृच्छिक संख्या 0..32 25 से अधिक है, तो रोल करें। हालांकि, आप 26 के एक से अधिक की तलाश करके मनमाने ढंग से लंबे परिणाम के खिलाफ बाधाओं को ढेर कर सकते हैं जो लंबे समय तक जाने का एक छोटा सा मौका प्रदान करता है।

32 - 26 = 6 
64 - 52 = 12 
128 - 78 = 50 

... और इसी तरह।मैं एक साथ Python स्क्रिप्ट फेंक दिया बाहर बिट्स का सबसे अच्छा उपलब्ध संख्या, 32 अप करने के लिए लगाने की गिगल्स के लिए, और इस परिणाम मिला:

2^13 - 26 * 315 = 2 
2^14 - 26 * 630 = 4 

तो किसी भी तरह, आप अगर rerolling की एक में 1 2^12 मौका है आप 13 या 14 बिट्स का उपयोग करते हैं। इस मामले में आपका एल्गोरिथ्म होगा:

def random_character(): 
    r = 8190 
    while r >= 8190: 
     r = rand(13) # assuming rand generates an N bit integer 
    return chr(r % 26 + ord('a')) 

संपादित करें: जिज्ञासा से बाहर, मैं उन बाधाओं में कुछ महत्वपूर्ण मूल्यों के साथ तुलना में, देखने के लिए अगर 13 वास्तव में इष्टतम संख्या (यह मानते हुए आप बिट्स के किसी भी संख्या उत्पन्न कर सकते हैं किया गया था, 1 से 32, एक ही समय में - यदि आप नहीं कर सकते हैं, तो 13 बिट सर्वश्रेष्ठ की तरह दिखते हैं)। मेरे (स्वीकार्य रूप से नींद) गणित के आधार पर, यदि आप 32 बिट्स को सस्ते रूप में 16 के रूप में प्राप्त कर सकते हैं, तो इसके लिए इसके लिए जाएं। अन्यथा, पक्ष 13.

2^8 through 2^12: by definition, no better than 1/2^12 odds 
2^16: diff is 16, so 1/2^11 
2^17: diff is 6, so slightly under 1/2^14 
2^18: diff is 12, so slightly under 1/2^12 
2^19: diff is 24, so slightly under 1/2^14 
2^20: diff is 22, so slightly under 1/2^15 
2^21: diff is 18, so slightly under 1/2^16 
2^22: diff is 10, so slightly under 1/2^18 
2^23: diff is 20, so slightly under 1/2^18 
2^24: diff is 14, so slightly under 1/2^20 
2^25: diff is 2, so 1/2^24 
2^26: diff is 4, so 1/2^24 
2^27: diff is 8, so 1/2^24 
2^28: diff is 16, so 1/2^24 
2^29: diff is 6, so slightly under 1/2^26 
2^30: diff is 12, so slightly under 1/2^26 
2^31: diff is 24, so slightly under 1/2^26 
2^32: diff is 22, so slightly under 1/2^27