一个概率直觉题目

[mathzhaoliang]

我们假设一个人以太阳系中心为原点，从此位置出发，在一个平面内作步长为 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 各自获胜的概率变化很小。

[MoYi123]

1

从 A 点到 B 点的概率约等于 1/（ A，B 距离画一个圆，落在圆上的点的个数）
所以只要距离原点 2-3 个点就很难回到原点了。

[lpts007]

答案是 42 。

直觉没我强的同学可以百度搜“三长一短选最短”

[lpts007]

曾经，我的大头是上路一霸。

[sillydaddy]

原点只是一个点，而太阳系边缘也是"无数"个点，如果游走的起始点在中心点与边缘的中间，那概率比大概就是 45 亿千的量级。如果从中心点游走。。凭直觉我选 1

[Darkside]

盲猜

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

不知道有没有好心人愿意算一算。

[xuanbg]

回到原点的概率是 1/4 - 无穷小，走出太阳系的概率是 3/4 - 无穷大。因为走的步数越多，越不容易回到原点。

[winglight2016]

@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]

Martingale stopping? 好久没用概率论了

[no1xsyzy]

我只记得结论是二维游走回原点可能性随着允许半径扩大无限趋近 1

[BingoXuan]

可以简化为复数的随机游走，东 1+0j，南 0-1j，西-1+0j，北 0+1j 。回到原点概率会远高过走出太阳系。最简单的，沪指回到 3k 和上到 30k 的概率，前者远比后者大。

[mathzhaoliang]

@Catam 和 martingale 有关系，叫做 Green 函数。

[aguesuka]

又是你，上次 f(10000,10000)的函数有点美妙，是你想出来的吗？

[aguesuka]

我的思路是一维情况下，只有远离或者靠近，即距离+1 和-1 。那么从距离 n 出发时，到达 2n 和 0 的几率是一样的。递归，n 等于 1 的时候几率是 0 即到 2 和到 1 的几率是一样大的，log(2 ,2*0.45g )+log(2 ,1000)约等于 40 。二维情况，远离比靠近的几率要大。所以答案在 12 之间。

[mathzhaoliang]

@aguesuka

哈哈是来自一个题目 http://pywonderland.com/mabinogion-sheep-problem/
你那个 log 表达式看不懂。这个题目要严格解释起来确实要用到 Markov 链，鞅以及一些更精细的概念。

[aguesuka]

@mathzhaoliang 就是以 2 为底，45 亿千米即 450_000_000_000 米的对数。结果大约是 40，也就是回到原点的几率是达到 45 亿 km 的记录的 40 倍。
二维条件下，我感觉是不能用初等函数来描述的两个自然数比，已经超出的我的数学范围了。如果用程序来算这两个自然数的话，我想到的办法是 O(n^2)的时间复杂度。不知道有没有更快的方法。