E33 波利亚的醉汉.pdf

《E33 波利亚的醉汉.pdf》由会员分享，可在线阅读，更多相关《E33 波利亚的醉汉.pdf（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、波利亚的醉汉 1 波利亚的醉汉 波利亚（George Polya） 1921 年发表 论文“ber eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Stra ennetz.” 提出了“随机游走问题” 2 波利亚的醉汉 考虑一个喝醉的酒鬼，他走出家门在 一条足够长的笔直街道上随机游走 他每一步都以概率1/2选择向东走1 米，以概率1/2选择向西走1米 假设他只要没回到家门前只要没回到家门前，就会按照 这种方式无限地走下去 他最终能回到家门口的概率是多少？ 答案是惊人的“1”！ 3 波利亚的醉汉 使用格

2、路模型的一个计算方法： 只考虑“一半”情形，就是假设第1步必定是往右 （东）走的 剩下一半情形是对称的 而后原问题的概率就等于这限定了第一步的问题的概 率 很容易知道，必定是走了偶数步后才有可能正好在家 门口 对于 n 1 ，定义 S(n) 为经过 2n 步才第一次回到家门 口的“走路方案数” 例如 S(1) = 1 （右左） S(2) = 1 （右右左左） S(3) = 2 （右右右左左左、右右左右左左） 4 波利亚的醉汉 如果将往左（西）走改为往上走，那么醉汉的随 机游步就相当于在下面的格点图中，从 (1, 0) 出 发，每次等概率地向上走1格或者向右走1格 而回到家门前就相当于走到了直线

3、 y=x 上 5 波利亚的醉汉 经过 2n 步才第一次回到家门口就相当于 从 (1, 0) 走到 (n, n 1) 而且不走到直线 y=x 上，最后再向上走一格 例如下图 6 波利亚的醉汉 从 (1, 0) 走到 (n, n 1) 且不走到 y=x 上 不能“接触”对角线的格路问题 方案数：卡特兰数 Cn 1 7 波利亚的醉汉 于是，在确定第一步的走法后，经过 2n 步才第一次回到家门口的概率是 8 波利亚的醉汉 在0附近，有 对所有的正整数 n 求和就得到他最终能 回到家门口的概率是 9 1 波利亚的醉汉 2维情况：假设城市的街道 呈网格状分布，他每走到一 个十字路口，都会等概率地 向东、南

4、、西、北任意走一 格，那么他最终能回到家门 口的概率还是1 3维情况，他最终能回到家 门口的概率只是0.34 之后随着维度增加，回到出 发点的概率变得越来越低： 10 维数 最终能回到 家门的概率 3 33.77% 4 19.32% 5 13.52% 6 10.47% 7 8.58% 8 7.29% 9 6.34% 10 5.62% 波利亚的醉汉 最后要说明的问题是：明明他可以一可以一 直往东头也不回地走下去直往东头也不回地走下去的！为什么 他最终能回到家门口的概率是“1”？ 换言之，什么叫做他可以“以概率以概率1 （with probability one）”回到家？ 这是因为概率概率1不等于必然，概不等于必然，概 率率0也不等于也不等于不可能不可能 11