蚂蚁森林保护区巡查次数的数学期望是多少？

Yiyan

给没有玩过的同学简单介绍一下。
巡查路线是一个环形路线，路线上一共分布着n个站点。
从起点出发，生成一个[1,m]之间的随机整数X，逆时针前进X步，所到达的站点视为已巡视，所途径的其他站点不视为已巡视。
如此反复，直至重复Y次这样的过程后所有的站点均被巡视过。
现在的问题是，假设生成[1,m]之间的随机整数这一步的概率是均匀的（实际上蚂蚁森林是不是这么做的我姑且存疑），那么Y的数学期望是多少？

Tanix

从当前所在站点朝一个方向将巡查线路展开，可以得到一个n位向量，对应一个状态，总共有2^n个状态
状态之间有转移概率，并且最后都会到全部被巡视的状态，所以可以看成有一个吸收状态的吸收马尔可夫链，求平均吸收时间为多少
这些状态可以分成n+1组，记为G_i:有i个站点被巡视过的状态集合,0\le i\le n，那么G_i只能到达G_i或G_{i+1}
一般的情况难以求解，但当n=m的时候，G_i中每个状态的平均吸收时间\mu_i都相同，可得方程组
\mu_n=0\\ \mu_i=1+\frac{i}{n}\mu_i+\frac{n-i}{n}\mu_{i+1},\ 0\le i\le n-1
即
\mu_n=0\\ \mu_i-\mu_{i+1}=\frac{n}{n-i},\ 0\le i\le n-1
累加得
\mu_0=\sum_{i=0}^{n-1}\frac{n}{n-i}=n\sum_{i=1}^{n}\frac{1}{i}

Cauch

Tanix
好!随机过程学的非常扎实（）
但是实际情况m=3，n比m大很多，要怎么算呢😂

Tanix

Cauch 如果n和m确定的话，可以从G_n开始，将G_i中所有状态的平均吸收时间代入G_{i-1}对应的方程组，得到只关于G_{i-1}内变量的线性方程组，解之，重复这个过程，直到算出初始状态的平均吸收时间

Tanix

手动求了一下n=4,m=3的情况，发现n=m+1时，G_i内所有以1开头的状态的平均吸收时间一样，用\mu_i表示，那么可以列出方程组
\mu_{m+1}=0\\ \mu_{i}=1+\frac {i-1} m \mu_{i}+\frac {m-i+1} m \mu_{i+1},\ 1\le i\le m\\ \mu_0=1+\mu_1
即
\mu_{m+1}=0\\ \mu_i-\mu_{i+1}=\frac{m}{m-i+1},\ 1\le i\le m\\ \mu_0-\mu_1=1
累加得
\mu_0=1+\sum_{i=1}^m \frac{m}{m-i+1}=1+m\sum_{i=1}^m \frac{1}{i}