酒鬼漫步的数学——随机过程 | 张天蓉专栏

无规行走是一类随机过程。何谓随机过程？之前我们以丢硬币为例介绍了随机变量，随机过程就是一系列随机变量的集合。比如说，每丢一次硬币，便产生一个随机变量X，那么，我们一次又一次地丢下去，便产生出一系列的随机变量X1，X2…… Xi ……，酒鬼的漫步也类似，总的路径是酒鬼多次随机选择行走的所有路径的集合。随机变量序列集合起来，便形成了“随机过程”。随机过程中的Xi，可看作是时间 ti 的“函数”。

与经典物理学类似，物理系统随时间演化的过程，要遵循牛顿物理学的规律。随机过程也有它的运动规律。但不同的是，随机过程的变量是取值不确定的随机变量，这使得随机过程相比于“不随机的过程”更难以处理。

此处还应介绍一个新的定义——伯努利过程。丢一次硬币产生一个取值为1或0的随机变量X，那么，接连丢下去产生的随机变量的集合就被称为伯努利过程。伯努利过程是一个时间离散，取值也离散的随机过程，其中随机变量的样本空间只有两个取值：成功（1）、或失败（0），成功的概率为p。例如，掷一个6面对称的骰子，如果将“3”出现的概率定为成功的话，则多次掷骰子的结果是一个p=1/6的伯努利过程。

马尔可夫链^[1]

伯努利过程比较乏味，因为得到正面的概率是个固定值p，每次抛掷的结果互相独立，这种独立性是构成之前所介绍的“赌徒谬误”的基础。

然而，真实随机变量之间，往往存在着互相依赖的关系。比如说，考虑明天北京下雨或天晴的可能性，一般来说与北京今天、昨天的气候状况有关。

►图2：典型的马尔可夫过程

简单而言，假设明天下雨的概率只与今天的天气有关，则“雨晴”的转换可以用一个如图2a的图形来描述。图中，“雨”和“晴” 两种状态之间被数条带箭头的曲线连接。这些连线表示从今天的状态，如何预测明天的状态。比如说，从状态“雨”出发有两条连线：结束于状态“晴”的右边那一条标上了“0.6”，意思是说：“今天雨明天晴的概率是60%”；左边曲线绕了一圈又返回“雨”，标识0.4，即“明天继续下雨的概率是40%”。可以类似地理解从状态“晴”出发的两条曲线：如果今天晴，那么明天有80%的可能性晴，20%的可能性下雨。

时间上离散的过程，也被称为“链”，上述例子是一个典型的、也是最简单的马尔可夫链，它也得名于俄罗斯数学家安德烈·马尔可夫（Andreyevich Markov，1856－1922）。马尔可夫链具有马尔可夫性质，也被称为“无记忆性”或“无后效性”，即下一状态的概率分布只由当前状态决定，与过去的事件无关。反映到上述案例中，明天“晴雨”的概率只与今天的状态有关，而与昨天以及更早之前的气候均无关。

除了用图形来表示马尔可夫链之外，“雨晴”变换关系也可以用图2b的转换矩阵P来描述。矩阵中的数值，表示系统演化“一步”后状态之间的转移概率。矩阵表示中的状态是一个矢量，图2b中，今天的状态被表示为一个分量为0.3和0.7的矢量，明天的状态则由P乘以今天之状态而得到。

►图3：时齐马尔可夫链

值得注意的是，上述矩阵中的转移概率并不随时间而变化，即矩阵中的各个元（0.4, 0.6, 0.2, 0.8）的数值是固定的，这种马尔可夫过程页叫做时齐马尔可夫过程。比如说，如图3所示，假设北京任何一天的“晴雨”状态都由前一天的状态乘以同样的转换矩阵P而得到，则这个过程是时齐的。通常考虑的马尔可夫过程，都被假定是“时齐”的。

除了“时齐”性之外，人们还对长时间后趋于稳定状态的马尔科夫过程颇为感兴趣。

假设一周内的股票市场只用简单的3种状态表示：牛市、熊市、停滞不前。其转移概率如图4所示。

►图4：股票市场的极限概率分布

当时间足够长的时候，这个马尔可夫链产生的一系列随机状态趋向一个极限向量，即图4中右下角所示的矢量Xlimit =[0.47, 0.3, 0.23]，也就是系统最后的稳态向量。按照这个特殊的股票市场模型，长远的市场趋势趋于稳定，即每周的股票情况是：47%的概率是牛市、30%熊市、23%停滞不前。

酒鬼失足、赌徒破产及鸟儿回家

无规行走可以看做是马尔科夫链的特例[2]，它的状态空间不是像上述抛硬币等例子中那种由简单的几种有限的基本状态构成的，而是由无限延伸的“物理空间”构成，这儿的“空间”可以是任意维度的。

那么，为什么说酒鬼漫步是马尔可夫链呢？因为，醉汉在时刻 ti+1 的状态（即位置）仅由他在时刻 ti 的状态（xi, yi），以及他随机选择的方向所决定，与过去（ti 之前）走过的路径无关。

我们再来讨论一个“酒鬼掉下悬崖”的趣题。前文曾经介绍过高尔顿钉板实验，可作为一维无规行走的例子。高尔顿钉板虽然貌似一个二维空间，但因为小球在垂直方向的运动并不是随机的，而是每次固定向下1格，因此可以视作一个向下的时间轴，而水平方向则是一个一维无规行走，见图5。

►图5：求一维酒鬼掉下悬崖的概率

在图5中，钉板的水平方向为x轴，垂直向下为时间轴。悬崖处设为x=0（图5左边虚线）。假设酒鬼（顶端的小球）起始时位于x=n的格点位置，即离悬崖有n格之遥。酒鬼朝下漫步过程中的每一步，向右（x增大）概率为p，向左概率为（1-p）。现在问：酒鬼从位置n漫游，掉下悬崖的概率是多少（悬崖的位置在x=0处，所以，当随机变量x的值到达0，可作为酒鬼掉下了悬崖的判据）？

先考虑一个简化的具体问题，比如说，设酒鬼漫步时向右走的概率p=2/3，向左走的概率为q=1-p=1/3，那么，酒鬼从x=1的位置开始漫游掉下悬崖的概率是多少？

也许有人会很快就得出答案：酒鬼从x=1向左走一步就到了悬崖，而他向左走的概率为1/3。那么，他掉下悬崖的概率不就是1/3吗？事情并不是那么简单。1/3是酒鬼第一步向左走掉下悬崖的概率，但他第一步向右走仍然有可能掉下悬崖，比如说，右走一步之后又再左走两步不也一样到达x=0的格点吗？所以，掉下悬崖的总概率比1/3要大，要加上第一步向右走到了x=2的点但后来仍然掉下悬崖的概率。

为了更清楚地分析这个问题，我们将酒鬼从x=1处漫步到x=0处的概率记为P1。这个概率显然就是刚才简化问题中要求解的：从x=1处开始漫步掉入悬崖的概率。同时，从这个问题的平移对称性考虑，P1也是酒鬼从任何x=k左移一个格点，漫步（不管多少步）到达x=k-1格点位置的概率。需要注意：酒鬼走一步，与他的格点位置移动一格是两码事，位置从x=k左移到x=k-1，也许要走好几步，这与两点之间的“路径与位移”是一个道理。

除了P1之外，将从x=2处开始漫步掉入悬崖的概率记为P2=P₁² ，x=3处的概率记为P3=P₁³……以此类推，如刚才所分析的，对P1可以列出一个等式：

P1 = 1-p+pP₁²

其中，p是酒鬼朝悬崖反方向游走的概率。由此可以解出P1 = 1或者P1= (1-p)/p。对这个问题有意义的解是P1= (1-p)/p，Pn=P₁ⁿ 。

当p=1/2时，P1=1，意味着酒鬼最终一定会掉下悬崖；当p<1/2，P1>1，Pn也一样，但概率最多只能为1。所以，如果酒鬼朝悬崖反方向的概率不足1/2的话，无论他开始时距离悬崖多远，酒鬼也是肯定要掉下悬崖的；如果p=2/3，算出P1=1/2，Pn=(1/2)ⁿ，n越大，即酒鬼初始位置离悬崖越远，失足的可能性便越小。

无规行走模型的应用范围很广，酒鬼失足悬崖的问题也有许多不同的故事版本，但描述的数学模型基本一致。比如说，赌徒破产问题就是其中一例：赌徒在赌场赌博，赢的概率是p，输的概率1-p，每次的赌注为1元，假设赌徒最开始时有赌金n元，赢了赌金加一元，输了赌金减一元。问：赌徒输光的概率是多少？这个问题与上面解决的酒鬼悬崖问题的数学模型完全一样，赌金的数目对应于酒鬼漫步中的一维距离x，悬崖位置x=0便对应于赌金输光赌徒破产。从上面分析可知，即使p=1/2，酒鬼也必定掉下悬崖，即赌徒最终一定破产。

酒鬼失足问题还可以稍加变换构成一些新型的趣题。比如说，假设酒鬼的路上两边都有悬崖，计算分别掉到两边悬崖的概率；赌博问题上，便相当于两个赌徒A和B赌博，看谁先输光。

也可以假设酒鬼的路上根本没有悬崖，且路的两头都可以无限延伸，酒鬼从自家门口出发，要你计算，酒鬼出去漫游之后，最后还能够回到家的概率等于多少？

美籍匈牙利数学家波利亚（George Pólya，1887－1985）认真研究了以上所提的“酒鬼回家”问题[3]。

根据刚才的讨论，酒鬼随机游走在长度无限（一维）没有悬崖的路上，时左时右，但只要时间足够长，他最终总能回到出发点。因此，最终回家的概率是100% 。二维的情形也类似，只要时间足够长，这个醉鬼总能回到家，概率仍然是 100% 。波利亚在 1921 年证明了这点，但三维的答案又如何呢？

波利亚令人吃惊地证明了在维数比2更高的情况下，酒鬼回家的概率远小于1！比如，在三维网格中随机游走，最终能回到出发点的概率只有 34% ，这也被称为波利亚定理（见图6）。