猫捉老鼠问题
Posted in Interesting Maths by Eagle Fantasy on September 20th, 2009
这个是我室友的力学老师留给他们的思考题，因为它完全符合思维过程相当困难、但是解答却极为漂亮简单的原则，所以我就转过来分享一下。
在数轴上，0的位置停着一个不动的老鼠，1的位置在初始时刻有一只猫。猫是可以走动的，每一步在数轴上分别以二分之一的概率或朝着正方向或朝着负方向走1的距离。当猫到达0的位置时，猫就抓到老鼠了，游戏结束。问当猫走的步数趋向于无穷大的时候，最终捉到老鼠的概率是多大？一定要先仔细思考再看解答…
解答：
将所求概率记为P。
猫第一步以1/2的概率左行捉到老鼠，对P的贡献是1/2.
猫第一步以1/2的概率右行，到达x=2的位置。为捉到老鼠，猫首先必须左行到x=1的位置，这与问题所求的猫从x=1到x=0位置的情况相同，概率同为P。到达x=1的位置后，游戏又回到初态，猫左行至x=0处概率仍为P。因此，猫先右行至x=2，然后最终回到x=0对P的贡献为1/2*P*P。
因此有P=1/2+1/2*P*P
解得P=1。
最终的结论，居然是猫有100%的概率捉到老鼠，这多少有点出人意料。至少我在之前是怎么都觉得不是100%的…这个问题当时我们宿舍的人讨论了一个晚上都没有结果，我还编了个小程序算了算小数据情况，没想到就被这么一个简单的式子搞定了…
Related posts:
September 20th, 2009 at 8:13 pm
解法确实没发现问题，但是有点不太明白，一定有一些极端情况啊，例如猫在两点间打转，或者一直往正方向走……
Reply
September 21st, 2009 at 2:02 am
这个证明不错啊
这是随机漫步问题
wiki 上说
http://en.wikipedia.org/wiki/Random_walk
在无穷长度的随机漫步中，漫步者通过每一点的次数都是无穷多的
也不难理解，随机走嘛，一直走下去肯定能有一天晃荡到原点的
Reply
September 21st, 2009 at 10:11 am
前几天也在纠结一个问题：
猫在1/2时刻向右走1位，3/4时刻再向右走1位，7/8时刻再走1位，……问在时刻1，数轴上有猫的概率为多少，一个可能的解答是：
E=并(P_k) 其中E为时刻1时数轴上有猫事件，P_k为时刻1数字k上有猫事件
由可列可加性知道
P(E)<=sum P(P_k)=0
从而时刻1时数轴上有猫的概率为0
哈哈
事实上在时刻1的概率空间是没有定义的
Reply
September 21st, 2009 at 8:54 pm
有点类似赌博
初始有1元钱，输赢概率1/2，赢则赚一元，输则赔一元，一直玩下去一定会输光
Reply
Eagle Fantasy reply on September 21st, 2009:
哈 这个类比太强大了 果然是Pia神牛啊
Reply
funphy reply on September 22nd, 2009:
由数学归纳法，不管初始有多少钱，输赢概率1/2，赢则赚一元，输则赔一元，一直玩下去一定会输光啊。。。
PS:如果赢的概率x大于1/2,解出来p=1或p=x/(1-x)，前者应该是增根，如果考虑庄家每轮收取一定手续费，又如何？。。。。。
Reply
September 22nd, 2009 at 8:01 pm
当猫只能走有限步n时
n=2k时，回过原点的概率为1-C(k,2k)/2^(2k)
n=2k+1时，回过原点的概率为1-C(k,2k+1)/2^(2k+1)
易证这两个结果都趋向于1
Reply
September 23rd, 2009 at 8:55 am
这个证明的思路就同计算机中“递归”思想一样巧妙。谢谢分享！
Reply
September 26th, 2009 at 9:30 pm
你可以再验证一个有趣的东西：猫要转到老鼠的期望时间是无穷大的…
Reply
September 26th, 2009 at 11:08 pm
这个..神奇啊
Reply
September 28th, 2009 at 8:47 pm
这个叫做1D 随机游动的回归性, 2D以上就没有这个性质了.
Reply
September 29th, 2009 at 11:21 am
有一个疑问。。
按照《有趣的无规行走模型》那篇文章的说法，N趋于无穷的时候，猫移动的距离不是应该趋向于根号N吗?。。
为什么这里是-1了。。
且我写了个小程序模拟了下。。N开到1000000，猫也离远点甚远。。且确实近似等于根号N。。
Reply
Eagle Fantasy reply on September 29th, 2009:
只要曾经到过-1这个位置就算 不是最终趋近于到-1…
Reply
October 1st, 2009 at 9:57 am
可以这样想么，事件的反面就是猫走的步数趋向于无穷大后猫抓不到老鼠，也就是猫最终停留在正方向任一位置，概率应该是趋近0
Reply
October 11th, 2009 at 1:11 am
证得好NB啊……
话说费曼讲义好像有这么一段和这个有关系……
Reply
October 11th, 2009 at 9:27 pm
我曾经算过，当向左概率为时也可以有解，若a>0.5时有唯一有意义的解P=1，但当a<0.5是有两解，P1=1，P2<1，不知如何处理。
又及，此问题若在二维平面或三维空间内考虑，也可以得到同样的结论
Reply
October 11th, 2009 at 9:36 pm
不小心写漏了，重写一次……
我曾经算过，当向左概率不为0.5时也可以有解，若a>0.5时有唯一有意义的解P=1，但当a<0.5是有两解，P1=1，P2<1，不知如何处理。
又及，此问题若在二维平面或三维空间内考虑，也可以得到同样的结论
Reply
October 11th, 2009 at 9:37 pm
再及，若对时间列方程貌似无解，难道是无限大？！
Reply
November 28th, 2009 at 7:38 pm
给出的证明确实比较物理，但是比较直观的就是无穷数列求和，而你给的这个数列，它的和数学上是收敛于一的
Reply
January 13th, 2010 at 5:32 pm
突然想到这道题，于是到网上搜了下。
看来是Phy@PKU的师弟
当时记得习题课的时候，一个同学说：在哲学上讲，如果猫抓不到老鼠，就不会停下来，所以概率是1…
纯当笑料 哈哈
Reply
February 8th, 2010 at 4:13 pm
随机过程里面是这么描述这个问题的，关键词：
马尔科夫过程，一步转移矩阵，遍历性，……
Reply
March 21st, 2010 at 9:19 am
其实无论猫距离老鼠多远，无论猫朝两个方向走的概率如何，猫最终都会走到老鼠的位置。
Reply
July 14th, 2010 at 6:59 pm
就像…所有实数中随机选，0的概率是多少？
Reply