生成隨機（a，b）調用Random（0,1）

已知Random(0,1)函數，它是一個統一的隨機函數，意思是它將給出0或1，概率爲50％。執行Random(a, b)，只打電話Random(0,1)生成隨機（a，b）調用Random（0,1）

我到目前爲止是，把範圍a-b在0基於數組，然後我有索引0,1,2 ... b-a。

然後調用RANDOM(0,1) b-a次，將結果作爲生成的idx求和。並返回元素。

但是由於書中沒有答案，我不知道這種方式是正確的還是最好的。如何證明返回每個元素的概率完全相同，並且是1/(b-a+1)？

什麼是正確/更好的方法來做到這一點？

2011-12-10 Kent

可能的重複：[如何使用錯誤的生成器獲取隨機數]（http://stackoverflow.com/questions/7694933/how-to-get-random-numbers-with-the-wrong-generator） – PengOne

如果您的RANDOM（0,1）返回0或1，每個都有0.5的概率，那麼您可以生成位，直到您有足夠的二進制數來表示數（b-a + 1）。這給你一個稍大的範圍內的隨機數字：如果失敗，你可以測試並重復。就像這樣（在Python中）。

def rand_pow2(bit_count): 
    """Return a random number with the given number of bits.""" 
    result = 0 
    for i in xrange(bit_count): 
     result = 2 * result + RANDOM(0, 1) 
    return result 

def random_range(a, b): 
    """Return a random integer in the closed interval [a, b].""" 
    bit_count = math.ceil(math.log2(b - a + 1)) 
    while True: 
     r = rand_pow2(bit_count) 
     if a + r <= b: 
      return a + r

來源

2011-12-10 17:34:31

該解決方案通過在0 ..（2^N-1）上產生均勻分佈，然後在超出所需範圍以在2的非冪次上構造均勻分佈時丟棄結果，從而產生均勻分佈。您的解決方案構造二項分佈。 – 2011-12-10 22:00:36

我明白了，你的方式是正確的。但結果行是'result + = RANDOM（0,1）* 2 ** i'對嗎？ – Kent

是的，你可以用任何方式構造它，甚至可以導致+ = RANDOM（0，1）<< i。 – 2011-12-10 22:15:16

當你對隨機數求和時，結果不再是均勻分佈的 - 它看起來像一個高斯函數。查閱「大數法則」或閱讀任何概率書/文章。就像翻動硬幣100次，極不可能給出100個頭。它可能會提供接近50個頭和50個尾巴。

來源

2011-12-10 17:28:58 user949300

謝謝對於這些信息，我會搜索一些相關的文章閱讀。 – Kent

你的願望把範圍0到a-b首先是正確的。但是，你不能像你所說的那樣去做。 This question問清楚如何做到這一點，而the answer利用獨特的分解。在的基礎上編寫m=a-b，記錄最大需要的指數，比如e。然後，找到m的最大倍數，它小於2^e，稱之爲k。最後，用RANDOM(0,1)生成e號碼，把它們作爲基地2擴大一些號碼x，如果x < k*m，返回x，否則再試一次。該計劃看起來是這樣的（簡單的情況下，當m < 2^2）：

int RANDOM(0,m) { 

    // find largest power of n needed to write m in base 2 
    int e=0; 
    while (m > 2^e) { 
     ++e; 
    } 

    // find largest multiple of m less than 2^e 
    int k=1; 
    while (k*m < 2^2) { 
     ++k 
    } 
    --k; // we went one too far 

    while (1) { 
     // generate a random number in base 2 
     int x = 0; 
     for (int i=0; i<e; ++i) { 
      x = x*2 + RANDOM(0,1); 
     } 
     // if x isn't too large, return it x modulo m 
     if (x < m*k) 
      return (x % m); 
    } 
}

現在，你可以簡單地添加到a結果a和b之間得到均勻分佈的數字。

來源

2011-12-10 22:08:05 PengOne

分而治之可以幫助我們在範圍[a，b]中使用隨機（0,1）生成一個隨機數。我們的想法是

如果a等於b，則隨機數在該範圍[A，B]
生成隨機（0,1）
如果是以上的
查找中間0，在範圍[一，MID]返回一個隨機數使用遞歸
在範圍否則返回的隨機數[中間+ 1，b]上使用遞歸

工作「C」的代碼如下。

int random(int a, int b) 
{ 
    if(a == b) 
     return a; 

    int c = RANDOM(0,1); // Returns 0 or 1 with probability 0.5 
    int mid = a + (b-a)/2; 

    if(c == 0) 
     return random(a, mid); 
    else 
     return random(mid + 1, b); 
}

來源

2014-07-12 04:12:45 Bilal

如果所有子範圍的大小相等，只會在範圍是2的冪時纔會發生均勻分佈。它在數學上等同於生成位，並且只有在拒絕位於範圍之外的位集不屬於2的冪。 – pjs

感謝@pjs指出！ – Bilal

如果您有以相同的概率返回{0, 1}一個RNG，你可以很容易地創建一個返回數字{0, 2^n}具有相同概率的RNG。

要做到這一點，你只需使用你原來的RNG n次，並得到一個二進制數字，如0010110111。每個數字（從0到2^n）是相同的可能性。

現在很容易得到一個RNG從a到b，其中b - a = 2^n。您只需創建一個先前的RNG並將其添加a即可。

現在最後一個問題是如果b-a不是2^n？

好東西，你必須做幾乎沒有。依靠rejection sampling技術。它告訴你，如果你有一個很大的集合，並且有一個RNG超過這個集合，並且需要從這個集合的一個子集中選擇一個元素，你可以繼續從一個更大的集合中選擇一個元素並丟棄它們直到它們存在於你的子集中。

所以你所做的就是找到b-a並找到第012個這樣的b-a <= 2^n。然後使用拒絕採樣，直到您選取一個更小的元素b-a。比你剛剛添加a。

來源

2016-04-25 01:56:05

生成隨機（a，b）調用Random（0,1）

回答

相關問題