动机
离散链记录每次更新后去哪里,却没有记录更新之间停留多久。两个系统可以依次到访完全相同的状态,但在各状态所占的实际时间比例截然不同。连续时间马尔可夫(Markov)链加入依赖状态的停留时钟;只要不同状态的变化快慢有别,这一层便很重要。
例如机器在两种模式间交替。如果离开第一种模式的速率是第二种的九倍,两种模式的到访次数相等,但时间占用比例并不相等。混淆跳链与实际时间链,便会丢失引入时钟所要表达的特征。
本节研究有限或可数空间上的纯跳跃链,再专门研究一步只移至相邻状态的生灭链。无限空间中,有限时间以前可能发生无限次跳跃,因此使用平稳方程之前必须交代非爆炸条件。
定义
定义 3.1.1
(速率、停留时间与嵌入跳链)
可数空间上的保守速率矩阵 满足 时 ,以及
在 的状态 ,先等待速率 的指数时间,再以概率 选择下一个不同状态 。给定所到访的状态序列后,各停留时间独立。若 ,则 吸收。依次到访的状态形成嵌入跳链 。
具体构造可取互相独立的单位速率指数变量 ,以及独立的跳跃目的地抽样。若第 跳后的状态为 ,停留时间为 。令 , 是头 段停留时间之和。在 以前,当 时令 ;遇到吸收状态则停止跳跃。若从每个起点均几乎必然有 ,称过程非爆炸。在证明此性质以前,构造只给出爆炸前的最小过程。
概念视角算法
相互竞争的时钟给出同一跳跃规则
不必先用一个停留时钟再抽取目的地;可以对每个 启动一个速率为 的独立指数时钟,并跳往最先响的时钟。由于 ,第一次响铃时间 几乎必然被达到,而且
因此停留时间是速率为 的指数变量,目的地的分布是 ,两者相互独立,与定义完全一致。无记忆性使所有时钟在跳跃后重新开始。在这一描述中,每个 是某一特定转移的速率。
定义 3.1.2
(生成矩阵与生灭速率)
非爆炸链的转移概率为 。速率矩阵描述短时间极限
在 上,生灭链具有 、(),且 ;其余非对角速率为零。平稳概率分布要求对所有 都有 。
对角元 是非正速率,吸收状态时为零,并非转移概率,其作用是平衡总流出速率。 各行和为零, 及 各行和为一。生灭模型的零状态没有负邻居;在那里加入死亡转移会改变状态空间,破坏原来的边界条件。
定理/命题
定理 3.1.3
(有界速率、均匀化与平稳性)
假设 且 。则链非爆炸, 是随机矩阵,而且
对概率行向量 , 等价于平稳性。有限空间上 ;若链不可约,便有唯一正平稳分布,且 。
对生灭链,平稳方程可以明确求解。
定理 3.1.4
(有界速率下的生灭平衡)
假设所有 均有 ,所有 均有 ,且 。令
存在平稳概率分布,恰好当 。此时唯一分布为 ,满足细致平衡 。若 ,权重不能归一化;单凭此事不能分辨零常返与暂态。
有界速率是此处采用的充分条件,使存在性与平稳性均有完整理由。许多速率无界的实用模型也非爆炸,但须另行证明。在无限空间写出形式上的 解,并不会自动证明非爆炸,也不会自动证明该解是所需过程的平稳分布。
证明思路
证明
(泊松(Poisson)时钟实现这条链)
使用速率 的泊松(Poisson)时钟;每次响起按 更新,容许选回原状态。位于 时,每次响起真正离开的概率为 。截至时间 尚未真正离开的概率是
给定离开后,目的地 的概率为 ,故构造恰有指定的停留时间与目的地。任何有界时段内只有有限次泊松响铃,因此真正跳跃不能爆炸。对响铃次数条件化即得 公式。 的自转移只是虚拟更新,并非原过程额外的真正跳跃。
若 ,则 ,均匀化和式每一项均保持 。反方向在零时刻微分平稳等式,得到 。速率有界时,生成矩阵在可和行向量上是有界算子,因此即使状态可数,也可交换此极限。有限矩阵时同一级数等于 。有限不可约情形选 ,使各状态都有正的虚拟自环。离散链 不可约且非周期,故收敛至唯一平稳分布;泊松计数依概率趋于无限,从而给出连续时间收敛。真正跳跃即使确定性交替,随机停留时间仍使观察时刻不受离散周期阻碍。
证明透视
速率上界在哪里用到
上界 用了三次,每次目的不同。
- 它使 成为随机矩阵,钟响因而可以由真正的离散链实现;虚拟自环吸收剩余速率 。
- 它把非爆炸化为单个泊松过程的性质:真正跳跃是钟响的子集,而钟响在有界区间内有限。
- 它使 成为可和行向量上的有界算子,从而在可数空间上也可以在零点对 求导。
关键一步是稀疏化:几何个数的钟响、每次是速率 的指数等待,加起来是速率 的指数等待。有限收敛的叙述再加一个想法:取 使自环为正, 因而非周期;泊松计数趋于无穷,把离散收敛转移到连续时间。
生灭定理只需要平稳方程及零处的边界。
证明
(每条边上的概率流为零)
生灭链在零状态的方程为 。在内部状态重排平衡方程得
所以跨每条边的概率流相同,边界迫使此常数为零。反复代入便得 。若 ,归一化得到概率向量,再由有界速率均匀化证明平稳。若 ,除非 ,否则不能归一化;但 又迫使所有分量为零。这也证明成功归一化时的唯一性。
第一个定理的收敛叙述除有限性外还需要不可约性。
反例模式
缺乏不可约性的有限链
断言:每条有限链都有唯一平稳分布,且 。取状态 ,,其他非对角速率为零,所以 与 是吸收态。,故 迫使 ,而每个 ()都是平稳的。从状态一出发,链以速率 离开,并各以概率 选择两个吸收态,所以 ,而 、。极限取决于起点。正是不可约性迫使 各行趋向同一个向量。
向前方程、向后方程与可观察量
均匀化还解释转移矩阵所满足的微分方程。对绝对收敛的泊松级数微分,或对有界矩阵指数微分,得到
向前方程 考虑时段末端的可能转移;向后方程 考虑起点附近的首次转移。初始行分布为 时, 满足 ,各坐标平衡流入与流出。把导数设零会得到平稳方程,但它们在上述假设下的充分性,仍来自已建立的过程构造。
有时状态函数比整个分布更易解读。对有界实函数 ,定义
它是位于 时,可观察量的瞬时期望变化率。速率及函数皆有界,保证求和与微分合法,得 。这并非声称个别样本路径有普通导数:纯跳跃路径在跳跃间固定,在跳跃处不连续;导数属于对众多路径的期望。
生灭计数取 ,形式漂移在正状态为 ,在零为 。但此函数无界,不能直接套用有界函数结论;须先局部化或建立所需矩界。检查符号或数值软件方程时,这个细节很实用:漂移公式形式正确,仍可能超出证明假设的适用范围。
例题详解
例题 3.1.5
(两种模式:时钟改变占用比例)
设 、,则
嵌入链确定性交替,平稳分布为 。但两种停留时间的均值是 及 ,所以较慢的第一状态占较多时间。由零开始,令 。向前方程 配合 ,给出 。这验证收敛,也显示嵌入分布有别于实际时间平衡。
例题 3.1.6
(固定速率的单服务器计数)
所有状态以速率 出生;正状态以速率 死亡,零状态不死亡。总速率至多 ,故存在且非爆炸。权重为 、,从而
细致平衡直接由 验证。一般固定出生率 、正状态死亡率 给出 。平稳概率恰在 时存在。两率相等时,常数权重不可和;形式等式不能当作平衡概率。
例题 3.1.7
(各状态速率有限仍会爆炸)
纯生链从零开始,出生率 。每个停留速率皆有限,但相邻独立停留时间满足
交换和与期望由单调收敛定理保证。非负随机变量若期望有限,便几乎必然有限,因此有限随机时间以前已有无限次出生,最小过程几乎必然爆炸。只检查 每行的总离开速率有限,并不能证明非爆炸。相比之下,固定速率泊松纯生过程的停留时间和由强大数定律趋于无限。
常见错误
常见错误
(混淆跳链权重与实际时间权重)
跳链在转移时刻抽样;连续时间平稳分布在一般固定时刻抽样。在不可约且相关归一化常数有限时,平稳跳链权重正比于 ,因为快速状态的到访更频繁。例如 、 时,实际时间平衡为 ;嵌入链仍交替,到访频率相等。把实际时间权重乘以 ,恰得相等跳跃权重。吸收状态没有下一次真正跳跃,须另行处理。
常见错误
(把细致平衡当作平衡的定义)
一般链中,细致平衡比平稳性强。三状态有向环沿正方向各以速率一转移,均匀分布是平稳的,因各状态流入、流出平衡。但逆边速率为零,故不满足边上的细致平衡。生灭模型的细致平衡来自最近邻结构及反射边界,是推导结果,并非通用规则。
常见错误
(以为截断可以创造平衡)
数值截断也会改变边界。在 截断并禁止最后一次出生,会产生有限反射模型。平稳权重只是保留原权重至 ,再用有限和归一化。若无限模型本有平衡且省略尾部很小,可作近似;若原来 发散,有限截断不能替无限模型创造平衡。
总结
速率矩阵指定指数停留时钟与跳跃目的地。有界总速率容许泊松时钟构造,同时证明非爆炸、给出转移半群并证明 的作用。生灭平衡化为逐边零概率流,之后仍须检查可和性。无限状态存在性、实际时间平稳性及跳链平稳性是三项不同检查。
练习
快速检查
(对 、,求实际时间平稳分布、平均停留时间及嵌入平稳分布。)
平衡唯一一条边上的概率流。
解答 · 答案
平衡方程是 ,故分布为 。平均停留时间依次为 、。嵌入链交替,故为 ;把 乘以离开速率 ,也验证了跳跃权重相等。
快速检查
(生灭链对所有 有 ,对 有 。求平稳分布、正状态概率及平均状态。)
权重是公比为 的等比数列。
解答 · 答案
令 ,则 。正状态概率为 ,平均为 。总速率不超过 ,故可以使用有界速率定理。
快速检查
(对 选均匀化速率 。求 、验证行和及平稳分布,并解释自转移为何不改变模型。)
逐个元素计算 。
解答 · 答案
。两行之和都是一;两行都等于 ,故这个向量被保持。选回当前状态的钟响不是真正离开;泊松稀疏化给出离开速率 及 ,因而保持原来的指数停留分布。
练习 3.1.8
(纯生链速率为 。不求爆炸时刻的分布,证明从零出发会爆炸。)
核心证明
解答(3)
- 1
计算期望停留时间
从零出发,第 次停留时间是均值为 的指数变量。
- 2
把期望相加
关键一步
。
依据: 单调收敛定理适用于非负部分和 。
- 3
得出爆炸
∎期望有限的非负随机变量几乎必然有限,所以 几乎必然成立,有限时间前已发生无限次出生。无须知道 的密度。