ddef coin_new(): while True: a = coin() if coin() != a: return a
完整测试代码：
def coin(): return 0 if random.randint(1,10) > 4 else 1def coin_new(): while True: a = coin() if coin() != a: return aif __name__ == '__main__': a = 0 b = 0 n = 100000 for _ in range(n): if coin_new():a += 1 if coin():b += 1 print(f"1:{a/n},1:{b/n}")
def coin_new(): while True: a, b = coin(), coin() if a & b: return 0 if a | b: return 1
P(0) = 0.3，P(1) = 0.7
每抛一次硬币，会得到二进制数的一位，连续抛 4 次硬币，可以等概率生成 [0, 15] 的每个数，记为 x。去掉 [10, 15]，剩下 [0, 9] 的每个数依然是等概率的。如果 x ∈ [ 0 , 2 ] x /in [0, 2] x∈[0,2]，返回 0； x ∈ [ 4 , 9 ] x /in [4, 9] x∈[4,9]，返回 1； x ≥ 10 x ≥ 10 x≥10，重复上述过程。
def coin_new(): while True: x = 0 for _ in range(4): x = (x << 1) + coin() if x <= 2: return 0 if x <= 9: return 1
总结
每抛一次硬币，会得到二进制数的一位，连续抛 k 次硬币，可以等概率生成 [ 0 , 2 k − 1 ] [0, 2^k-1] [0,2k−1] 的每个数在 [ 0 , 2 k − 1 ] [0, 2^k-1] [0,2k−1][ 中，选取 m 个数返回 0，n 个数返回 1，则 0、1 的概率分别为 m m + n /frac{m}{m+n} m+nm 、 n m + n /frac{n}{m+n} m+nn。
关于 k 的选择，最少需要满足 N < = 2 k − 1 N <= 2^k-1 N<=2k−1，N 是生成对应概率分布至少需要多少个不同数字。比如要生成 1/3、2/3 的分布，至少需要 3 个不同数字，则 N = 3, k = 2；要生成 3/10、7/10 的分布，至少需要 10 个数字，则 N = 10, k = 4。
k 最多则没有限制，我们总可以通过抛更多次硬币来解决问题，只需要把无用的数字舍弃即可。但我们的目的是尽可能减少无用数字的比例，因为每次遇到无用数字时，都需要重新生成新的数字。
def rand10(): while True: x = (rand7() - 1) * 7 + (rand7() - 1) if 1 <= x <= 40: return x % 10 + 1 x = (x % 40) * 7 + rand7() # 1~63 if x <= 60: return x % 10 + 1 x = (x - 61) * 7 + 7 # 1~21 if x <= 20: return x % 10 + 1
每次 while 执行的时候，只有 1 个无用数字（21）会被舍弃，重新执行的概率很低。
RandM 生成 RandN
已知 RandM() 可以等概率的生成 [0, M-1] 范围的随机整数，那么执行 k 次，每次都得到 M 进制的一位，可以等概率生成 [ 0 , M k − 1 ] [0, M^k-1] [0,Mk−1] 范围的随机整数，记为 x。
RandN 至少需要 N 个均匀随机整数，因此只需要取 k，使得 M k − 1 > = N M^k-1 >= N Mk−1>=N 即可，此时有多种方式得到 RandN： 一种是只在 x ∈ [ 0 , N − 1 ] x /in [0, N-1] x∈[0,N−1] 时返回 x，另一种是利用取余运算，在保证等概率的前提下，尽可能多的利用生成的数字，从而减少舍弃的数字比例，降低 while 重复执行的概率。
