रैंडम (ए, बी) को केवल रैंडम (0,1) के साथ कैसे कार्यान्वित करें?

Question

संभव डुप्लिकेट:
how to get uniformed random between a, b by a known uniformed random function RANDOM(0,1)

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

प्रक्रिया रैंडम के एक कार्यान्वयन का वर्णन करें (एक, बी) जो केवल रैंडम (0,1) को कॉल करता है। ए और बी के एक समारोह के रूप में, आपकी प्रक्रिया के अपेक्षित चलने का समय क्या है? रैंडम (ए, बी) के परिणाम की संभावना शुद्ध रूप से वितरित की जानी चाहिए, क्योंकि रैंडम (0,1)

यादृच्छिक फ़ंक्शन के लिए, परिणाम ए और बी के बीच पूर्णांक होते हैं, विशेष रूप से। उदाहरण के लिए, यादृच्छिक (0,1) या तो 0 या 1 उत्पन्न करता है; रैंडम (ए, बी) उत्पन्न करता है एक, एक + 1, एक + 2, ..., ख

मेरे समाधान इस तरह है:

for i = 1 to b-a 
    r = a + Random(0,1) 
return r 

चलने का समय टी = बा

है

क्या यह सही है? क्या मेरे समाधान के परिणाम समान रूप से वितरित किए गए हैं?

धन्यवाद

क्या मेरी नई समाधान इस तरह है यदि:

r = a 
for i = 1 to b - a //including b-a 
    r += Random(0,1) 
return r 

यदि यह सही नहीं है, यही कारण है कि r + = यादृच्छिक (0,1) में आता है आर समान रूप से वितरित नहीं?

Answer 1

अन्य ने समझाया है कि आपका समाधान क्यों काम नहीं करता है। यहां सही समाधान है:

1) सबसे छोटी संख्या, p, जैसे कि 2^p > b-a खोजें।

2) निम्नलिखित कलन विधि को पूरा करें:

r=0 
for i = 1 to p 
    r = 2*r + Random(0,1) 

3) यदि rb-a से अधिक है, तो चरण 2.

4) आपका परिणाम है जाना r+a

तो चलो यादृच्छिक की कोशिश करते हैं (1,3)।
तो b-a 2.
2^1 = 2 है, इसलिए p ताकि 2^p से अधिक 2.
तो हम करेंगे पाश दो बार है 2 होना होगा।के लिए सभी संभव outputs कोशिश करते हैं:

00 -> r=0, 0 is not > 2, so we output 0+1 or 1. 
01 -> r=1, 1 is not > 2, so we output 1+1 or 2. 
10 -> r=2, 2 is not > 2, so we output 2+1 or 3. 
11 -> r=3, 3 is > 2, so we repeat. 

तो समय की 1/4, हम उत्पादन 1. बार हम उत्पादन 2. बार हम उत्पादन 3. का 1/4 और 1/4 के का 1/4 उस समय हमें एल्गोरिदम को दो बार दोहराना होगा। अछा लगता है।

ध्यान दें कि आप इस एक बहुत क्या करना है अगर, दो अनुकूलन काम कर रहे हैं:

1) आप एक ही रेंज काफी उपयोग करते हैं, एक वर्ग है कि p गणना करता है एक बार तो आप गणना करने के लिए नहीं है यह हर बार।

2) कई CPUs में चरण 1 करने के तेज़ तरीके हैं जो उच्च-स्तरीय भाषाओं में प्रकट नहीं होते हैं। उदाहरण के लिए, x86 CPUs में BSR निर्देश है।

Answer 2

नहीं, यह सही नहीं है, यह विधि (a+b)/2 पर ध्यान केंद्रित करेगी। यह एक द्विपक्षीय वितरण है।

क्या आप वाकई Random(0,1) पूर्णांक उत्पन्न करते हैं? अगर यह 0 और 1 के बीच फ्लोटिंग पॉइंट वैल्यू का उत्पादन करता है तो यह अधिक समझ में आता है। फिर समाधान एक एफ़िन ट्रांसफॉर्मेशन होगा, a और b से स्वतंत्र समय चल रहा है।

एक विचार जो मैंने अभी किया था, अगर यह पूर्णांक मानों के बारे में है: bisection का उपयोग करें। प्रत्येक चरण में, आपके पास low-high श्रेणी है। यदि Random(0,1) 0 देता है, तो अगली रेंज low-(low+high)/2 है, अन्य (low+high)/2-high। विवरण और जटिलता आपको छोड़ दी गई है, क्योंकि यह होमवर्क है।

जो एक समान वितरण (लगभग) बनाना चाहिए।

संपादित करें:लगभग महत्वपूर्ण शब्द है। वर्दी अगर b-a+1 2 की शक्ति है, तो यह बंद होने पर बहुत दूर नहीं है, लेकिन आम तौर पर पर्याप्त नहीं है। आह, ठीक है, यह एक सहज विचार था, उन्हें ठीक नहीं मिल सकता है।

Answer 3

सबसे पहले मुझे लगता है कि आप वास्तव में परिणाम जमा कर रहे हैं, प्रत्येक चरण पर 0 या 1 जोड़ना नहीं। कुछ संभाव्यताओं का उपयोग करके आप साबित कर सकते हैं कि आपका समाधान समान रूप से विचलित नहीं है। परिणामस्वरूप मूल्य आर (ए + बी)/2 सबसे बड़ा है।उदाहरण के लिए यदि कोई 0 है और बी 7 है, तो आपको एक मूल्य 4 प्राप्त करने का मौका है (7 का संयोजन 4) 2 द्वारा विभाजित 2 शक्ति से विभाजित है। इसका कारण यह है कि इससे कोई फर्क नहीं पड़ता कि 7 मूल्यों में से 4 1 परिणाम अभी भी होंगे 4.

आपके द्वारा अनुमानित चलने का समय सही है।

Answer 4

आपका समाधान के स्यूडोकोड तरह दिखना चाहिए:

r=a 
for i = 0 to b-a 
    r+=Random(0,1) 
return r 

समान वितरण का सवाल है, यह सोचते हैं यादृच्छिक कार्यान्वयन इस यादृच्छिक संख्या जनरेटर पर आधारित है पूरी तरह से वर्दी प्राप्त करने की बाधाओं 0 या 1 50% कर रहे हैं कि। इसलिए जिस नंबर को आप चाहते हैं उसे प्राप्त करना उस विकल्प का परिणाम बार-बार किया जाता है।

तो एक = 1, बी = 5 के लिए, 5 विकल्प हैं।

1 होने का अंतर 5 निर्णय, सब 0, बाधाओं शामिल है कि 0.5 हैं^5 = 3.125%

हो रही 5 की संभावना 5 निर्णय, सभी 1, बाधाओं शामिल है कि के हैं 0.5^5 = 3.125%

जैसा कि आप इससे देख सकते हैं, वितरण समान नहीं है - किसी भी संख्या की बाधा 20% होनी चाहिए।

Answer 5

आपके द्वारा बनाए गए एल्गोरिदम में, यह वास्तव में समान रूप से वितरित नहीं होता है।

परिणाम "आर" हमेशा "ए" या "ए + 1" होगा। यह उससे परे कभी नहीं चलेगा।

वह कुछ इस तरह दिखना चाहिए:

r=0; 
for i=0 to b-a 
    r = a + r + Random(0,1) 

return r; 

अपने गणना में "आर" को शामिल करके, आप की "अनियमितता" भी शामिल कर रहे पाश रन "के लिए" सभी पिछले।

Answer 6

नहीं, आपका समाधान सही नहीं है। इस योग में द्विपक्षीय वितरण होगा।

हालांकि, आप 0, 1 का शुद्ध यादृच्छिक अनुक्रम उत्पन्न कर सकते हैं और इसे बाइनरी संख्या के रूप में पेश कर सकते हैं।

repeat 
    result = a 
    steps = ceiling(log(b - a)) 

    for i = 0 to steps 
    result += (2^i) * Random(0, 1) 
until result <= b 

केनीटीएम: मेरा बुरा।

Answer 7

मैंने अन्य उत्तरों को पढ़ा। मस्ती के लिए, यादृच्छिक संख्या खोजने के लिए यहां एक और तरीका है:

b-a तत्वों के साथ एक सरणी आवंटित करें। सभी मान 1 पर सेट करें। सरणी के माध्यम से Iterate। प्रत्येक nonzero तत्व के लिए, सिक्का फ्लिप, जैसा कि यह थे। यदि यह 0 आया है, तो तत्व को 0 पर सेट करें।

जब भी, एक पूरी यात्रा के बाद, आप केवल 1 तत्व शेष है, तो आप अपने अनियमित संख्या: a+i जहां i अशून्य तत्व का सूचकांक है (हम 0 पर अनुक्रमण प्रारंभ कल्पना करते हुए)। सभी संख्याएं समान रूप से समान हैं। ...

यह O(infinity) होता (आप इस मामले में जहां यह बराबर हैं के साथ सौदा करने के लिए होता है, लेकिन मैं आप के लिए एक व्यायाम के रूप कि छोड़ दें।) :) औसत पर, हालांकि, आधा संख्या का सफाया किया जाएगा , इसलिए log_2 (b-a) का औसत केस चलने का समय होगा।