是否可以建構一個輸出數字具有一定漢明權重分佈的 PRNG？
我需要一個非均勻隨機數生成器，其中每個 n 位輸出都有一個具有一定二項分佈的漢明權重。
例如，我想要一個非均勻 PRNG，它生成具有漢明權重的 32 位輸出，其二項式分佈為 n=32，p=0.1。例如，輸出 0xFF 的機率應該明顯低於 0x200，而 0x200 的機率又應該與 0x1 相同。
也許我可以修改像 xorshift 或 LFSR 這樣的 PRNG 的輸出來適應這個？我考慮過拒絕對輸出進行採樣，但統一 PRNG 的漢明權重分佈不一定包含具有可變參數 p 的給定二項式分佈，尤其是當 p << 0.5 時。
我不關心輸出的加密質量。但是，我正在開發具有 2 KB SRAM 的 8 位微控制器，因此記憶體和速度都是我最關心的問題。在最天真的情況下，我會生成一個隨機數數組，並在給定門檻值機率的情況下將每個元素轉換為 0 和 1，最後將生成的 0 和 1 數組轉換為整數。但我真的非常想避免這種 n 元素數組的記憶體成本。
顯而易見的方法是生成 N 個字，並使用邏輯運算將它們組合成一個字，這樣輸出字的每個位都是 1，機率約為 0.1（並且各個位不相關）。
在最簡單的情況下，您可以生成 3 個單詞，然後將它們組合成一個單詞。在 C 中，這將是：
r1 = rand(); r2 = rand(); r3 = rand(); return r1 & r2 & r3;這使每個位集的機率為 0.125，接近 0.1
如果這還不夠接近，您可以通過使用更多位來獲得更接近的近似值；例如，
r1 & r2 & r3 & ~(r4 & r5)以機率設置位的結果 $ 3/32 = 0.09375 $使用這種技術，您可以使用 $ n $ 隨機詞以機率生成位集 $ k 2^{-n} $ 對於某個整數 $ k $ ; 這可以任意接近 0.1。
這顯然使用最少的記憶體；計算時間並不算太糟糕（假設您的 rand 實現很便宜），除非您堅持對目標機率有一個非常好的近似值。
而且，雖然我說的是“單詞”，但您的實現將使用它認為最方便的任何大小；對於 8 位 CPU，每個字可能是 8 位（您只需執行 4 次即可生成所需的 32 位）。