随机游走(Random Walk)模型详解：历史

随机游走（Random Walk，缩写为 RW），是一种数学统计模型，它是一连串的轨迹所组成，其中每一次都是随机的。它能用来表示不规则的变动形式，如同一个人酒后乱步，所形成的随机过程记录。

1905年，由卡尔·皮尔逊首次提出。

随机游走的形式有：

随机游走(random walk)矩阵可以看做是马尔科夫链的一种特例。

喝醉的酒鬼总能找到回家的路，喝醉的小鸟则可能永远也回不了家。

一维、二维随机游走过程中，只要时间足够长，我们最终总能回到出发点;

三维网格中随机游走，最终能回到出发点的概率只有大约 34%；

四维网格中随机游走，最终能回到出发点的概率是 19.3% ；

八维空间中，最终能回到出发点的概率只有 7.3% ；

定理是著名数学家波利亚（George Pólya）在 1921 年证明的。

随机游走是现实生活中常见的一种模型：

气体分子的运动、滴入水中的墨水 、气味的扩散、醉汉行走轨迹、花粉的布朗运动、证券的涨跌、抛硬币…

早期搜索引擎如Yahoo使用的是关键字匹配技术，性能容易受到关键词频率的欺骗，所以搜索效果不是很好。

1998年Jon Kleinberg 提出了HITS算法，Sergey Brin 和 Larry Page 提出了 PageRank算法之后，搜索的正确率就得到了巨大的改观，这两种技术都是基于Random Walk。