随机过程5(11-12)

第五章离散时间马尔可夫链马尔可夫过程是前苏联数学家A.A.Markov首先提出和研究的一类随机过程.经过世界各国几代数学家的相继努力,至今已成为内容十分丰富,理论上相当完整,应用也十分广泛的一门数学分支.它的应用领域涉及计算机、通讯、自动控制、随机服务、可靠性、生物、经济、管理、气象、物理、化学等.马尔可夫(1856年6月14日——1922年7月20日）马尔可夫对数学的最大贡献是在概率论领域作出的．十九世纪后二十年，他主要是沿着切比雪夫开创的方向，致力于独立随机变量和古典极值理论的研究，从而改进和完善了大数定律和中心极限定理．二十世纪初，他的兴趣转移到相依随机变量序列的研究上来，从而创立了以他命名的著名概率模型——马尔可夫链．王梓坤院士(1929年—)江西吉安人,1952年大学毕业后，被分派到天津南开大学数学系任教.是一位对我国科学和教育事业作出卓越贡献的数学家和教育家，也是我国概率论研究的先驱和学术带头人之一。1954年，他又以优异的成绩考取了赴苏研究生。踏进世界著名学府－莫斯科大学，在这个学府世界概率论的奠基人柯尔莫哥洛夫院士正领导看一个强有力的概率研究集团。柯尔莫高洛夫慧眼识英才，非常信赖这位由中国选派的年轻人的能力，把他选作自己的研究生，去攻概率论的中心问题随机过程理论。当时中国近代数学才刚刚起步，大学也没有概率课程。此时苏联的概率论水平已届于世界最前列。王梓坤也根本不知道什么是概率，可他的研究方向又恰恰被定为概率论，著有《概率论基础及其应用》、《随机过程论》、《生灭过程与马尔科夫链》等9部数学著作．马尔可夫过程的定义马尔可夫链的转移概率与概率分布齐次马尔可夫链状态的分类转移概率的稳定性能本章主要内容引例(有限制随机游动问题)设质点只能在{0，1，2，···，a}中的各点上作随机游动，移动规则如下：1{1,2,,1}ia（）移动前处;1,0,,rqprqp0000,0,1prprii+1i-1pqr010p0r20i（）移动前处3ia（）移动前处a-1aqaar,0,1aaaaqrqr设Xn表示质点在n时刻所处的位置§1马尔可夫过程的定义一.基本概念1．马尔可夫性通俗地说，就是在知道过程现在的条件下，其将来的条件分布不依赖于过去，则称}),({TttX具有马尔可夫（Markov)性。定义设}),({TttX是一个随机过程，如果}),({TttX在t0时刻所处的状态为已知，它在时刻0tt所处状态的条件分布与其在t0之前所处的状态无关。0tt现在0tt将来0tt过去2.马尔可夫过程定义设}),({TttX的状态空间为S,122,,nntttT如果对(),,1,2,,1iiiXtxxSin在条件下)(ntX的条件分布函数恰好等于11()nnXtx在条件下的条件分布函数,即11221111(),(),,()(()((,))())nnnnnnnnnPXtxPXtxXtxXtxXtxXRtxx{(),}XttT马尔则称为可夫过程.3.马尔可夫链定义参数集和状态空间都是离散的马尔可夫过程称为马尔可夫链。注只讨论马尔可夫链的状态空间为有限或可列无限.则马尔可夫性可表示为12122,,,,,,nnntttTiiiS对11111122()(),((())(()()),),,nnnnnnnnnPXtiPXtixXtiXtiRXtiXti有特别对取T={0,1,2,···}的马尔可夫链，记为}0),({nnX或}0,{nXn此时的马尔可夫性为011,,,,,nniiiS对有0111(1))(1)(0),(1(()(())),,nnnnPXniPXiXiXniXXniin10110111,),,(()nnnnnnnnXPXiPXXiXiiXii或今后,记{1,2,3,},{0,1,2,}ST{,0}nXn马尔可夫链记为马氏链也称,或系统二马尔可夫链的转移概率1.转移概率定义设}0,{nXn是马尔可夫链,称条件概率{,0}nXnni(它表示系统在时处于状态的条件下经过k步转移,于n+k时到达状态j的条件概率).()()(,,,0,)1kijnknpnPXjXijSnik{,0}nXn为在n时的k步转移概率.()()kijipnj称以为第行底列元素的矩阵))(()()()(npnkijkP{,0}nXn为系统在n时的k步转移概率矩阵.()(())ijnpnP记为特别当k=1时，(1)()ijnpn为系统在时的一步转移概率,(1)(1)()(())ijnpnP为系统的一步转移概率矩阵()ijpn记为定义称可数维的矩阵)(ijpP为随机矩阵，如果0,(,)1,()ijijjpijpi显然，}0,{nXn在n时的k步转移概率矩阵)()(nkP是一随机矩阵.特别k＝０时，约定(0)1,,,00ijijijpijSnij(0)()I.Pn此时为单位矩阵实际中常会碰到具有时齐性的马氏链若对任意的状态i,j和时刻n，均有()(1)(2)ijijijpnpnpn则称马氏链X具有时齐性，或称X为其次马尔科夫链，简称齐次马氏链.引例(有限制随机游动问题)设质点只能在{0，1，2，···，a}中的各点上作随机游动，移动规则如下：1{1,2,,1}ia（）移动前处;1,0,,rqprqp0000,0,1prprii+1i-1pqr010p0r20i（）移动前处3ia（）移动前处a-1aqaar,0,1aaaaqrqr设Xn表示质点在n时刻所处的位置，则其一步转移概率矩阵为{,0}{0,1,,}nXnSa是以为状态空间的齐次马尔可夫链.aarqprqprqprqpr000000000000000000000000P例１(天气预报问题)如果明天是否有雨仅与今天的天气(是否有雨)有关，而与过去的天气无关.并设今天下雨、明天有雨的概率为a，今天无雨而明天有雨的概率为b，又假设有雨称为0状态天气，无雨称为1状态天气.Xn表示时刻n时的天气状态，则}0,{nXn是以}1,0{S为状态空间的齐次马尔可夫链.其一步转移概率矩阵为bbaa11P天气的变化过程还可以用不同的马尔科夫链来描述，假设任意一天的天气与前一天的天气有关，即如果昨天和今天都为晴天，明天为晴天的概率为α，昨天和今天分别为晴天和阴天，明天为晴天的概率为β，昨天和今天分别为阴天和晴天，明天为晴天的概率为γ，如果昨天和今天都为阴天，明天为晴天的概率为δ。如果将阴天和晴天分别记为0,1，则昨天和今天的所有天气情况可以用数对表示为集合S={（1,1），（1,0），（0,1），（0,0）}，由此，将数对看做状态，天气的变化过程可用状态空间为S上的其次马尔科夫链描述，一步转移概率矩阵为：100001100001P练习天气预报问题，其模型是：今天是否下雨依赖于前三天是否有雨（即一连三天有雨；前面两天有雨，第三天晴天…..),问能否把这一问题归纳为一马尔科夫链，如果可以，问该过程的状态有几个？如果过去一连三天有雨，今天有雨的概率为0.8；过去连续为晴天，而今天有雨的概率为0.2；在其他天气情况，今天的天气和昨天相同的概率为0.6，求这个马儿科夫链的转移概率.例2（埃伦菲斯特模型）设一个坛子中装有m个球，它们或是红色的，或是黑色的，从坛子中随机的摸出一球，并换入一个相反颜色的球.其一步转移概率矩阵为01000001010000000202000001010000010mmmmmmmmmP{,0}nXn是以},,1,0{mS为状态空间的齐次马尔可夫链.设经过n次摸换,坛中黑球数为Xn,则例3（群体增长）某种生物群体的每个个体在其生存期内彼此独立地产生后代，假设每个个体都以概率pk产生k个后代，且有00,(1,2,)1kkkpkp用Xn表示第n代生物群体的总数，它是生物群体的第n-1代的每个个体的后代个数的总和，因此第n+1代的个体总数仅依赖于第n代的个体总数，所以X={Xn,n=0,1,2,···}是一个马尔科夫链，状态空间为S={0,1,2，···}则马氏链的一步转移概率为：1()nnPXjXi如果记第n代的生物群体个数nXi记i个个体各自产生的后代数分别记为随机变量，且有概率分布12,,,i(0,1,,)lli(),0,1,2lkPkpk故一步转移概率为112()()nniPXjXiPj例4（卜里耶模型）设一个坛子里有b个黑球和r个红球，每次随机地从坛子中摸出一个球后再放回去，并加入c个与摸出球同颜色的球。重复以上步骤将摸球进行下去，设Xn表示第n次摸球放回后坛子中的黑球数，试写出其一步转移概率矩阵和状态空间1()(),1,0,ijnnpnPXjXiijicbrncijibrnc其他例5：设是相互独立同分布的随机变量序列，且{:0}nn(1),(1)1,0,0nnPpPppn令随机序列：0,0nnkkXn验证：随机序列X={Xn:n≥0}是一个齐次马氏链.例6设一个服务站有M位服务员,顾客不断来到并请求服务.假定在Δt时间内来到一位顾客的概率为λΔt+o(Δt),没有顾客来到的概率为1-λΔt+o(Δt),来到两位或两位以上顾客的概率为o(Δt).来到的顾客,当有空闲的服务员时,则立即接受服务.否则排队等待,直到正在服务的顾客结束服务,服务员空闲后再为排队的顾客服务.假定每位在时刻t正在接受服务的顾客在时刻t+Δt结束服务的概率为μΔt+o(Δt),并假定各顾客的来到时刻及其被服务的时间相互独立.令X(t)表示时刻t要求服务的顾客数(包括正在服务的和等待的顾客数).(1)试说明{X(t),t≥0}是马尔可夫过程.分析或提示(1)由题意设法验证{X(t),t≥0}是一个齐次泊松过程,故它必是马尔可夫过程例7在二元传输中,依次的n个中继站从一个站向下一个站传送0或1.每个接收站以概率p正确地接收信号,而以概率q=1-p发生错误.X(0)表示初始站发出的数字,X(n)表示经n次传输后第n个接收站收到的数字,则{X(n),n≥0}是两个状态的马氏链.§２.马尔科夫链的概率分布定理(C-K方程)()()()()()(),,,0,,kmkmijilljlpnpnpnknmkijS或矩阵形式)()()()()()(knnnmkmkPPP（解决了k步转移概率与一步转移概率间的关系）证明()(){)kmijnkmnpnPXjXi{,())nkmnlnkPXjliXX,){()nkmnnklPXjXliX,)()nkmnnlkPXjXiXl)(,)(nnkmnnnklkPXiPXjXXlXil)(()nnkmnknklPXiPllXXjX()()()()kmilljlpnpnk系统在n时从状态i的出发,经过k+m步转移,于n+k+m时到达状态j,可以先在n时从状态i出发，经过k步转移于n+k时到达某种中间状态l,再在n+k时从中间状态l出发经过m步转移于n+k+m时到达最终状态j,而中间状态l要取遍整个状态空间S.C-K方程的直观意义：定理马尔可夫链的k步转移概率由其一步转移概率所完全确定.若取m=1,则由C-K方程的矩阵形式:)()()()()()(knnnmkmkPPP得(1)()(1)()()()kknnnkPPP(1)()(1)()knnknk