醉鬼能回家，但喝醉的鸟儿可能永远回不了家！

Eufisky posted @ 2017年11月21日 18:28 in 机器学习 , 691 阅读

A drunk man will find his way home, but a drunk bird may get lost forever. —— Kakutani

醉鬼总能找到回家的路；但是喝醉了的鸟儿可能永远回不了家。 —— 角谷静夫

今天我们要谈的是一个概率论中的重要结论：Z^d上的随机游走当d≥3时是非常返的，而当d=1,2时是常返的。

Z^d在这里表示由d 维欧氏空间中全体整点（即坐标全为整数的点）构成的集合。想象有一只青蛙以秒为时间单位在Z^d上做随机游走，那么它将按如下规则运动：在初始时刻（记为第0秒），青蛙位于原点；在每一秒钟，青蛙都会等概率地跳到某一个与它上一秒所在位置相邻的整点。由于Z^d上的每个整点都有2d个邻居，因此这个概率也就是1/(2d)（见下图)。

我们这里介绍的随机游走看似一个简单的数学模型，其实它的应用十分广泛。最常见的例子有物理学中布朗运动，金融市场中股票价格波动等等。

那么我们的问题就是，既然青蛙一开始位于原点，那是否总存在一个（随机）时刻T，使得第T秒时青蛙又回到原点呢？如果是，那么我们就称这样随机游走是“常返”的，否则就称是“非常返”的。

事实上，我们总可以假设存在一个介于0和1之间的实数p，它就是青蛙回到原点的概率。仔细想想，其实p的存在性本身也是不平凡的，因为我们知道古典概率论中，事件的概率只涉及到有限个变量，而这里回到原点的行为却与青蛙在无穷时间内的行为有关。当然，在公理化概率论中，通过建立起合适的概率空间，我们可以说明这样的p是存在的。这样，我们通过引入p，判断常返性就转化为判断p是否等于1的问题了，因为“总能回到原点”用概率论的语言来说就是“以概率1回到原点”。

下面我们来看随机游走另一个有趣的性质：马氏性。我们注意到，对于任意给定的时刻，比如第100秒，第100秒后的青蛙的位置只取决于第100秒时青蛙的位置，而前100秒的时间里，青蛙如何跳到这一位置方式无关。这就是所谓的“马氏性”，即给定现在，未来和过去独立。随机游走还具有“强马氏性”。所谓“强马氏性”，是指可以把前述的“第100秒”换成任意“只取决于历史的随机时间”（这样的时间又叫停时）。比如我们定义T成为青蛙第一次回到原点的时刻，那么T就是一个停时，并且关于T的强马氏性可以这么理解为：在随机时间T之后发生的事情，与在随机时间T之间发生的事情无关，因为我们知道在第T秒，青蛙又回到原点了，所以在时间T后开始的随机游走与一开始从原点出发的随机游走将遵循同样的规律。

如果要解释什么叫“只取决于历史”，不妨看一个买卖股票的例子。比如说你今天想卖出一只股票，你当然希望可以在一天当中最高价的时候卖。但很遗憾，除了碰运气，这是不可能做到的，因为除非一天已经结束了，没人能知道股价什么时候位于最高点。相反，如果你的策略是，“如果股票价格位于过去12个小时内的最高点就卖出股票”，那这就是一个可行的策略。后面这个策略中的交易时间就是一个“只取决于历史”的随机时间，也就是停时，而前者“一天当中的最高价”则不是停时。

如果你没看懂上面一大串关于马氏链和停时的描述，没关系，你一定也可以直观地理解以下结论。如果从原点出发的青蛙以概率p会回到原点，那么青蛙一定会以概率p^2(p^n表示p的n次方，下文相同)回到原点两次，这是因为，青蛙回到原点两次＝青蛙回到原点1次＋青蛙从原点出发再回到原点1次。由强马氏性，拆分后的第二个事件的（条件）概率也是p；因此，青蛙回到原点两次的概率就是p^2。同理，青蛙会以概率p^3回到原点3次，以概率p^4回到原点4次，等等。如果我们把青蛙回到原点的总次数记为N，那么上面的计算表明P(N≥k) = p^k，也就是说N是一个服从几何分布的随机变量。当p=1时，上述论证依然成立，只不过我们得到的N是一个取值恒为+∞的随机变量。

于是，根据几何分布的期望公式，我们得到了N的期望为EN = 1/(1-p)；同样地，当p=1时，该式理解为EN=+∞。因此，EN是有限还是无穷，就刻画了随机游走是否常返。

我们还可以从另一个角度来计算EN。令X(n)为第n秒青蛙所在的位置，而an是取值0和1的随机变量，其中a(n)＝1当且仅当X(n)=0，即a(n)＝1当且仅当第n秒青蛙位于原点。根据定义我们得到N是全体a(n)的和，也就是N=a(1) + a(2) +…+ a(n) +… 这是显然的，因为整个数列(a(n))中有多少个1，就代表青蛙返回了多少次原点。

当我们对以上无穷和式取期望，并根据期望的线性性，交换无穷求和与求期望的顺序（这里能够换序是因为涉及的项an都是非负的，因此满足换序的条件），我们得到

EN = E(a(1) + a(2) +…+ a(n) +…) = E a(1) + E a(2) +...+E a(n) +...

等等，E a(n) 是什么呢？根据定义，E a(n) = P(X(n)= 0)，正是第n秒青蛙恰好位于原点的概率！计算这个概率就是一个组合问题了，而判断常返性则变成了一个判断无穷级数敛散性的问题。

记A(n)= E a(n) ＝ P(X(n)= 0)。下面我们的目标就是对A(n)进行估计，并由此判断无穷级数∑A(n)是否收敛。

在一维(d=1)时，如何计算A(n)呢？注意到每一秒钟青蛙必须向左跳或者向后跳。因此在第n秒回到原点的必要条件就是n为偶数。而当n为偶数时，青蛙必须恰好有n/2的时间向左跳，有n/2的时间向右跳，才能在第n秒回到原点。我们知道每秒钟青蛙向左和向右的概率都是1/2，那么利用组合数公式，我们就得到

对于阶乘，斯特林公式给出了渐近公式：m! ∼(m/e)^n·sqrt(2πn) （sqrt表示开二次根号，下同）。代入A(n)的表达式，我们得到A(n)∼1/n·sqrt(2/π)这个渐近关系当然只限于n为偶数）。微积分中熟知的结论是p级数∑1/n^p收敛当且仅当p>1，否则发散。于是我们得到∑A(n)在d=1时发散，也就是说一维随机游走是常返的。

如果我们在高维时采用类似的方法，就能得到A(n) ∼ c· n^(-d/2)，其中c是与d有关的一个常数。同样再借助p级数的知识，就能得到当且仅当d/2 > 1时，也就是d ≥3时，随机游走不常返；相反，d=1，2时，随机游走常返。

为了避免复杂的组合数估计，我们也可以从另一个简单的事实中看出A(n)的阶就是n^(-d/2)。如果我们令y(n)=X(n)-X(n-1)为第n秒时青蛙的位移，容易看出所有y(n)都是独立同分布的随机单位向量。由中心极限定理，Z(n) :=X(n)/sqrt(n) = (y(1) + y(2) + … y(n))/sqrt(n)将趋向于一个d维正态分布Z。那X(n)=0意味着什么呢？由于X(n)只能取整点，那么X(n)= 0表明Z(n)的取值大约位于原点附近一个边长为的1/sqrt(n)小正方体中。根据中心极限定理，Z(n)的取值落于这个小正方体中的概率与Z是差不多的，而对于后者，这样的概率恰恰就约等于小正方体的体积，(1/sqrt(n))^d（注意到是d维空间），乘以原点处Z的密度函数大小，一个非零的常数。这样我们就很容易得到了A(n) ∼ c· n^(-d/2)这个结论。

如果要把这个随机游走的小结论用于生活中，我们也许会为再也不用担心认不得路而感到欣慰，因为二维随机游走是常返的，就算是不认识路随便乱走，也总能到达任何想去的地方！当然这句话既对也错；对的地方在于，由常返性，确实总存在一个时间T，在平面上随机游走的你也能走到任意想去的地方；错的地方在于，更进一步的理论表明，这个随机时间T是一个期望为无穷的随机变量，也就是从平均的意义上说，你永远也到不了目的地！

作者：小米