随机游走
- 英文：random walk
- 定义：随机游走，概念接近于布朗运动，是布朗运动的理想数学状态。
- 核心概念：任何无规则行走者所带的守恒量都各自对应着一个扩散运输定律。
- 随机游走算法的基本思想是:
从一个或一系列顶点开始遍历一张图。在任意一个顶点，遍历者将以概率1-a游走到这个顶点的邻居顶点，以概率a随机跳跃到图中的任何一个顶点，称a为跳转发生概率，每次游走后得出一个概率分布，该概率分布刻画了图中每一个顶点被访问到的概率。用这个概率分布作为下一次游走的输入并反复迭代这一过程。当满足一定前提条件时，这个概率分布会趋于收敛。收敛后，即可以得到一个平稳的概率分布。
随机游走过程
一维的随机游走可定义如下： 每过一个单位时间，游走者从数轴位置x出发以固定概率随机向左或向右移动一个单位.
不妨将n时刻游走者的位置记为Ln,则有
讯享网
其中X1,X2,…,Xn为相互独立的随机变量，满足
- 最经典的一维随机游走问题有赌徒输光问题和酒鬼失足问题。
一维有边界的随机游走问题
- 下面先对一维双边界随机游走问题进行求解：
- 设初始位置为
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）–生成随机漫步数据
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/118790.html