V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
牛客网
mathzhaoliang
V2EX  ›  程序员

一个概率直觉题目

  •  
  •   mathzhaoliang · 3 天前 · 1043 次点击

    我们假设一个人以太阳系中心为原点,从此位置出发,在一个平面内作步长为 1 米二维的随机游动,即他每一次都随机选择东、南、西、北四个方向之一,然后向这个方向移动 1 米的距离。一旦某个时刻这个人走出了太阳系,或者回到了原点则过程结束。

    现在有 A 和 B 两个旁观者打赌,赌这个人是先回到原点,还是先走出太阳系。A 说这个人会先回到原点,B 说这个人会先走出太阳系。

    考考大家的直觉:A 和 B 获胜的概率分别是多少?

    从直觉看,毫无疑问 A 获胜的概率更大一些,毕竟从原点出发回到原点还是挺容易的。所以我提供几个选项供大家选择:

    1. B 获胜的概率在 0.1 - 1 之间。
    2. B 获胜的概率在 0.01 - 0.1 之间。
    3. B 获胜的概率在 0.01 - 0.001 之间。
    4. B 获胜的概率小于千分之一。

    大家猜猜哪个答案是对的?作为参考,太阳系的半径为 45 亿千米。

    这个问题是有较为准确的估计的,令人惊讶的是,如果你把范围放大到银河系 (半径 10^21 米),那么 A, B 各自获胜的概率变化很小。

    第 1 条附言  ·  3 天前
    B 获胜的准确值大约在 1/20 左右,所以答案是 2 。

    更准确的结论是:随着范围半径 R 的增大,B 获胜的概率近似为

    1 / (1.0293737 + lnR * 2 /π )

    所以如果你把范围扩大到银河系的话 (半径为 5 万光年),B 获胜的概率仍然有 1/30 左右,下降不大!
    15 条回复    2020-10-18 18:03:45 +08:00
    MoYi123
        1
    MoYi123   3 天前
    1

    从 A 点到 B 点的概率约等于 1/( A,B 距离画一个圆,落在圆上的点的个数)
    所以只要距离原点 2-3 个点就很难回到原点了。
    lpts007
        2
    lpts007   3 天前 via Android
    答案是 42 。

    直觉没我强的同学可以百度搜“三长一短选最短”
    lpts007
        3
    lpts007   3 天前 via Android
    曾经,我的大头是上路一霸。
    sillydaddy
        4
    sillydaddy   3 天前 via Android
    原点只是一个点,而太阳系边缘也是"无数"个点,如果游走的起始点在中心点与边缘的中间,那概率比大概就是 45 亿千的量级。如果从中心点游走。。凭直觉我选 1
    Darkside
        5
    Darkside   3 天前
    盲猜

    设操作序列长度为 n 。A 获胜的条件是东西步数一样,南北步数一样( n 只能为偶数),然后排列组合算一算; B 获胜的条件是 4^n 减去 A 获胜的情况。然后就是数列求和。

    不知道有没有好心人愿意算一算。
    xuanbg
        6
    xuanbg   3 天前
    回到原点的概率是 1/4 - 无穷小,走出太阳系的概率是 3/4 - 无穷大。因为走的步数越多,越不容易回到原点。
    winglight2016
        7
    winglight2016   3 天前
    @xuanbg xd,虽然我概率没学懂,但是我想提醒一下,概率值在 0-1 之间

    @Darkside 我的思路也是类似,不过,并不是非要四步才能回去,两步也是可以的,所以应该是这样:
    1/4*1/4+( 1-1/4*1/4 )*( 1/4*1/4 )+( 1-X )*( 1/4*1/4 )。。。X 是加法数列的第二项,因为到了第三四步或者五六步依然是 1/4*1/4 的机会和前面两步达成刚好相反的效果

    大概推导一下,1/4*1/4*( 1-1/4*1/4+1/4*1/4 -( 1/4*1/4 )^2...),想不到,最终算下来居然是 1/16,选 B 吗?
    Catam
        8
    Catam   3 天前 via iPhone
    Martingale stopping? 好久没用概率论了
    no1xsyzy
        9
    no1xsyzy   3 天前
    我只记得结论是二维游走回原点可能性随着允许半径扩大无限趋近 1
    BingoXuan
        10
    BingoXuan   3 天前 via Android
    可以简化为复数的随机游走,东 1+0j,南 0-1j,西-1+0j,北 0+1j 。回到原点概率会远高过走出太阳系。最简单的,沪指回到 3k 和上到 30k 的概率,前者远比后者大。
    mathzhaoliang
        11
    mathzhaoliang   3 天前
    @Catam 和 martingale 有关系,叫做 Green 函数。
    aguesuka
        12
    aguesuka   3 天前 via Android
    又是你,上次 f(10000,10000)的函数有点美妙,是你想出来的吗?
    aguesuka
        13
    aguesuka   3 天前 via Android
    我的思路是一维情况下,只有远离或者靠近,即距离+1 和-1 。那么从距离 n 出发时,到达 2n 和 0 的几率是一样的。递归,n 等于 1 的时候几率是 0 即到 2 和到 1 的几率是一样大的,log(2 ,2*0.45g )+log(2 ,1000)约等于 40 。二维情况,远离比靠近的几率要大。所以答案在 12 之间。
    mathzhaoliang
        14
    mathzhaoliang   3 天前
    @aguesuka

    哈哈是来自一个题目 http://pywonderland.com/mabinogion-sheep-problem/
    你那个 log 表达式看不懂。这个题目要严格解释起来确实要用到 Markov 链,鞅以及一些更精细的概念。
    aguesuka
        15
    aguesuka   3 天前
    @mathzhaoliang 就是以 2 为底,45 亿千米即 450_000_000_000 米的对数。结果大约是 40,也就是回到原点的几率是达到 45 亿 km 的记录的 40 倍。
    二维条件下,我感觉是不能用初等函数来描述的两个自然数比,已经超出的我的数学范围了。如果用程序来算这两个自然数的话,我想到的办法是 O(n^2)的时间复杂度。不知道有没有更快的方法。
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2897 人在线   最高记录 5168   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 13:25 · PVG 21:25 · LAX 06:25 · JFK 09:25
    ♥ Do have faith in what you're doing.