《应用随机过程教程》教学资源（参考资料）与在算法和智能计算中的应用——第6章 连续时间的Markov链（Q-过程）

龚光鲁,钱敏平著应用随机过程教程及其在算法与智能计算中的应用 清华大学出版社,2003 第6章连续时间的 Markov链(Q-过程) 1连续时间的 Markov链及其转移矩阵 1.1连续时间的 Markov链的定义及等价性描述 定义6.1随机变量族{1I≥0}称为连续吋间的 Markov链,如果这些随机变量都是 离散的(状态空间S至多是一个可数集,即它或者有限,或者与自然数一一对应)而且对于 vm≥0,Vs>s1>…sm≥0及任意状态i,j,,…,ln,都有 P(5=j,=14=i1,…,5=m)=P(5*=,= (6.1) Markov性可以有许多等价叙述,我们概括如下: 等价叙述1若A为只与资料{n,l<s}有关的一个事件,则有 P(5=,=,A)=P(5=,=1) 等价叙述2对于过程在时刻s以后所确定的事件B及等价叙述1中之A有 P(BS,=i, A)=P(BSs=) 等价叙述3在已知“现在”的条件下,“将来”与“过去”是条件独立的 等价叙述4对状态空间上的任意有界函数∫,及S>S1>…>Sn>0,均有 E((),=54=1…5,=)=E((,料 (6.1)式也是(6.4)式的特例,即f(x)=l(x)的情形) 等价性质5(最一般的形式)对于常见的实数集合A,只由随机序列{}在时刻s及 其后的信息所决定的随机变量n,以及任意S>S1>…>Sn>0,恒有 P(n∈Nk,=5 5=im)=P(n∈Ak,=) 或更一般地 ,=54=4…5,=m)=E(n,= (6。5) 1.2连续时间的 Markov链概率转移矩阵 定义6.2记 P(s,D)=P(=5,=1)(t2s) 定义无穷矩阵

142 龚光鲁，钱敏平著 应用随机过程教程及其在算法与智能计算中的应用 清华大学出版社,2003 第6章 连续时间的 Markov 链 (Q-过程) 1 连续时间的 Markov 链及其转移矩阵 1．1 连续时间的 Markov 链的定义及等价性描述 定义６.１ 随机变量族{ : t ³ 0} t x 称为连续时间的 Markov 链, 如果这些随机变量都是 离散的 (状态空间S 至多是一个可数集, 即它或者有限, 或者与自然数一一对应), 而且对于 "m ³ 0,"s > s1 > Lsm ³ 0 及任意状态 m i, j,i , ,i 1 L , 都有 ( + = | = , = 1 , , = ) = t s s s1 s m P j i i i m x x x L x P( j | i) xs +t = x s = . (6. 1) Markov 性可以有许多等价叙述，我们概括如下： 等价叙述１ 若 A 为只与资料{ ,u s} xu < 有关的一个事件, 则有 P( j i, A) P( j i) xs +t = x s = = xs +t = x s = . (6. 2) 等价叙述 2 对于过程在时刻s 以后所确定的事件 B 及等价叙述 1 中之 A 有 P(B i, A) P(B i) xs = = xs = . (6. 3) 等价叙述 3 在已知“现在”的条件下，“将来”与“过去” 是条件独立的. 等价叙述 4 对状态空间上的任意有界函数 f ，及 s > s1 > L > sm > 0 ，均有 ( ( ) , , ) ( ( ) ) 1 1 E f i i i E f i s t s s s m s t s m x + x = x = L x = = x + x = (6. 4) ((6. 1)式也是 (6. 4)式的特例, 即 ( ) ( ) { } f x I x = j 的情形). 等价性质 5（最一般的形式） 对于常见的实数集合L ，只由随机序列{ }t x 在时刻 s 及 其后的信息所决定的随机变量h ，以及任意 s > s1 > L > sm > 0 ， 恒有 ( , , ) ( ) 1 1 P i i i P i s s s m s m h Î Lx = x = L x = = h Î Lx = 或更一般地 ( , , ) ( ) 1 1 E i i i E i s s s m s m h x = x = L x = = h x = . （6。5） 1. ２ 连续时间的 Markov 链概率转移矩阵 定义６.２ 记 pij(s,t) = P( j | i),(t s) xt = x s = ³ . 定义无穷矩阵

P(S,)=(P(s,1) 称为转移矩阵.补充定义P(S,s)=I(无穷单位矩阵) 命题6 (概率转移矩阵族的性质) 与离散时间情形类似地,对于为分量全是1的无穷行向量(矩阵)1,我们有 (P.1)0≤p(S,0)≤1,P(s,1)1=1 (P.2)( Chapman-Ko l mogorov方程)对于vu≥t≥s有 P(S, u)= P(s, 1) P(t, u) 其分量形式为 Pn(.n)=∑PA(SD)P2(,) 证明与离散时间情形类似 1.3连续时间的时齐的 Markov链 定义δ·4连续时间的 Markov链称为时齐的,如果其转移阵P(Ss,s+)与s无关,此 时我们另记 P(t-s)=P(S,1)。 那么 Chapman- Kolmogorov方程变为 P(S+1)=P(s)P(t) 在本书中,除非特别声明,我们所考虑的连续时间的 Markov链均为时齐的.与时间离散 的情形类似,连续时间的 Markov链的转移矩阵P()是刻画此链的统计特征的要素.即有 定理6.5( Markov链的有限维分布与绝对概率) (1)若时续的时间 Markov链{,t20}的初始分布为1(0)=P(50=1),其转移矩 阵为P()=(P(D),则对于v0<4<…<,有 P(50=l0,541=1,…,5,=n)=4(0)p1(1)P42(2-1)…Pn(tn--)(6.9) (2)设H1(1)=P(51=1),并记由1()构成的行向量为p()=((1):i∈S),那么 (t+s)=H(s)P(t),从而有p()=(0)P(1) 从而连续时间的 Markov链的统计性质(包括其长期行为)完全由转移矩阵P()及初始分布 (0)所决定 连续时间的 Markov链也有强 Markov性 离散时间的时齐 Markov链的多步转移矩阵P是由一个”最小的”P所生成的,而在 143

143 P (s,t) ( p (s,t)) = ij ， 称为转移矩阵．补充定义 P(s,s) = I (无穷单位矩阵). 命题６.３ （概率转移矩阵族的性质） 与离散时间情形类似地, 对于为分量全是 1 的无穷行向量(矩阵) 1,我们有 (P.1) 0 £ p (s,t) £ 1 ij , P (s,t) 1 T =1T . (P.2) (Chapman-Kolmogorov 方程) 对于"u ³ t ³ s 有 P (s,u) = P(s,t) P(t,u) , (6. 6) 其分量形式为 = å k pij(s,u) pik (s,t) pkj (t,u) . (6. 6)’ 证明与离散时间情形类似. １．３ 连续时间的时齐的 Markov 链 定义６．４ 连续时间的 Markov 链称为时齐的, 如果其转移阵 P(s,s + t) 与 s 无关. 此 时我们另记 P (t - s) = P(s,t) 。 (6. 7). 那么 Chapman-Kolmogorov 方程变为 P (s + t) = P(s) P(t) (6. 8) 在本书中, 除非特别声明，我们所考虑的连续时间的 Markov 链均为时齐的．与时间离散 的情形类似, 连续时间的 Markov 链的转移矩阵 P(t) 是刻画此链的统计特征的要素. 即有 定理 6．５ （Markov 链的有限维分布与绝对概率） （1） 若时续的时间 Markov 链{ ,t ³ 0} t x 的初始分布为 (0) ( ) 0 P i mi = x = ，其转移矩 阵为 P(t) ( p (t)) = ij ，则对于 n " < t <L < t 0 1 , 有 ( , , , ) (0) ( ) ( ) ( ) 0 = 0 t1 = 1 t = n = i0 i0 i1 1 i1 i2 2 - 1 i -1 i n - n-1 P i i i p t p t t p t t L n L n n x x x m (6. 9) （2）设 (t) P( i) mi = xt = ，并记由 (t) mi 构成的行向量为 m (t) = ( (t) : i S) mi Î ，那么 m(t + s) = m(s) P (t) ，从而有 m(t) = m(0) P (t) 从而连续时间的 Markov 链的统计性质（包括其长期行为）完全由转移矩阵 P(t) 及初始分布 m(0) 所决定. 】 连续时间的 Markov 链也有强 Markov 性. 离散时间的时齐Markov链的多步转移矩阵 P (n) 是由一个 ”最小的” P 所生成的, 而在

连续时间时,在P(1)中找不到直接生成它的最小者”但是,从 Chapman-Kolmogorov方程 P(s+D)=P(s)P(t),P(0)=I的形式看,它是一个无穷维的矩阵值函数方程我们拿一个 与它相象而最且简单的函数方程∫(t+s)=f(m)f(s),∫(0)=1分析,这个方程在t=0处 连续的通解为且而解∫()则完全由α=∫'(O)确定。由此猜测,在正常的情形下,如果 P()->I满足,P()在t=0处的微商P'(0)似乎应该存在,而且描述P()的演化 进程的最基本的量也应该就是P'(0) 事实上,在实际应用中都可以无妨地认为,P'(O)确实有限,而且唯一确定了P(t)(用 严格的数学可以证明,P(O)只是在较广的意义理解下存在,即:P2(.(≠存在,但Pa(0)却 可能取-∞,而且这样的P'(0)未必能唯一地确定P(1),这些都是理论概率论中的纯数学问题,而在 实际应用中一般是不会遇到的).于是就应用范围所关心的视点而言,我们可以说,在实用中遇 到的连续时间的 Markov链的转移矩阵P()关于t是可微的,而且P()可由它在t=0处的 微商P'(0)所确定 定义6.6设P()0→I满足,把P(0)记为Q,称为转移矩阵P(t)的转移速 率矩阵或形式生成元(有时也简称为Q矩阵)即 Q=P(0) (6.10 概率速率矩阵Q之所以重要,是因为一般P()不能直接由测量得到,然而Q却可通 过实验手段测得.由它再通过解一个称为 Kolmogorov方程的矩阵微分方程就可解出P(t) (参见后文).这样就能得到连续时间的 Markov链的统计分布.这构成了研究连续时间的 Markov链的统计行为的主要思路 又由于形式生成元Q与转移矩阵P()间的密切关系,所以在我国的概率界常称P()为 转移速率矩阵Q的Q过程.这是一个具有中国特色的称谓 在本章中,我们恒假定满足 P(t 2 Poisson过程与复合 Poisson过程再访 例6.7( Poisson过程作为 Markov过程转移矩阵与转移速率矩阵)

144 连续时间时, 在P (t) 中找不到直接生成它的”最小者”. 但是, 从 Chapman-Kolmogorov 方程 P (s + t) = P(s) P (t) , P(0) = I 的形式看, 它是一个无穷维的矩阵值函数方程. 我们拿一个 与它相象而最且简单的函数方程 f (t + s) = f (t) f (s), f (0) = 1分析， 这个方程在t = 0 处 连续的通解为且而解 f (t) 则完全由 a = f '(0) 确定. 由此猜测，在正常的情形下，如果 P (t) ¾t¾®0® I 满足, P (t) 在t = 0 处的微商 P ’(0) 似乎应该存在, 而且描述 P(t) 的演化 进程的最基本的量也应该就是 P ’(0) ． 事实上，在实际应用中都可以无妨地认为，P ’(0) 确实有限，而且唯一确定了 P(t) (用 严格的数学可以证明, P ’(0) 只是在较广的意义理解下存在, 即： p '(0),(i j) ij ¹ 存在, 但 '(0) pii 却 可能取 - ¥ ， 而且这样的 P ’(0) 未必能唯一地确定 P (t) , 这些都是理论概率论中的纯数学问题, 而在 实际应用中一般是不会遇到的). 于是就应用范围所关心的视点而言, 我们可以说, 在实用中遇 到的连续时间的 Markov 链的转移矩阵 P (t) 关于t 是可微的, 而且 P(t) 可由它在t = 0 处的 微商 P ’(0) 所确定. 定义６.６ 设P (t) ¾t¾®0® I 满足，把 P ’(0) 记为 Q , 称为转移矩阵 P(t) 的转移速 率矩阵或形式生成元（有时也简称为Q 矩阵） 即 Q P D = ’(0) . (6. 10) 概率速率矩阵Q 之所以重要， 是因为一般 P(t) 不能直接由测量得到, 然而Q 却可通 过实验手段测得. 由它再通过解一个称为 Kolmogorov 方程的矩阵微分方程就可解出 P (t) (参见后文)． 这样就能得到连续时间的 Markov 链的统计分布. 这构成了研究连续时间的 Markov 链的统计行为的主要思路. 又由于形式生成元Q 与转移矩阵P (t) 间的密切关系, 所以在我国的概率界常称P(t) 为 转移速率矩阵Q 的 Q-过程. 这是一个具有中国特色的称谓． 在本章中, 我们恒假定满足 P (t) ¾t¾®0® I . (6.11) 2 Poisson 过程与复合 Poisson 过程再访 例６．７ （Poisson 过程作为 Markov 过程转移矩阵与转移速率矩阵）

Poisson过程是独立增量过程,所以它有 Markov性.故它是连续时间的 Markov链,由 第3章知道 Poisson过程的转移矩阵依赖于连续时间参数t,即 P()=(P,P2()=12-m) (其它情形) 因此转移矩阵是一个上三角形无穷矩阵.这时转移速率矩阵(形式生成元)为 λ0 0-0 0-0 Q=(q,) 注意 Poisson过程的转移速率矩阵Q的每一行的和都是0.这个事实对于只有有限个 状态的连续时间的 Markov链总是对的,写成向量形式就是Q17=0.但是对于一般有可数 个状态的连续时间的 Markov链确未必正确.因为在数学上我们只能证明Q1≤0,因 此也就引出了许多的困难,从而激起了纯理论研究的概率论学者的兴趣.好在实际应用中 的连续时间的 Markov链,常常都满足QI=0 定义6.8满足条件 P()-I,Q1=0 (6.12) 的Q称为保守的转移速率矩阵 在实际应用中就忽视Q17≠0的情形这就是说,在实际应用中遇到的转移矩阵总 认为是保守的。即如果发现了非保守情形,则可能是遗漏了某些状态. 例6.9(复合 Poisson过程的转移矩阵与转移速率矩阵) 设N为强度λ的 Poisson过程,{}k}为与之独立的独立同分布随机序列,则 是复合 Poisson过程.又因为它也是独立增量过程,所以它有 Markov性.假定 ff2…J ∑f=1 那么ξ是连续时间的 Markov链.我们来求它的转移矩阵与转移速率矩阵.对于S<t pn(s,1)=0,(>j),pn(s,1)=P(N,-N=0)=e-) 145

145 Poisson 过程是独立增量过程, 所以它有 Markov 性. 故它是连续时间的 Markov 链, 由 第３章知道 Poisson 过程的转移矩阵依赖于连续时间参数t ， 即 P ï î ï í ì ³ = = - - - 0 ( ) ( ) ( )! ( ) ( ) ( ), ( ) 其它情形 j i j i t e t p p t j i t ij ij l l . 因此转移矩阵是一个上三角形无穷矩阵. 这时转移速率矩阵（形式生成元）为 Q = ( ) ij q = ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç ç ç ç ç è æ - - - O O O O O O 0 0 0 0 0 l l l l l l . 注意 Poisson 过程的转移速率矩阵Q 的每一行的和都是 0. 这个事实对于只有有限个 状态的连续时间的Markov链总是对的, 写成向量形式就是Q 1 = 0 T . 但是对于一般有可数 个状态的连续时间的 Markov 链确未必正确． 因为在数学上我们只能证明 Q 1 £ 0 T , 因 此也就引出了许多的困难, 从而激起了纯理论研究的概率论学者的兴趣. 好在实际应用中 的连续时间的 Markov 链, 常常都满足Q 1 = 0 T ． 定义６.８ 满足条件 P (t) ¾t¾®0® I ，Q 1 = 0 T (6．１2) 的Q 称为保守的转移速率矩阵． 在实际应用中就忽视 Q 1 ¹ 0 T 的情形. 这就是说, 在实际应用中遇到的转移矩阵总 认为是保守的。 即如果发现了非保守情形, 则可能是遗漏了某些状态. 例６.９（复合 Poisson 过程的转移矩阵与转移速率矩阵） 设 Nt 为强度l 的 Poisson 过程， { } Yk 为与之独立的独立同分布随机序列， 则 Nt t =Y + +Y D x 1 L 是复合 Poisson 过程．又因为它也是独立增量过程, 所以它有 Markov 性. 假定 ,( 1) 1 2 ~ 1 2 å = ÷ ÷ ø ö ç ç è æ j j j k f f f f j Y L L L L ． 那么 t x 是连续时间的 Markov 链．我们来求它的转移矩阵与转移速率矩阵．对于 s < t p (s,t) 0,(i j) ij = > ， ( ) ( , ) ( 0) t s ii t p s t P N N e - - = - = = l

而当i<j时,由独立增量性及全概率公式得到 P(s,D)=P(5,=5,=1)=P(x+1+…+YN=j-iH1+…+YN,=) =P(Xx,+…+YA,=j-1)=P(Y1+…+1M2-N,=j-) ∑P(H+…+Vk=j-l|N-N,=k)P(N,-N,=k) k≥1 ∑P(H+…+X=j-)P(N-N,=k) 归纳地记概率向量∫=(f1,…,f2)的k次卷积(它们代表k个独立同分布的随机变量的 和的分布)为 f(1)=f,f(D)=∑/()(-n 那么我们得到 P2(31)=∑∫”(-)e a(-((t-s) 这说明转移矩阵是时齐的上三角形无穷矩阵.易见其转移速率矩阵为 λA1M/2 λMf1M2 M12 Q=(q 由此可见复合 Poisson过程的Q矩阵也是保守的 3.由转移速率矩阵确定时间连续的 Markov链 3.1 Kolmogorov方程及 Master方程 定理6.10 (1)Q=P(0)=(qn)在广义下存在,即 -∞≤qn≤0.q20.(≠∑q≤0 (6.14) (2)若总状态数有限,则qn>-∞,且Q保守(即∑q1=0)此时P(由Q唯 地确定,而且它可以表达为以下的收敛级数: P() I++ 146

146 而当 i < j 时， 由独立增量性及全概率公式得到 p (s,t) P( j | i) ij = xt = x s = ( | ) 1 1 P Y Y j i Y Y i Ns Nt Nt = + +L+ = - +L+ = ( ) 1 P Y Y j i Ns Nt = + +L+ = - ( ) 1 P Y Y j i Nt Ns = +L+ - = - ( | ) ( ) 1 1 P Y Y j i N N k P N N k k t s t s k = å + + = - - = - = ³ L ( ) ( ) 1 1 P Y Y j i P N N k k t s k = å + + = - - = ³ L 。 归纳地记概率向量 f ( , , , ) = f 1 L f i L 的k 次卷积(它们代表k 个独立同分布的随机变量的 和的分布)为 å= - = = - l j k k l f l f f l f j f l j 1 1 * * 1 1 ( ) , ( ) ( ) ( ) ． 那么我们得到 å³ - - - = - × 1 * ( ) ! ( ( )) ( , ) ( ) k k k t s ij k t s p s t f j i e l l ． 这说明转移矩阵是时齐的上三角形无穷矩阵．易见其转移速率矩阵为 Q = ( ) ij q = ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç ç ç ç ç è æ - - - O O O O O O L L L L 1 2 1 2 1 2 0 0 f f f f f f l l l l l l l l l ． (6. 13) 由此可见复合 Poisson 过程的Q 矩阵也是保守的． 3． 由转移速率矩阵确定时间连续的 Markov 链 3. 1 Kolmogorov 方程及 Master 方程 定理 6. １０ (1) Q = P ’(0) ( ) ij = q 在广义下存在, 即: q 0, q 0,(i j) - ¥ £ ii £ ij ³ ¹ ,å £ j ij q 0 . (6. 14) (2) 若总状态数有限, 则 qii > -¥ , 且Q 保守 (即 å = j ij q 0 ). 此时P (t) 由Q 唯一 地确定, 而且它可以表达为以下的收敛级数: P (t) = e Q t D = + + +L 1! 2! 2 Q Q I ; (6.15)