随机游走
-
英文：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）–生成随机漫步数据
