用公平的硬币模拟 1/Pi概率?


可能会有多种答案,发回想象力啦!

Sample:
1、1/2的概率:抛掷1次硬币即可
2、1/4的概率:抛掷2次硬币即可,取2个正面的结果
3、1/5的概率:抛掷3次硬币即可,取3个正面的结果,若出现2个正面则再掷3次硬币重复之前判定过程
4、依此类推我们可以在有限期望抛掷次数的条件下模拟所有有理数的概率

现在我们需要要用这枚标准的硬币模拟1/Pi的概率,具体要求如下:
1、我们可以保证抛掷正反概率相同(标准的硬币),但不能保证抛掷落点均匀分布
2、要求概率模拟十分精确,并且抛掷硬币次数的期望为有限次。(由于pi是无理数所以不能通过逼近的方法模拟十分精确概率了)
已邀请:

EagleSky - 每天刷刷算法多好,真不想做学术

赞同来自:


第二个条件的概率模拟十分精确且有限次估计是没有办法做到了。

一种简单的思路就是先把\(\frac{1}{\pi}\)写成一个二进制小数,\(\frac{1}{\pi} = 0.318309886\cdots = 0.01010001011111\cdots\),然后取另一个二进制小数\(a=0\)。我们开始丢硬币来确定\(a\)的值。第一次为正面记为\(a = 0.1\),第一次为反面记为\(a = 0.0\);第二次为正面则加上一个\(0.01\),否则就加上一个\(0.00\);第三次为正面则加上\(0.001\),否则加上一个\(0.000\),……这样不断重复下去,知道可以确定a与\(\frac{1}{\pi}\)的大小关系则停止。我们知道在\(0\to1\)上均匀分布的小数小于\(\frac{1}{\pi}\)的概率为\(\frac{1}{\pi}\),所以停止丢硬币时\(a<\frac{1}{\pi}\)的概率即为\(\frac{1}{\pi}\)。

当然这只不过是一种逼近,是不精确的。

要回复问题请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~