中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 第二章 Markov过程 本章我们先讨论一类特殊的参数离散状态空间离散的随机过 程,参数为T=01,2,…}=N,状态空间为可列S={1,2,…}或有限 S={1,2,…,n}的情况,即讨论的过程为 Markov链。 Markov链最 初由 Markov于1906年引入,至今它在自然科学、工程技术、 生命科学及管理科学等诸多领域中都有广泛的应用。之后我们将 讨论另一类参数连续状态空间离散的随机过程,即纯不连续 Markov过程。 1. Markov链的定义 定义:设随机序列{X(n)n≥0}的状态空间为S,如果对 n∈N,及a,i S,P{X(0) X(n)=in}>0, 有: P{X(n+1)=inX(0)=i,Xx(1)=,…Y(m)=in}= =P(X(n+1)=in X(n)=i,) 则称{X(mn),n≥0}为 Markov链 注1:随机序列{X(m)n≥0}也可记为{Xn;n≥0}。 注2:等式(A)刻画了 Markov链的特性,称此特性为 Markov 性或无后效性,简称为马氏性。 Markov链也称为马氏链 定义:设{Y(n),n≥0}为马氏链,状态空间为S,对于Vi,j∈S, 称
中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 第二章 Markov 过程 本章我们先讨论一类特殊的参数离散状态空间离散的随机过 程，参数为 0 T ={0,1,2, } = N ，状态空间为可列 S ={1,2, } 或有限 S ={1,2, ,n} 的情况，即讨论的过程为 Markov 链。Markov 链最 初由 Markov 于 1906 年引入，至今它在自然科学、工程技术、 生命科学及管理科学等诸多领域中都有广泛的应用。之后我们将 讨论另一类参数连续状态空间离散的随机过程，即纯不连续 Markov 过程。 1． Markov 链的定义 定义：设随机序列 {X (n); n 0} 的状态空间为 S ，如果对 n N0 ，及 i 0 ,i 1 , ,i n ,i n+1 S, P{X (0) = i 0 , X (1) = i 1 , , X (n) = i n } 0 ， 有： { ( 1) ( ) } { ( 1) (0) , (1) , , ( ) } 1 1 0 1 n n n n P X n i X n i P X n i X i X i X n i = + = = + = = = = = + + (A) 则称 {X (n); n 0} 为 Markov 链。 注 1：随机序列 {X (n); n 0} 也可记为 {X ; n 0} n 。 注 2：等式（A）刻画了 Markov 链的特性，称此特性为 Markov 性或无后效性，简称为马氏性。Markov 链也称为马氏链。 定义：设 {X (n); n 0} 为马氏链，状态空间为 S ，对于 i, jS ， 称
中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 P{X(n+1)=i2n|Y(mn)=1}p,(m) 为马氏链{Y(m)n≥0}在n时刻的一步转移概率。若对于ⅵ,j∈S, 有 P{X(n+1)=nX(m)=n}≡P,(n)≡P 即上面式子的右边与时刻n无关,则称此马氏链为齐次(或时齐 的)马氏链 对于齐次马氏链,我们记P=(p,),称矩阵P为齐次马氏链的 步转移概率矩阵,简称为转移矩阵。 注3:对于马氏链{X(m)n≥0},我们有: P{X(0)=i0,X(1) (n)=1 P{X(n)=n|X(0)=in,X(1)=i1…,X(m-1)=in1} P{X(0)=i0,X(1)=1,…,X(n-1)=in-} P{X(mn)=|X(n-1)=in}.P{X(0)=b,X() =P{X(n)=in|X(m-1)=n}P{X(n-1)=in|X(m-2)=ln2} P{X(1)=1X(0)=}P{X(0)=i} p_(n-1)P 2)…P(0)·P(X(0)=b} 因此,只要得到了马氏链的一步转移概率及初始分布,就可以求 得马氏链的任意前n+1维的联合分布。特别地,若马氏链是齐次 的,则由转移矩阵及初始分布,就可以得到齐次马氏链的任意前 n+1维的联合分布。 注4:一步转移概率满足:
中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 { ( 1) ( ) } ˆ ( ) P X n + = i n+1 X n = i n = pi j n 为马氏链 {X (n); n 0} 在 n 时刻的一步转移概率。若对于 i, jS ， 有 n n pi j n pi j P{X (n +1) = i +1 X (n) = i } = ˆ ( ) 即上面式子的右边与时刻 n 无关，则称此马氏链为齐次（或时齐 的）马氏链。 对于齐次马氏链，我们记 ( ) P = pi j ，称矩阵 P 为齐次马氏链的 一步转移概率矩阵，简称为转移矩阵。 注 3：对于马氏链 {X (n); n 0} ，我们有： ( 1) ( 2) (0) { (0) } { (1) (0) } { (0) } { ( ) ( 1) } { ( 1) ( 2) } { ( ) ( 1) } { (0) , (1) , , ( 1) } { (0) , (1) , , ( 1) } { ( ) (0) , (1) , , ( 1) } { (0) , (1) , , ( ) } 0 1 0 0 1 1 2 1 0 1 1 0 1 1 0 1 1 0 1 1 1 1 0 1 p n p n p P X i P X i X i P X i P X n i X n i P X n i X n i P X n i X n i P X i X i X n i P X i X i X n i P X n i X i X i X n i P X i X i X n i i i i i i i n n n n n n n n n n n n n n n = − − = = = = = = − = − = − = = = = − = = = − = = = − = = = = = − = = = = = − − − − − − − − − − 因此，只要得到了马氏链的一步转移概率及初始分布，就可以求 得马氏链的任意前 n +1 维的联合分布。特别地，若马氏链是齐次 的，则由转移矩阵及初始分布，就可以得到齐次马氏链的任意前 n +1 维的联合分布。 注 4：一步转移概率满足：
中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 P,(n)≥0(,j∈S) ∑P,(m)=1i∈S 注5:若状态空间是有限的,设状态数为n则一步转移矩阵是 n阶方阵,若状态是无限可列的情形,则一步转移矩阵只是形式 上的矩阵。 2.普曼一柯尔莫哥洛夫(C一K)方程 (一)m步转移概率的定义 定义:称pm(n)=P{X(n+m)=jX(n)=为马氏链{X(m)n≥0} 的m步转移概率。在齐次马氏链的情况下,p(n)与n无关,我 们记为p),称 为齐次马氏链的m步转移(概率)矩阵。 显然有: pm(n)≥0(i,j∈S) m=1时,即为一步转移矩阵。 规定: (m)=6
中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 = j S i j i j p n i S p n i j S ( ) 1 ( ) 0 ( , ) 注 5：若状态空间是有限的，设状态数为 n 则一步转移矩阵是 n 阶方阵，若状态是无限可列的情形，则一步转移矩阵只是形式 上的矩阵。 2． 普曼－柯尔莫哥洛夫（C－K）方程 （一） m 步转移概率的定义 定义：称 ( ) { ( ) ( ) } ( ) p n P X n m j X n i m i j = + = = 为马氏链 {X(n); n 0} 的 m 步转移概率。在齐次马氏链的情况下， ( ) ( ) p n m i j 与 n 无关，我 们记为 (m) i j p ，称 ( ) ( ) (m) i j m P = p 为齐次马氏链的 m 步转移（概率）矩阵。 显然有： ( ) 1 ( ) ( ) 0 ( , ) ( ) ( ) p n i S p n i j S j S m i j m i j = m =1 时，即为一步转移矩阵。 规定： = = = i j i j pi j n i j 0 1 ( ) (0)
中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 (二)切普曼一柯尔莫哥洛夫(C一K)方程 定理:对于m步转移概率有如下的C一K方程 pm"(m)=∑p(m)P(n+m)( 对于齐次马氏链,此方程为: p pmp(,j∈S)(C-K方程 证明:由全概率公式,有: n+r P(X(n+m+r)=jX(n)=i EPX(n+m+r)=j, X(n+m)=kX(n)=i; 2PX(n+m+r)=jX(n+m)=k, X(n)=i; P(X(n+m)=k X(n)=i; XPX(n+m+r)=jX(n+m)=k]P(X(n+m)=k X(n)=i; =∑P(m)P(m+m) 对于齐次马氏链的情形:我们可以写成矩阵的形式即有: P(m+r)= P(m)P(r) 由此推出: P(m)= p(m-p 其中:P=P 由此可知:对于齐次马氏链,如果知道了它的初始分布(0)和 一步转移矩阵P,就可以求得X(m)的所有有限维概率分布。即有:
中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 （二）切普曼－柯尔莫哥洛夫（C－K）方程 定理：对于 m 步转移概率有如下的 C－K 方程： ( ) ( ) ( ) ( , ) ( ) ( ) ( ) p n p n p n m i j S k S r k j m i k m r i j = + + 对于齐次马氏链，此方程为： ( , ) ( ) ( ) ( ) p p p i j S k S r k j m ik m r i j = + （C－K 方程） 证明：由全概率公式，有： + = + = + + = + = + = = + = = = + + = + = = = + + = + = = = + + = = = k S r k j m i k k S k S k S m r i j p n p n m P X n m r j X n m k P X n m k X n i P X n m k X n i P X n m r j X n m k X n i P X n m r j X n m k X n i P X n m r j X n i p n ( ) ( ) { ( ) ( ) } { ( ) ( ) } { ( ) ( ) } { ( ) ( ) , ( ) } { ( ) , ( ) ( ) } { ( ) ( ) } ( ) ( ) ( ) ( ) 对于齐次马氏链的情形：我们可以写成矩阵的形式即有： (m r) (m) (r) P = P P + 由此推出： m m m m P = P P = = P = P − ( ) ( ) ( 1) (1) 其中： P = P (1) 由此可知：对于齐次马氏链，如果知道了它的初始分布 (0) 和 一步转移矩阵 P ，就可以求得 X (n) 的所有有限维概率分布。即有：
中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 P{X(n1)=i12X(m2)=12…,X(m)=ik}= ∑p).-n"p pm-ipm P(X(0)=j) 上式中各m步转移概率均可由C-K方程求出,利用一步转 移矩阵及初始分布就可以完全确定齐次马氏链的统计性质。 3.马氏链的例子 随机游动: (1)无限制的随机游动: 以x(n)表示时刻n时质点所处的位置,则{X(m),n=0,1,2…}是 一齐次马氏链,其状态空间为S=(…-2,-10,12…},一步转移概 率为 P1:+1=P (i∈S,0<p<1) P1=q=1-p,(i∈S,0<p<1) 0 (i≠i+1,i-1,j∈S) 现在求n步转移概率p": 设n次转移中向右m次,向左m2次,则有 n+J m1(+1)+m2(-1)=j 即有 n+I-l n-J+I =10Pq2,(+j-1是偶数) 0 (n+j-i是奇数) p"={C;pq,(m+j-i是偶数) (n+j-i是奇数)
中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 − − − = = = = = = − − − − − − j S n j i n n i i n n i i n n i i k k p p p p P X j P X n i X n i X n i k k k k k k k k { (0) } { ( ) , ( ) , , ( ) } ( ) ( ) ( ) ( ) 1 1 2 2 1 1 2 1 1 2 1 2 2 1 1 1 上式中各 m 步转移概率均可由 C－K 方程求出，利用一步转 移矩阵及初始分布就可以完全确定齐次马氏链的统计性质。 3． 马氏链的例子 ⚫ 随机游动： （1） 无限制的随机游动： 以 X (n) 表示时刻 n 时质点所处的位置，则 {X(n), n = 0,1,2} 是 一齐次马氏链，其状态空间为 S ={ ,−2,−1,0,1,2, } ，一步转移概 率为： = + − = = − = − + 0 , ( 1, 1, ) 1 , ( , 0 1) , ( , 0 1) 1 1 p i i i j S p q p i S p p p i S p i j i i i i 现在求 n 步转移概率 (n) ij p ： 设 n 次转移中向右 m1 次，向左 m2 次，则有 2 , ( 1) ( 1) 2 1 2 1 2 1 2 n j i m n j i m m m j i m m n − + = + − = + + − = − + = 即有： + − + − = + − + − − + 0 , ( ) , ( ) 2 2 2 ( ) 是奇数 是偶数 n j i C p q n j i p n j i n j i n j i n n i j + − + − = 0 , ( ) , ( ) 2 2 2 ( ) 是奇数 是偶数 n j i C p q n j i p n n n n n ii
中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 (2)带有一个吸收壁的随机游动: 特点:当X(m)=0时,X(m+1)就停留在零状态。 此时{X(m,n=012…}是一齐次马氏链,其状态空间为 S={0,1,2,},一步转移概率为: P ii+l (i≥1,t∈S) P PP Pq01 (i≥1,i∈S) (≠i+1,i-1,i≥1,i∈S) 注意;状态为马氏链的吸收状态的充要条件是:p,=1 (3)带有二个吸收壁的随机游动 此时{X(n),n=0,12…}是一齐次马氏链,状态空间为 S={0,1,2…,a},0,a为两个吸收状态,它的一步转移概率为 1000 p 0 q000 000 000 000 P g0 p 000 000.00 00000 q P 000 0 00 即有:
中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 （2） 带有一个吸收壁的随机游动： 特点：当 X (n) = 0 时， X(n +1) 就停留在零状态。 此 时 {X(n), n = 0,1,2} 是一齐次马氏链，其状态空间为 S ={0,1,2, } ，一步转移概率为： = = + − = = − + 1 0 ( 1, 1, 1, ) ( 1, ) ( 1, ) 0 0 1 1 p p j i i i i S p q i i S p p i i S i j i i i i 注意； i 状态为马氏链的吸收状态的充要条件是： pi i =1。 （3） 带有二个吸收壁的随机游动： 此 时 {X(n), n = 0,1,2} 是 一 齐 次 马 氏 链 ， 状 态 空 间 为 S ={0,1,2, ,a} ， 0, a 为两个吸收状态，它的一步转移概率为： ( 1) ( 1) 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 + + = a a q p q p q p P 即有：
中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 P1+=P (1≤i≤a-1) P1=q=1-p(1≤isa-1) P2=0 l;1 P P P=0G≠0) P ≠a (4)带有一个反射壁的随机游动: 特点:一旦质点进入零状态,下一步它以概率p向右移动一 格,以概率q=1-p停留在零状态。 此时的状态空间为S={0,1,2,},它的一步转移概率为: P ii+l P (i≥1) P11=q=1-P(≥1) P1=0 Po =p P p-q po,=0(≠0,1) (5)带有二个反射壁的随机游动: 此时的状态空间为S={012.…,a},它的一步转移概率矩阵为: 000 0 0 qg000 P0g p00 00000 0 000 0 0 0 0 0000 0000 0 即有:
中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 0 ( ) 0 ( 0) 1 1 0 ( 1, 1;1 1) 1 (1 1) (1 1) 0 00 1 1 p j a p j p p p j i i i a p q p i a p p i a a j j a a i j i i i i = = = = = + − − = = − − = − − + （4） 带有一个反射壁的随机游动： 特点：一旦质点进入零状态，下一步它以概率 p 向右移动一 格，以概率 q =1− p 停留在零状态。 此时的状态空间为 S ={0,1,2, } ，它的一步转移概率为： 0 ( 0,1) 1 0 ( 1, 1; 1) 1 ( 1) ( 1) 0 00 01 1 1 = = − = = = + − = = − = − + p j p p q p p p j i i i p q p i p p i j i j i i i i （5） 带有二个反射壁的随机游动： 此时的状态空间为 S ={0,1,2, ,a} ，它的一步转移概率矩阵为： ( 1) ( 1) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 + + = a a q p q p q p q p q p P 即有：
中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 Ppppp P P =q=1-p 0(j≠0,1) Pa=0(≠a,a-1) ●排队模型 (1)离散排队系统 考虑顾客到达一服务台排队等待服务的情况。 若服务台前至少有一顾客等待,则在单位时间周期内,服务员 完成一个顾客的服务后,该顾客立刻离去;若服务台前没有顾客, 则服务员空闲。 在一个服务周期内,顾客可以到达,设第n个周期到达的顾客 数5n是一个取值为非负整数的随机变量,且{n,n≥l相互独立同 分布。在每个周期开始时系统的状态定义为服务台前等待服务的 顾客数。若现在状态为i,则下周期的状态/应该为: l5 i=0 其中ξ为该周期内到达的顾客数。 记第n个周期开始的顾客数为x,则Xn=(X-1)+5,其 中amax{a,0},根据马氏链的定义,可知{X,n≥0是一马氏链。 若假设P{n=k}=a,a20,∑a=1,则{Xn,n≥0}的一步转移 概率为:
中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 0 ( , 1) 0 ( 0,1) 1 1 0 1 01 00 = − = = = − = = = = − − p j a a p j p q p p p p p p q p a j j a a aa ⚫ 排队模型 （1） 离散排队系统 考虑顾客到达一服务台排队等待服务的情况。 若服务台前至少有一顾客等待，则在单位时间周期内，服务员 完成一个顾客的服务后，该顾客立刻离去；若服务台前没有顾客， 则服务员空闲。 在一个服务周期内，顾客可以到达，设第 n 个周期到达的顾客 数 n 是一个取值为非负整数的随机变量，且 { , n 1} n 相互独立同 分布。在每个周期开始时系统的状态定义为服务台前等待服务的 顾客数。若现在状态为 i ，则下周期的状态 j 应该为： = − + = , 0 ( 1) , 1 i i i j 其中 为该周期内到达的顾客数。 记第 n 个周期开始的顾客数为 X n ，则 X n = X n − + n + + ( 1) 1 ，其 中 a = ˆ max{a,0} + ，根据马氏链的定义，可知 {X , n 0} n 是一马氏链。 若假设 { } , 0 , 1 0 = = = k= n ak ak ak P k ，则 {X , n 0} n 的一步转移 概率为：
中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 ≥0 P,=a-i>1,j≥i-1 J 0i>1,j1时,则当n充分大后,等待顾客的队伍 将无限增大;若EEn=∑a0时,有: Xn1=5+52+…+5x 其中占是第n代中第个个体产生下一代的个数 由此可知,只要给定X,那么X的分布就完全决定了,且 与以前的x,Xn1,…无关,故{Xn,n≥1是一马氏链。把这一类 马氏链称为离散的分支过程。可以证明:
中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 0 1, 1 1, 1 0 0 1 1 0 = − = − = = + − p i j i p a i j i p a j p a j i j i j j i j j j j 易见：当 1 0 = k= E n ak 时，则当 n 充分大后，等待顾客的队伍 将无限增大；若 1 0 = k= E n ak ，则等待服务的顾客队伍长度趋近 某种平衡。 （2） G/M/1 排队系统 略。（见纯不连续马氏过程的内容，以后会讲到。） ⚫ 离散分支过程 考虑某一群体，假定某一代的每一个个体可以产生 个下一 代，其中 是取值非负整数的离散型随机变量， { } , 0 , 0 , 1 0 = = = k= k k ak P k a a k ，设某一代各个体产生下一代 的个数相互独立同分布且与上一代相互独立。 令： X n 表示第 n 代个体的数目，则当 X n = 0 时，有 X n+1 = 0 ； 当 X n 0 时，有： n Xn X +1 = 1 + 2 ++ 其中 i 是第 n 代中第 i 个个体产生下一代的个数。 由此可知，只要给定 X n ，那么 X n+1 的分布就完全决定了，且 与以前的 X n−1 , X n−1 , 无关，故 {X , n 1} n 是一马氏链。把这一类 马氏链称为离散的分支过程。可以证明：
中科院研究生院2004~2005第一学期随机过程讲稿孙应飞 P,=P(Xm=jX=l}=P{51+52+…+5,=X,= P{51+52 5=j} ak jIax' 注:设F()是随机变量的母函数,即F(s)=∑as;又设第 0代有一个个体,即P{X0=1}=1,则与X分布相应的母函数为 G(s)=s;另外,x1=5,因此与X分布相对应的母函数为 G1(s)=F(s) 设Xn的母函数为G(s),则G2(s)=G(F(s)=F(F(s),所以有: G(s)=F(F(…F(S))=F"(s) 由此等式可得以上的结论。 习题:P111-112:7、8、9、11、12
中科院研究生院 2004～2005 第一学期 随机过程讲稿 孙应飞 0 0 1 2 1 1 2 ! { } { } { } = = + = = + + + = = = = = + + + = = j x i k k k j i i j n n X n j x a x P j p P X j X i P j X i n 注：设 F(s) 是随机变量 的母函数，即 = = 0 ( ) k k k F s a s ；又设第 0 代有一个个体，即 P{X0 =1} =1 ，则与 X0 分布相应的母函数为 G (s) = s 0 ；另外， X1 = ，因此与 X1 分布相对应的母函数为 ( ) ( ) 1 G s = F s 。 设 X n 的母函数为 G (s) n ，则 ( ) ( ( )) ( ( )) 2 1 G s = G F s = F F s ，所以有： ( ) ( ( ( ))) ( ) ( ) G s F F F s F s n n n = = 由此等式可得以上的结论。 习题：P111－112：7、8、9、11、12