随机游走(Random Walk)算法

随机游走

• 英文：random walk

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

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

• 随机游走算法的基本思想是:
  从一个或一系列顶点开始遍历一张图。在任意一个顶点，遍历者将以概率1-a游走到这个顶点的邻居顶点，以概率a随机跳跃到图中的任何一个顶点，称a为跳转发生概率，每次游走后得出一个概率分布，该概率分布刻画了图中每一个顶点被访问到的概率。用这个概率分布作为下一次游走的输入并反复迭代这一过程。当满足一定前提条件时，这个概率分布会趋于收敛。收敛后，即可以得到一个平稳的概率分布。

随机游走过程

一维的随机游走可定义如下： 每过一个单位时间，游走者从数轴位置x出发以固定概率随机向左或向右移动一个单位.
不妨将n时刻游走者的位置记为Ln,则有

其中X1,X2,…,Xn为相互独立的随机变量，满足

• 最经典的一维随机游走问题有赌徒输光问题和酒鬼失足问题。

（1）赌徒在赌场赌博，赢的概率是p，输的概率1-p，每次的赌注为1元，假设赌徒最开始时有赌金1元，赢了赌金加1元，输了赌金减1元。问赌徒输光的概率是多少？
（2）一个醉鬼行走在一头是悬崖的道路上，酒鬼从距离悬崖仅一步之遥的位置出发，向前一步或向后退一步的概率皆为1/2，问酒鬼失足掉入悬崖的概率是多少？

**

一维有边界的随机游走问题

**

• 下面先对一维双边界随机游走问题进行求解：
• 设初始位置为
  x=n，边界为x=0和x=w，其中0<=n<=w，n、w为整数。游走者每个单位时间移动一次，向左、向右移动的概率都为1/2，达到边界后停止移动。

若用Sn表示初始位置为x=n时最终落入边界x=0的概率。显然我们会有S0=1和Sw=0，即初始位置为边界的情况。
若0<n<w，则考虑其下一次移动。有1/2的概率向左到达 n-1，有1/2的概率向右到达n+1。 则由全概率公式可得，

整理得到

利用

可得

累加法可得，

由S0=1，Sw=0，可得

同理，Tn初始位置为x=n时最终落入边界x=w的概率，可得Tn=n/w。 对于单边界情况，可以令w趋于正无穷得到，即可得Sn=1，Tn=0。

• 具体随机游走算法的讲解和代码请参考：
  介绍一个全局最优化的方法：随机游走算法(Random Walk)
  数据分析学习笔记（六）-- 随机漫步
  Python数据可视化（1）–生成随机漫步数据