從線性同餘RNG

如果我具有線性同餘發生器，使得給定的種子特異性每一次，我可以確切地知道，我們可以產生已知的僞隨機數的固定序列均勻分佈生成隨機矢量在[1，K]之間，我應該如何使用這樣一個RNG生成一個均勻分佈在[1，K^M]之間的M維隨機向量？從線性同餘RNG

通過讓隨機向量在[1，K^M]之間均勻分佈是什麼意思？你的意思是每個條目在[1，K]中應該是統一的，並且在轉換成數字時的向量應該是統一的？ – user2566092

@ user2566092：的確，這就是我想要的。 –

我不知道你打算使用或者什麼K的範圍是什麼編程語言和M是的，但如果K是2的冪，你可以簡單的後面附上M僞隨機數的二進制表示得到一個僞隨機數均勻分佈在[1，K^M]上。如果K不是2的冪，則可以使用某種分區函數，或重新滾動某些值來構造[1，K^M]分佈式數字的位。

2013-08-01 22:38:19 MattG

問題是，如果它是一個線性同餘生成器，我們知道（種子，當前數）可以確定下一個僞隨機數是什麼，這樣我們將無法生成均勻分佈在[1， K^M]，對嗎？ –

是的，LCG的序列相關性會帶來問題。 sh1的答案探討了一些替代方案。 – MattG

如果你對LCG除了M維情況以外都滿意，那麼最基本的解決方案是將M個獨立的種子用於M個獨立的發生器。這至少可以確保給定向量的元素是獨立的（達到種子算法的極限）。

然而，你可能真的想要的是一個PRNG狀態至少M*log_2(K)位，它可以保證向量的所有部分之間的一些混合。如果這超過了64位，那麼使用LCG來實現這一點似乎需要付出很多努力才能實現比許多更簡單的解決方案更弱的功能。

如果M是恆定的並且不是不合理的大，那麼你可以看看xorshift，multiply-carry-carry或者well。否則，你可能會堅持使用一個衆所周知的巨週期發生器或密碼算法，並對理論侷限性視而不見。

2013-08-02 00:00:30 sh1

回答