动机
返回概率可以趋零,但其和仍发散,所以某时刻占据特定状态变得不大可能,不能判断是否终会返回。暂态与零常返的转移概率都趋零,但期望总到访次数分开两者。正常返则有另一极限结构,由周期决定哪些子序列可收敛。
本节证明逐点叙述,不把时间平均直接当成普通极限;平均零的序列仍可偶尔有尖峰。零常返情形缺少的是分析论证:马尔可夫(Markov)算子收缩加权平方范数,迫使晚期可能取值在各状态渐近相同;无限不变质量再迫使共同值为零。
预备的平稳判据及非周期耦合定理,已在可数常返、Kac 公式与耦合证明,其证明使用回返循环及强大数定律。以下明确指出此依赖;新趋零论证所需的加权方差及子序列事实则全部展开。不假设更新、Tauberian 或未命名的分析收敛定理。
定义
设 为可数 上不可约随机矩阵,写 。常返表示返回概率一;平均返回时间有限为正常返,否则零常返;返回概率小于一是暂态。不可约性使各状态分类相同。
定义 2.8.1
(不变测度与加权平方范数)
不变测度是向量 ,各 且 ,总质量可无限。对实函数 定义
分析中只使用平方范数有限的函数;单一状态的指示函数属于此空间,因该状态的不变权重有限。
定义 2.8.2
(周期与循环类)
正返回步数的最大公因数为 ,称周期。选参考状态 ,循环类 是可从 以模 余 的步数到达之状态,类索引按模 解读。以下会证明标签定义良好及所需性质,而不单凭记号假设。
定理/命题
定理 2.8.3
(非正常返情形的趋零)
不可约可数链若暂态或零常返,则
零常返叙述不需非周期。暂态时 ;零常返的返回和发散,即使每项趋零。
定理 2.8.4
(正常返周期极限)
链正常返,平稳概率为 、周期为 ,则各循环类有 。若 ,对 ,
整个子序列分布甚至以全变差收敛至 上为 、外部为零的概率向量。重标循环类即可处理其他初态。
证明思路
暂态与回返循环测度
证明
(有限到访,以及由回返循环得到的不变测度)
状态 返回概率 时,包括零时刻的总到访期望是 ,因至少 次到访的概率,由击中时刻马尔可夫性为 。从别处开始先击中 或永不击中,期望次数是击中概率乘上述有限均值。Tonelli 使期望次数等于 。非负收敛级数的项趋零,证暂态情形。
常返时固定 ,令 是首次正返回。定义 为时刻零至 到访 的期望,则 ,各项正且有限,。正性来自返回前由 到 的简单路径。对 ,每次到访都有正概率沿固定简单路径在另一个 以前到 ,所以次数有几何尾界。
把循环中的期望离开改计为期望到达,初终都是 ,便证不变性。项皆非负,总质量无限时也可用 Tonelli。总质量是 ,故零常返时恰为无限。这建立分析所需的全部测度假设,不只写一条形式不变方程。
加权平方范数引理
零常返情形建立在以下引理之上,先就非周期链陈述。
引理 2.8.5
(无限不变测度下的趋零)
设 是可数 上不可约且非周期的链, 是不变测度,对每个 有 ,且 。则对所有 有 。
证明
(范数收缩、方差恒等式与平坦极限)
加权 Jensen、不变性及非负求和给出
各 行和合法:绝对期望不超过二阶矩平方根,而 ,故该行二阶矩受全局有限平方范数除以 控制。
固定目标状态 ,设 ,分量是零至一的转移概率。平方范数递减至有限极限,所以每个固定 有
差额有精确方差表达式
对概率行展开平方可证方差恒等式;平方可积与非负求和给无限版本。若 可从同一 以 步到达,和式界住其平方差的一个固定正倍数,所以取值差趋零。
非周期性使任意两状态都有这种共同步数。参考状态有限多个返回步数的最大公因数已为一,串接返回路径使返回步数对加法封闭,因此它们的非负组合包含所有足够大整数:选一长度,对其模数各余类取得组合代表,再加该长度的倍数。有限余类群中非负组合也产生反元素,故所有余类皆出现。再接上参考状态通往 的固定路径,所有足够大的共同长度皆有正概率。因此每对 都有 。
选一子序列使 收敛至 ,有界性保证可取得。其他每个坐标也沿此子序列趋同一 。对任意有限 ,
有限集递增穷尽无限不变质量,故 。每个子序列的标量极限都是零,所以整个序列在每个坐标趋零,不只是 Cesàro 结论。
证明透视
无限不变质量为何迫使零
证明先把不等式变成恒等式,再把恒等式变成极限;每个假设各有一个用途。
- 不变性用了两次:在收缩 中通过 ,以及在方差恒等式中,那里 对 不变。 有限使起始范数 有限。
- 关键一步是方差恒等式。范数 递减且有下界,所以任何固定 步的范数下降都趋零;恒等式把这个趋零的下降转化为:凡可从同一状态以 步到达的两个状态, 在其上渐近相等。
- 非周期性为每对状态提供这样的共同步数,于是平坦性扩展到整个 。
- 无限质量只在最后使用。取值为 的平坦轮廓,在有限集 上的平方范数约为 ;它要一直不超过 ,只能 。
论证以紧致性收尾:每个子序列都有进一步的子序列具平坦极限,每个这样的极限都是零,所以整个序列逐点趋零。这补上由平均到逐点的缺失步骤,无须更新定理或 Tauberian 黑箱。
把引理用于回返循环测度,就证非周期零常返情形。无限质量这一假设不能删去,两状态链即可说明。
反例模式
有限不变质量留下非零的平坦极限
断言:对任何具不变测度的不可约非周期链,都有 。取 , 的每个元素都是 。则 不变,总质量有限,为 ;而对 ,。证明的每一步都成立: 是常数,所以范数下降为零, 恰好平坦,。失效的是最后一步,因为 并不迫使 。所以断言错误。修正后的叙述需要 ;质量有限时,平坦极限就是平稳概率 ,这里为 ,即正常返情形的极限。
循环类消除周期障碍
证明
(循环类、质量平衡与逐类耦合)
从 到同一状态的两条路径长度,其差是 倍数:接同一条返回 路径,便成两个返回步数。因此标签定义良好,每步使类前进一,某条返回路径中全部 类都会出现。 限在任一类不可约,因同类间路径长度为 倍数;其返回步数除以 后最大公因数一,故非周期。
对任意不变测度,非负求和及一步类前进给
类只有有限多个,所以总质量无限时每类都无限。限制测度对 不变,逐类用加权范数引理。由 推至 ,先走 步,再按所得状态平均趋零概率;概率加权可数和由有界收敛交换极限。这证所有周期的零常返趋零。
平稳概率则由同一等式得 ,限制 的平稳概率是该类上的 。先前非周期正常返耦合定理可用于此不可约非周期限制。其已展开的证明是:独立乘积链有不变概率,由共同长度路径不可约,再由已证平稳判据常返,因此几乎必然到固定对角状态;相遇后用相同转移,尚未相遇的概率界住全变差。这里引用的是已证平稳判据,不是外部更新极限定理。
由 开始, 步后在 上形成概率混合;每个混合起点在 下皆收敛至该类 ,全变差距离至多一,所以平均亦收敛。其他类在这些时刻概率为零,证明循环极限并完成两定理。
例题详解
例题 2.8.6
(暂态有偏游走)
整数线最近邻游走向右概率 ,奇数步返回概率零,第 步为 。二项幂级数 给返回零的期望次数二,故暂态,各转移概率趋零。整个到访和有限,比单项趋零更强。
例题 2.8.7
(返回常返但概率仍趋零)
简单对称整数游走的返回母函数为 , 增至一时发散,非负单调收敛使返回和无限,故常返。计数测度不变且无限。周期二,而 在任一奇偶类不可约非周期,计数质量亦无限,所以已证引理给转移概率趋零。平稳递推使坐标在整条整数线仿射,不存在非零非负可和解,故没有平稳概率。这是零常返,不是暂态。
例题 2.8.8
(状态权重不等的周期极限)
以概率 到 、 到 ,两者必回 。类是 、,周期二,平稳向量 。由 ,偶数时刻点质量在 ,奇数时刻在 的分布为 ,恰是相容类平稳权重的两倍,其他类零。乘二才能使子序列极限总质量为一。
概念视角代数
在谱中看见周期
对这个有限链,循环极限就是一个谱分解。矩阵 的特征值为 ;对应 与 的右特征向量为 和 ,左特征向量为 和 ,并已归一化使 。因此当 时,
第二项正是两个类之间的交替。对任何周期为 的不可约有限链,Perron–Frobenius 定理指出:模为一的特征值恰为各个 次单位根,并且每个都是单重的。
常见错误
不变测度与不变概率须分清。证明中的无限质量导致逐点零极限,不能写个无限分母便归一化。
常见错误
(把单项趋零读成到访总和有限)
概率趋零不表示总到访次数期望有限,非负发散级数的项可趋零:对称整数游走有 ,但返回和无限,游走常返。暂态是关于总和的叙述,不是关于单项的叙述。
常见错误
(把 Cesàro 极限升格为普通极限)
Cesàro 收敛不能无额外理由推出普通极限。在上面的周期例子中, 的平均收敛至 ,各项却在 与 之间交替。零常返情形中,加权方差证明正好提供所欠的理由。
常见错误
(不指定余类便取周期极限)
正常返周期链若不指定余类便对 取极限,会混合不相容支集,也会遗失因子 。沿 的正确极限,在相容类上是 ,在其他地方是零。
总结
暂态趋零来自有限总到访;零常返趋零来自不变测度收缩,以及无限质量上不可能有非零平坦有限范数极限。循环类处理周期,正常返子序列则收敛至相容类内归一化平稳概率。
练习
快速检查
(暂态状态返回概率 ,从 击中它的概率 。求从 出发的期望总到访次数,并解释转移概率趋零。)
先计算由该状态本身出发的到访次数。
解答 · 答案
由该状态开始的平均次数 ,乘击中概率得 。它等于非负转移概率和,有限故每项趋零。
快速检查
(确定性三状态有向环,求平稳概率及由固定状态出发的三个余类极限。)
每个循环类都只有一个状态。
解答
平稳分布 ,周期三。模三余零、一、二的时刻,分布分别是对应后继环状态的点质量,等于各单点循环类平稳权重的三倍。
快速检查
(无限测度各分量正且有限,某序列平方范数至多 ,沿子序列所有坐标趋于同一 ,证明 。总质量有限时有何不同?)
先在有限集上处理。
解答
每个有限 由有限和收敛得 ,穷尽使 任意大,故 。总质量有限时,非零常数也有有限平方范数,此界不能迫使其为零。
快速检查
(用对称整数游走及返回母函数,解释逐点转移极限为零为何不蕴含暂态。)
令 增至一。
解答
在 发散,所以期望返回次数无限而常返;无限测度论证仍使各转移概率趋零。级数总和与单项极限回答不同问题。