均勻分佈的隨機數生成

爲什麼此代碼會生成均勻分佈的數字？我理解它有一些困難。有人可以解釋嗎？謝謝。均勻分佈的隨機數生成

int RandomUniform(int n) { 
    int top = ((((RAND_MAX - n) + 1)/n) * n - 1) + n; 
    int r; 
    do { 
    r = rand(); 
    } while (r > top); 
    return (r % n); 
}

更新：我明白爲什麼rand（）％n不給你一個均勻分佈的序列。我的問題是爲什麼

top = ((((RAND_MAX - n) + 1)/n) * n - 1) + n;

這裏有什麼關心？我認爲一個簡單的頂部= RAND_MAX/n * n會做。

來源

2013-02-04 JASON

你爲什麼認爲它確實生成一個統一的分佈？ – Alnitak

函數假設rand()是均勻分佈的;不管這是否是一個有效的假設取決於rand()的實施。

給定一個統一的rand()，我們可以通過計算rand()%n得到[0,n)範圍內的一個隨機數。但是，一般來說，這不會很統一。例如，假設n是3和RAND_MAX爲7：

rand()  0 1 2 3 4 5 6 7 
rand() % n 0 1 2 0 1 2 0 1

我們可以看到，在0和1想出的3/8的概率，而2只用2/8的概率出現：所述分配不統一。

您的代碼丟棄了大於或等於它可以生成的n的最大倍數的任何值rand()。現在，每個值都有平等的概率：

rand()  0 1 2 3 4 5 6 7 
rand() % n 0 1 2 0 1 2 X X

所以0,1和2都拿出1/3的概率，只要我們沒有這麼走運，循環永遠不會終止。

關於你提到的更新：

我認爲，一個簡單的頂部= RAND_MAX/N * N會做。

如果RAND_MAX是一個獨佔邊界（比實際最大值多一個），那麼這就是正確的。由於它是一個包容性界限，我們需要添加一個來獲得排他性界限;並且由於下面的邏輯與>比較針對一個包容結合，然後在計算之後再次減去一個：

int top = ((RAND_MAX + 1)/n) * n - 1;

然而，如果RAND_MAX是等於INT_MAX，則計算將溢出;要避免這種情況，在計算開始減n，並在年底再次添加：

int top = (((RAND_MAX - n) + 1)/n) * n - 1 + n;

來源

2013-02-04 15:45:40

感謝您的解釋 – JASON

潛在的問題是：假設你有一個隨機數發生器my_rand()，它產生的值從0到6（包括0和6），並且你想產生從0到5的值（包括0和5）;如果你運行你的發電機並且返回my_rand() % 6，你將不會得到一個統一的分配。當my_rand()返回0時，您得到0;當它返回1時，你得到1，等到my_rand()返回6;在這種情況下，my_rand() % 6爲0.因此總的來說，my_rand() % 6將返回0的次數是任何其他值的兩倍。解決這個問題的方法是不要使用大於5的值，即，而不是my_rand() % 5您編寫一個循環並放棄my_rand()中太大的值。這基本上就是問題中的代碼所做的。我沒有跟蹤它，但通常的實現是計算n的最大倍數小於或等於RAND_MAX，並且每當rand()返回一個大於該倍數的值時，返回並獲取新值。

來源

2013-02-04 15:40:16

很好的解釋，但仍然要求輸入RNG確實具有均勻分佈。 – Alnitak

@Alnitak - 真實。 –

另外，如果'RAND_MAX'足夠大（通常是這樣）並且'n'足夠小，那麼上面的代碼所產生的差異可以忽略不計。 – Alnitak

我沒有通過計算頂部跟蹤代碼，但RAND_MAX是rand()可以返回的最大值; (RAND_MAX + 1)/n * n會是一個更好的上限，但如果RAND_MAX是INT_MAX，結果將是不可預測的。所以也許所有的代碼都試圖避免溢出。

來源

2013-02-04 16:02:07

謝謝。我想我明白了。這是正確的，n應該除以RAND_MAX + 1，代碼做RAND_MAX + 1 - n然後做/ n * n，避免溢出。謝謝。 – JASON

對於'n'的某些值，它會產生一個較低的值，這反過來會浪費比必要的更多的隨機數。例如，如果'RAND_MAX'是奇數（通常是這樣），並且'n'是'（RAND_MAX + 1）/ 2'，那麼平均來說，代碼會爲每個隨機數調用rand（）產生。 –

考慮你的選擇'（RAND_MAX/n）* n'會爲'n = RAND_MAX-1'做些什麼。 –

均勻分佈的隨機數生成

回答

相關問題