以有限的方式獲得一致的概率分佈

Question

假設您有一枚硬幣，並且您希望以相等的概率在3個數字（或更多）之間隨機選擇。如果你只是爲每一對投注一枚硬幣，那麼你就會給第一輪的倖存者兩次失敗的機會，並且分配不均勻。

一般來說，你有一個函數Random（0,1），返回0，概率爲0.5，概率爲1。使用這個函數，使Random（a，b）以相等的概率返回[a，b]範圍內的任何整數。

任何想法？

Answer 1

給定隨機（0,1）時，生成隨機（0,3）更容易。隨機（0,3）可以通過兩次連續投幣來模擬以產生四個存儲桶：00,01,10,11。

通常，隨機（0,2^n-1）隨機（0，1）[即一個公平的硬幣]。任何其他隨機（0，n）將很難生成，並且不是真正的「隨機」 - 因爲您必須預先確定要視爲屬於「其他」桶的結果數量。

你可以近假冒隨機（0,2）這樣的（紅寶石般的僞代碼）：

options = ['h', 't', 'n']  # heads, tails, neither 
hash = {'h' => 0, 't' => 0, 'n' => 0} # number of 'heads', 'tails', 'neither' 
rand = options[random(0, 1)] 
rand = 'n' if (hash[rand] % 3 == 2) # every third 'h' or 't' is an 'n' 
hash[rand] ++ # update buckets 

再次，這是不是因爲每三頭「隨機」或尾部被認爲是一個「既不」。

更新：有關更優雅的答案，請參閱相關問題。 Creating a random number generator from a coin toss