关于随机游走
yurongyi
·
·
个人记录
一般随机游走是指在数轴上每一步有50%向左或向右走，这里讨论一些奇奇怪怪随机游走的问题。
（其实是数学
1. 数轴上随机左右走，从零到1的期望步数：
令f_i表示从0到i的期望步数，则由期望的线性性可以得到f_i=f_1*i。
接着，不难发现f_1=\frac{f_2}{2}+1=\frac{2*f_1}{2}+1=f_1+1,矛盾了
所以我们不难看出f_1为无穷大。
怎么证明呢？
我有一个完美的证明方法，但是这里空白太小了，写不下，所以只给出感性证明。（不严谨）
\because f_i=\frac{f_{i+1} + f_{i-1}}{2}+1
\therefore 2*f_i=f_{i+1} +f_{i-1}+2
\therefore f_{i+1}-f_i=f_i-f_{i-1}-2
$\therefore$ 如果$f_1$不为无穷大，必然存在一个足够大的$k$使得$f_k$为负数,但期望显然不为负数，矛盾。
$\therefore f_1$为无穷大，证毕。
#### 2. 数轴上随机游走n步，与原点距离的期望值
这个问题比较困难~~我不会~~，先把问题转移一下
显然最终在原点左右两边的情况对答案的贡献是相等的，所以我们只考虑数轴原点的一侧。但从0走到另一侧的情况怎么考虑呢？
我们发现这等同与走到同侧的1点。所以我们让在0的时候100%走到1点，就完成了一个完美的问题转移。
我们令$f_{i,j}$表示从$i$点走$j$步与原点距离的期望值，不难得到转移式：$f_{i,j} = \frac{f_{i+1,j-1}+f_{i-1,j-1}}{2},f_{i,0}=i$，要求的期望值即为$f_{0,i}$, ~~所以直接dp~~
这种东西一看就是有通项的，有$O(1)$做法为什么要$O(n^2)dp$呢
~~先dp打个表~~
0.00000 1.00000 1.00000 1.50000 1.50000 1.87500 1.87500 2.18750 2.18750 2.46094 2.46094
1.00000 1.00000 1.50000 1.50000 1.87500 1.87500 2.18750 2.18750 2.46094 2.46094 2.70703
2.00000 2.00000 2.00000 2.25000 2.25000 2.50000 2.50000 2.73438 2.73438 2.95312 2.95312
3.00000 3.00000 3.00000 3.00000 3.12500 3.12500 3.28125 3.28125 3.44531 3.44531 3.60938
4.00000 4.00000 4.00000 4.00000 4.00000 4.06250 4.06250 4.15625 4.15625 4.26562 4.26562
5.00000 5.00000 5.00000 5.00000 5.00000 5.00000 5.03125 5.03125 5.08594 5.08594 5.15625
6.00000 6.00000 6.00000 6.00000 6.00000 6.00000 6.00000 6.01562 6.01562 6.04688 6.04688
7.00000 7.00000 7.00000 7.00000 7.00000 7.00000 7.00000 7.00000 7.00781 7.00781 7.02539
8.00000 8.00000 8.00000 8.00000 8.00000 8.00000 8.00000 8.00000 8.00000 8.00391 8.00391
9.00000 9.00000 9.00000 9.00000 9.00000 9.00000 9.00000 9.00000 9.00000 9.00000 9.00195
10.0000 10.0000 10.0000 10.0000 10.0000 10.0000 10.0000 10.0000 10.0000 10.0000 10.0000
看出来什么了吗？
你会发现$f_{0,i}$的值每隔两位变化一次。
这是为什么呢？
因为，有一个显然的特性：在奇数步时不可能出于原点，所以再走一步向左向右对答案的贡献是一样的。而在偶数步时再走一步，从原点走出的情况会对答案产生额外的贡献。
经过一番繁琐的推式子，可以得出：
$$
f_{0,n}= \displaystyle\sum_{i=0}^{\lfloor\frac{n-1}{2}\rfloor}{\frac{2i!}{2^{2i}*i!^2}}
$$
真的是太酷啦！