[转]数轴上的随机游走问题

数轴原点上有一个点，每步以1/2的概率向左或向右移动1个单位长度（下文称为一步随机游走），由此可以引出许多有趣的问题：

随机游走n步后距原点距离的期望

    对这个问题可以分情况讨论：n为奇数或n为偶数。

    当n为奇数时，设n=2k+1，k为非负整数，由于正反方向是对称的，下面考虑这个点坐标为正的情况：设点向正方向上走了n-i步，负方向上走了i步，i=0,1,2,...,k，则走法数显然为C(i,n)。这样所求期望值就等于

    其中左边乘以2是考虑向反方向“对称”移动的情况，C(i,n)/2^n为这个点恰好“正方向上走了n-i步，负方向上走了i步”的概率，n-2i是这个点坐标的绝对值。

    接下来就是一个简单的求值问题了：

    当n为偶数时，设n=2k，k为非负整数，同理可以列出表达式：

    和上面的表达式形式相同：i的取值同样是0,1,2,...,k，当i=k时出现了一点小不同：这个点仍然在原点，按道理不应该乘2，但此时n-2i=0，乘不乘2无所谓，于是就得到一样的式子。化简过程有些差别：

    由此得到通项公式：

    接下来，分析这个函数的数量级：先看右边这一部分

    可以用Stirling公式换掉这里的阶乘（等价无穷大），结果为：

    而k可以换为n/2。于是E_n的近似表达式：

    或者用下面的式子表示：

    由此可以得到，E_n大致与√n成正比。

    很多人试着做“硬币随机抛掷实验”，却发现最后正面次数距总次数的1/2越来越远，其实这并不奇怪：随着抛掷次数n的增加，绝对误差就可以用上面的E_n衡量，显然是越来越大的，但是相对误差大致和n的-1/2次方成正比，随n增大而减小。所以正面次数除以总次数，得到的比值仍然是不断接近1/2的。

游走到原点左侧（猫捉老鼠问题）

    若这个点从原点出发，随机游走无穷次，求这个点走到过-1点至少一次的概率（显然这与“走到原点左侧至少一次”是等价的）。或者形象一点：老鼠在-1点处不动，猫从原点随机游走，假设猫可以游走无穷次，若走到-1点老鼠就被捉，求猫捉到老鼠的概率。

    显然，猫如果捉到老鼠，一定是在奇数步后第一次捉到。设第一次捉到老鼠时，猫走了2k+1步，则显然最后一步是从0走到-1，而前2k步是在原点右侧（包括原点）随机游走。这就是说，在每一步走完之后，向右的步数总大于向左的步数。如果按照先后顺序，向右走换为1，向左走换为0，就会得到一个长度为2k的01串，其中有k个0，k个1，到这里可以看出：这种01串的个数就是Catalan数！也就是说，如果串长为2k，则满足要求的串的个数为Catalan数

    这样所求的概率就容易表示出来，它是一个无穷级数：

    求出来它的值就行了。幸运的是，C_k有对应的生成函数：

    于是有

    令x=1，则此式的值就是所求的无穷级数的值，结果为1。也就是说，猫有100%的概率能抓到老鼠。乍一看有些反直觉，猫如果一直向右走，就抓不到老鼠；但是仔细一想就能发现：这跟在全体实数中随机选数道理一样，选到无理数的概率为1，并不代表不会选到有理数。猫抓到老鼠的概率为1，并不代表猫没有可能抓不到老鼠。

猫抓老鼠问题中游走步数的期望

    上面已经证明，猫抓到老鼠的概率为1，一定有很多人也感兴趣猫抓到老鼠所用步数的期望。式子容易推出来，它仍然是一个无穷级数：

    继续用生成函数的方法解决：

    当x=1时，这个级数发散，可以认为级数的和为∞。也就是说，猫为了抓到老鼠，平均需要随机游走∞步。这无疑又是一个反直觉的结果。好可怜的喵~~~