Skip to content

September 20, 2009

39

猫捉老鼠问题

作者: physixfan

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

在数轴上,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
39 Comments Post a comment
  1. Sep 20 2009

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

    Reply
  2. Sep 21 2009

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

    Reply
  3. bobye
    Sep 21 2009

    前几天也在纠结一个问题:
    猫在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
  4. pia
    Sep 21 2009

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

    Reply
    • Sep 21 2009

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

      Reply
      • funphy
        Sep 22 2009

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

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

  5. pia
    Sep 22 2009

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

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

    Reply
  6. nick
    Sep 23 2009

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

    Reply
  7. Sep 26 2009

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

    Reply
  8. Sep 26 2009

    这个..神奇啊

    Reply
  9. hoxide
    Sep 28 2009

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

    Reply
  10. hanxu33
    Sep 29 2009

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

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

    Reply
    • Sep 29 2009

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

      Reply
  11. 逗你玩得乐
    Oct 1 2009

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

    Reply
  12. 弱弱元培男
    Oct 11 2009

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

    Reply
  13. maxwell's demon
    Oct 11 2009

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

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

    Reply
  14. maxwell's demon
    Oct 11 2009

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

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

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

    Reply
  15. maxwell's demon
    Oct 11 2009

    再及,若对时间列方程貌似无解,难道是无限大?!

    Reply
  16. righthand
    Nov 28 2009

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

    Reply
  17. Korn
    Jan 13 2010

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

    看来是Phy@PKU的师弟

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

    纯当笑料 哈哈

    Reply
  18. ET民工
    Feb 8 2010

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

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

    Reply
  19. HYRY
    Mar 21 2010

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

    Reply
  20. QQ903806024
    Jul 14 2010

    就像…所有实数中随机选,0的概率是多少?

    Reply
  21. Monte Carlo
    May 30 2012

    这不是Markov模型吗??

    Reply
  22. Jan 23 2015

    因为无限二字

    Reply

Trackbacks & Pingbacks

  1. 赌场是凭借这个方法赚钱的吗? | 宇宙的心弦
  2. 赌徒,猫,老鼠,酒鬼 at Ponder Never Stop

Share your thoughts, post a comment.

(required)
(required)

Note: HTML is allowed. Your email address will never be published.

Subscribe to comments