机器人入行指南
原理层/马尔可夫链:时间平均何时等于集合平均

原理层 T18 / 27 · 收敛与不动点

马尔可夫链:时间平均何时等于集合平均

replay buffer 打散时间相关性为什么合法、on-policy 分布是什么——答案都在平稳分布和遍历定理里。前提是链不可约且非周期,缺一不可。

马尔可夫性未来只依赖现在转移矩阵行和为 1平稳分布π = πP 的解遍历性时间平均=集合平均时间平均=集合平均是 MCMC 与 on-policy 采样共同的理论靠山
约 55 分钟2 定理6 步证明4 题自测

一句话结论

有限马尔可夫链只要不可约且非周期,就存在唯一的平稳分布 π,从任何初始分布出发 π_k = π_0 P^k 收敛到它,且时间平均收敛到 π(遍历定理)。两个前提缺任何一个,结论都可能失效。

策略评估时「用轨迹上的频率估计状态访问概率」,离策略修正时的权重设计,replay buffer 从旧轨迹采样——每一件事的合法性都依赖本篇的定理。更深一层:策略 π 诱导的马尔可夫链的平稳分布就是 on-policy 访问分布 d^π,它是策略梯度定理里那个权重项。

为什么需要它

两个实际问题先摆出来。其一:你在环境里跑了 10 万步数据,想知道某个状态出现频率是多少——这个「频率」稳定吗?会收敛到某个确定的值吗?其二:replay buffer 里的数据是按时间顺序高度相关的(相邻几步几乎同一个局部),从中随机采样、当作独立样本用,凭什么可以?

两个问题的答案都指向同一组概念:平稳分布(系统长时间运行后状态的分布)和遍历性(时间平均等于集合平均)。「稳定吗」由前者回答,「凭什么」由后者回答。

先约定对象:有限状态 {1,…,n},转移矩阵 P(P_ij = 从 i 一步到 j 的概率,行随机:每行和为 1)。链马尔可夫的含义:下一步的分布只依赖当前状态,与怎么到达当前状态无关。

两个前提登场。不可约:从任何状态出发都能(经若干步)到达任何其他状态——链不碎成孤岛。非周期:回到同一状态所需步数不全是某个 d>1 的倍数——链不「走拍子」。周期链的典型:确定性交替 A→B→A→B,它的分布永远在两个状态间震荡,永不收敛。

定义

定义 6.1 平稳分布

行向量 π 满足 π = πP 且 Σπ_i = 1、π_i ≥ 0,叫平稳分布。含义:如果当前状态分布是 π,走一步后分布还是 π——系统达到统计平衡。

为什么这样定注意它是一个「不动点方程」:π 是转移算子的特征值 1 对应的左特征向量。这与 T5 的不动点是两回事——那里是值函数向量的逐点迭代,这里是分布的矩阵乘法,但「迭代找平衡」的思想同源。

定义 6.2 时间平均与集合平均

时间平均:沿一条长轨迹,状态 i 出现的频率 (1/T)Σ1s_t=i。集合平均:固定时刻的状态分布中 i 的概率,长时间后即 π_i。遍历性 = 两者(T→∞ 时)相等。

为什么这样定RL 的所有「按经验估计」默认了遍历性成立。本篇的任务是把「什么时候成立」说精确。

定理与证明

定理 6.1 不可约有限链的平稳分布存在且唯一

P 不可约(有限状态)⇒ 存在唯一 π=πP(概率向量)。若再非周期,则 P^k 的每一行收敛到 π。

证

存在性(构造):取任意初始分布 μ,考虑 Cesàro 平均 μ_k = (1/k)Σj=1k μP^j。有限维空间上概率向量集是紧集,μ_k 有收敛子列,极限记 π。

π 是不动点:πP = lim (1/k)Σ μPj+1 = lim (1/k)(Σj=2k+1 μP^j) = π + lim (μPk+1 − μP)/k = π(后一项被 1/k 压没)。归一化和非负性在极限下保持。∎(存在性)

唯一性(主步骤):设 π、ν 都是不动点。关键事实:不可约链中,对任意状态 i、j,存在 m 使 (P^m)_ij > 0(从 i 能到 j)。于是 π_i = Σ_l π_l (P^m)_li ≥ π_j (P^m)_ji > 0——所有 π_i > 0(平稳分布严格为正)。

现在取 π = πP^m 与 ν = νP^m,比较两者的差在某个「最重」的状态上:设 δ_i = π_i/ν_i,取 δ 最小的状态 k,则对任意 i:π_i = Σ_l π_l (P^m)_li ≥ Σ_l δ_k·ν_l (P^m)_li = δ_k ν_i,即 δ_i ≥ δ_k 对一切 i。由 Σπ=Σν=1,所有 δ_i 相等——π=ν。∎(唯一性)

收敛性(陈述主步骤):非周期时 P 的模 1 以外的特征值绝对值全 <1(Perron-Frobenius 定理的内容),几何衰减 ⇒ P^k → 1π(每行都是 π)。完整证明依赖特征值理论,超出本篇边界。

注诚实标注:存在性和唯一性的证明是完整的;收敛速率依赖 Perron-Frobenius 定理,只陈述。周期链的反例(确定性交替)说明非周期不可省:它是「分布收敛」的前提,但平稳分布存在唯一不需要它。

定理 6.2 遍历定理(陈述+直观论证)

不可约正常返链上,时间平均几乎必然收敛:limT→∞ (1/T)Σt=1T 1s_t=i = π_i。

证

完整证明(Birkhoff 遍历定理或马尔可夫链专用版)超出边界。直观论证链条:平稳分布是「不变」的测度 → 系统长期行为被 π 主导 → 单条轨迹「看遍」所有状态(不可约保证)且按 π 的比例访问(正常返保证)→ 频率即概率。

注RL 里它几乎总是被默认成立。要知道失效的情形:链分成不连通块(时间平均取决于起点所在块)、吸收态(频率全堆在吸收态)、周期链(频率仍收敛到 π 但分布序列震荡)。奖励设计里造出吸收态(episode 卡死)时,「经验频率=期望频率」就悄悄失效了。

手算一遍

两状态链:P(0→0)=0.9,P(0→1)=0.1,P(1→0)=0.2,P(1→1)=0.8。手算平稳分布,并估计混合速度。

  1. 解 π=πP。第一分量:π_0 = 0.9π_0 + 0.2π_1 → 0.1π_0 = 0.2π_1 → π_0 = 2π_1。
  2. 加归一化:π_0 + π_1 = 1 → π = (2/3, 1/3)。
  3. 验证流平衡(另一条独立检查):从 0 流出到 1 的概率流 π_0·0.1 = 1/15,从 1 流入 0 的 π_1·0.2 = 1/15,相等 ✓。
  4. [object Object]
  5. 分布误差 ~ 0.7^k:k=10 时 0.7^10≈0.028,k=20 时 0.0008。与实测吻合(P^10 后 [0.7467, 0.2533],误差 0.080≈π_0·0.7^10 的量级)。
答

π=(2/3, 1/3),混合时间尺度 ~1/(1−λ₂)≈3.3 步(每 3 步误差降一半)。手算过程中用了「解线性方程 + 流平衡验证 + 特征值估计」三件事——都只依赖本篇定义。

实跑一遍

数字出处

同一链的实测(特征向量法 + 40 万步模拟):

  • 平稳分布(P^T 特征向量)= [0.666667, 0.333333],与手算逐位一致
  • 分布收敛:P^1 后 [0.900, 0.100] → P^5 [0.781, 0.219] → P^10 [0.747, 0.253] → P^20 [0.723, 0.277] → π
  • 时间平均(s0 频率):前 1000 步 0.714(还没混合完)→ 1 万步 0.6706 → 10 万步 0.6686 → 0.6667
  • 收敛速率由次特征值 0.7 控制:0.7^20 ≈ 8e−4,与 10 万步时残余偏差 0.002 同量级

映射回强化学习

这里的对象RL 里的对应物站内用法
平稳分布 π策略 π 下的 on-policy 状态访问分布 d^π——策略梯度定理里的权重用法 →
遍历定理replay buffer 采样≈独立同分布采样的合法性根基用法 →
周期性失效episode 卡死在循环里时经验频率偏离 d^π用法 →
混合时间环境探索不充分时采集数据的「有效样本量」缩水用法 →

边界:这一篇停在哪里

本篇停在哪里:一般状态空间的遍历理论(Harris 链)、混合时间的定量界、可逆链与细致平衡,都不讲。够用判据:有限状态 + 不可约 + 非周期,本篇定理全部适用;RL 环境几乎总满足(探索噪声让任何状态可达)。

自测 4 题

全是手算和「找证明错在哪」类题目,不出背诵题。答不上来回到对应小节。

01平稳分布存在唯一需要什么条件?分布收敛又需要什么?

存在唯一:不可约(有限链)。分布收敛(P^k 每行→π):再加非周期。反例:确定性交替链 A↔B 有唯一平稳分布 (1/2,1/2),但 P^k 永远在两个分布间震荡——平稳性和收敛性是两回事。

02replay buffer 把相关数据当独立样本用,遍历定理给的是哪部分保证?还缺什么?

遍历定理保证时间平均→π(长期频率合法)。缺的是「有限样本的方差分析」——相关样本的有效样本量比独立样本小(混合时间越长缩水越多)。实践中 buffer 够大 + 随机采样把相关性打散到可接受,但没有免费午餐。

03两状态链 P(0→0)=0.5, P(0→1)=0.5, P(1→0)=0.5, P(1→1)=0.5 的平稳分布是什么?混合速度呢?

π=(1/2,1/2)。次特征值 = 迹−1 = 0——一步就混合到位(P 本身每行都是 π)。对比上一题的 0.7:链越「健忘」混合越快。这是混合时间由次特征值控制的又一例证。

04训练中 policy 更新后,d^π 也在变。这和本篇定理冲突吗?

不冲突,但要分清时间尺度:每个固定策略 π 下,环境是固定马尔可夫链,d^π 是它的平稳分布(本篇定理适用);策略更新是在「换一条链」。这本质是两时间尺度问题——T10 的主题。

接着看

全系列 27 篇

T1矩阵就是旋转的记账本约 25 分钟T2从斜率到梯度:机器人学习算法的第一行约 25 分钟T3向量与受力:点积的物理读法约 20 分钟T4两把尺子和一把更好的尺子约 25 分钟T5电机转一圈的账:弧度、转速与功率约 20 分钟T6复数乘法就是旋转:四元数的一维版约 20 分钟T7基与坐标:为什么机器人什么都用矩阵约 45 分钟T8矩阵乘法:变换的串联,不是表格运算约 40 分钟T9雅可比:关节转一度,末端动多少约 45 分钟T10特征向量:矩阵不敢动的方向约 45 分钟T11SVD 与伪逆:没有精确解时,找最近的解约 50 分钟T12泰勒展开:用直线替曲线打工约 40 分钟T13概率空间:为什么「随机」需要公理约 50 分钟T14期望:「平均」的严格构造约 55 分钟T15条件期望:竖线的真正含义约 60 分钟T16四个不等式:「多少样本才够」的定量答案约 45 分钟T17范数与不动点:「一定收敛」的出处约 55 分钟T18马尔可夫链:时间平均何时等于集合平均约 55 分钟T19MDP 的数学构造:一条公理值多少钱约 50 分钟T20动态规划:两种迭代的账约 50 分钟T21优化:约束为什么不能只靠罚约 55 分钟T22随机逼近:学习率公式里的每一条约 55 分钟T23接触的数学:Hertz 理论约 45 分钟T24摩擦与摩擦锥:约束的几何形状约 40 分钟T25力封闭与抓取度量:ε 是一个线性规划约 50 分钟T26接触运动学:滚动为什么不是「贴着滑」约 45 分钟T27滑移检测:从「感觉到了」到「算出来了」约 50 分钟