为什么使用有时什么也不做的时钟?
生成矩阵告诉我们链离开各状态有多快;转移矩阵告诉我们经过指定时间后它在哪里。这是两个不同问题。只知道下一次跳跃的目的地,并没有计入观察前完全没有跳跃、已经跳了数次,或离开后又返回原状态的可能性。
前面的生成矩阵笔记已介绍均匀化。本篇把它展开为精确的构造,以及带有余项保证的实际计算。一个共同时钟在所有状态都会响;部分钟响只是保留原状态。这些看似多余的操作,把不同的停留速率换成一个独立泊松(Poisson)计数。给定该计数后,问题就变成普通随机矩阵的幂次。
本篇一律考虑有限状态空间。因此所有离开速率有有限共同上界,矩阵运算都是有限维的,构造的路径也存在于每个有限时刻。一般无界速率的存在性,以及嵌入链占用问题,留在前面的笔记处理。
有限生成矩阵与独立构造材料
设 S={1,…,d},其中 d≥1。保守生成矩阵是满足下列条件的实矩阵:
qij≥0(i=j),qi:=j=i∑qij,qii=−qi.
因此 Q1=0,其中 1 是全为一的列向量。本篇以行向量表示概率分布。选取 λ>0 且 λ≥imaxqi,定义
K=I+Q/λ,Kii=1−qi/λ,Kij=qij/λ(i=j).
K 的每个元素非负,每行总和是一。Q 的非对角元素具有“每单位时间”的量纲;K 的元素则是概率。
若取 λ<imaxqi,对角元素 1−qi/λ 便是负数,K 不是转移矩阵,无法用来作这个概率构造。代数恒等式 etQ=e−λteλtK 仍然成立,但各项失去概率意义;泊松尾项保证之后的反例说明了其后果。
取转移矩阵为 K 的离散马尔可夫(Markov)链 Y0,Y1,…,以及速率为 λ、与整条离散链独立的泊松过程 N(t)。初始分布为 α 时,令 Y0 服从 α 并与时钟独立;Y 每次转移都使用新的独立随机选择。设
X(t)=YN(t).
独立性不可省略。一个随机下标只有泊松边际分布并不足够:若下标依赖 Y 未来的转移,给定下标就可能改变链的分布。我们先建立互相独立的材料,再将它们组合。
零速率情况很直接。若希望取 λ=0,条件 λ≥imaxqi 迫使 Q=0。直接定义 X(t)=X(0) 及 P(t)=I 即可,既不用除以零,也不用替 Q/0 定义意义。对同一零生成矩阵,也可以任取正的 λ,此时 K=I,所有钟响都是虚拟更新。
从虚拟事件到真正停留时间
设 X(0)=i 且 qi>0,并令 Hi=inf{t≥0:X(t)=i} 为首次真正离开的时刻。真正离开前,每次钟响以概率 1−qi/λ 保留状态 i。给定 N(t)=n,直到时间 t 仍未离开的概率为 (1−qi/λ)n。取平均得到
iPr(Hi>t)=n=0∑∞e−λtn!(λt)n(1−qi/λ)n=e−qit.
真正停留时间是速率 qi 的指数变量,两次钟响之间的等待则是速率 λ 的指数变量。两者不一定是同一段随机时间,因为第一次钟响可能只是虚拟更新。
对不同状态 j,把离开前可能出现的虚拟事件次数相加,得到
iPr(下个不同状态=j)=n=0∑∞(1−qi/λ)nλqij=qiqij.
目的地也与离开时间独立。不能只从两个边际分布推断这一点。令 G 是首次成功离开的钟响编号,则 G=n 且目的地为 j 的联合概率是
(1−qi/λ)n−1λqij=Pr(G=n)qiqij,n≥1.
因此目的地与 G 独立,也与独立的时钟等待时间独立;真正停留时间是前 G 段时钟等待的总和。离开时,新的转移选择及新的指数时钟等待使论证重新开始。因此,给定真正到访的状态序列,各次停留时间具有通常指数构造所要求的条件独立性。若 qi=0,整行没有向外速率,Kii=1,状态 i 就是吸收状态。
泊松过程在任意有界区间内几乎必然只有有限次事件,真正跳跃次数也因此有限。这直接证明非爆炸性。它没有替离开速率无界的可数生成矩阵证明任何结论;那种矩阵可能根本没有有限的共同 λ。
转移分布与半群
对上述独立构造及 λ>0,
P(t)=e−λtn=0∑∞n!(λt)nKn=etQ,t≥0.这些矩阵都是随机矩阵,满足 P(0)=I、P(s+t)=P(s)P(t),以及
P′(t)=P(t)Q=QP(t).对概率行向量 π,下列三条件等价:πQ=0、πK=π,以及对每个 t≥0 都有 πP(t)=π。若 Q=0,所有概率分布都平稳,包括直接使用零时钟的构造。
给定 N(t)=n,独立性使 Yn 的分布保持不变,因此从 Y0 出发的转移矩阵是 Kn。这证明泊松混合公式。每项非负,每行总和等于相应泊松权重;整个级数的行总和是一。
构造具有马尔可夫性:时间 s 之后,时钟有独立增量,尚未使用的转移选择也是新的。令 Gs 包含截至 s 的时钟历史及 Y0,…,YN(s)。给定这个较大历史,未来转移只通过 X(s) 依赖过去,所以 E[f(X(s+t))∣Gs]=(P(t)f)(X(s))。自然历史 FsX=σ(X(r):0≤r≤s) 包含于 Gs。条件期望的塔式性质因此给出以 FsX 条件化的同一公式,这才是 X 本身所需的马尔可夫性。
半群恒等式还有一个有启发性的直接证明。将两个级数相乘,按 m+n=r 分组,再用二项式定理:
P(s)P(t)=e−λ(s+t)r=0∑∞λrKrm=0∑rm!(r−m)!smtr−m=e−λ(s+t)r=0∑∞r![λ(s+t)]rKr=P(s+t).非负元素容许重新分组;在任何有限矩阵范数下也有绝对收敛。由 Q=λ(K−I),且 K 与 I 可交换,收敛的矩阵指数级数给出 etQ=e−λteλtK。这证明第二个公式,并容许在有界时间区间逐项微分。特别地,P′(0)=Q。
最后,πQ=0 等价于 πK=π。后者推出每个 n 都有 πKn=π,所以混合分布保留 π。反过来,将 πP(t)=π 在零点微分,便得 πQ=0。有限维性保证这个微分合法。上述等价性完全不需要不可约假设。
证明透视
每个假设负责哪一步?
证明分四步,每一步消耗不同的假设。
- 混合公式以 N(t)=n 条件化。这只因时钟与整条链 Y 独立才合法;条件 λ≥imaxqi 使每个 Kn 都是转移矩阵,因此每一项都是行和等于相应泊松权重的非负矩阵。
- 马尔可夫性先对包含时钟及离散路径的较大历史 Gs 证明。微妙之处在塔性质:右边 (P(t)f)(X(s)) 已关于 FsX 可测,所以给定 Gs 成立的公式,给定较小历史 FsX 也成立。
- 半群律及 etQ=e−λteλtK 是矩阵代数;非负性允许重新分组,K 与 I 可交换则允许拆开指数。
- 有限维性允许在零点求导,把 πP(t)=π 变成 πQ=0。
论证得以闭合,是因为构造已经定义了一个概率过程;对无界无限状态模型,只写矩阵幂次并不能提供同样的构造。
任选时钟速率为何不改变过程?
不同的容许正值 λ 给出不同的 K,也产生不同数目的虚拟事件,但它们都给出同一个 etQ。它们亦给出前面已推导的同一组真正指数停留时间及目的地分布。增大 λ 只增加计算工作,不会增加模型本身的转移。
固定时刻的转移核也决定长期行为;在有限状态下答案是完整的。
每个有限保守生成矩阵都有平稳概率。若 Q 不可约,则对每个 u>0,P(u) 的所有元素为正,平稳概率 π 唯一,并且对每个初始概率 α 都有 αP(t)→π。
存在性不需要不可约。一个有限维证明从平均 T−1∫0TαP(s)ds 出发。概率单纯形紧致,所以存在收敛子序列。将平均乘以 P(u),只是平移积分区间;其 ℓ1 差不超过 2u/T。因此每个子序列极限对任意 u≥0 都平稳。
要证唯一性,现在假设不可约并固定 u>0。每对 i=j 之间都有一条有限的正速率路径,故 K 的某个幂在 (i,j) 位置为正,而它在时间 u 的泊松权重也为正。对 i=j,零次幂 K0=I 已经贡献正对角元素。因此 P(u) 的所有元素为正。若 η=i,jminPij(u) 及 δ=dη,则 0<δ≤1。当 δ<1,可写 P(u)=δ1v+(1−δ)B,其中 v 是均匀分布,B 是随机矩阵。这把概率分布之差的 ℓ1 范数收缩至不超过原来的 1−δ 倍。若 δ=1,所有行已等于 v。两个平稳分布因此必须相同。相同收缩论证证明在 u 的整数倍时刻收敛;不足 u 的剩余时间不会增加与平稳分布的距离。即使真正跳跃交替发生,固定时刻概率仍可以收敛。
证明透视
存在性与唯一性的两个不同理由
存在性与唯一性依靠不同的性质。存在性只用到有限性:时间平均位于紧致单纯形内,而平移窗口的估计 2u/T 使每个子序列极限对每个 P(u) 都不变。唯一性需要不可约,它通过 P(u) 每个元素皆正而起作用;对角元素自然为正,因为有零事件项 e−λuI。关键一步是分解 P(u)=δ1v+(1−δ)B。对分布 α,β 有 (α−β)1=0,所以共同部分消失,每经过长度 u 的一步,差只剩下 1−δ 倍。
完整的二状态计算
本例使用状态 0,1,速率为 q01=1 及 q10=3。取 λ=4,则
Q=(−131−3),K=(3/43/41/41/4)=:Π.Π 每行都是 π=(3/4,1/4),所以 Π2=Π。但零次幂仍是 I,代表没有钟响。将其余权重相加,得到完整转移矩阵:
P(t)=e−4tI+(1−e−4t)Π=(3/4+e−4t/43(1−e−4t)/4(1−e−4t)/41/4+3e−4t/4).在 t=(log2)/4,矩阵是 (7/83/81/85/8)。在 t=1/2,第一行约为 (0.783833821,0.216166179)。矩阵从 I 开始,每行总和是一,在零点的导数是 Q,各行则趋向 π。这些是不同方面的核对。
从零开始,到时间 t 完全没有真正离开的概率是 e−t;完全没有钟响的概率是 e−4t。两者都不是 P00(t),因为终点是零也可能发生于离开再返回之后。真正嵌入链的矩阵为 R=(0110),平稳到访分布是 (1/2,1/2);均匀化链 K 的不变分布却是 (3/4,1/4)。典型到访对两个状态给予相同权重;典型时刻则较常落在停留较久的零状态。这个有限例子分清 R、K 与 P(t),无须重做一般占用转换定理。
任何容许的时钟速率都可以使用,较快的时钟只是增加虚拟事件。
对同一生成矩阵取 λ=8,则
K=I+Q/8=(7/83/81/85/8)=Π+21(I−Π);由 Π2=Π 及 Π(I−Π)=0 得 Kn=Π+2−n(I−Π)。泊松混合给出系数
e−8tn∑(8t)n2−n/n!=e−8te4t=e−4t,所以仍有 P(t)=Π+e−4t(I−Π)。平稳时时钟以速率 8 响,真正跳跃的速率却是 3/2,只有 3/16 的钟响改变状态;λ=4 时这一比例是 3/8。
概念视角结构
三种不同计数
泊松计数记录潜在更新,真正跳跃计数记录实际状态改变,固定时刻观察则只记录当前状态。在二状态例子中,第一种计数的均值是 4t,与初始分布无关。在平稳状态下,第二种计数的均值是 [(3/4)1+(1/4)3]t=3t/2。第三种观察在每个时刻的分布都是 (3/4,1/4)。把三者都当成同一种“转移”,就会丢失均匀化本来要保留的时钟信息。
带严格余项的有限计算
对 x=λt 及非负整数 m,定义
wn=e−xn!xn,Pm(t)=n=0∑mwnKn,sm=n=0∑mwn,εm=1−sm.
在 x=0 时约定 w0=1,便精确得到单位矩阵。对 x>0,省略的权重等于尾概率 εm=Pr(Poisson(x)>m)。Pm 每行总和是 sm 而非一。它是次随机的下近似,并不是精确的随机转移矩阵。
逐元素有 0≤P(t)−Pm(t),且差矩阵每行总和为 εm。因此,对任意初始概率 α 及集合 A⊆S,
(αPm(t))(A)≤αPr(X(t)∈A)≤(αPm(t))(A)+εm.对任何满足 ∣f(i)∣≤M 的实值观察量,
∣αP(t)f−αPm(t)f∣≤Mεm.这是精确算术下的截断界;浮点舍入误差需要另外控制。
省略各项都是非负矩阵,行总和各为 wn。把它们相加就得到逐元素及行总和的结论。集合截取的省略质量介于零与全部质量之间。对观察量,取绝对值后以 M 控制每个被省略的 f 值即可。
省略项的非负性,正是条件 λ≥imaxqi 发挥作用之处。
反例模式
慢时钟破坏下界
断言:既然对每个 λ>0 都有 etQ=e−λtn∑(λt)nKn/n!,误差保证对任何时钟速率都成立。取例题的二状态生成矩阵及 λ=2<q1=3,则 K=I+Q/2=(1/23/21/2−1/2) 有负元素,且 K2=I。在 t=(log2)/2,只保留零次项的截断是 P0(t)=e−2tI=I/2,但 P11(t)=1/4+3e−4t/4=7/16<1/2。所以 P(t)−P0(t) 有负元素,P0 不是下界。条件 λ≥imaxqi 使每个 Kn 非负,证明用的正是这一点。
若 sm>0,也可以将结果归一化为 Pm/sm。对初始分布 α,这是给定 N(t)≤m 的条件终点分布;它一般不再是逐元素下界。把真实分布写成这个条件分布与给定 N(t)>m 的条件分布的混合,可证归一化答案与真实分布的全变差距离不超过 εm。此处全变差定义为 Asup∣μ(A)−ν(A)∣。
若只计算一个初始分布,不需要形成所有完整矩阵幂。从 v0=α 出发,更新 vn+1=vnK,并累加 n=0∑mwnvn。精确恒等式 w0=e−x 及 wn+1=wnx/(n+1) 对所有有限 x≥0 都成立;对大小适中的 x,这个向前递推在数值上方便。若 x 很大,从零开始可能产生下溢;选用数值稳定的权重算法,是精确算术误差保证之外的数值分析工作。
利用比值可以取得明确尾界。若 x<m+2,第一个省略权重之后的每个比值都不超过 x/(m+2),所以
εm≤1−x/(m+2)e−xxm+1/(m+1)!.
例题 3.6.6
(为 t=1/2 的二状态分布给出误差保证)
取 λ=4、t=1/2,则 x=2。m=8 时条件 x<m+2 成立,且
ε8≤1−2/10e−229/9!=567e−2<0.000239.由于 n≥1 时 Kn=Π,零到一的近似概率是 (s8−e−2)/4≈0.216107,精确值是 (1−e−2)/4≈0.216166。实际误差为 ε8/4≈0.0000594,一般保证则容许整个 ε8。有效的上界不必恰好等于误差。
习题
练习 3.6.7
(对上述二状态生成矩阵取 λ=3。求 K,验证其不变分布,并由其幂次恢复 P(t)。为什么 K 有负特征值也没有问题?)
核心
解答(3)
1写出 K 并检验不变性
K=I+Q/3=(2/311/30),直接相乘得 (3/4,1/4)K=(3/4,1/4)。
2把 K 拆成互补投影
K=Π−31(I−Π),Kn=Π+(−1/3)n(I−Π),n≥0. 依据: Π2=Π 且 Π(I−Π)=0。
3对泊松计数取平均
混合把第二个系数化成 e−3texp(−t)=e−4t,所以仍有 P(t)=Π+e−4t(I−Π)。随机矩阵要求元素非负,而不是特征值非负;离散幂中的交替因子被随机时钟平均掉了。
练习 3.6.8
(设 Q=(−2020) 且 λ=2。求 P(t)、所有平稳概率,以及从状态零出发在 t=(log2)/2 的分布。若所有速率为零,答案如何改变?)
基础
解答(3)
1计算 K 的幂
K=(0011) 在 n≥1 时满足 Kn=K,所以
P(t)=e−2tI+(1−e−2t)K=(e−2t01−e−2t1). 2求平稳分布并代入时刻
πQ=0 迫使 π0=0,故 (0,1) 是唯一平稳分布。在 t=(log2)/2,e−2t=1/2,从零出发的分布是 (1/2,1/2),并不平稳。
3处理零生成矩阵
若 Q=0,两个状态都是吸收态,P(t)=I,所有概率分布都平稳;可以直接使用零时钟,或使用正时钟及 K=I。
练习 3.6.9
(证明尾项比值界。对 x=2,求使该界保证 εm<10−3 的最小 m,并判断把 Pm 换成 Pm/sm 后是否仍保留逐元素下界性质。)
核心
解答(3)
1与几何级数比较
关键一步
省略的总和至多是 wm+1k≥0∑(x/(m+2))k,即所述上界。
依据: 对 n≥m+1,wn+1/wn=x/(n+1)≤x/(m+2)<1。
2代入 x=2
m=7 时上界为 e−2(28/8!)⋅79≈0.00110,仍太大;m=8 时为 e−2/567<0.000239。所以 m=8 是最小的保证选择。
3检验归一化截断
归一化不保留下界。在二状态例子中,其零到零元素是 3/4+e−2/(4s8);因 s8<1,它大于真实值 3/4+e−2/4。条件混合论证仍保证全变差误差界。
练习 3.6.10
(在二状态例子中从零出发,求时间 t 前真正跳跃次数的期望,并与潜在更新次数的期望比较。解释只计算零到一转移为何得到不同答案。)
综合
解答(3)
1对离开速率积分
真正跳跃次数的期望为 E0J(t)=∫0t[p0(s)⋅1+p1(s)⋅3]ds。
依据: 从状态 i 开始、长度为 h 的区间中,恰有一次钟响贡献的真正跳跃期望为 qihe−4h,两次或以上钟响的贡献至多 4h(1−e−4h)=O(h2);对 [0,t] 的分割求和再加细,便得速率积分。
2代入转移分布
由 p0(s)=3/4+e−4s/4,
E0J(t)=∫0t[3/2−e−4s/2]ds=23t−81−e−4t. 3比较其他计数
潜在更新的均值为 4t,包括被拒绝的自更新。只计零到一转移的期望是 ∫0tp0(s)ds=43t+(1−e−4t)/16,因为它省略了所有一到零的跳跃。只要清楚说明所计的事件,每种计数都有用途。