使用一個概率集合來生成另一個概率集合

Question

如何從較小的概率集合生成更大的概率集合？
這是從算法設計手冊-Steven Skiena
問：

使用隨機數發生器（rng04），其從{0,1,2,3,4}生成數以相等的概率來寫一個隨機數發生器，以相同的概率產生0到7（rng07）的數字？

我現在嘗試了3個小時左右，主要是基於總結兩個rng04輸出。問題是，在這種情況下，每個值的概率是不同的 - 4可以以5/24的概率出現，而0出現的概率是1/24。我嘗試了一些方法來掩蓋它，但不能。

有人可以解決這個問題嗎？

Answer 1

你必須找到一種方法來結合兩組隨機數（第一個和第二個隨機{0,1,2,3,4}），並使n*n明顯的可能性。基本上問題是，除了你得到這樣的東西

 X 
     0 1 2 3 4 

    0 0 1 2 3 4 
Y 1 1 2 3 4 5 
    2 2 3 4 5 6 
    3 3 4 5 6 7 
    4 4 5 6 7 8 

其中有重複，這不是你想要的。一種可能的方法來組合使用兩套將是Z = X + Y*5其中X和Y是兩個隨機數。這將使你喜歡這個

 X 
     0 1 2 3 4 

    0 0 1 2 3 4 
Y 1 5 6 7 8 9 
    2 10 11 12 13 14 
    3 15 16 17 18 19 
    4 20 21 22 23 24 

一組結果所以，現在你有一個更大的隨機數集，你需要做反向而使其變小。這樣設置有25不同的值（因爲你開始與5，並用兩個隨機數，所以5*5=25）。你想要的集合有8個不同的值。一個天真的方式做這將是

x = rnd(5) // {0,1,2,3,4} 
y = rnd(5) // {0,1,2,3,4} 
z = x+y*5 // {0-24} 
random07 = x mod 8 

確實，這有一系列的{0,7}。但值{1,7}似乎3/25倍，價值0會出現4/25倍。這是因爲0 mod 8 = 0，8 mod 8 = 0，16 mod 8 = 0和24 mod 8 = 0。

爲了解決這個問題，你可以修改上面這個代碼。

do { 
    x = rnd(5) // {0,1,2,3,4} 
    y = rnd(5) // {0,1,2,3,4} 
    z = x+y*5 // {0-24} 
while (z != 24) 

random07 = z mod 8 

這將需要一個值（24），它擺脫你的概率和丟棄。生成一個新的隨機數，如果你得到這樣一個'不好的'值將會使你的算法運行的時間稍長一點（在這種情況下，1/25的時間需要運行2x的時間，1/625需要3x的時間長等）。但它會給你正確的概率。

Answer 2

我的邏輯是這樣的：

rn07 = 0; 
do { 
    num = rng04; 
} 
while(num == 4); 

rn07 = num * 2; 
do { 
    num = rng04; 
} 
while(num == 4); 

rn07 += num % 2 

Answer 3

真正的問題，當然，是一個事實，即在（在這種情況下4）的總和的中間數發生在許多組合（0 + 4 ，1 + 3等），而0和8只有一種生成方式。

我不知道如何解決這個問題，但我會盡量減少一點。需要考慮的幾點：

• 0-7範圍有8個可能的值，所以最終你應該瞄準的可能情況的總數必須是8的倍數。這樣你可以有一個整數該共域中每個值的分佈。
• 當您計算兩個密度函數的總和時，可能情況的數量（當您評估總和時不一定是不同的，就輸入的不同排列而言）等於每個輸入的大小的乘積集。因此，給定兩個{0,1,2,3,4}集合在一起，你就有5 * 5 = 25的可能性。
• 不可能從5的冪（見第二點，但將其推廣到任意數量的集合> 1）得到8的倍數（見第一點），所以您將需要有可能的剩餘在你的功能中的情況，如果它們發生，忽略其中的一些。
• 就目前而言，最簡單的方法就是使用兩個{0,1,2,3,4}集合（25個可能性）的總和，忽略1（離開24個，8的倍數）。
• 因此，現在的挑戰已經減少到：找到一種方法來分配8個輸出值中剩餘的24種可能性。爲此，您可能不想使用總和，而只是輸入值。

要做到這一點的一種方法是，想象一下從您的輸入構建的基數5中的數字。忽略44（這是你的第25個，多餘的價值;如果你得到它，綜合一組新的輸入），並採取其他模式8，你會得到0-7跨越24個不同的輸入組合（每個3），這是平等的分配。