概率生成问题
有一枚不均匀的硬币，要求产生均匀的概率分布 有一枚均匀的硬币，要求产生不均匀的概率分布，如 0.25 和 0.75 利用 rand7() 实现 rand10()
不均匀硬币 产生等概率
现有一枚不均匀的硬币 coin()，能够返回 0、1 两个值，其概率分别为 0.6、0.4。要求使用这枚硬币，产生均匀的概率分布。即编写一个函数 coin_new() 使得它返回 0、1 的概率均为 0.5。
# 不均匀硬币，返回 0、1 的概率分别为 0.6、0.4
def coin():
return 0 if random.randint(1,10) > 4 else 1
统计抛两次硬币的结果的概率分布：
结果 0 1
0 0.60.6=0.36 0.60.4=0.24
1 0.40.6=0.24 0.40.4=0.16
连续抛两枚硬币得到 0 1 和 1 0 的概率分布是相同的。因此这道题的解法就是连续抛两次硬币，如果得到 0 1，返回 0；如果得到 1 0，返回 1；如果两次结果相同，则重新抛。
以此类推，无论这枚不均匀硬币的概率是多少，都可以用这种方法得到等概率的结果。
ddef coin_new():
while true:
a = coin()
if coin() != a:
return a
完整测试代码：
def coin():
return 0 if random.randint(1,10) > 4 else 1
def coin_new():
while true:
a = coin()
if coin() != a:
return a
if __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}")
均匀硬币 产生不等概率
现有一枚均匀的硬币 coin()，能够返回 0、1 两个值，其概率均为 0.5。要求编写一个函数 coin_new()，使得它返回指定的 0、1 概率分布。
# 均匀硬币
def coin():
return random.randint(0,1)
p(0) = 1/4，p(1) = 3/4
对于均匀硬币而言，连续抛两次，得到 0 0、0 1、1 0、1 1 的概率均为 1/4。显然，只需要连续抛两次硬币，如果得到 0 0，返回 0，其他情况返回 1。
def coin_new():
return coin() or coin()
p(0) = 1/3，p(1) = 2/3
连续抛两次硬币。如果得到 1 1，返回 0；如果得到 1 0 或 0 1，返回 1；如果得到 0 0，继续抛硬币。
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 最多则没有限制，我们总可以通过抛更多次硬币来解决问题，只需要把无用的数字舍弃即可。但我们的目的是尽可能减少无用数字的比例，因为每次遇到无用数字时，都需要重新生成新的数字。
rand7 生成 rand10
已有方法 rand7() 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10() 生成 1 到 10 范围内的均匀随机整数。
抛硬币可以看作是 rand2()，均匀生成 0、1 两个整数。如何根据 rand2() 生成 rand10()？将每次抛硬币的结果，看作二进制的每一位，就可以得到 [ 0 , 2 k − 1 ] [0, 2^k-1] [0,2k−1] 范围内的均匀随机整数。只需要抛 4 次硬币，就能得到 [0, 15] 范围的整数。返回 [1, 10] 范围的整数，其他情况则重新抛硬币。
def rand10():
while true:
x = 0
for _ in range(4):
x = x << 1 + rand2()
if 1 <= x <= 10: return x
取 rand7() – 1 作为对应的 7 进制位。每执行 k 次 rand7()，将得到一个 k 位的 7 进制整数，在 [ 0 , 7 k − 1 ] [0, 7^k-1] [0,7k−1] 范围内均匀分布。
只需执行 k = 2 次 rand7()，就可以得到范围为 [0, 48] 的均匀整数：
当 x ∈ [ 1 , 10 ] x \in [1, 10] x∈[1,10] 时返回 x，否则重新计算：
def rand10():
while true:
x = (rand7() - 1) * 7 + (rand7() - 1);
if 1 <= x <= 10: return x
进一步优化
选择 [1, 40] 范围里的数，通过取余运算来得到 [1, 10] 范围的数：
def rand10():
while true:
x = (rand7() - 1) * 7 + (rand7() - 1)
if 1 <= x <= 40:
return x % 10 + 1
对于上面这 9 个无用数字，计算 x % 40 可以得到 [0, 8] 范围的均匀随机整数。此时再调用一次 rand7()，计算 (x % 40) * 7 + rand7()，这相当于 rand9() * 7 + rand7()。显然，可以得到 [1, 63] 范围的均匀随机整数。这时 [1, 60] 范围里的数都可以用来作取余运算，只有 61、62、63 共 3 个无用数字：
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
对于 61、62、63，再调用一次 rand7()，计算 (x – 61) * 7 + rand7()，相当于 rand3() * 7 + rand7()，可以得到 [1, 21] 范围的均匀随机整数，这时再作取余运算，只有 1 个无用数字（21）：
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 重复执行的概率。
到此这篇关于python 概率生成问题案例详解的文章就介绍到这了,更多相关python 概率生成问题内容请搜索www.887551.com以前的文章或继续浏览下面的相关文章希望大家以后多多支持www.887551.com！
