请选择 进入手机版 | 继续访问电脑版

[python] Python 概率天生 标题 案例详解

[复制链接]
查看223 | 回复37 | 2021-9-13 12:27:30 | 显示全部楼层 |阅读模式

概率天生 标题

  1. 有一枚不均匀的硬币,要求产生均匀的概率分布
  2. 有一枚均匀的硬币,要求产生不均匀的概率分布,如 0.25 和 0.75
  3. 利用 Rand7() 实现 Rand10()
复制代码

不匀称 硬币 产生等概率

现有一枚不匀称 的硬币 coin(),可以或许 返回 0、1 两个值,其概率分别为 0.6、0.4。要求利用 这枚硬币,产生匀称 的概率分布。即编写一个函数 coin_new() 使得它返回 0、1 的概率均为 0.5。

  1. # 不均匀硬币,返回 0、1 的概率分别为 0.6、0.4
  2. def coin():
  3. return 0 if random.randint(1,10) > 4 else 1
复制代码

统计抛两次硬币的结果 的概率分布:

  1. 结果 0 1
  2. 0 0.6<em>0.6=0.36 0.6</em>0.4=0.24
  3. 1 0.4<em>0.6=0.24 0.4</em>0.4=0.16
复制代码

一连 抛两枚硬币得到 0 1 和 1 0 的概率分布是雷同 的。因此这道题的解法就是一连 抛两次硬币,假如 得到 0 1,返回 0;假如 得到 1 0,返回 1;假如 两次结果 雷同 ,则重新抛。

以此类推,无论这枚不匀称 硬币的概率是多少,都可以用这种方法得到等概率的结果 。

  1. ddef coin_new():
  2. while True:
  3. a = coin()
  4. if coin() != a:
  5. return a
复制代码

完备 测试代码:

  1. def coin():
  2. return 0 if random.randint(1,10) > 4 else 1
  3. def coin_new():
  4. while True:
  5. a = coin()
  6. if coin() != a:
  7. return a
  8. if __name__ == '__main__':
  9. a = 0
  10. b = 0
  11. n = 100000
  12. for _ in range(n):
  13. if coin_new():a += 1
  14. if coin():b += 1
  15. print(f"1:{a/n},1:{b/n}")
复制代码

匀称 硬币 产生不等概率

现有一枚匀称 的硬币 coin(),可以或许 返回 0、1 两个值,其概率均为 0.5。要求编写一个函数 coin_new(),使得它返回指定的 0、1 概率分布。

  1. # 均匀硬币
  2. def coin():
  3. 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。

  1. def coin_new():
  2. return coin() or coin()
复制代码

P(0) = 1/3,P(1) = 2/3

一连 抛两次硬币。假如 得到 1 1,返回 0;假如 得到 1 0 或 0 1,返回 1;假如 得到 0 0,继续抛硬币。

  1. def coin_new():
  2. while True:
  3. a, b = coin(), coin()
  4. if a & b: return 0
  5. 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,重复上述过程。

  1. def coin_new():
  2. while True:
  3. x = 0
  4. for _ in range(4):
  5. x = (x << 1) + coin()
  6. if x <= 2: return 0
  7. 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] 范围的整数,其他环境 则重新抛硬币。

  1. def rand10():
  2. while True:
  3. x = 0
  4. for _ in range(4):
  5. x = x << 1 + rand2()
  6. 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,否则重新计算:

  1. def rand10():
  2. while True:
  3. x = (rand7() - 1) * 7 + (rand7() - 1);
  4. if 1 <= x <= 10: return x
复制代码

进一步优化

选择 [1, 40] 范围里的数,通过取余运算来得到 [1, 10] 范围的数:

  1. def rand10():
  2. while True:
  3. x = (rand7() - 1) * 7 + (rand7() - 1)
  4. if 1 <= x <= 40:
  5. 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 个无用数字:

  1. def rand10():
  2. while True:
  3. x = (rand7() - 1) * 7 + (rand7() - 1)
  4. if 1 <= x <= 40:
  5. return x % 10 + 1
  6. x = (x % 40) * 7 + rand7() # 1~63
  7. if x <= 60: return x % 10 + 1
复制代码

对于 61、62、63,再调用一次 Rand7(),计算 (x - 61) * 7 + Rand7(),相称 于 Rand3() * 7 + Rand7(),可以得到 [1, 21] 范围的匀称 随机整数,这时再作取余运算,只有 1 个无用数字(21):

  1. def rand10():
  2. while True:
  3. x = (rand7() - 1) * 7 + (rand7() - 1)
  4. if 1 <= x <= 40:
  5. return x % 10 + 1
  6. x = (x % 40) * 7 + rand7() # 1~63
  7. if x <= 60: return x % 10 + 1
  8. x = (x - 61) * 7 + 7 # 1~21
  9. 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 概率天生 标题 内容请搜刮 脚本之家从前 的文章或继续欣赏 下面的相干 文章渴望 大家以后多多支持脚本之家!


免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

avatar 北右酝 | 2021-9-13 14:25:55 | 显示全部楼层
admin楼主,替我问候您主治大夫!
回复

使用道具 举报

avatar 缥缈的绽放山 | 2021-9-20 02:53:06 | 显示全部楼层
每天顶顶贴,一身轻松啊!
回复

使用道具 举报

avatar deer_____0 | 2021-9-21 04:49:00 | 显示全部楼层
东方不败外加灭绝师太啊!
回复

使用道具 举报

avatar 岳兄弟散养家鸡 | 2021-9-22 03:16:36 | 显示全部楼层
admin楼主的头像是本人吗?
回复

使用道具 举报

avatar 萍381 | 2021-9-22 14:29:05 | 显示全部楼层
内容很有深度!
回复

使用道具 举报

avatar 沙941 | 2021-9-26 03:39:20 | 显示全部楼层
admin楼主是一个神奇的青年!
回复

使用道具 举报

avatar 韩邑王生1977 | 2021-10-4 09:54:38 | 显示全部楼层
在哪里跌倒,就在那里多爬一会儿!
回复

使用道具 举报

avatar 胡胡胡美丽_ss | 2021-10-9 12:19:35 | 显示全部楼层
admin楼主,您主治大夫在到处找您呢!
回复

使用道具 举报

avatar 永远爱你冰塘 | 2021-10-9 12:19:38 | 显示全部楼层
感谢admin楼主的推荐!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则