想象在曼哈顿东西南北格点化的街道中有一个小醉汉，他每次从他当时所在的交叉路口选择一条街，也就是随机选择了东南西北4种方向之一，然后往前走，走到下一个路口又随机选择一次……如此继续下去，他走的路径会具有什么样的特点呢？

上述问题被称之为“酒鬼漫步”，数学家们将酒鬼的路径抽象为一个数学模型：无规行走，或称随机游走（random walk）。曼哈顿的酒鬼只能在二维的城市地面上游荡，因此是一种“二维无规行走”，见图1。

图1：酒鬼漫步和二维无规行走路径

随机过程

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

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

伯努利过程

丢一次硬币产生一个取值为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：时齐马尔可夫链

转移概率不随时间而变化的马尔可夫过程叫做时齐马尔可夫过程。比如说，如图3所示，假设北京任何一天的“晴雨”状态都由前一天的状态乘以同样的转换矩阵P而得到，那就是时齐的。通常考虑的马尔可夫过程，都被假定是“时齐”的。

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

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

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

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

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

无规行走可以看做是马尔科夫链的特例^【2】，它的状态空间不是像上述抛硬币等例子中那种由简单的几种有限可数个基本状态构成，而是由无限延伸的“物理空间”构成，这儿的“空间”可以是1、2、3维的，也可以扩展到更高维。

为什么说酒鬼漫步是马尔可夫链呢？因为醉汉在时刻t_i+1的状态（即位置），仅仅由他在时刻t_i的状态（x_i, y_i），以及他随机选择的方向所决定，与过去（t_i之前）走过路径无关，现在讨论一个1维空间“酒鬼掉下悬崖”的趣题。

曾经介绍过的高尔顿钉板，可作为一维无规行走的例子。高尔顿钉板虽然貌似一个2维空间，但因为小球在垂直方向的运动并不是随机的而是固定的，每次向下1格，可以当作向下的时间轴，水平方向则是一个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处的概率记为P₁。这个概率显然就是刚才简化问题中要求解的：从x=1处开始漫步掉入悬崖的概率。同时，从这个问题的平移对称性考虑，P₁也是酒鬼从任何x=k左移一个格点，漫步（不管多少步）到达x=k-1格点位置的概率。需要注意：酒鬼走一步，与他的格点位置移动一格是两码事，位置从x=k左移到x=k-1，也许要走好几步。

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

P₁= 1-p+pP₁²，

由此可以解出P₁ = 1或者P₁= (1-p)/p。对这个问题有意义的解是P₁= (1-p)/p，P_n=P₁ⁿ。

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

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

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

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

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

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

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

图6：“酒鬼小鸟回家”定理

酒鬼不可能在空中游走，鸟儿的活动空间才是3维的，因此，美国日裔数学家角谷静夫（Shizuo Kakutani，1911–2004）将波利亚定理用一句通俗又十分风趣的语言来总结：喝醉的酒鬼总能找到回家的路，喝醉的小鸟则可能永远也回不了家^【4】。

无规行走也是物理学中布朗运动的数学模型，欲知详情，且听下回分解。

参考文献：

【1】维基百科：马尔可夫链

https://zh.wikipedia.org/wiki/%E9%A9%AC%E5%B0%94%E5%8F%AF%E5%A4%AB%E9%93%BE

【2】wikipedia：https://en.wikipedia.org/wiki/Random_walk

【3】Finch, S. R. "Pólya's Random Walk Constant." §5.9 inMathematical Constants. Cambridge, England: Cambridge University Press, pp.322-331, 2003.

【4】A joke by Shizuo Kakutani at a UCLA colloquium talk as attributed inRick Durrett's book Probability:Theory and Examples.