如何有效地生成獨立但有偏差的隨機位流？

通常，在密碼學中，人們對消除獨立（真實）隨機位流的偏差感興趣，並且存在幾種算法可以做到這一點。反過來呢？假設我有一個獨立且無偏的隨機位流可供我使用，並且我想生成一個統計上獨立的位流，但是在哪裡 $ \Pr[B=0] = \frac{1}{5} $ ， 說。如何在不犧牲初始來源的太多熵的情況下做到這一點？這種精確情況的通用算法將包括繪圖 $ 3 $ 位，並將它們解釋為數字 $ 0 \leq a \leq 7 $ . 如果 $ a=0 $ ，然後輸出 $ 0 $ , 否則如果 $ a < 5 $ ，然後輸出 $ 1 $ , 否則什麼也不輸出。問題是我會犧牲很多熵：有機率 $ \frac{1}{4} $ ，我丟棄 3 位，並且有機率 $ \frac{3}{4} $ ，我將 3 位熵轉換為一個。您是否知道一種較少熵飢餓的方法？

如果您想要一個在消耗隨機比特流方面效率最高的答案，那麼您需要一個用於算術編碼的解碼器。但是，如果您使用的是中等速度的 CSPRNG，為什麼要犧牲額外的時鐘週期來從每個無偏位中壓縮所有有偏位？

如果您想要一個更有效的算法，如何：

int biased_bit(double bias) {
   for (;;) {
       bias = 2 * bias;
       if (get_random_bit() == 0) {
           bias = bias - 1;
           if (bias <= 0) return 0;
       } else {
           if (bias >= 1) return 1;
       }
   }
}

假設 get_random_bit() 返回均勻分佈的獨立隨機位，並假設 $ 0 \le bias \le 1 $ , 那麼這會返回一個 1 的機率 $ bias $ , 和 0 機率 $ 1-bias $ . 這使用每個偏置輸出位的預期 2 位輸入（除了偏置為 $ a/2^{b} $ 對於整數 $ a, b $ ; 在這種情況下，預期使用的位數更少）。相反，您所說的技術將採取（對於 $ bias = \frac{1}{5} $ ) 每個偏置輸出位的預期輸入為 4.8 位。

另一方面，我不同意你原來的前提；您可以使用高效的CSPRNG廉價地獲得無偏、獨立分佈的隨機位。是的，計算無界的對手可以將它們與隨機區分開來；除非您的攻擊者屬於該類別，否則您可以忽略該區別。

引用自：https://crypto.stackexchange.com/questions/6505