动机
马尔可夫(Markov)链记录逐步变化的状态,例如小型队列的待处理任务数、图上的位置,或有限状态控制器的模式。其核心是条件独立性:知道现在状态后,已记录的过去不再提供下一步的额外信息。因此状态必须包含足够信息;若控制器带有隐藏计时器,只记录可见模式而省略计时器,便可能失去马尔可夫性。
长期行为有几个不同问题:离开某状态后是否会返回?若必定返回,平均等多久?是否存在经一次转移仍保持不变的概率分布?常返性、正常返性及平稳性将这些问题连接起来,但不能互换。即使有限链有平稳分布,从固定起点出发的分布仍可永远振荡。
本节由转移矩阵及首步条件化出发,研究返回概率及有限状态平衡,再用可数状态的反例指出有限性的重要。全节以行向量表示分布。
定义
定义 2.1.1
(时间齐次马尔可夫链)
在有限或可数状态空间 上,若对每个正概率的历史都有
则 是转移矩阵为 的时间齐次马尔可夫链。各 ,且 。 步转移矩阵为 ,故初始分布 在第 步变为 。
对中间状态条件化可得 。可数空间中各项非负,没有条件收敛的抵消问题。任意随机矩阵与初始分布均可通过逐次抽取下一状态构造一条链;等价地,其有限历史概率为 ,彼此相容。
定义 2.1.2
(击中、返回与互通)
对 ,令 。对单一状态 ,首次返回为 ,空集的下确界定为 。若 ,称 常返;否则称暂态。常返状态若 ,称正常返;若期望无限,称零常返。
若某个 使 ,称 可由 到达。彼此可到达的状态称互通;所有状态互通的链称不可约。互通类若不能经一步转移离开,称闭类。对至少在某个时刻有正返回概率的状态, 的周期是集合 的最大公因数。若此返回时刻集合为空,本节不赋予周期。有可能返回的不可约链,其状态有相同周期;周期为一称非周期。
定义 2.1.3
(平稳分布)
概率行向量 若满足 ,称平稳分布。由 开始,各时刻的一维分布相同。由状态 出发的极限分布则要求 对各 收敛至指定概率向量,须另行证明其存在。
定理/命题
定理 2.1.4
(以期望到访次数判断常返性)
令 。则
因此,常返等价于返回概率级数发散,并非等价于平均返回时间无限。
定理 2.1.5
(有限不可约链的平衡与收敛)
有限不可约链有唯一平稳概率向量 ,各 ;所有状态正常返,且 。若再假设非周期,则对所有 有 。即使有周期,平均转移概率仍满足
不可约是此处唯一性的充分条件,并非必要条件:可约链若只有一个闭的不可约类,仍可有集中于该类的唯一平稳分布。在可数无限不可约链中,平稳概率分布存在恰好等价于正常返,仅常返并不足够。以下解释有限情形;可数延伸另需可积性论证,此处不作完整证明。
概念视角结构
平稳性就是每个割集上的流量平衡
对概率向量 ,方程 等价于概率流在每个割集上平衡:对每个 ,
把 对 求和,再消去留在 内的流量,即得此恒等式;取 则重新得到第 个方程。选好割集可以缩短计算:对只在相邻整数之间移动的链, 与其余状态之间的割集直接给出 。
证明思路
两条定理都建立在同一个工具上:每次到访固定状态,链便重新开始,路径因而分拆成相互独立的游程。
证明
(在返回时重新开始以计算到访次数)
每次返回 ,链都可从 重新开始。击中时刻的马尔可夫性可将“该时刻等于整数 ”的事件逐一分开,再用普通马尔可夫性证明。因此,包括零时刻在内,至少到访 次的概率为 。尾和为 ;当 时它等于 ,当 时为 。另一方面,单调收敛定理允许交换非负到访和与期望,得到第一定理的概率级数。
证明
(回返循环、最大值原理与收缩)
正常返。 有限不可约链中,固定目标 。每个状态都有一条正概率路径通往 。状态有限,故可选共同路径长上界 ,以及各路径概率的共同正下界 。尚未击中时,往后 步内击中的条件概率至少为 ,所以击中时间尾部按长度 的区段受几何级数控制。首步后同样论证,便得 。有限性正用于取得共同正下界。
存在性。 在两次到访 之间,计算各状态 的期望到访次数,再除以 ,得到概率向量 。一个回返循环的起点与终点都是 ,因此各状态的期望流入等于期望流出,得 。终端返回以前恰好到访 一次,故 。
唯一性与正性。 若 ,在 取最大值的状态,只能转往同样取最大值的状态。不可约性将此值传遍所有状态,所以 的右零空间只包含常数向量。有限维矩阵的行秩等于列秩,故左零空间也是一维;归一化后平稳向量唯一。某个正分量可沿正概率路径到达任何状态,由平稳性可知所有分量皆正。从任何其他状态 重做回返循环构造,得到第 个分量为 的平稳向量;由唯一性它就是 ,所以对每个 都有 。
收敛。 有限不可约非周期链存在某个 ,使 各分量皆正。理由是返回路径长的最大公因数为一,串接路径可形成所有足够大的长度,再接上状态间的路径。令 、。每行均包含共同质量 乘均匀分布;移除共同部分,便知乘以 将两个概率分布的全变差距离缩小至至多 倍。重复后趋于 ,其余步数不增加距离。有周期时,随机矩阵的幂仍有界;Cesàro 平均消去单位圆上除 外的特征值,而单特征值 给出同一平稳极限。这证明平均收敛,并未宣称普通收敛。
证明透视
有限性、不可约性与非周期性在哪里用到
平衡定理的证明分四部分,每个假设都在可辨认的步骤中使用。
- 有限性用于共同界 与 ,由此得 。没有它,每个状态仍可到达 ,等待时间却可能有无限均值,常见错误一节的对称游走正是如此。它也再用于秩相等,以及在 有限时得到 。
- 不可约性用了三次:从每个状态到达 、把调和函数 的最大值传遍各状态,以及使 的每个分量为正。
- 非周期性只在最后一部分使用,用来找到严格正的幂 。没有它,只剩 Cesàro 平均的结论。
关键一步是回返循环构造。由 回到 的循环起点与终点相同,所以各状态的期望流入与期望流出相抵, 是由计数而非解方程得到的。除以 需要 ,所以要先证明正常返。论证以唯一性收尾:从每个状态构造的循环向量都是同一个 ,于是单一状态的 变成对所有状态成立的 。
击中概率为何选最小解
首步方程无须预先假设最终击中,而构造本身就指出哪一个解才是击中概率。
命题 2.1.6
(击中概率是最小解)
设 ,。则对 有 ,对 有 。若 满足同样的方程,则对每个 都有 。
证明
(有限时域递增至击中概率)
令 为截至第 步已到达 的概率,包括零时刻,故 。在 上保持为一,在外部则更新为
事件随时域递增,所以概率递增至最终击中概率;在非负和式取极限便得调和方程。若 是另一个非负解且边界值为一,归纳给出各时域均有 ,故极限 。这证明最小性,并非任意加给代数系统的规则。
最小性并非技术细节:在无限空间中,单靠方程可以有许多解。
反例模式
单靠边界值不能决定击中概率
断言:击中概率是首步方程在 上取一、取值于 的唯一解。考虑非负整数上每步由 移至 的确定性链,并取 。从正整数出发永不到零,故该处的击中概率为零。然而对每个常数 ,令 、对 令 ,则对 有 ,这正是首步方程。所以有界方程组有无限多解。修正后的叙述就是上述命题:击中概率是最小非负解,这里即 ,而有限时域构造正好选出它。
期望击中时间也可安全地由有限时域生存概率相加:,容许值为无限。因此代数求出的均值候选,仍须用尾界或其他理由验证有限性。无限空间中,各状态都有路径通往目标,并不提供等待时间的共同上界,尤其要小心。
例题详解
例题 2.1.7
(两个模式的真正极限分布)
设
平稳方程给出 ,故 。两状态互通且各有自环,因此非周期。令 ,则 ,故 。这直接证明任意初始分布均收敛。返回状态 的平均时间是 步;一步自环也算返回,所以平均可以小于二。
例题 2.1.8
(有平稳分布却不收敛)
确定性交替链的矩阵是 ,平稳分布为 。从状态 出发,偶数时刻在状态 的概率为 ,奇数时刻为 ,故没有普通极限,周期为 。时间平均概率却趋于 。若以平稳分布开始,各时刻边际概率都是 ,但相邻状态仍高度依赖。
例题 2.1.9
(首步方程与可约链的唯一平衡)
在 上令 吸收;由 或 以概率 到 ,以概率 到另一非零状态。对 ,首步条件化给出
所以 。 时有 ,独立验证期望有限。非零状态的平稳方程是 、,迫使两者为零。因此可约链仍有唯一平稳分布 。非零状态暂态;吸收状态正常返,返回时间为一。
常见错误
常见错误
(把均值方程当作均值有限的证明)
在 外写下 ,并不证明 有限:若均值无限,方程只以空洞的 形式成立。尾界才补上所欠的理由,例如第三个例题中的 。
常见错误
(把平稳分布读成极限分布)
存在满足 的 ,并不表示从固定起点出发会收敛。交替链有 ,但 在 与 之间交替。普通收敛除有限不可约外还需要非周期性。
在可数无限空间中,有限定理的另一个假设会悄然失效,下例显示失去的是什么。
反例模式
单有常返不足以给出平稳概率
断言:不可约常返链必有平稳概率分布。取整数上的简单对称随机游走。它常返:,级数发散,所以第一定理给出 。它保持计数测度,这是总质量无限的不变测度。但平稳性要求 ,所以 是 的仿射函数;整条整数线上非负、非零的仿射序列不可能可和。因此没有平稳概率,游走是零常返。修正后的叙述要求正常返:不可约链有平稳概率恰好等价于正常返,而有限性保证了这一点。
总结
转移矩阵幂描述有限时刻分布,首步方程描述击中问题,回返循环解释平衡。有限不可约性保证正常返及唯一正平稳分布;非周期性再保证从各起点出发的收敛。无限链还须检查可和性及返回时间有限性,调和方程则须配合最小解条件。
练习
快速检查
(求 的平稳分布与平均返回时间。由各起点出发是否收敛?)
用两个状态之间的平衡方程。
解答 · 答案
平衡给出 ,故 ,平均返回时间为 及 。交叉转移皆正,所以不可约;对角皆正,所以非周期,从而收敛。
快速检查
(状态 、 吸收;由 、 各以概率 移向相邻整数。求由各内部状态出发先到 而非 的概率,以及期望吸收时间。)
写出首步方程,再检查有限性。
解答
设 。由 、 得 。均值满足 、、,故 。任一内部状态下一步吸收的概率都是 ,生存尾为 ,故均值确实有限。
快速检查
(给出有多个平稳分布的可约链,列出全部平稳分布,并解释为何不违反不可约定理。)
两个吸收状态便足够。
解答 · 答案
两状态上取 。两者皆吸收,每个 ,,都是平稳分布。它们不互通,不符合定理的不可约假设。
快速检查
(若状态的首次返回概率 ,求包括零时刻在内的期望总到访次数,以及至少到访三次的概率。)
每次返回都是成功概率为 的新试验。
解答
期望总次数为 。至少三次到访需要两次成功返回,概率为 。此状态仍属暂态;期望总到访有限,完全可以同时有不小的多次返回概率。