随机游走查看源代码讨论查看历史

随机游走（random walk）也称随机漫步，随机行走等是指基于过去的表现，无法预测将来的发展步骤和方向。核心概念是指任何无规则行走者所带的守恒量都各自对应着一个扩散运输定律，接近于布朗运动，是布朗运动理想的数学状态，现阶段主要应用于互联网链接分析及金融股票市场中。

随机游走图片来源百度网原图链接

中文名:随机游走

外文名:random walk

别 名:随机行走

核 心:一个扩散运输定律

定 义:即随机游走，

概念接近于布朗运动

应 用:计算机、金融

释义

英文：random walk

定义：随机游走，概念接近于布朗运动，是布朗运动的理想数学状态。

核心概念：任何无规则行走者所带的守恒量都各自对应着一个扩散运输定律。

定律介绍

无规则行走

无规则行走在任意尺度上都具有相似结构。例如一个在二维（d=2）格子上游动，每一定时间以相同概率移动到其相邻位置，其轨迹即二维随机轨迹，同样可以扩展到三维。举个例子，你取2个硬币一个1分，一个5分。你每五秒，将2个硬币掷一次，1分硬币用于左右移动标记，5分硬币用于前后移动标记，绘出路径就是你的二维无规则行走。假如你走了1000步那么你回到起点的方式M0有多少种？那么么必须正反面各500次。即，对一个特定投币序列将投出正面的序号列出清单，清单包括500个不同的整数这个量为：1000！/500！，而任意两张清单只在元素存在换序的差异，则实际上并无区别所以必须除以可能的置换数500!,M0=1000！/（500×500！），“！”表示阶乘。回到原点的概率P0=M0/M，这个概率满足二项分布。

对于所有M种可能可以用斯特林公式进行计算，通过计算我们知道回到起点的概率很低。

随机游走图片来源百度网原图链接

要想找出第1000步后你走了多远，你可以列出1000次投币的结果序列然后对所有（x1000）的2次方求平均，得到1000步后的均方位置；这显然太复杂，好在还有另外的方法。我们可以将所有2的N次方种可能行走一一配对，每一配对由相同的x（N-1）；{（N-1）为x的下脚标}的两个可能性相等的行走组成，只是最后一步不同。N步随机性走的均方位移比N-1步大a的2次方，后者又比N-2步大a的2次方，均方位移=Na的2次方。a为格子间隔，每一个格子点上游动的可能方向有2d个（d是格子维数）单位时间内游动的方差为D=a2/（2d）t，D为扩散系数（一些参考书中也用字母K表示，

===a后面的2为次方，后面凡数字在字母后面都表示指数)===。 对于一维无规则行走的均方位移随时间线性增加2Kt，扩散常数D=a2/（2Δt）。这个逻辑可以推广到二维和三维。

也许行走若干个步后他会回到出发点，但这样的概率非常小。他离开酒吧的距离满足扩散定律。

（a）二维无规则行走；

随机游走图片来源百度网原图链接

（b）当步骤更多，步幅更低时二维无规则行走；

（c）三维无规则行走。

扩散定律

扩散以一个初始分布释放大量的无规则行走，观察他们的密度，就会得到分布函数。

1855年法国生理学家Fick提出了描述扩散规律的基本公式—菲克定律，在一维（如x方向扩散的）粒子流密度（即单位时间内在单位截面上扩散的粒子流）JN与粒子数密度梯度dc/dx成正比。扩散通量J=-D×（dc/dx），称为菲克定律又称扩散第一定律。进一步消掉J，找出浓度随时间的变化关系dc/dt=D（d2c/dx2），称为菲克第二定律；在高等教材中可以写成偏导的形式d换成ә。

任何单次步骤不会遵从扩散定律，但只要等待足够长的时间和步骤，便可精确预测无规则行走。布朗运动就是无规则行走这一现象的宏观观察。通过扩散定律我们将布朗运动的微观参数（步长a和间隔时间Δt）与宏观实验可观测量（扩散常数D）建立了联系。然而一个方程无法解出两个未知量，测量K不足以得到a和Δt。这意味着还需要其他能够说明摩擦与扩散定量联系的公式。

扩散定律是跨学科的普适定律

对无规则行走的数学处理使用了过于简化的假设，扩散定律是普适的，只要给定独立随机行走的某种分布，它就不依赖于具体的模型。涨落是随机的、混沌的，无规则行走的结果就是扩散，这包括物质扩散、动量扩散、热量扩散等。这也意味着结晶学、天文学、生物学、气象学、流体力学、经济学都将用到扩散定律。扩散定律是普适的，在这里我们作为一个结论而接受下来，具体的一系列数学证明过程给予舍弃。感兴趣的朋友可以参见任何一本物理化学教材或分形教材。

扩散定律与守恒量

扩散是一个随机涨落的过程，在本科一年级的物理课程已经提及一个落体最终会达到取决于摩擦的“末速度”。以悬浮颗粒来考虑摩擦，颗粒虽然受随机碰撞，仍获得了一个净漂移速度。v=f/ζ，ζ=2m/Δt，其中ζ是黏性摩擦系数，与扩散系数一样可以实验测量。摩擦源于物理实体与周围热致扰动的流体随机碰撞。每一种颗粒当置于不同的溶剂中时都会有相应特征D（扩散系数）和ζ。球体的黏性摩擦系数与尺寸间存在简单关系，ζ=6πηR斯托克斯（stokes）公式；R是颗粒半径，η是常数称为流体黏度（水的黏度为10-3kg/ms）。

由于有效步长a和Δt无法观察，要想证实扩散与粘滞仅仅是热运动的两个方面，我们还需要第三个关系。爱因斯坦注意到a和Δt的关系，按照推导理想气体定律的思路：（a/Δt）2=kBT/m，联合起来就构成爱因斯坦第一扩散公式：ζD=kBT。越小的颗粒受到摩擦阻力越小，但扩散系数会更大，更容易扩散。ζD的乘积提供了一个可证伪的预言来检验“热即分子的无规则运动”；这个预言提出不久就立刻被佩兰（Jeans Perrin）和其他人的实验所证实。任何无规则行走携带的守恒量都各自对应一个扩散定律。

理想状态

无规则行走只是布朗运动的理想状态。

在很多系统都存在不同类型的无规则行走，他们都具有相似结构。单个的随机事件我们不可预测，但随机大量的群体行为，却是精确可知的，这就是概率世界的魅力，在偶然中隐含着必然。随机性造成了低尺度下的差异性，但在高尺度下又表现为共同的特征的相似性。按照概率的观点“宇宙即是所有随机事件概率的总和”。

相关研究

椭球体布朗运动相关研究

虽然无规则行走导致的扩散满足以上的方程并有普适性，但假如这样的“无规则行走”某个方向，并不是完全随机呢？以前面提到的投硬币为例子，一个1分，一个5分，其中1分硬币破损使得正反面概率不相等，并且随机若干步后，将1分和5分硬币所代表的方向对调；那么二维的无规则行走路径必然发生改变。

当年爱因斯坦的论文是探讨球形颗粒的布朗运动，我们知道球形颗粒的旋转并不影响他的平移，旋转的非球形例子却会影响它的平移。实际中，大量布朗运动的颗粒都是非球形的，所以更多的模型不得不考虑随机转动问题。其实即使对球形颗粒在黏性流体中，也要考虑随机转动产生的转动摩擦系数对扩散的影响。

随机游走图片来源百度网原图链接

宾夕法尼亚大学的网站报道，研究人员用数字视屏显微镜观察水中悬浮椭球体的随机旋转和移动。球形颗粒扩散分布将随时间逐渐变宽，为高斯型浓度分布；而椭球颗粒不满足高斯分布。随着布朗运动的深入研究，越来越多的实验表明布朗运动颗粒的行为与爱因斯坦一个世纪前的假设不同。

2005年10月的物理评论快报，提到现在实验室可以跟踪布朗运动颗粒的测量精度达到微秒和纳米的尺度。科学家们也发现活细胞的许多基本过程由布朗运动所驱动。试验结果描述布朗运动的方程式偏离标准理论的，实际的布朗运动要比理想化的无规则行走要复杂。

标准的无规则行走，色彩标记显示出椭球的耦合方向和位移，并清楚的表明椭球的扩散其长轴比其短轴扩散更快。 观点的缺憾

布朗运动是分形的典型例子，理想状态下的布朗运动是高斯正态分布，当然更多的布朗运动研究细节我们不做探讨。任何事物都不是孤立的，都是相互作用、相互联系的。用还原论观点将系统一个个隔离是对事物的理想化，是在一定程度上精确定量描述系统，当然这也是认识事物必经的步骤，但是有缺陷的。

哥德尔不完备定理，以及认识主体对客体的反映永远存在这不完备性。我观赞同哥本哈根学派的主张“自然科学不是自然界本身，而是人和自然界间关系的一部分，因而依赖人”。无论用还原论还是整体论都是用抽象去阐明物质的特性，这些抽象在任何时候仅仅是近似地、有条件的把握了物质的本质，不是世界的全部。布朗运动研究的历史，具有典型性，有点像整个科学研究史的缩影。人对事物的认识总是渐进的，不断深入的，随着认识深入会发现各种模型都是理想化的条件。这种认识永远无法走向事物的绝对认识，因为孤立的事物是不存在的，所有的系统都是宇宙整体的一部分。

其他类型

与P2P

许多系统都有类似无规则行走的例子。例如：P2P（Peer-to-Peer，对等计算，简称P2P）搜索中Random Walk搜索方法在随机漫步中，请求者发出K个查询请求给随机挑选的K个相邻节点。然后每个查询信息在以后的漫步过程中直接与请求者保持联系，询问是否还要继续下一步。如果请求者同意继续漫步，则又开始随机选择下一步漫步的节点，否则中止搜索又开始随机选择下一步漫步的节点，否则中止搜索又开始随机选择下一步漫步的节点，否则中止搜索。

与高分子

高分子的形状类似于无规则行走，把高分子想象成由N个单元排成的长串。每个单元都由一个完全柔软的铰链与下一个单元相连，就像一串回形针。热平衡时，这些铰链全部处于随机选取的角度，高分子每一时刻的形状都会不同，每一时刻都是一个无规则行走。如果合成的高分子由不同数量的单元组成，线团尺寸的增加正比于其摩尔质量的平方根。 如果单元间存在着强烈的相互吸引力，高分子将不再采取无规则行走构象而是密堆成一个球体，例如血清球蛋白。可以通过比较高分子的体积和假设所有密堆占的最小体积，将高分子分为“紧密型”和“舒展型”。即使高分子不坍缩为团，单体也并非真正处于任何位置，两个单体不可能占据空间同一点，这是自回避现象。这样标度指数（线团尺寸的增加正比于其摩尔质量的指数）就由0.5变为其他值，所以这个值往往略大一点。不管精确值是什么，高分子运动的复杂性可涌现出简单的标度关系。

梅尔（B.Maier）和雷德勒尔（J.Radler）首先构建了一个带正电的表面并让他吸附带负电荷的单链DNA然后对被吸附的DNA分子不断变化的构象进行连续快照（DNA带有荧光染色）。DNA分子可以是自交叉的但每次出现这种情况都是一个消耗结合能的过程，在交叉点处那条带负电的链并不与带正电的表面接触，而是被强迫与另一条带负电的链接触。因此我们可以认为线团尺寸遵从二维无规自回避行走标度律，标度指数为0.75。一旦结合在平面上，DNA链就开始各种蜿蜒构象间的变化，梅尔和雷德勒尔计算出了高分子链的回转半径与首末端距离的均方有关，标度指数0.79接近于理论的0.75。

与金融市场

股票市场由无数的亚单元即投资者构成。每个投资者为个人经验、感情和不完全信息所左右，其决策立足于其他投资的的决策以及汇总的信息中的随机事件，在经济学上研究这样的决策叫做博弈论（game theory）。当然单个投资者的行为不可预测，但长期来看，股票价格作某种带漂移的无规则行走。驱动这个行走的包括投资者的突发奇想、自然灾难、公司倒闭、以及其他不可预知的新闻事件。

为什么行走会是随机？假如一个分析员发现12月末股价会上扬，到1月初在下跌，一旦这种规律被市场参与者得知自然人们会选择这段时间内抛出股票，这一行为导致了股票下跌，消除了这种效应的可能。股票的公平原则即要求公开信息资源，使得一个投资者没有更多战胜其他投资者的有用信息。在信息完全公开的情况下长时间的股票曲线应该近似于一维无规则行走。

任何无规则行走者所带的守恒量都各自对应着一个扩散运输定律。比如粒子数守恒对应物质扩散，能量守恒对应热传导定律，热传导定律可以看成另一条菲克型定律。

模型

互联网用户在上网时，往往有类似的网络行为：输入网址，浏览页面，然后顺着页面的链接不断打开新的网页。随机游走模型就是针对浏览网页的用户行为建立的抽象概念模型。之所以要建立这个抽象概念模型，是因为包括PageRank算法在内的很多链接分析算法都是建立在随机游走模型基础上的。

在最初阶段，用户打开浏览器浏览第1个网页，假设我们有一个虚拟时钟用来计时，此时可以设定时间为1，用户在看完网页后，对网页内某个链接指向的页面感兴趣，于是点击该链接，进入第2个页面，此时虚拟时钟再次计时，时钟走向字2，如果网页包含了k个出链，则用户从当前页面跳转到任意一个链接所指向页面的概率是相等的。

用户不断重复以上过程，在相互有链接指向的页面之间跳转。如果对于某个页面所包含的所有链接，用户都没有兴趣继续浏览，则可能会在浏览器中输入另外一个网址，直接到达该网页，这个行为称为远程跳转（Teleporting）。假设互联网中共有m个页面，则用户远程跳转到任意一个页面的概率也是相等的，即为1/m。随机游走模型就是一个对直接跳转和远程跳转两种用户浏览行为进行抽象的概念模型。