Markov链的状态分类PPT课件.ppt

上传人:可**** 文档编号:87349034 上传时间:2023-04-16 格式:PPT 页数:43 大小:1.98MB
返回 下载 相关 举报
Markov链的状态分类PPT课件.ppt_第1页
第1页 / 共43页
Markov链的状态分类PPT课件.ppt_第2页
第2页 / 共43页
点击查看更多>>
资源描述

《Markov链的状态分类PPT课件.ppt》由会员分享,可在线阅读,更多相关《Markov链的状态分类PPT课件.ppt(43页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、3.2 Markov链的状态分类链的状态分类互达性和周期性互达性和周期性定义定义3.3 设i 和j 是时齐的Markov链的两个状态,如果存在n0,使得 ,则称从状态i 可达可达状态j,记作ij.反之,以i j表示从状态i 不可达不可达状态j,即对一切n0,.若ij且ji,则称状态i和j互达互达(相通),记作ij.注注:引入互达性概念是为了对状态进行分类.命题命题3.1 互达性是等价关系,即满足:(1)自反性:ii;(2)对称性:若ij,则ji;(3)传递性:若ik 且kj,则ij.证证:(3)若ik 且kj,则存在整数n和m使得:由Chapman-Kolmogorov方程得:即:ij.类似可

2、证ji.在数学上,等价关系可以用于对集合进行分割.因此,我们也可以利用互达性对状态空间进行分类,并且这些类在互达关系下是等价类.定定义义3.4 一个Markov链的状态空间,如果在互达性这一等价关系下都居于同一类,那么就称这个Markov链是不不可可约约的.否则,这个Markov链就被称为是可约可约的.注注:引入可约/不可约概念是为了以后研究状态的周期,进一步是为了研究转移概率的极限性质.则显然1,2和3,4,5是状态在互达意义下的两个等价类.因此,这个Markov链是可约的.比如其中一个子链为:例例3.6 若Markov链有转移概率矩阵给出这个Markov链状态的等价类,并且试给出其n步转移

3、概率矩阵.练习练习:若Markov链有转移概率矩阵答答:等价类为:1,4,2,5和3.其中3为吸收态.用Mathematica软件计算知:所以定定义义3.5 设i为Markov链的一个状态,使 的所有正整数n(n1)的最大公约数,称为状态i的周期周期,记作d(i)或 di.如果对所有n1,都有 ,则约定周期为;d(i)=1的状态i称为是非周期非周期的.推论推论:如果n不能被周期d(i)整除,则必有 .注注:当状态i的周期为d时,不一定成立.试求状态0的周期.例例3.7 若Markov链有状态0,1,2,3和转移概率矩阵解解:状态转移可以用下图表示用数学归纳法不难求出:所以 d(0)=2.试求状

4、态1的周期.练习练习:若Markov链有状态1,2,3和转移概率矩阵解解:状态转移可以用下图表示所以 d(1)=2.您能求出状态您能求出状态2的周期吗的周期吗?命题命题3.2 如果ij,则 di=dj.证证:设m1,n1,使得 ,则因此,m+n同时能被di及dj整除.对于任意的s1 即:m+s+n也能被dj整除.因此,s能被dj整除.从而dj整除的 最大公因子di.根据对称性,di也整除dj,所以 di=dj.满足 ,则引引理理3.1 设m2,正整数s1,s2,sm的最大公因子为d,则存在正整数N,使得nN时,必有非负整数c1,c2,cm使 .我们引入状态周期概念的目的,是为了研究状态转移矩阵

5、的极限性质,即当n时P(n)的极限,这个矩阵可以反映出Markov链在平稳状态时的特征。因此,下面我们将讨论周期的基本性质,为此先给出一个数论中的结论:推推论论3.1 设状态i的周期为di.如果 ,则存在整数N,使得对所有nN恒有证证:这时存在正整数s1,s2,sm,使得它们的最大公因子为d,且 .命命题题3.3 如果状态i有周期d,则存在整数N,使得对所有nN恒有 .由引理3.1,存在正整数N,使得nN时,必有非负整数c1,c2,cm使 .从而因为状态空间有限,对全部的状态对(i,j),求出N(i,j).并取 ,则显然对所有状态i和j,当nN时有 .证证:由于Markov链是不可约的,过程的

6、任两个状态i和j都是互达的,于是m(与i和j有关)使得 .由推论3.1及链的非周期性知,存在N,使得当nN时,.命命题题3.4 设P为一个不可约、非周期、有限状态Markov链的转移矩阵,则必存在N,使得当nN时,P(n)的所有元素都大于0.显然这是一个不可约、非周期、有限状态的Markov链.例例3.8 若Markov链有转移概率矩阵 常返与瞬过常返与瞬过定义:定义:则 表示从状态i出发在第n次转移时首次到达状态j的概率。定义:定义:则 表示从状态i出发在第n次转移时首次回到状态i的概率。定义:定义:则 表示从状态i出发最终到达状态j的概率.性质:性质:当i j 时,则 i j fij 0.

7、定义定义3.5 如果 fii=1,则称状态i是常返常返的.否则,即fii 0,有因此,例例3.9 考虑整数点上的随机游动.向右移动一格的概率为p,向左移动一格的概率为q=1-p.从原点0出发,则一步转移概率矩阵为:所以利用Stirling公式知,当n充分大时于是因此,当p=0.5时 ,当p0.5时即当p=0.5时状态0是常返的;当p0.5时0是瞬过的.定义定义 对常返状态i我们定义Ti为首次返回状态i的时刻,即:称作常返时常返时.记 ,则有 ,所以是首次返回i的期望步数,叫作状态i的平均常返时平均常返时.定义定义 一个常返状态i当且仅当i=时称为是零零常返常返的,当且仅当i0(每一分量均大于0

8、),则称此马尔链为一正则链正则链(regular chain)补充:正则链与吸收链补充:正则链与吸收链定理定理C1.若A为正则链的转移矩阵,则必有:(1),其中W为任一分量均大于零的随机矩阵;(2)W的所有行向量均相同定理定理C2.记定理 C1中W的行向量为=(1,m),则:(1)对任意随机向 量x,有 ;(2)是P的不动点向量,即P=,P的不动点向量是唯一的定定义义C2.状态Si 称为马氏链的吸吸收收状状态态,若转移矩阵P的第i 行满足:Pii=1,Pij=0 (ji)定义定义C3.马氏链被称为吸收链吸收链,若其满足:(1)至少存在一个吸收状态;(2)从任一状态出发,经有限步转移总可到达某一

9、吸收 状态根据定义C3,例例3.1中Xn即为一吸收链 具有r个吸收状态,mr个非吸收状态的吸收链,它的mm转移矩阵P的标准形式为其中Ir为r 阶单位阵,O为r(m-r)零阵,R为(m-r)r 矩阵,Q为(m-r)(m-r)矩阵令B=(IQ)-1,称B为基矩阵基矩阵定定理理C3.吸收链的基矩阵B中的每个元素,表示过程从一个非吸收状态出发到达每个非吸收状态的平均转移次数定定理理C4.设N=BC,B为吸收链的基矩阵,C=(1,1,1)T,则N的每个元素表示从非吸收状态出发,到达某个吸收状态被吸收之前的平均转移次数定定理理C5.设F=BR=(fij),其中B为吸收链的基矩阵,R为T中的子阵,则fij表

10、示从非吸收状态i出发,被吸收状态 j吸收的概率例例C1.1(竞赛问题竞赛问题)甲乙两队进行一场抢答竞赛,竞赛规则规定:开始时每队各记2分,抢答题开始后,如甲取胜则甲加1分而乙减1分,反之则乙加1分甲减1分(每题必需决出胜负)规则还规定,当其中一方的得分达 到4分时,竞赛结束求:(1)甲队获胜的概率有多大?(2)竞赛从开始到结束,平均转移的次数为多少?(3)甲获得1、2、3分的平均次数是多少?设甲取胜一题的概率为p (0p1),p与两队的实力有关甲队得分有5种可能,即0,1,2,3,4我们分别记为状态S0,S1,S2,S3,S4,其中S0和S4是吸收状态,S1,S2和S3是非吸收状态过程以S2作为初始状态根据甲队赢得1分的概率为p,建立转移矩阵P:S 0 S 1 S 2 S 3 S 4 将上式改记为标准形 式T:其中计算基矩阵B:记q=1-p,则因为S2是初始状态,根据定理C3,甲队获分为1,2,3分的平均次数为 又 根据定理C4,以S2为初始状态,甲队最终获胜的平均转移次数为又因为根据定理C5,甲队最后获胜的概率。练习练习(例(例3.1):老鼠在迷宫里找奶酪问题老鼠在遇到猫之前找到奶酪的概率THANK YOUSUCCESS2023/4/943可编辑

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 生活休闲 > 生活常识

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁