1 基本概念
随机游走是描述随机演化过程的基础模型，通常指系统在每一步都按照某种随机规则改变位置或状态。它的核心特征是“当前变化带有随机性”，而整体轨迹则由一连串随机步骤累积形成。由于定义简明、可分析性强，随机游走常被视为理解随机过程的入门模型。
1.1 定义
随机游走可以看作一个按时间推进的随机序列。系统在每个时刻根据预设概率选择下一步的方向、长度或状态，因此其演化结果并不唯一，而是以概率方式分布在不同路径上。
1.1.1 离散时间随机游走
离散时间随机游走是在一系列离散时刻上进行更新的模型。每一步结束后，系统会进入新的位置或状态，常见形式包括整数格点上的位移、图中顶点之间的跳转等。这类模型便于用递推关系和概率矩阵进行分析。
1.1.2 连续时间随机游走
连续时间随机游走则允许状态在连续时间轴上变化，跳跃发生的时刻由随机机制决定。与离散时间模型相比，它更适合描述等待时间不固定的系统，如粒子在介质中的迁移或网络节点间的不规则跳转。
1.2 组成要素
随机游走通常由状态空间、步长规则和初始条件等部分构成。不同要素的设定会直接影响轨迹形态、返回性质以及长时间行为。
1.2.1 状态空间
状态空间是系统可到达位置或状态的集合，可以是整数轴、二维平面、多维晶格，也可以是图上的节点集合。状态空间的结构决定了随机游走的可达范围与路径约束。
1.2.2 步长与方向
步长描述每次移动的距离，方向则决定移动朝向。若步长固定且方向按概率随机选择，模型通常较为简单；若步长可变或方向受历史影响，模型会表现出更复杂的统计特征。
1.2.3 初始位置
初始位置是随机游走的起点，常记为某个确定状态。尽管它只是模型的初始条件，但在有限时间范围内会明显影响轨迹分布，并在边界受限时影响命中概率和停留时间。
1.3 基本假设
经典随机游走往往建立在若干简化假设上，以便得到清晰的理论结论。这些假设并非在所有应用中都成立，但它们构成了许多分析方法的基础。
1.3.1 独立性
独立性指各步之间相互不影响，即某一步的方向或结果不依赖于此前路径。该假设使得整体过程可由单步分布叠加而成，是经典随机游走的重要前提。
1.3.2 同分布性
同分布性表示每一步服从相同的概率规则。这样一来，模型在时间上具有统一的统计结构，便于研究长期行为和极限性质。
1.3.3 平稳性
平稳性通常指过程的统计规律不随时间平移而改变。对于随机游走而言，这意味着在任意时刻开始观察，其单步机制在形式上保持一致。
1.4 典型示例
随机游走的典型例子有助于理解其直观含义，也展示了不同设定下轨迹的差异。最常见的是对称、带偏和多维情形。
1.4.1 一维对称随机游走
在一维对称随机游走中，系统每一步以相同概率向左或向右移动同样距离。该模型简单而经典，常用于演示返回原点、扩散速度和波动增长等现象。
1.4.2 偏置随机游走
偏置随机游走是指各方向的选择概率不相等。若向某一方向的概率更大，轨迹的平均位置会逐渐偏移，表现出明显的漂移趋势。
1.4.3 二维与高维随机游走
在二维或更高维空间中，系统的可行移动方向增多，路径也更为丰富。随着维度上升，返回起点的性质会发生显著变化，这也是随机游走理论中的重要主题。
2 分类与变体
随机游走可以按照时间结构、空间结构、步长规则及特殊约束进行分类。不同变体对应不同的应用背景，也反映出随机过程建模的多样性。
2.1 按时间结构分类
时间结构决定系统是在固定时刻更新，还是在随机时刻跳转。两种设定在理论处理和应用场景上各有特点。
2.1.1 离散时间随机游走
离散时间模型按步数推进，每一步对应一次状态更新。它适合描述按轮次进行的决策过程，也常见于数学教学和算法分析。
2.1.2 连续时间随机游走
连续时间模型在随机到达的时刻发生跃迁，中间状态保持不变。它常用于刻画等待时间不均匀的扩散过程和排队系统。
2.2 按空间结构分类
空间结构决定系统在何种几何环境中移动，不同空间会带来不同的转移方式和边界效应。
2.2.1 一维随机游走
一维随机游走发生在直线或整数轴上，路径只向前后两个方向延伸。它是最基础的模型，也是许多理论结论的起点。
2.2.2 多维随机游走
多维随机游走发生在平面或更高维空间，单步选择更丰富。维度增加后，路径往往更难重复访问同一位置，整体行为也更接近扩散。
2.2.3 图上的随机游走
图上的随机游走以顶点为状态、以边为可行转移。它广泛应用于网络分析、搜索排序和随机采样等领域。
2.3 按步长规则分类
步长规则决定每次移动的幅度及其变化方式，是影响轨迹形态的重要因素。
2.3.1 简单随机游走
简单随机游走通常指步长固定、方向由简单概率决定的模型。它结构清晰，常作为更复杂模型的比较基准。
2.3.2 带偏随机游走
带偏随机游走在不同方向上赋予不等概率，因此整体轨迹会出现漂移。它适合描述存在外部驱动或内在倾向的系统。
2.3.3 变步长随机游走
变步长随机游走允许每一步的长度不同，且可由随机机制决定。此类模型更接近真实系统中的非均匀运动。
2.4 特殊模型
一些随机游走引入额外约束或依赖结构，以表达更复杂的行为模式。
2.4.1 自回避随机游走
自回避随机游走要求路径尽量不重复访问已到过的位置。该模型常用于高分子链和排布问题的近似描述。
2.4.2 带记忆随机游走
带记忆随机游走使当前决策受到历史路径影响，突破了独立步长的限制。它能够表现出偏好、习惯或反馈机制。
2.4.3 随机环境中的随机游走
随机环境中的随机游走是指路径规则本身也具有随机性。也就是说，行走者所处的空间会影响其转移概率，并且这种空间结构可能因位置不同而变化。
3 数学性质
随机游走之所以重要，在于它既有直观图像，又能导出一系列深刻的数学性质，包括转移规律、波动增长和极限行为等。
3.1 马尔可夫性质
经典随机游走通常具有马尔可夫性质，即未来状态只依赖当前状态，而与更早的历史无关。这一性质使过程可通过局部转移规则刻画。
3.1.1 转移概率
转移概率描述从一个状态跳到另一个状态的可能性。它是随机游走的核心参数，决定了路径的短期演化方式。
3.1.2 状态转移矩阵
当状态空间有限或可编号时，可用状态转移矩阵组织所有转移概率。矩阵形式便于计算多步转移、稳态分布和谱性质。
3.2 期望与方差
随机游走的平均位置与波动规模是衡量其整体行为的基本统计量。
3.2.1 位置期望
位置期望反映随机游走在平均意义下的偏移方向。对称模型中期望通常保持在起点附近，而带偏模型则会随步数增长而移动。
3.2.2 方差增长
方差用于描述位置分布的扩散程度。对许多简单随机游走而言，方差会随时间近似线性增长，体现出典型的扩散特征。
3.3 返回与命中
返回和命中问题关注路径是否以及何时到达某个指定状态，是随机游走中最经典的研究方向之一。
3.3.1 首次回返时间
首次回返时间指系统第一次回到初始位置所需的步数或时间。该量的分布常用于衡量路径的循环特性。
3.3.2 命中概率
命中概率表示在给定条件下，随机游走最终访问某个状态的可能性。它与状态空间结构、维度和边界条件密切相关。
3.3.3 递归性与暂留性
递归性指系统会以概率一再返回某些状态；暂留性则表示存在正概率永远不再返回。二者反映了随机游走在长期尺度上的根本差异。
3.4 极限定理
极限定理研究随机游走在步数很大时的近似行为，是连接离散模型与连续理论的重要桥梁。
3.4.1 中心极限定理
中心极限定理说明在适当标准化后，随机游走的位置分布往往趋近于正态分布。这解释了其扩散形态的普遍性。
3.4.2 大数定律相关结果
大数定律相关结果表明，随机游走的平均速度会趋向某个确定值或保持稳定。对于有偏模型，这种极限通常体现为非零漂移。
3.4.3 不变性原理
不变性原理指出，经过适当缩放后，随机游走可在极限上逼近连续扩散过程。它为离散模型与布朗运动之间建立了严密联系。
4 经典结果
随机游走理论中有若干公认的经典结论，它们不仅具有理论代表性，也常被用作教学中的重点例题。
4.1 波利亚定理
波利亚定理讨论简单随机游走在不同维度中的返回性质，是该领域最著名的结果之一。
4.1.1 一维情形
在一维中，简单对称随机游走几乎必然会回到原点，因此表现出递归性。这一结论直观而重要，常被视为随机游走的基本事实。
4.1.2 二维情形
二维简单对称随机游走同样具有几乎必然回返的性质。尽管路径在平面上更为分散，但长期看来仍会反复访问起点附近区域。
4.1.3 三维及以上情形
在三维及更高维中，简单对称随机游走不再具有必然回返性。随着维度提高，轨迹更容易“逃离”起点，从而出现暂留行为。
4.2 醉汉问题
醉汉问题是随机游走最常见的通俗表述之一，通常用来描述一个人沿直线或网格随机行走的路径。
4.2.1 线性路径分析
在线性路径中，醉汉每一步向左或向右移动，轨迹可直接映射为一维随机游走。该模型常被用于说明位置分布和回到原点的可能性。
4.2.2 期望距离
期望距离衡量醉汉与出发点之间的平均偏离程度。一般而言，随着步数增加，距离的典型尺度会按平方根量级增长。
4.3 赌场模型
赌场模型将随机游走与输赢过程联系起来，常用于分析资金在随机波动下的演化。
4.3.1 公平游戏
在公平游戏中，每次赢和输的概率相同，资金变化可视为无偏随机游走。长期上虽然平均收益为零，但短期波动仍可能很大。
4.3.2 带优势游戏
带优势游戏对应一方略占概率优势的情形，资金轨迹会呈现单向倾斜。此时随机游走带有明确漂移，结果更偏向有利一方。
4.3.3 破产概率
破产概率指资金在有限或无限时间内降至零的可能性。它与初始资本、胜负概率及边界设置密切相关，是博彩模型中的核心指标。
4.4 反射与吸收边界
边界条件用于描述随机游走到达某些边界后如何继续演化，是受限空间模型的重要组成部分。
4.4.1 反射边界条件
反射边界表示系统到达边界后被“弹回”内部，不能越界。该条件适合刻画封闭区域中的反弹行为。
4.4.2 吸收边界条件
吸收边界表示一旦到达边界，过程便停止或被固定在该点。它常用于首次到达时间和逃逸问题。
4.4.3 混合边界条件
混合边界同时包含反射和吸收成分，不同边界点的处理方式可能不同。此类设置更贴近复杂几何环境中的实际过程。
5 重要工具与方法
研究随机游走常借助多种数学工具，从递推方程到谱分解，再到数值模拟，形成了较完整的方法体系。
5.1 差分方程方法
差分方程方法通过分析相邻步之间的关系，建立随机游走量的递推表达式。
5.1.1 递推关系
递推关系将当前状态的概率、期望或命中时间与前一状态联系起来，是求解随机游走问题的常用起点。
5.1.2 边界条件求解
当状态空间有限或存在边界时，必须结合边界条件确定唯一解。通过设置吸收、反射或混合条件，可以得到具体的概率结果。
5.2 生成函数方法
生成函数把离散概率序列编码为一个解析对象，便于提取分布信息和渐近性质。
5.2.1 概率生成函数
概率生成函数能够整理位置分布或到达时间分布，并通过代数运算推导出高阶性质。它常用于处理卷积结构和首次通过问题。
5.2.2 矩生成函数
矩生成函数用于汇总随机变量的各阶矩信息，有助于分析均值、方差及尾部行为。对于随机游走，它常与极限定理和偏差估计相结合。
5.3 矩阵与谱方法
矩阵和谱方法特别适合有限状态或规则图上的随机游走分析。
5.3.1 特征值分析
特征值反映系统在不同模式下的衰减或保持能力。通过考察转移矩阵的特征值，可以分析混合速度和长期趋势。
5.3.2 特征向量分解
特征向量分解将复杂的转移过程拆分为若干独立模式，便于研究多步演化。它在求解概率分布和稳态行为时非常有用。
5.4 模拟与数值方法
对许多复杂随机游走，解析解难以直接获得，因此常借助模拟和数值计算。
5.4.1 蒙特卡罗模拟
蒙特卡罗模拟通过大量随机采样近似估计概率量和期望量。它简单灵活，适合研究高维或复杂边界下的行为。
5.4.2 数值近似
数值近似方法包括截断、离散化和迭代求解等技术，可用于求解难以显式表达的分布或命中时间。
5.4.3 误差评估
误差评估用于衡量近似结果与真实值之间的差距。它有助于判断模拟规模是否足够，以及数值解是否稳定可靠。
6 应用领域
随机游走因其通用性，被广泛用于自然科学、工程技术和社会行为建模。
6.1 物理学
在物理学中，随机游走是理解扩散与涨落的重要工具，尤其适合描述粒子在介质中的运动。
6.1.1 扩散与布朗运动
随机游走与扩散过程密切相关，常被用作布朗运动的离散近似。通过这种方式，可以解释粒子位置随时间扩散的规律。
6.1.2 热运动模型
热运动模型将微观粒子的无规则碰撞视为随机位移，从而建立宏观扩散和温度关系的简化描述。
6.2 计算机科学
随机游走在算法设计、网络分析和数据采样中都有重要作用。
6.2.1 随机算法
某些随机算法利用随机游走在搜索空间中探索解空间，以提高效率或避免陷入局部最优。
6.2.2 图搜索与采样
在图结构中，随机游走可用于访问节点、估计连通性以及生成近似样本，尤其适合大规模网络。
6.3 金融数学
金融数学中常借助随机游走刻画资产价格的随机波动，尽管真实市场通常更复杂，但该模型仍具有基础意义。
6.3.1 价格路径建模
价格路径建模把资产价格看作随机演化序列，用以描述短期波动和趋势偏移的可能性。
6.3.2 风险与波动分析
随机游走可帮助分析价格偏离、回撤和波动范围，为风险评估提供直观框架。
6.4 生物与生态
在生物和生态研究中，随机游走常用于模拟个体移动、资源寻找和扩散过程。
6.4.1 觅食路径
觅食路径模型把动物寻找食物的移动视为随机探索，有助于研究搜索效率与环境适应性。
6.4.2 种群扩散
种群扩散可通过随机游走近似描述个体在空间中的迁移，从而分析扩张速度与分布形态。
6.5 社会与行为模型
随机游走也被用于简化社会行为中的变化过程，尤其是在决策和信息传播的抽象建模中。
6.5.1 选择行为建模
选择行为建模利用随机游走描述个体在多个选项间的随机切换，适合表示不稳定偏好或反复试探。
6.5.2 舆论传播简化模型
在舆论传播的简化模型中，随机游走可用来表示意见在群体间的随机扩散与转移，但通常仅作为抽象近似。
7 扩展主题
随机游走不仅是独立模型，也与马尔可夫链、布朗运动、图论和随机矩阵等理论密切相连。
7.1 与马尔可夫链的关系
随机游走通常可视为马尔可夫链的一类重要实例，其状态演化遵循相同的局部转移思想。
7.1.1 状态转移结构
在马尔可夫链框架下，随机游走的每个状态都对应一个转移分布，整体结构由转移图或转移矩阵表示。
7.1.2 稳态与遍历性
当状态空间有限且满足适当条件时，随机游走可能具有稳态分布，并表现出遍历性，即长时间平均接近整体平均。
7.2 与布朗运动的关系
离散随机游走在适当缩放后可逼近连续的布朗运动，因此两者在理论上具有深层联系。
7.2.1 离散到连续极限
通过缩小步长并加快时间尺度，离散随机游走可以在极限中转化为连续扩散过程。这一思想构成了许多近似理论的基础。
7.2.2 扩散近似
扩散近似将随机游走的宏观行为看作连续扩散方程的离散来源，适用于研究大尺度平均行为。
7.3 与图论的关系
图论为随机游走提供了自然的离散空间，尤其适合描述网络中的跳转过程。
7.3.1 有限图随机游走
有限图上的随机游走研究节点访问、回返时间和混合速度。它在连通图、树和环图等结构上都有典型结果。
7.3.2 随机游走与连通性
随机游走能够反映图的连通特征，某些访问性质与图的结构紧密相关，因此常被用于网络诊断和结构分析。
7.4 与随机矩阵的联系
随机游走与随机矩阵在谱性质和动力学描述上存在交集，尤其在复杂系统研究中较为常见。
7.4.1 谱分布
随机矩阵的谱分布可影响随机游走的传播和混合特性。通过谱分析，可以了解系统中不同模式的重要程度。
7.4.2 随机过程耦合
在耦合框架下，随机游走可与其他随机过程共同建模，以比较不同系统之间的同步、偏差或相关性。
8 研究历史
随机游走的发展贯穿概率论、统计物理和应用数学的多个阶段，逐步从直观问题演化为系统理论。
8.1 早期起源
随机游走的思想可追溯到早期概率问题与物理随机运动的观察，后来逐渐形成统一的数学模型。
8.1.1 经典概率问题
早期概率研究中的掷硬币、路径计数和赌博问题，为随机游走提供了最初的形式背景。
8.1.2 统计物理中的引入
随着统计物理的发展，随机游走被用来刻画粒子无规则运动和扩散现象，推动了其应用范围扩大。
8.2 理论发展
在20世纪，随机游走逐步成为随机过程理论中的核心内容，并与其他分支深度融合。
8.2.1 20世纪重要进展
这一时期，返回性、命中时间、极限定理和谱分析等问题得到系统研究，随机游走的数学框架日趋成熟。
8.2.2 现代随机过程理论
现代随机过程理论将随机游走置于更一般的框架中，结合马尔可夫过程、扩散过程和鞅理论，形成更统一的研究视角。
8.3 相关学者贡献
随机游走理论的完善离不开多位学者在基础理论和应用推广上的持续贡献。
8.3.1 基础理论贡献
基础理论方面的工作主要集中在返回性判定、极限定理、谱方法以及随机过程结构的形式化表达。
8.3.2 应用推广贡献
应用推广方面的研究则将随机游走引入物理、计算机、金融与生态等领域，使其成为跨学科建模的重要工具。