设置
操作
显示选项
转移矩阵编辑器
每一行必须求和为 1.0（随机矩阵）
概率分布
收敛到平稳分布
数学分析
当前分布 p_t
平稳分布 π
π 满足 π = πP
P 的特征值
随机矩阵保证 λ₁ = 1
链的性质
混合时间估计
到达与 π 距离 ε = 0.01 的步数
全变差距离
δ(t) = 0.5 × Σ|p_t(i) - π(i)|
什么是马尔可夫链？
马尔可夫链是一个具有无记忆性的随机过程：未来状态仅依赖于当前状态，而不依赖于之前的事件序列。
马尔可夫性质
P(X_{t+1} | X_t, X_{t-1}, ..., X_0) = P(X_{t+1} | X_t)
转移公式
p_{t+1} = p_t P
其中 p_t 是时刻 t 的分布向量，P 是转移矩阵
核心概念
- 状态空间 S: 所有可能状态的集合
- 转移矩阵 P: P[i][j] = P(X_{t+1}=j | X_t=i)
- 随机矩阵: 每一行求和为 1.0
- 路径概率: 路径上转移概率的乘积
平稳分布 π
平稳分布 π 是一个在马尔可夫链中保持不变的概率分布：一旦系统达到 π，它将永远停留在那里。
平稳方程
π = πP
或等价地: π(P - I) = 0
左特征向量解释
π 是对应于特征值 1 的 P 的左特征向量
πP = λπ where λ = 1
存在性和唯一性
- 存在性: 每个有限马尔可夫链至少有一个平稳分布
- 唯一性: 对于不可约链（所有状态相通）保证唯一性
- Perron-Frobenius定理: 对于常规链，π 的所有元素都为正
全变差距离
δ(t) = 0.5 × Σ|p_t(i) - π(i)|
度量当前分布与平稳分布的接近程度
收敛性质
在什么条件下马尔可夫链会收敛到其平稳分布？
链类型
- 常规（非周期+不可约）: 从任何起始分布收敛到唯一的 π
- 周期性: 状态以周期性模式循环
- 可约: 包含吸收状态或多个相通类
收敛速度
由第二大特征值模（SLEM）决定:
|p_t - π| ≈ C × |λ_2|^t
谱隙 = 1 - |λ₂|，更大的谱隙 = 更快的收敛
混合时间
达到与平稳分布 ε 接近的时间:
t_mix(ε) = log(ε) / log(|λ_2|)
周期性检测
当状态的所有返回循环长度都能被 d 整除时，状态具有周期 d
- 非周期: d = 1（可以随时返回）
- 周期性: d > 1（循环是同步的）
细致平衡（可逆链）
π(i)P(i,j) = π(j)P(j,i)
π 为平稳分布的充分条件
实际应用
PageRank 算法
Google 的 PageRank 将网络浏览建模为随机游走。平稳分布给出每个网页的重要性。
P = (1-d)M + d(1/n)J
M: 链接矩阵, d: 阻尼因子, J: 全1矩阵
图上的随机游走
用于网络分析、推荐系统和图采样。平稳分布与节点度数相关。
MCMC 采样方法
马尔可夫链蒙特卡罗方法通过构建以目标分布为平稳分布的链，从复杂概率分布中生成样本。
- Metropolis-Hastings algorithm
- Gibbs sampling
- Boltzmann machines
隐马尔可夫模型 (HMM)
用于语音识别、生物信息学和金融。HMM 具有底层马尔可夫链和隐藏状态。
排队论
生灭过程对队列建模。平稳分布给出系统中拥有 n 个顾客的长期概率。
棋盘游戏
像大富翁和蛇梯这样的游戏可以建模为马尔可夫链，以计算期望的游戏长度和访问频率。