动机
有限不可约链不能一直探索新状态;无限空间却可以,因此有限状态平衡定理需要替代版本。即使链几乎必然返回,远游也可能长得令平衡概率无法存在。关键区别在于终会返回,还是以有限的平均时间返回。
合适的分析单位,是离开一个参考状态后完整返回的一次远游。记录其中各状态的到访次数,再把期望次数除以期望远游长度,应能产生概率分布。但远游长度可能期望无限,无限求和也需要理由。本节会逐一处理,而不把无限测度形式地归一化。
本节以独立可积变量的强大数定律为预备知识,不在此证明该定律。以下则会建立本节可数链结论所需的其余论证。分布以行向量表示,时间为离散。
定义
定义 2.2.1
(返回时间、正常返与循环占用)
设可数空间 上的随机矩阵 不可约。固定 ,令
常返表示 ;正常返再要求 ;均值无限的常返称零常返。
在常返不可约链中,由每个起点都几乎必然击中其他状态。理由是常返状态有无限次返回,每次返回都有一个固定正概率沿有限路径到达目标;持续失败的概率趋零。在击中时刻使用马尔可夫(Markov)性,可按时刻等于哪个整数分类证明。
计算一个循环,包含起始的 ,但不包含终端返回,故 。由 Tonelli 定理,总质量是 ;此定理容许交换非负和与期望,即使结果无限亦可。在常返情况,各个 本身有限:由 有一条简单路径以正概率在再次到访 以前到达 ,所以返回 前到访 的次数有几何尾界。
定义 2.2.2
(全变差距离与非周期性)
概率向量 的全变差距离定为
非周期表示某状态所有正返回步数的最大公因数为一;不可约性使各状态周期相同。平稳概率满足 。
概念视角结构
全变差就是最佳耦合
全变差也是所有耦合中最小的不一致概率:在 、 的所有配对上,。对任何耦合,。反过来,在每个对角点 放质量 ;剩余质量为 ,而两个归一化后的剩余部分支撑不相交,其乘积便把这些质量全部放在对角线以外。下文的相遇论证只是其中一种耦合,给出的是上界。
定理/命题
定理 2.2.3
(可数平稳判据与 Kac 公式)
不可约可数链存在平稳概率分布,恰好当它正常返。此分布唯一,各分量皆正,且
参考状态可任意选取,所以每个状态的平均返回时间都是 。
定理 2.2.4
(占用平均与普通收敛)
对不可约正常返可数链,由任意初始状态出发,对每个 均有
若链亦非周期,则各 都有 。此处不宣称任何收敛速率。
证明思路
构造并识别平稳分布
证明
(回返循环给出平稳分布,反之亦然)
先设 。计算返回前各状态的期望离开次数,并用条件期望,得到
起点和终点都是 ,所以把时刻 换成 不改变净次数。和式非负,交换均合法。除以有限总质量 ,便得平稳概率。
反过来,设平稳概率 存在。不可约性推出各 :某个正质量状态可在有限步内到达任何状态,且 。以 开始。“第 步是往后永不到访 的最后一次到访”这些事件互斥,而且各有概率 。它们的总概率不能超过一,故共同概率为零, 常返。同样论证各状态,再用不可约性,得由每个起点几乎必然击中 。
按零至第 步之间最后一次到访 的时刻,分解 。若最后到访在 ,贡献是 。余项来自完全避开 的路径,其对所有 的总质量至多 ,其中 包括零时刻。由几乎必然击中及控制收敛,此量趋零。因此
对 求和得 ,故 有限,Kac 公式成立,所有平稳概率都等于循环构造。改用另一参考状态即得其相应公式。
由循环得到时间平均
证明
(再生与强大数定律)
由击中时刻的马尔可夫性,从 起的相邻回返循环独立同分布。长度的均值为有限的 ;到访 的报酬均值为 ,且报酬不超过循环长度。对两组序列使用强大数定律,第 步前完成的循环数除以 趋于 ,每个完成循环的平均报酬趋于 。
未完成循环不造成渐近误差。若返回时刻依次为 ,强大数定律给出 ;比较相邻归一化和式,得到 。未完成报酬不超过该循环长度,故相对于 可忽略。由另一初始状态出发,首次击中 几乎必然有限,只多出有限前缀。这证明路径占用极限。比例介于零与一之间,故可取期望得到平均转移概率极限。
非周期收敛的耦合证明
证明
(与平稳副本相遇)
先证一个路径事实:不可约非周期链中,每对 都有 对所有足够大的 成立。在参考状态,有限多个正返回步数已可令最大公因数为一。它们的非负整数组合包含所有足够大的整数:选其中一个长度 ,对模 的每个余类选一个非负组合代表,再添加若干个 。代表存在,因这些长度的余数在有限循环群生成整个群,非负组合也能表示反元素。接上通往参考状态及离开它的固定路径,即证一般 的事实。
现在独立运行两个副本,一个从 出发,一个以平稳分布开始。乘积链的转移概率为 ,不变概率是 。上述路径事实保证两坐标可在同一个足够大的步数到达指定目标,故乘积链不可约。已证的平稳判据使它常返,因此几乎必然击中固定对角状态 。
相遇后让两副本使用相同的未来转移。由击中时刻马尔可夫性,每个边际仍遵循原链,但两者从此相等。对任意集合 ,两者落在 的概率差,不超过尚未相遇的概率;后者趋零。对 取上确界,便得全变差收敛。第二副本可按平稳混合取任意初态,因为乘积链由每个起点都几乎必然相遇。
证明透视
每个假设用在哪里
有限平均返回长度容许归一化及报酬强大数定律;不可约性传播常返并保证唯一性;非周期性只用于普通收敛证明中的乘积链不可约性。移除非周期性,不会令循环平均或 Kac 公式失效。
不可约步骤还有一个重要细节。由常返的 重复尝试固定路径,必能最终到达 。若由该 出发有正概率永不到 ,则由 沿正概率简单路径在返回前到 ,再避开 ,便给出正概率不返回 ,与常返矛盾。因此每个状态都几乎必然击中 ;改换目标重复此论证,就得到循环与耦合证明使用的整个常返类性质。
例题详解
例题 2.2.5
(倒数后重置的链)
由零以概率 选非负整数 并跳至 ,之后确定性地逐步倒数至零。假设每个 ,且 。一个回返循环长 ;正状态 恰在 时到访一次,所以
若 ,则 ,所有 都有 。零处正自环使链非周期,因此全变差收敛。若重置值几乎必然有限但均值无限,每次远游仍返回,却没有平稳概率。
例题 2.2.6
(零常返整数游走)
整数线上的简单对称游走满足 。期望到访级数发散,故常返。候选不变概率向量 则须满足 ,即相邻差为常数。整条整数线上的非负仿射序列只能是非负常数,非零时不可和。Kac 判据因此识别它为零常返。其周期亦为二;常返与非周期是不同问题。
例题 2.2.7
(有限均值不消除周期)
确定性两状态交替的平均返回步数都是二,平稳分布为 。每条路径渐近一半时间在各状态,但由固定状态开始,一维分布永远交替,全变差收敛失败。独立乘积链分成对角与非对角类,正好指出耦合证明中哪个假设失效。
常见错误
常见错误
(把无限不变向量归一化)
总质量无限的不变向量并非概率;反过来,候选权重之和有限,也须先证明对实际链不变。回返循环论证在明确假设下同时提供两点。单条前后相关的轨迹的平均由再生性证明,并非把相邻状态当成独立。
反例模式
逐点收敛不等于对起点一致收敛
收敛定理一个诱人的加强版是 。取 的倒数链即可推翻它,尽管该链不可约、非周期且正常返,并有 。从 出发时,在每个时刻 链都位于 ,故 ,且
由于 任意,在每个固定时刻对起点取上确界都至少是 。定理只断言每个固定起点的收敛。在有限空间上,有限多个起点的最大值确实趋于零;但在可数空间上,一致性需要另外的控制。
耦合相遇时间也不必期望有限;几乎必然有限已足以证明全变差收敛。
总结
回返循环把常返问题变成归一化问题。有限平均循环等价于唯一平稳概率,其倒数给出参考状态质量。再生报酬证明占用平均;非周期性再容许乘积链耦合,把平均提升为单时刻分布收敛。
练习
快速检查
(倒数模型取 ,。求平稳分布与各状态平均返回时间。)
用 及 Kac 公式。
解答 · 答案
几何尾为 ,,故所有 有 ,而 。零自环保证非周期。
快速检查
(若 ,, 使总和为一。不求 ,分类倒数链并说明理由。)
把 与调和级数比较。
解答
平方倒数级数收敛,概率可归一化;但 ,由与调和级数比较可见。每次 几乎必然有限,故每次返回发生但均值无限。链不可约且零常返,没有平稳概率。
快速检查
(不可约平稳链有 。求平均返回时间及长期到访比例。单凭此数据可否证普通收敛?)
分清时间平均与单一时刻分布。
解答 · 答案
Kac 公式给五步,占用比例几乎必然趋于 。所用普通收敛定理还要求非周期,单凭 数值不能验证。
快速检查
(两个确定性交替副本从相反状态出发,为何乘积链耦合失败,即使各链皆正常返?)
追踪两个坐标之差模二的值。
解答
两坐标在每步仍相反,乘积链无法到对角,因此可约。不能由整个乘积空间有平稳概率,就推论从非对角状态出发的不可约常返性。缺少的非周期条件,正是先前保证乘积不可约性的条件。