無偏隨機數發生器使用偏倚的隨機數發生器

Question

你有一個有偏倚的隨機數發生器，產生1概率爲p，0爲概率（1-p）。你不知道p的價值。使用它可以產生一個無偏的隨機數發生器，其產生1的概率爲0.5，0的概率爲0.5。

注意：這個問題是從介紹由Cormen，Leiserson，維斯特，斯坦算法的練習題（CLRS）

Answer 1

事件（P）（1-p）和（1-P）。 （p）是等概率的。將它們分別作爲0和1，並丟棄另外兩對結果，得到一個無偏的隨機生成器。

在代碼中，這是爲做容易，因爲：

int UnbiasedRandom() 
{ 
    int x, y; 

    do 
    { 
     x = BiasedRandom(); 
     y = BiasedRandom(); 
    } while (x == y); 

    return x; 
} 

Answer 2

您需要從RNG畫對值直到你得到不同值的序列，即，零後面緊跟着一個或一個零。然後，您獲取該序列的第一個值（或最後一個，無關緊要）。

（只要引出的一對或者是兩個零或兩個1即重複）這背後的數學很簡單：0然後1序列具有非常相同的概率爲1，則零序。通過總是將這個序列的第一個（或最後一個）元素作爲新的RNG的輸出，我們有機會得到一個零或一個。

Answer 3

下面是一種方法，可能不是最有效的。咀嚼一堆隨機數，直到得到[0 ...，1，0 ...，1]形式的序列（其中0 ...是一個或多個0）。計數0的數量。如果第一個序列較長，則生成一個0，如果第二個序列較長，則生成一個1.（如果它們相同，則再試一次。）

這就像HotBits從放射性生成隨機數粒子衰變：

由於任何給定衰變的時間是隨機的，因此兩個連續衰變之間的間隔也是隨機的。我們所做的是測量一對這樣的間隔，並根據兩個間隔的相對長度發出一個零位或一位。如果我們測量兩個衰變相同的間隔，我們丟棄測量並再次嘗試

HotBits: How It Works

Answer 4

歸因於馮·諾伊曼同時獲得兩個比特的特技，具有01對應於0和10到1，重複00或11已經出現。使用此方法需要提取以獲取單個位的位的預期值爲1/p(1-p)，如果p特別小或大，則該位可能會變得非常大，因此值得問一問該方法是否可以改進，特別是因爲它是它顯然會拋出很多信息（全部是00和11）。

谷歌搜索「馮·諾伊曼特技偏置」產生this paper，開發針對該問題的更好的解決方案。這個想法是，你仍然需要一次兩位，但如果前兩次嘗試只產生00秒和11秒，你把一對0作爲單個0和一對1作爲一個1，並且應用馮諾依曼的技巧對這些對。如果這也不起作用，那麼在這個級別的對上繼續類似的組合，等等。

此外，本文將此發展爲從偏置源生成多個無偏位，本質上使用兩種不同的方法從位對生成位，並給出一個草圖，表明這是最優的，原始序列在其中熵的位數。

Answer 5

produce an unbiased coin from a biased one的程序首先歸因於Von Neumann（一個在數學和許多相關領域做了大量工作的人）。程序非常簡單：

• 投擲硬幣兩次。
• 如果結果一致，重新開始，忘記兩個結果。
• 如果結果不同，請使用第一個結果，忘記第二個結果。

這個算法工作的原因是因爲越來越HT的概率p(1-p)，這是與獲取TH (1-p)p。因此兩個事件同樣可能。

我也在讀這本書，它會詢問預計的運行時間。兩次投擲不相等的概率爲z = 2*p*(1-p)，因此預計運行時間爲1/z。

---

前面的例子看起來令人鼓舞的（畢竟，如果你有一個偏見硬幣的p=0.99偏見，你需要把你的硬幣大約50倍，這是沒有那麼多）。所以你可能會認爲這是一個最佳算法。可悲的是，事實並非如此。

這是它與Shannon's theoretical bound（圖片取自answer）的比較。它表明算法很好，但遠不是最優的。

你能想出的改善，如果你會考慮HHTT將通過該算法被丟棄，但其實它具有相同的概率TTHH。所以你也可以在這裏停下來並返回H.HHHHTTTT也是如此。使用這些情況可以改善預期的運行時間，但不會使其在理論上最佳。

---

而在最後 - Python代碼：

import random 

def biased(p): 
    # create a biased coin 
    return 1 if random.random() < p else 0 

def unbiased_from_biased(p): 
    n1, n2 = biased(p), biased(p) 
    while n1 == n2: 
     n1, n2 = biased(p), biased(p) 

    return n1 

p = random.random() 
print p 

tosses = [unbiased_from_biased(p) for i in xrange(1000)] 
n_1 = sum(tosses) 
n_2 = len(tosses) - n_1 
print n_1, n_2 

這是不言自明的，這裏有一個例子結果：

0.0973181652114 
505 495 

正如你看到的，但是我們有0.097的偏差，我們得到大約相同數量的1和0