为什么要倒过来看?
转移矩阵让我们由现在预测下一个状态。假如把一段处于平稳状态的记录倒放,问题便变成:已知现在的状态,之前各个状态的可能性有多大?答案既取决于正向转移,也取决于各状态被访问的频率。罕见状态可以很容易转到常见状态,但反方向的转移却不一定频繁。
本节讨论有限状态、时间齐次的链。下文以行向量表示分布,并假设读者熟悉条件概率和矩阵乘法。
流量与反向链
设 是有限状态空间 上的随机矩阵, 是各分量均为正的平稳概率分布。令链以 开始,则每个后续时刻的分布都是 。定义一步平稳流量
平稳性表示每个状态的流入总量等于流出总量:。这并不表示每一对状态之间的两个方向流量都相等。
定理 2.10.1
(平稳有限链的反演)
对 定义
任取固定终点 ,反向序列 ()是一条初始分布为 、转移矩阵为 的马尔可夫(Markov)链。此外 ,而 。
证明
(沿路径抵消平稳权重)
由平稳方程,;各项也非负。正向路径 的概率 等于
因为各个 因子互相抵消。右边正是反向初始分布和转移所给出的路径概率,因而证明有限时间范围内的反向马尔可夫性。另外,;再用一次反演公式便得到 。除以 需要正值假设;平稳记录中不会观察到平稳质量为零的状态,要另行处理。
贝叶斯(Bayes)公式可以直接给出单步反向概率;路径证明更进一步说明整段反向记录也是马尔可夫链。这里固定有限终点,不必预先构造双向无限时间过程。
细致平衡比平稳性强
定义 2.10.2
(可逆性)
若一条平稳链的每条有限路径,与把它倒转后的路径具有相同概率,就称这条链可逆。这等价于 ,也就是以下细致平衡方程:
事实上,长度为一步的路径概率相等便给出这些方程;反过来,方程使 ,路径定理便保证任意有限长度的正反路径概率相等。
概念视角代数
可逆性即流量矩阵对称
细致平衡就是说流量矩阵 (其中 )是对称矩阵。等价地,对列向量上的加权内积 , 是自伴的:
两者对所有 相等,恰好当 。此时 是与 相似的实对称矩阵,所以可逆链只有实特征值。下面的循环链有复特征值 ,仅凭这一点已可知它对任何平稳分布都不可逆。
细致平衡是求平稳分布的常用方法,因为它是逐对的条件,而不是按顶点排列的方程组。
命题 2.10.3
(细致平衡推出平稳性)
若概率向量 对所有 满足 ,则 。一般而言逆命题不成立。
证明
(对起始状态求和)
对每个 ,把细致平衡对 求和,得 ,因为 的第 行和为一。逆命题不成立:平稳性只平衡每个顶点的总流量,细致平衡却要求每对状态的两个方向分别抵消。例题中的循环链对均匀分布平稳,却有 。
实际求解时,可以先找正权重 ,使 ,再除以 。有限空间的总和必然有限;可数无限空间则不能想当然地认为总和有限,下例说明了这一点。
反例模式
细致平衡权重需要有限总和
断言:在可数状态空间上,满足细致平衡的正权重总可归一化为平稳概率。取 上以概率 向右、以概率 向左的游走,其中 。权重 在每条边上满足细致平衡:,而 。但 ,因为两边尾部之一是发散的等比级数。事实上这个游走是暂态的,根本没有平稳概率。修正后的叙述加上假设 ;此时由上述命题, 是可逆的平稳概率。
例题
例题 2.10.4
(两状态链)
设
两状态间的平衡方程为 ,所以 。两方向流量都等于 ,对角方程自动成立,故 。事实上,任何具有严格正平稳分布的两状态链都可逆:唯一非平凡的平稳方程,正是唯一非平凡的细致平衡方程。
例题 2.10.5
(平稳但不可逆的循环流)
在状态 上令 。均匀分布 是平稳的:每个状态流入的概率与流出的概率相同。然而 ,。反向链必定沿相反方向移动,因此与正向链不同。此链有周期;平稳性仍然成立,只是由固定状态出发时未必收敛。
若想要非周期的例子,可令 。均匀分布仍然平稳,而 、。自环消除了周期,却没有消除循环流。因此平稳性和非周期性都不能推出可逆性。
第三个例子直接用细致平衡求 ,再验证反向矩阵并不是转置。
例题 2.10.6
(三状态的生灭链)
设
一步之内只有相邻状态互通,所以细致平衡只有两条非平凡方程: 及 。因此 、,归一化得 。用第一列验证平稳性:。此链可逆,所以 。转置则不同:它的第一行 之和为 ,所以 甚至不是随机矩阵。这里的边界情形是转移图为一条没有环路的路径;对这种图,下面的环路判别法自动成立,细致平衡总可逐条边求解。
环路判别法及其限制
循环流的例子提示:不可逆性是环路的性质。以下判别法把这一点说得精确。
定理 2.10.7
(可逆性的环路判别法)
设 是有限不可约链,且 当且仅当 。则 对某个严格正的平稳分布可逆,当且仅当每条使用正概率转移的有向环路 都满足
证明
(由根状态沿路径构造权重)
必要性:把环路上各条边的细致平衡方程相乘,消去正的 因子即可。充分性:选一个根状态 ,令 。沿由 到 的正概率路径,逐步定义 。任意两条路径给出的乘积相同:先走第一条,再反向走第二条,便得到闭合路径,可应用环路条件。不可约性保证每个状态都可到达。所得权重在每条正概率边上满足细致平衡;由对称支撑假设,零概率边也没有问题。最后把正权重归一化为 ,由上述命题它是平稳的。
证明透视
为什么权重定义良好
充分性的证明以沿路径的乘积定义 ,所以唯一真正的困难是与路径无关。这正是用到环路条件之处:两条由 到 的路径合成一条闭合路径,而闭合路径的条件使两个乘积相等。闭合路径可以重复经过状态,但它可分解为有向环路,所以对环路的条件已经足够。
对称支撑假设用了两次:比值 的分母必须非零,而 的边自动满足细致平衡。不可约性使每个 都有定义,有限性则使 有限,这正是上面可数反例中失效的一步。这也说明,若图中有多个独立环路,只检查其中一个并不足够:只要一条环路不平衡,就有两条路径给出不同结果。
常见错误
常见错误
(用转置来反演)
反向链是 ,而不是 。两者只在 均匀时一致,例如双随机矩阵。在生灭链的例子中, 有一行之和为 ,根本不是转移矩阵。
常见错误
(由平稳性推断可逆性)
解出 本身并不保证细致平衡。循环链对均匀分布平稳,但 、。必须逐对检查 ,或对每条环路使用环路判别法。
练习与解答
快速检查
(设 。求平稳分布 和平稳状态下的 。)
两状态链只有一条非平凡的平衡方程。
解答 · 答案
由 和总和为一,得 。细致平衡成立,所以 。
快速检查
(一条三状态链以概率 顺时针移动,以概率 逆时针移动。求平稳分布及反向转移概率。此链可逆吗?)
先检查各列之和。
解答 · 答案
每列的总和都是一,故 。反向链交换两个方向的概率:顺时针为 ,逆时针为 。两方向边流量不同,因此不可逆。等价地,顺时针环路的乘积为 ,其反向为 。
快速检查
(假设 对严格正的平稳分布 可逆。证明对每个 ,都有 。)
比较一条路径与其反向路径。
解答 · 答案
正向每条 步路径与其反向路径概率相同。对所有中间状态求和,就得到所需等式。也可利用 和路径中的因子抵消。
快速检查
(某同学在可数无限状态空间找到满足细致平衡的正向量 ,便断言 是概率分布。给出反例,并指出缺了什么步骤。)
试考虑对称游走。
解答 · 答案
整数上的简单对称随机游走取 ,每条边都满足细致平衡,但 。归一化需要非零且有限的总质量;这里得到的是不变测度,不是概率分布。