Skip to content

September 20, 2009

36

猫捉老鼠问题

这个是我室友的力学老师留给他们的思考题，因为它完全符合思维过程相当困难、但是解答却极为漂亮简单的原则，所以我就转过来分享一下。

在数轴上，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%的...这个问题当时我们宿舍的人讨论了一个晚上都没有结果，我还编了个小程序算了算小数据情况，没想到就被这么一个简单的式子搞定了...

无觅相关文章插件，快速提升流量

Read more from Interesting Maths
,
  • http://www.superwyh.com Superwyh

    解法确实没发现问题，但是有点不太明白，一定有一些极端情况啊，例如猫在两点间打转，或者一直往正方向走……

  • http://chunhao.net Chunhao

    这个证明不错啊
    这是随机漫步问题
    wiki 上说
    http://en.wikipedia.org/wiki/Random_walk
    在无穷长度的随机漫步中，漫步者通过每一点的次数都是无穷多的
    也不难理解，随机走嘛，一直走下去肯定能有一天晃荡到原点的

  • http://bobye.bokewan.com bobye

    前几天也在纠结一个问题：
    猫在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的概率空间是没有定义的

  • pia

    有点类似赌博
    初始有1元钱，输赢概率1/2，赢则赚一元，输则赔一元，一直玩下去一定会输光

  • http://www.eaglefantasy.cn Eagle Fantasy

    哈 这个类比太强大了 果然是Pia神牛啊

  • funphy

    由数学归纳法，不管初始有多少钱，输赢概率1/2，赢则赚一元，输则赔一元，一直玩下去一定会输光啊。。。

    PS:如果赢的概率x大于1/2,解出来p=1或p=x/(1-x)，前者应该是增根，如果考虑庄家每轮收取一定手续费，又如何？。。。。。

  • pia

    当猫只能走有限步n时
    n=2k时，回过原点的概率为1-C(k,2k)/2^(2k)
    n=2k+1时，回过原点的概率为1-C(k,2k+1)/2^(2k+1)

    易证这两个结果都趋向于1

  • nick

    这个证明的思路就同计算机中“递归”思想一样巧妙。谢谢分享！

  • http://zhiqiang.org/blog/ zhiqiang

    你可以再验证一个有趣的东西：猫要转到老鼠的期望时间是无穷大的...

  • http://www.eaglefantasy.cn Eagle Fantasy

    这个..神奇啊

  • hoxide

    这个叫做1D 随机游动的回归性, 2D以上就没有这个性质了.

  • hanxu33

    有一个疑问。。
    按照《有趣的无规行走模型》那篇文章的说法，N趋于无穷的时候，猫移动的距离不是应该趋向于根号N吗?。。
    为什么这里是-1了。。

    且我写了个小程序模拟了下。。N开到1000000，猫也离远点甚远。。且确实近似等于根号N。。

  • http://www.eaglefantasy.cn Eagle Fantasy

    只要曾经到过-1这个位置就算 不是最终趋近于到-1...

  • 逗你玩得乐

    可以这样想么，事件的反面就是猫走的步数趋向于无穷大后猫抓不到老鼠，也就是猫最终停留在正方向任一位置，概率应该是趋近0

  • 弱弱元培男

    证得好NB啊……
    话说费曼讲义好像有这么一段和这个有关系……

  • maxwell’s demon

    我曾经算过，当向左概率为时也可以有解，若a>0.5时有唯一有意义的解P=1，但当a<0.5是有两解，P1=1，P2<1，不知如何处理。

    又及，此问题若在二维平面或三维空间内考虑，也可以得到同样的结论

  • maxwell’s demon

    不小心写漏了，重写一次……

    我曾经算过，当向左概率不为0.5时也可以有解，若a>0.5时有唯一有意义的解P=1，但当a<0.5是有两解，P1=1，P2<1，不知如何处理。

    又及，此问题若在二维平面或三维空间内考虑，也可以得到同样的结论

  • maxwell’s demon

    再及，若对时间列方程貌似无解，难道是无限大？！

  • righthand

    给出的证明确实比较物理，但是比较直观的就是无穷数列求和，而你给的这个数列，它的和数学上是收敛于一的

  • Korn

    突然想到这道题，于是到网上搜了下。

    看来是Phy@PKU的师弟

    当时记得习题课的时候，一个同学说：在哲学上讲，如果猫抓不到老鼠，就不会停下来，所以概率是1...

    纯当笑料 哈哈

  • ET民工

    随机过程里面是这么描述这个问题的，关键词：

    马尔科夫过程，一步转移矩阵，遍历性，……

  • HYRY

    其实无论猫距离老鼠多远，无论猫朝两个方向走的概率如何，猫最终都会走到老鼠的位置。

  • http://None QQ903806024

    就像...所有实数中随机选，0的概率是多少？

  • Pingback: 赌场是凭借这个方法赚钱的吗？ | 宇宙的心弦

  • Stockard

    。。。概率为1不等于百分之百捉到老鼠。

  • Chaos423

    为什么P=1/2+1/2*P*P??? 不考虑猫先走到3或其他点再回到0的情况么？

  • Myy711

    就像级数求和之前先得证明级数收敛一样，你做这个方程之前也得先证明步骤趋于无穷大时，概率不是发散的吧？ 感觉和1 + (-1) + 1 + (-1)....一样的谬论~

  • Yangtzerong

    这题解得好

  • Yangtzerong

    博主研究一下概率大于1是什么含义，普遍的数学含义

  • also tang

    例子举得不好

  • Yefllower

    可不可以这样考虑，设猫在x位置，那么猫一直向左走抓到老鼠的概率是(1/2)^x,于是在1号位置开始，概率为1/2+(1/2)^2+(1/2)^3+...极限是1...

  • 877131596

    你没看清楚解题过程。他的解题过程是分成两种情况，第一种情况是向左走概率为1/2。第二种情况是向右走，抓住老鼠的概率是1/2*P。

  • 877131596

    这题好像有漏洞。因为步数是无穷长，所以抓住老鼠就没有什么概率了，结果应该是要么抓住老鼠，要么抓不住。把题改一下就是当猫向左走的概率大于o，就肯定能抓住老鼠，当向左走的概率为零时就肯定抓不住老鼠（这不废话吗，嘿嘿）。因为这个题在步数上的无穷，假设猫移动一步需要的时间极少接近于零而且向左走的概率不是0。现在放猫，突然猫不动了，这个题结束，为什么结束呢？因为猫抓住老鼠了。

  • Pingback: 赌徒，猫，老鼠，酒鬼 at Ponder Never Stop

  • Anonymous

    要把猫到达2号位置、3号位置、4号位置的概率也要乘进去吧，不过这些概率都不好算。。。

  • Anonymous

    同Myy711说的一样，我也认为作者默认了步骤趋于无穷大时，概率P收敛，若不收敛，显然不能这样两边划等式。这道题我想了一下，我的方法是考虑用格路径去做：把猫往左行一格用向上行一格代替，往右走不变，这样就把猫的行走路径用二维格平面表示出来，显然，猫一直只能往右上方走。现在问题变为：猫走了无限步后，所有可能的格路径和直线y=x-1不相交的概率（画个图便知）。然后，我再将求格路径总数用二叉树去处理，算得当猫走了n步后，抓到老鼠的概率约为1-1/（2^（n/2））。当n趋于无穷时，概率趋于1。不知道我这样想对不对？