动机
平稳分布是指在马尔可夫(Markov)链走一步之后保持不变的分布。平稳分布存在,并不等于链会收敛到它:一条链可以有平稳分布,却从某个特定起点出发永远振荡。懒惰性,即允许链停留在原地,可以消除这种振荡。
我们首先证明每条有限链都有平稳分布。然后在明确的不可约性与自环假设下,给出定量的收敛证明。作为应用,连通无向图上的懒惰随机游走会收敛到一个按度数加权的分布。
定义
定义 5.4.1
(平稳分布与不可约性)
设 是有限非空状态空间 上的转移矩阵。若行概率向量 满足 ,则称 是平稳的。若每个状态都可以沿着一条由正概率转移构成的有限路径到达其他任意状态,则称该链是不可约的。
定义 5.4.2
(全变差距离)
全变差距离为 。我们使用配套章节中已证明的耦合不等式:对分布 的任意耦合,它们的全变差距离至多等于耦合后两个状态不同的概率。
定理
定理 5.4.3
(有限平稳分布的存在性)
每个有限马尔可夫链至少有一个平稳概率分布。
定理 5.4.4
(存在可达自环时的收敛性)
设有限链不可约,并且存在状态 满足 。则它有唯一的平稳分布 ,并且存在整数 与 ,使得对每个初始分布 与每个整数 ,都有
证明:Cesàro 平均
证明
(Cesàro 平均有平稳的极限点)
任取初始分布 ,并定义
概率单纯形是紧致集,所以这个序列有收敛子列。它在一次转移之后的差是望远镜和:
分子的每个坐标都有界,所以这个差趋于零。若沿某个子列有 ,则由矩阵乘法的连续性得 。极限仍然是概率向量。这就在不假设不可约性、也不假设原序列 收敛的情况下证明了存在性。
证明透视
以紧致性与裂项取代收敛
紧致性提供极限点,裂项求和说明它是平稳的;证明既没有用到不可约性,也没有用到 的收敛。边界项 的每个坐标的绝对值至多为 ,因为 与 都是概率向量,所以即使各个分布振荡,它也趋于零。沿子列取极限用到右乘 的连续性,这在状态空间有限时成立;极限仍是概率向量,因为单纯形是闭集。在交替的两状态链上,分布 永远互换,平均却收敛到 。
证明:共同的终点
证明
(通过共同终点的耦合)
由不可约性,每个状态 都有一条通向 的正概率路径。为每个 选定一条有限路径。令 不小于所有选定路径的长度。较短的路径通过在 处添加自环补齐,直到恰好有 步,其概率仍为正。因此对每个 都有 。
状态只有有限个,所以 。同时 。对每个 ,把 步转移分布分解为在 处的公共质量 与一个剩余概率分布。若 ,则每个状态在 步内以概率一到达 ,下一步论证是显然的。否则,剩余分布为
为了在一个长为 步的区块上耦合两个副本,使用一个概率为 的共同伯努利(Bernoulli)决定。若成功,则把两个区块终点都置于 ;否则,分别从各自的剩余分布中抽取终点。每个终点都具有正确的 边缘分布。一旦两个副本重合,就让它们使用相同的后续转移,从而保持相等。
在某个区块之前尚未相遇的条件下,它们在该区块末尾相遇的概率至少为 。因此经过 个区块后它们仍不相同的概率至多为 。把从 出发的链与从平稳分布 出发的链耦合起来。第二条链的边缘分布在区块时刻始终为 ,由耦合不等式即得所示的界。
若 是另一个平稳分布,则让第一个副本从 出发。于是对每个 都有 ,所以该距离为零,。这就证明了唯一性。
证明透视
所有起点共用同一个硬币
不寻常的想法,是把 分解为 ,且对每个 的 都相同。这让从不同状态出发的两份拷贝共用同一枚硬币,因此无论它们的位置如何,都至少以概率 同时位于 。 上的自环只用来把每条路径补齐到共同的长度 。没有共同长度, 可能为零,周期链就是这样。
不可约性给出从每个状态出发的路径,有限性使最小值为正。论证以几何方式收束:每个区块都是一次新的机会,在尚未相遇的条件下,失败概率相乘为 。耦合只约束区块的终点,而这正是耦合不等式所需要的。
无向图上的懒惰随机游走
设 是有限、连通、无自环的无向多重图,至少有两个顶点,共有 条边的副本。在顶点 处,以概率 停留在 ;否则均匀地选取一条关联边的副本并沿其行走。每个顶点的度数都为正。定义
命题 5.4.5
(懒惰游走的平稳分布)
上述懒惰随机游走有唯一的平稳分布 ,并且收敛定理适用于它。
证明
(懒惰游走的细致平衡)
度数之和为 ,所以 是概率分布。对于相邻的不同顶点 ,设它们之间有 条平行边的副本,则
同一个细致平衡等式在 时是平凡的,对不相邻的顶点则两边都为零。对 求和即得平稳性。连通性给出不可约性,并且每个顶点的自环概率都是 ,所以收敛定理适用。只有当所有度数相等时,平稳分布才是均匀的。
例题详解
例题 5.4.6
(两状态振荡)
在一条边上的非懒惰游走会在它的两个端点之间确定性地交替。均匀分布是平稳的,但从某一端点出发的游走会在两个点质量之间交替,永远不会收敛到均匀分布。这里没有自环,所以上面的收敛定理不适用。
例题 5.4.7
(懒惰的两状态游走)
在同一条边上,懒惰游走以各一半的概率停留或跨过。无论从哪个端点出发,一步之后它的分布都是均匀的。定理的假设成立。
例题 5.4.8
(三个顶点的路径)
对于路径 ,度数分别为一、二、一。它的懒惰游走的平稳概率为 ,,。在平稳状态下,中间顶点被访问的频率是任一端点的两倍。
例题 5.4.9
(可约链)
若一条两状态链的两个状态都是吸收态,则这两个状态上的每个分布都是平稳的。存在性成立,但唯一性不成立,因为该链不是不可约的。
常见错误
反例模式
平稳不意味着每个起点都是平稳的
交替的两状态链有均匀的平稳分布,但点质量在每个时刻仍是点质量,并且在两个端点之间交替。平稳分布描述的是链从该分布出发时会发生什么;要使从其他起点出发也收敛,还需要额外的条件。
常见错误
(自环是充分条件而非必要条件)
这个证明假设某个状态上存在可达的自环,这是一个比最一般的非周期性判据更强的充分条件。它并不声称每个非周期不可约有限链都有自环,尽管存在更广的收敛定理。
常见错误
(耦合只控制区块的终点)
共同终点的耦合控制的是区块终点。它并不表示原来的两条链在区块内部必须沿相同的中间路径行走。可以在选定终点的条件下抽取路径,从而得到区块内部的完整耦合,但全变差的界只用到区块终点的分布。
从区块时刻到每个时刻
定理给出的是 的倍数时刻的界。它也蕴含中间时刻的收敛。对两个分布作用同一个转移矩阵不会增大全变差距离。用耦合来看这一点:先取这两个分布的一个最大耦合;当其状态相等时,让两者的下一个状态相同,并从相应的转移行中抽取。当它们不同时,使用这两行的任意耦合。一步之后两者不一致的概率不大于一步之前。
写 ,其中 。由于 ,对两个分布都作用 得
这个界可能偏保守:用来定义 的路径的概率可能非常小。它的目的是在所述假设下证明从每个初始分布出发的收敛性。要得到精确的混合时间估计,一般需要关于该链的更多信息。
没有自环的非周期性
自环假设很方便,但对有限不可约链是非周期的来说并不必要。考虑状态 ,转移 与 的概率为一,转移 与 的概率各为二分之一。其中没有自环,并且每个状态都可以到达其他任意状态。
状态零有长度为二和三的正概率返回路径: 与 。它们的最大公约数为一。状态一同样有长度为二和三的返回路径,状态二有长度为三和五的返回路径。因此按照通常的定义,即正返回时间的最大公约数,每个状态的周期都是一。这条链尽管没有一步自环,仍然是非周期的。
我们的证明没有使用一般的非周期定理;它借助自环把选定的路径补齐到同一长度。更一般的证明可以用一般的非周期性论证来取代这个方便的假设,但这里并未建立这一点。
细致平衡与平稳性
懒惰游走的计算使用了细致平衡:对每一对状态都有 。对 求和得
因为 中从 出发的那一行之和为一。因此细致平衡是平稳性的充分条件。它不是平稳性定义的一部分,有些平稳链并不是可逆的。
例如,确定性的有向圈 有均匀的平稳分布,但从零到一有正的流量,而从一到零没有一步流量。它与均匀分布并不满足细致平衡。这个例子把分布的不变性与更强的成对流量对称性区分开来。
度数权重的含义
在无向图中,每条边在每个端点处各贡献一个关联半边。简单随机游走在关联边的副本中进行选择,所以度数较大的顶点按比例获得更多的平稳质量。懒惰性带来的因子 在不同顶点之间转移的细致平衡计算中被约去;它改变游走的速度,但不改变这个平稳分布。
对于有一个中心与 个叶子的星图,中心的度数为 ,每个叶子的度数为一。共有 条边,所以中心的平稳概率为 ,每个叶子的概率为 。这些概率之和为一。只有当所有顶点的度数相等时,把它们视为等可能才是正确的。
定理假设图连通、无自环且至少有两个顶点,从而每个度数都为正,边的选取规则有定义。单顶点图可以单独处理:规定其唯一状态为吸收态,其平稳分布就是该点上的点质量。不连通的图有互不相通的连通分支,可能有多个平稳分布。
整数上的简单游走没有平稳概率分布,因为紧致性已经失效。
通往推广的路径
状态空间为无限时什么不再成立?
整数上的简单游走没有平稳概率分布,因为紧致性已经失效。
存在性通过单纯形的紧致性用到了有限性。在 上,每步以概率 向左或向右走的游走,需要对每个 都有 。于是 是线性的;非负性迫使 ,而总和为一又迫使 ,这是矛盾。这个游走的 Cesàro 平均仍然存在,但它们越来越分散,极限点不是概率分布。因此,无限链需要额外的假设,才能保证平稳分布存在。
对于 与目标 ,取 个区块(向上取整)就足够了。若 ,则一个区块就够。一旦知道所选路径的概率,这就给出了一个明确的、尽管可能偏松的混合时间上界。
参数 是通向 的选定路径的最大长度,并至少取为一。它不必是最小的公共长度。参数 是到达 的实际 步概率的最小值;选定的补齐路径的概率给出它的一个可计算的正下界。不同的 与路径选择会改变所得的数值估计,但不影响收敛证明的有效性。在具体应用中,比较若干这样的选择可以改进所得的界,但不一定能使最终的界对特定的链是精确的。
总结
Cesàro 平均为每个有限链给出平稳分布。不可约性加上一个正的自环,给出固定步数之后的共同终点,从而得到几何衰减的耦合界与唯一性。连通的懒惰无向游走的平稳概率与度数成正比。
练习
快速检查
(为什么交替的两状态链有均匀的平稳分布?)
交换两个相等的概率,再比较。
解答 · 答案
交换两个相等的概率不会改变均匀向量。
快速检查
(三个顶点的路径上的懒惰游走的平稳分布是什么?)
计算路径上各顶点的度数。
解答 · 答案
按路径顺序为 ,因为度数为一、二、一。
快速检查
(为什么公共质量 严格为正?)
它是有限多个正数中的最小值。
解答 · 答案
有限多个状态中的每一个,都有一条补齐到相同长度的、通向 的正概率路径。有限多个正数的最小值为正。
快速检查
(为什么存在性证明使用平均的收敛子列,而不是直接断言 收敛?)
想想交替链。
解答 · 答案
单独的分布可能振荡,交替链就是例子。紧致性保证平均有收敛子列,其望远镜和的极限是平稳的。