我们假设一个人以太阳系中心为原点,从此位置出发,在一个平面内作步长为 1 米二维的随机游动,即他每一次都随机选择东、南、西、北四个方向之一,然后向这个方向移动 1 米的距离。一旦某个时刻这个人走出了太阳系,或者回到了原点则过程结束。
现在有 A 和 B 两个旁观者打赌,赌这个人是先回到原点,还是先走出太阳系。A 说这个人会先回到原点,B 说这个人会先走出太阳系。
考考大家的直觉:A 和 B 获胜的概率分别是多少?
从直觉看,毫无疑问 A 获胜的概率更大一些,毕竟从原点出发回到原点还是挺容易的。所以我提供几个选项供大家选择:
大家猜猜哪个答案是对的?作为参考,太阳系的半径为 45 亿千米。
这个问题是有较为准确的估计的,令人惊讶的是,如果你把范围放大到银河系 (半径 10^21 米),那么 A, B 各自获胜的概率变化很小。
1
MoYi123 2020-10-18 01:42:14 +08:00
1
从 A 点到 B 点的概率约等于 1/( A,B 距离画一个圆,落在圆上的点的个数) 所以只要距离原点 2-3 个点就很难回到原点了。 |
2
lpts007 2020-10-18 02:32:36 +08:00 via Android
答案是 42 。
直觉没我强的同学可以百度搜“三长一短选最短” |
3
lpts007 2020-10-18 02:45:46 +08:00 via Android
曾经,我的大头是上路一霸。
|
4
sillydaddy 2020-10-18 07:56:35 +08:00 via Android
原点只是一个点,而太阳系边缘也是"无数"个点,如果游走的起始点在中心点与边缘的中间,那概率比大概就是 45 亿千的量级。如果从中心点游走。。凭直觉我选 1
|
5
Darkside 2020-10-18 08:32:30 +08:00
盲猜
设操作序列长度为 n 。A 获胜的条件是东西步数一样,南北步数一样( n 只能为偶数),然后排列组合算一算; B 获胜的条件是 4^n 减去 A 获胜的情况。然后就是数列求和。 不知道有没有好心人愿意算一算。 |
6
xuanbg 2020-10-18 09:19:43 +08:00
回到原点的概率是 1/4 - 无穷小,走出太阳系的概率是 3/4 - 无穷大。因为走的步数越多,越不容易回到原点。
|
7
winglight2016 2020-10-18 10:34:44 +08:00
|
8
Catam 2020-10-18 11:14:46 +08:00 via iPhone
Martingale stopping? 好久没用概率论了
|
9
no1xsyzy 2020-10-18 13:26:44 +08:00
我只记得结论是二维游走回原点可能性随着允许半径扩大无限趋近 1
|
10
BingoXuan 2020-10-18 13:26:58 +08:00 via Android
可以简化为复数的随机游走,东 1+0j,南 0-1j,西-1+0j,北 0+1j 。回到原点概率会远高过走出太阳系。最简单的,沪指回到 3k 和上到 30k 的概率,前者远比后者大。
|
11
mathzhaoliang OP @Catam 和 martingale 有关系,叫做 Green 函数。
|
12
aguesuka 2020-10-18 14:10:49 +08:00 via Android
又是你,上次 f(10000,10000)的函数有点美妙,是你想出来的吗?
|
13
aguesuka 2020-10-18 16:09:59 +08:00 via Android
我的思路是一维情况下,只有远离或者靠近,即距离+1 和-1 。那么从距离 n 出发时,到达 2n 和 0 的几率是一样的。递归,n 等于 1 的时候几率是 0 即到 2 和到 1 的几率是一样大的,log(2 ,2*0.45g )+log(2 ,1000)约等于 40 。二维情况,远离比靠近的几率要大。所以答案在 12 之间。
|
14
mathzhaoliang OP @aguesuka
哈哈是来自一个题目 http://pywonderland.com/mabinogion-sheep-problem/ 你那个 log 表达式看不懂。这个题目要严格解释起来确实要用到 Markov 链,鞅以及一些更精细的概念。 |
15
aguesuka 2020-10-18 18:03:45 +08:00
@mathzhaoliang 就是以 2 为底,45 亿千米即 450_000_000_000 米的对数。结果大约是 40,也就是回到原点的几率是达到 45 亿 km 的记录的 40 倍。
二维条件下,我感觉是不能用初等函数来描述的两个自然数比,已经超出的我的数学范围了。如果用程序来算这两个自然数的话,我想到的办法是 O(n^2)的时间复杂度。不知道有没有更快的方法。 |