动机
如果目前状态保留了决定下一次转移所需的信息,便较容易研究重复随机变化。本节建立有限状态模型,分别研究路径、首次到达与长期分布。
定义
状态保留所需信息
随机游走记录粒子随机移动后的连续位置。有限马尔可夫(Markov)链推广此想法:状态可以是任何足以决定下一状态分布的摘要。状态不必编码全部历史,但模型必须有理由舍去其余历史。
设 X0,X1,… 取值于有限集合 S。若每当条件事件概率为正时,
P(Xn+1=j∣X0=i0,…,Xn=i)=P(Xn+1=j∣Xn=i)=pij,且右边与 n 无关,过程便是时间齐次马尔可夫链。转移矩阵 P=(pij) 的元素非负,每行之和为一。
本文用行向量,初始分布 μ0 经一步后为 μ1=μ0P。
马尔可夫性是条件陈述,不是说连续状态独立。知道目前状态通常会大幅改变下一状态的概率。反过来,如果状态遗漏了持续存在的机器模式等重要隐藏变量,过程便可能不是马尔可夫链。
证明思路
以下路径计算结合乘法公式与马尔可夫性;到达概率则按第一步分类。两种方法均不假设相邻状态独立。
路径与转移矩阵的幂
对初始概率为 μ0(i0) 的路径 i0,i1,…,in,由乘法公式与马尔可夫性,其概率为
P(X0=i0,…,Xn=in)=μ0(i0)pi0i1⋯pin−1in.
对中间状态求和得到 Chapman–Kolmogorov 公式:从 i 经 n 步到 j 的概率是 (Pn)ij。两步时它等于 k∑pikpkj;每一项代表一条经 k 的互斥路径。因此 μn=μ0Pn。
在 0,1,2 三个状态上,粒子从 0 或 2 必定走到 1;从 1 则以各 1/2 概率走到两个邻点。从 1 出发两步后回到 1 的概率是 (1/2)(1)+(1/2)(1)=1。从 0 出发两步后到达 2 的概率为 1⋅(1/2)=1/2。列出路径可避免把互斥选项的概率错误相乘。
到达边界
考虑 {0,1,…,N} 上的游走,端点 0,N 为吸收状态。内点每一步独立地以概率 p 向右、q=1−p 向左,假设 0<p<1。令 hi 为从 i 出发先到 N 而非 0 的概率。
对 0<p<1 的这个游走,以概率一在 0 或 N 被吸收。从 i 出发先到 N 而非 0 的概率,在 p=q=1/2 时为 hi=i/N;在 p=q 时为
hi=1−rN1−ri,r=pq.
吸收:从内点 i 出发,接下来 N−i≤N 步全部向右便到达 N,所以 N 步内被吸收的概率至少为 δ=min(p,q)N>0。在时刻 N,2N,… 应用马尔可夫性,超过 kN 步仍未吸收的概率至多 (1−δ)k,极限为零。
方程:按第一步分类,并在时刻一应用马尔可夫性,得
h0=0,hN=1,hi=phi+1+qhi−1(1≤i<N).求解:因 hi=phi+qhi,递推式可写成 p(hi+1−hi)=q(hi−hi−1),所以 hi+1−hi=ri(h1−h0)=rih1,且 hi=h1k=0∑i−1rk。若 r=1,此式为 ih1,由 hN=1 得 h1=1/N,故 hi=i/N。若 r=1,此式为 h1(1−ri)/(1−r),由 hN=1 得 h1=(1−r)/(1−rN),即得上式。方程组的每个解都被迫成为这个形式,所以方程组恰有一个解,而到达概率就是这个解。
证明透视
一个证明里的三项工作
证明做了三件独立的事。第一步分类给出方程;它只用到时刻一的马尔可夫性,在任何状态空间都成立。关键一步是代数的:把递推式读成 hi+1−hi=r(hi−hi−1),二阶方程便化为只有一个未知数 h1 的等比数列。第二个边界值随即确定 h1;当 p=q 时 r=1,所以 1−rN=0。假设 0<p<1 用了两次:p>0 使 r 有定义,min(p,q)>0 使 δ 为正。吸收保证 1−hi 正是先到 0 的概率;同一几何存活上界在下文计算期望持续时间时再次使用。在无限状态空间上没有第二个边界值,递推式留下一族单参数的解,需要额外论证才能选出所求概率。
设 N=3、p=2/3、q=1/3,从 1 出发。r=1/2,故先到 3 的概率是 (1−1/2)/(1−1/8)=4/7。它大于公平游走的 1/3,但小于一,因为第一步向左便结束实验。
平稳与长期行为
若概率行向量 π 满足 πP=π,称它为平稳分布。
由归纳法,初始分布为 π 时,每个时刻的边际分布都是 π。这不表示每条路径不变,也不表示其他初始分布必定收敛至 π。
概念视角代数
平稳分布是左特征向量
方程 πP=π 表示 πT 属于 PT−I 的零空间:平稳分布是 P 对特征值 1 的左特征向量,并缩放至元素非负且总和为一。非零的左特征向量必定存在,因为 P 每行之和为一,所以 P1=1、det(P−I)=0,于是 PT−I 也奇异。这个观点也解释一个实用步骤:把 πP=π 的 ∣S∣ 条方程全部相加,得到恒等式 i∑πi=i∑πi,所以方程线性相关,可以把其中一条换成 j∑πj=1。单靠线性代数不能证明存在元素非负的特征向量;对不可约链,下面的定理提供这一点。
不可约是指任意一个状态都可在某个正步数到达任意另一状态。若链亦非周期,则对每个初始分布 μ0,有 μ0Pn→π。这里陈述这些标准结果但不证明。不可约是唯一性的充分条件,并非必要条件;上述收敛还需非周期性。
两状态确定交替的链,其 P 的两行是 (0,1) 和 (1,0)。方程 πP=π 要求两个分量相等,唯一平稳分布是 (1/2,1/2)。若从状态零出发,分布却在 (1,0) 和 (0,1) 之间交替,永不收敛。此链不可约,但周期为二。
期望吸收时间
最终结果的概率并不说明游走需时多久。对上述公平吸收游走,令 ti 为从 i 出发至吸收所需步数的期望,则 t0=tN=0,按第一步分类得 ti=1+(ti−1+ti+1)/2。额外的一计算第一步,即使它直接进入边界也要计算。
端点 0,N 吸收的公平最近邻游走,从 i 出发的期望吸收时间为 ti=i(N−i)。
要使递推式成立,吸收时间 T 须有有限期望:上一个证明的几何存活上界给出 E[T]=n≥0∑P(T>n)≤Nk≥0∑(1−δ)k<∞。递推式等价于 ti+1−2ti+ti−1=−2。对 ti=Ni−i2,线性部分的二阶差分为零,而 −i2 的二阶差分为 −((i+1)2−2i2+(i−1)2)=−2;并且 t0=tN=0。若有两个解,其差的二阶差分为零且两端值为零;该差是线性函数,因而恒为零。所以 i(N−i) 是唯一解。
边界为 0,6 时,从 3 出发的公平游走,其期望吸收时间为 3(6−3)=9 步;从 1 出发则为五步。这是平均值而非确定的停时。例如从 3 出发可连续向右三步到达 6,也可游荡更久。
此计算亦显示“向两个方向移动的概率相等”不表示期望到达边界的时间只有一步。粒子必须走到端点,并可能因折返而走更长的路。此公式特别依赖有限边界。
解 πP=π 只能找到转移下保持不变的分布,不能单凭此式断言链会接近它。运用有限链收敛定理前,要检查互通结构及周期性。
互通与闭类
若某整数 n≥0 满足 (Pn)ij>0,称 j 从 i 可达。若两状态互相可达,称它们互通。
互通把状态空间分割成类:自反性用到 P0=I,对称性包含于定义中,而传递性来自把正概率路径接起来。若类内没有一步转移到类外,称该类为闭类。链进入闭类后便不会离开。
这个结构有助理解平稳方程。有限链若有两个不同闭类,每个闭类都支持一个平稳分布;不同的混合给出整条链的不同平稳分布。因此不能因 P 是随机矩阵就假定平稳分布唯一。反之,不可约并非唯一性的必要条件。例如状态零吸收,而状态一以概率一走到零;唯一平稳分布集中在零,虽然零不能到达一。
在 0,1,2 三个状态上,两端点均吸收,而状态一以各 1/2 的概率走到两端。(1,0,0) 和 (0,0,1) 都是平稳分布,任何混合 (a,0,1−a),0≤a≤1,亦平稳。从一出发,一步后的分布是 (1/2,0,1/2),以后不变。极限分布依赖出发状态,故没有适用所有初始状态的单一吸引分布。
有限不可约链中,状态的周期是所有可能正返回步数的最大公因数;所有状态周期相同。若有正概率自环,它是一步返回,故不可约链的周期必为一。非周期性排除前面的确定交替,但不表示每个状态都须有自环。只要有长度二和三的返回路径,其最大公因数已是一。
以流量推导平稳分布
πP=π 表示平衡:下一步处于某状态的概率是流入该状态的概率之和。这不要求每对状态之间的流量相等。然而较强的成对条件,即细致平衡,常方便计算。
若概率向量 π 对所有 i,j 满足
πipij=πjpji,则 πP=π。
固定 j,对 i 把假设相加:i∑πipij=i∑πjpji=πji∑pji=πj,因为第 j 行之和为一。左边正是 πP 的第 j 个分量。
反例模式
不满足细致平衡的平稳链
断言:每个平稳分布都满足细致平衡。在状态 0,1,2 上令链确定地沿 0→1→2→0 移动,即 p01=p12=p20=1,其余元素为零。P 每一列恰有一个元素 1,所以 π=(1/3,1/3,1/3) 满足 πP=π。但 π0p01=1/3,而 π1p10=0。断言不成立:每个状态的总流入平衡,弱于每对状态之间的平衡;定理只给出充分条件。
转移矩阵两行为 (3/4,1/4) 和 (1/2,1/2)。成对平衡要求 π0/4=π1/2,即 π0=2π1;加上 π0+π1=1,得 (2/3,1/3)。两个非对角流量都等于 1/6。对角平衡自动成立,把答案代入 πP 可再作独立检查。
第一步分析与边界问题
到达概率的递推并不限于直线。对有限链中互不相交的目标集 B 与失败集 C,令 hi 为先到 B 而非 C 的概率。在 B 上设 hi=1,在 C 上设 hi=0;在两集以外,按第一步分类得 hi=j∑pijhj。若从每个其余状态出发都以概率一到达 B∪C,方程解唯一。
证明唯一性:两个解之差记为 d。反复代入可把 di 表为在第 n 时刻尚未到达边界时 d 的期望。有限状态空间上 d 有界,而尚未到边界的概率趋零,所以期望趋零,故 di=0。
几乎必然到达边界的条件很重要。若外部有吸收状态,该处方程只是 hi=hi,不能决定其值。先到目标而非失败的事件仍然定义良好,但单靠边界方程需要额外信息。因此检查可达性与终止性是建立计算的一部分,而非可有可无的代数细节。
状态选择与预测
指定状态后,转移矩阵才有意义。假设装置有持续多步的隐藏模式,发出警告的概率取决于该模式。单独的警告序列不一定是马尔可夫的:即使知道目前警告,较早警告仍可提供目前模式的信息,从而改变下一警告的预测。若模型的转移确实只依赖扩大的状态,把模式加入状态便可能恢复马尔可夫性。
即使转移矩阵正确,没有初始分布也未指定完整过程。同一矩阵在不同出发分布下可产生不同有限时间分布,μn=μ0Pn 清楚显示这点。平稳初始分布只是一个选择,不是默认假设。计算矩阵幂前应记录状态次序,以及分布采行向量还是列向量;反转约定会改变乘法次序。
以行向量表示分布时,更新是 μn+1=μnP。若改算 PμnT,组合的是 P 某一列的元素。对两行为 (3/4,1/4) 和 (1/2,1/2) 的矩阵及 μ0=(1,0),正确结果是 μ1=(3/4,1/4);而 Pμ0T=(3/4,1/2)T,元素之和为 5/4,并不是分布。检查元素之和是否为一,便能立即发现错误。
总结
转移矩阵的幂决定有限时间的分布;第一步方程可解边界问题。平稳分布在转移下保持不变,而从所有初始分布收敛还需要适当假设,例如有限、不可约及非周期。
练习
快速检查
(公平游走在 0,5 吸收,从 2 出发。求先到 5 的概率。)
解答 · 答案
公平公式 hi=i/N 给出 2/5。
快速检查
(转移矩阵两行为 (3/4,1/4) 和 (1/2,1/2)。求平稳分布。)
解答 · 答案
写 π=(a,1−a)。平稳方程第一个分量为 a=3a/4+(1−a)/2,即 3a/4=1/2,故 a=2/3,π=(2/3,1/3)。
快速检查
(上一题的链从状态 0 出发,求两次转移后在状态 1 的概率。)
解答 · 答案
把 0→0→1 与 0→1→1 两条路径相加:(3/4)(1/4)+(1/4)(1/2)=3/16+2/16=5/16。