probability - 以有限的手段获得均匀的概率分布

Question

假设您有一枚硬币，并且您想以相等的概率在 3 个（或更多）数字之间随机选择。如果你只是为每一对掷硬币，那么你就给了第一轮的幸存者两次失败的机会，而且分布不均匀。

通常，您有一个函数 Random(0,1) 以 0.5 的概率返回 0，以 0.5 的概率返回 1。使用此函数，使 Random(a,b) 以相等的概率返回范围 [a,b] 中的任何整数。

有任何想法吗？

Answer 1

给定 Random(0, 1) 更容易生成 Random(0,3)。Random(0, 3) 可以通过连续两次抛硬币来模拟生成四个桶：00、01、10、11。

一般来说，给定 Random(0, 1) [即公平硬币]，Random (0, 2^n-1) 很容易生成。任何其他 Random(0, n) 都将难以生成，并且不是真正的“随机”——因为您必须预先确定要考虑属于“其他”存储桶的结果数量。

你几乎可以像这样伪造Random(0,2)（类似 Ruby 的伪代码）：

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

同样，这不是“随机的”，因为每三个头部或尾部都被认为是“两者都不是”。

更新：请参阅相关问题以获得更优雅的答案。 通过抛硬币创建随机数生成器