转 波利亚酒鬼回家定理的证明 波利亚定理简单易懂

【转】波利亚酒鬼回家定理的证明 波利亚定理简单易懂
证明定理:喝醉的酒鬼总能找到回家的路,喝醉的小鸟则可能永远也回不了家。

假设有一条水平直线,从某个位置出发,每次有 50% 的概率向左走1米,有50%的概率向右走1米。按照这种方式无限地随机游走下去,最终能回到出发点的概率是多少?答案是100% 。在一维随机游走过程中,只要时间足够长,我们最终总能回到出发点。
现在考虑一个喝醉的酒鬼,他在街道上随机游走。假设整个城市的街道呈网格状分布,酒鬼每走到一个十字路口,都会概率均等地选择一条路(包括自己来时的那条路)继续走下去。那么他最终能够回到出发点的概率是多少呢?答案也还是 100% 。刚开始,这个醉鬼可能会越走越远,但最后他总能找到回家路。
不过,醉酒的小鸟就没有这么幸运了。假如一只小鸟飞行时,每次都从上、下、左、右、前、后中概率均等地选择一个方向,那么它很有可能永远也回不到 出发点了。事实上,在三维网格中随机游走,最终能回到出发点的概率只有大约 34% 。
这个定理是著名数学家波利亚(George Pólya)在 1921 年证明的。随着维度的增加,回到出发点的概率将变得越来越低。在四维网格中随机游走,最终能回到出发点的概率是 19.3% ,而在八维空间中,这个概率只有 7.3% 。
答:
酒鬼回到出发点概率的证明情况十分复杂,我只能简单说明:
酒鬼回到出发点概率=2步回到出发点的概率+4步回到出发点的概率+6步回到出发点的概率......
+2n步回到出发点的概率 当n趋近于无穷时,这个和=1.
2步回到出发点的概率=2*1*(1/2)^2
4步回到出发点的概率=2*1*(1/2)^4
6步回到出发点的概率=2*2*(1/2)^6
8步回到出发点的概率=2*5*(1/2)^8
10步回到出发点的概率=2*14*(1/2)^10
12步回到出发点的概率=2*41*(1/2)^12
2n步回到出发点的概率=2*(见下面解释)*(1/2)^(2n) (n>3)
把这些全加起来,n趋于无穷时 和就等于1
解释一下:每步回到出发点的概率是3个因数的乘积
第一个因数是2。先计算出朝一个方向走(左或右)回到原点的概率,再乘2就得到该步数下回到出发点的概率。
第2个因数:1,1,2,5,14,41...是走法,比如说12步有41种走法(朝一个方向走),这个数字是数出来的,再通过归纳猜想得到公式
第3个因数:(1/2)^2n , 2n 步回到出发点,说明走了2n步,每一步的概率是1/2 ,所以总共是(1/2)^2n
第2,3个因数的乘积得到了朝一个方向走回到原点的概率:比如12步回到出发点有41种走法,每种走法的概率均为(1/2)^12。朝左朝右走都有41种走法,总的概率就是2*41*(1/2)^12
如果是奇数步走法是回不到原点的。
三维网格中的情况更加复杂。暂时是很难想出来的。过几天可能就好了
追问
请问第2个因数,也就是走法,有没有一个通项公式呢
回答
这个通项公式是这样的
第2n部的走法=第2n-2步走法*a+ 2n-4步走法 * b+第2n-6部走法*c+第2n-8部走法*d........
a,b,c,d......分别等于第2,4,6,8......步走法
也就是a,b,c,d,e,f........=1,1,2,5,14,42...............

  

爱华网本文地址 » http://www.413yy.cn/a/25101017/330654.html

更多阅读

简单易学的小魔术——铁环自缚 简单易学的魔术

简单易学的小魔术——铁环自缚——简介简单易学的小魔术——铁环自缚简单易学的小魔术——铁环自缚——工具/原料铁链一条 铁环一个简单易学的小魔术——铁环自缚——方法/步骤简单易学的小魔术——铁环自缚 1、向观众展示铁链和

8种最受欢迎的漂亮围巾围法 精 简单漂亮的小围巾

天气越来越冷呼呼啦,大家应该都慢慢的拿出围巾来围了吧!不过相信大家一定跟我一样,经过一个漫长的春夏秋天,到了冬天早就都忘记去年是怎么围围巾的了吧。今天来跟大家教你八种围围巾的方法给大家看看,简单易学。8种最受欢迎的漂亮围巾围

dnf穿梭时空的证明任务怎么完成 精 时空穿梭系统

dnf穿梭时空的证明任务怎么完成 精——简介 《地下城与勇士》是一款韩国网络游戏公司NEOPLE开发的免费色扮演2D游戏,由三星电子发行,并于2005年8 月在韩国正式发布。该游戏是一款2D卷轴式横版格斗过关网络游戏 (MMOACT),大量继承了众多

怎样简单美观的折信纸 信纸怎么折简单又漂亮

怎样简单美观的折信纸——简介很简单,也很好学。怎样简单美观的折信纸——工具/原料一张长方形纸怎样简单美观的折信纸——方法/步骤怎样简单美观的折信纸 1、首先,将纸从中间对折,然后打开,在纸的中间会留下一道折痕。怎样简单美观

转载 转摘:《经济学家是我的仇人》,作者:周洛华

原文地址:转摘:《经济学家是我的仇人》,作者:周洛华作者:磐石校尉0112 《经济学家是我的仇人》,作者:周洛华    大约一个月之前,我在报上发表了一篇有关“油价接轨,房价暴跌”的文章。这篇文章引起了许多人的关注和反馈,怀疑者有之,反对

声明:《转 波利亚酒鬼回家定理的证明 波利亚定理简单易懂》为网友像雾像雨又像风分享!如侵犯到您的合法权益请联系我们删除