《第8讲 第4章马尔科夫链(3).ppt》由会员分享，可在线阅读，更多相关《第8讲 第4章马尔科夫链(3).ppt（42页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、4.3 4.3 状态空间的分解状态空间的分解 定义定义：C C为状态空间为状态空间I I的子集，的子集，则称则称C C为为I I的闭集。的闭集。引理引理4.44.4：若：若C C为状态空间为状态空间I I的闭子集，则对任意的闭子集，则对任意若对任意的若对任意的显然显然：若：若C C为状态空间为状态空间I I的闭子集，则的闭子集，则C C中元素形成的中元素形成的转移概率子矩阵转移概率子矩阵是随机矩阵是随机矩阵12341110.80.2例如：例如：从下面状态空间为从下面状态空间为I=1,2,3,4的马尔科夫链的转的马尔科夫链的转移概率图可以看到移概率图可以看到2,3是一个闭集是一个闭集2,3对应的
2、子矩阵对应的子矩阵(粉色部分）粉色部分）是随机矩阵。是随机矩阵。注意到：注意到：2,3，4也是闭集也是闭集2,3，4对应的子矩阵（绿色部分）对应的子矩阵（绿色部分）也是随机矩阵。也是随机矩阵。12341110.80.2但是闭集但是闭集2,3中的两个状态互通中的两个状态互通而闭集而闭集2,3，4中的中的3个状态不是互个状态不是互通的。通的。3不可达不可达4。同样同样I=1，2,3，4也可以看做闭集，也可以看做闭集，但其中的但其中的的的4个状态不是互通的。个状态不是互通的。为区别状态子集的这种不同特点，引入不可约子集的为区别状态子集的这种不同特点，引入不可约子集的概念：概念：定义定义：若：若C C
3、为状态空间为状态空间I I的闭子集，且的闭子集，且C C中任意两个状中任意两个状态互通，则称态互通，则称C C是是I I的不可约闭集；的不可约闭集；特别：特别：若若MarkovMarkov链链I I的任意两个状态互通，则称该的任意两个状态互通，则称该MarkovMarkov链是不可约的。链是不可约的。例例6：证明（马尔科夫链的常返态的几个性质）证明（马尔科夫链的常返态的几个性质）则表明由则表明由 出发不能概率出发不能概率1 1返回返回 ，证明证明（1 1）所以存在所以存在n 0 使使则导致由则导致由 出发不能概率出发不能概率1 1返回返回 ，（2）和）和（1）的证明类似。）的证明类似。（3）由
4、（由（2）知，）知，本例是马尔科夫链的常返态的一个重要性质！本例是马尔科夫链的常返态的一个重要性质！据此可对是马尔科夫链进行状态分解：据此可对是马尔科夫链进行状态分解：定理定理4.104.10：任一马氏链的状态空间任一马氏链的状态空间I I，都可以唯一分，都可以唯一分解为互不相交的子集解为互不相交的子集 之和：之和：其中其中是所有非常返态的集合。是所有非常返态的集合。是不可约的常返闭集是不可约的常返闭集注注1 1：注注2 2：是所有非常返态的集合，其中各状态未必互是所有非常返态的集合，其中各状态未必互通，周期也未必相同。通，周期也未必相同。注注3 3：证明证明首先将状态空间按个状态的常返性分解
5、为：首先将状态空间按个状态的常返性分解为：然后，将然后，将 进一步分解：进一步分解：作作作作同理，同理，是不可约的常返闭集。是不可约的常返闭集。重复此过程，得重复此过程，得是不可约的常返闭集是不可约的常返闭集为常返集，为常返集，为非常返集。为非常返集。证毕！证毕！华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞4.44.4的渐近性质与平稳分布的渐近性质与平稳分布定理定理*：证明：证明：一、一、的渐近性质的渐近性质华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞为非常返，或零常返时，为非常返，或零常返时，并注意到并注意到得：为正常返为正常返 时，时，得：为正常返为正常返 时：时：华北
6、电力大学数理学院华北电力大学数理学院 何凤霞何凤霞注注 若马氏链不可约，若马氏链不可约，此时该链所有的状态属性相同。此时该链所有的状态属性相同。若不可约马氏链为正常返非周期的，则：若不可约马氏链为正常返非周期的，则：若全为非常返或零常返的，或为正常返常周期的，若全为非常返或零常返的，或为正常返常周期的，极限结论和极限结论和定理定理*相同。相同。华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞 MarkovMarkov链极限研究中，对链极限研究中，对状态状态i常返特性的正判别和常返特性的正判别和i的平均返回时间的平均返回时间 是是两个关键的问题。两个关键的问题。下面我们给出在常见的有限维状
7、态空间时状态常返性下面我们给出在常见的有限维状态空间时状态常返性的一些结论；的一些结论；但是利用定义判别和计算都比较困难。但是利用定义判别和计算都比较困难。然后然后我们介绍平稳分布，并利用平稳分布我们介绍平稳分布，并利用平稳分布，计算，计算 并并研究研究MarkovMarkov链极限链极限华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞推论推论1 1：（1 1）有限马氏链，至少有一个正常返态，不可能）有限马氏链，至少有一个正常返态，不可能 有零常返态有零常返态若所有的状态为非常返或零常返，那么若所有的状态为非常返或零常返，那么证明：（证明：（1 1）试中令试中令 得：得：0=10=1，矛
8、盾。，矛盾。所以，有限马氏链必有正常返态。所以，有限马氏链必有正常返态。（*）（*）设有限马科科夫链有设有限马科科夫链有N N个状态，则个状态，则（2 2）有限不可约马氏链，所有的状态必为正常返！）有限不可约马氏链，所有的状态必为正常返！二、有限马氏链的状态特点二、有限马氏链的状态特点根据定理根据定理*，有：，有：华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞若有限马科科夫链存在零常返状态若有限马科科夫链存在零常返状态i，构造状态空间的子集：构造状态空间的子集：则则C(i)是不可约有限闭集，形成子马尔科夫链。是不可约有限闭集，形成子马尔科夫链。而而C(i)中的所有状态为零常返，中的所有
9、状态为零常返，所以，有限马氏链不存在零常返态。所以，有限马氏链不存在零常返态。这与有限马尔科夫链必有正常返态矛盾。这与有限马尔科夫链必有正常返态矛盾。（2 2）根据（根据（1 1）有限马氏链，至少有一个正常返态，有限马氏链，至少有一个正常返态，而不可约马尔科夫链所有的状态具有相同的常返而不可约马尔科夫链所有的状态具有相同的常返性，故全为正常返态。性，故全为正常返态。也称为正常返链。也称为正常返链。推论推论2 2：马氏链若有零常返态，则必有无穷多个零常返态马氏链若有零常返态，则必有无穷多个零常返态华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞三、平稳分布三、平稳分布定义定义4.11则称则
10、称 为该马氏链的为该马氏链的 平稳分布平稳分布注：注：即：即：若若 为马氏链为马氏链 的的 平稳分布，则平稳分布，则即：即：表明表明 Markov Markov链一旦在某个时刻进入平稳分布，则以后链一旦在某个时刻进入平稳分布，则以后的绝对概率分布保持不变，这也是的绝对概率分布保持不变，这也是“平稳平稳”的含义。的含义。华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞定理定理4.16 4.16 不可约非周期的马氏链，是正常返的充不可约非周期的马氏链，是正常返的充要条件是存在平稳分布，且此平稳分布就是极限分布：要条件是存在平稳分布，且此平稳分布就是极限分布：证明：证明：充分性：充分性：设设
11、为马氏链为马氏链 的的 平稳分布，则平稳分布，则故上式右端求极限可以和级数交换次序。故上式右端求极限可以和级数交换次序。与与 矛盾，矛盾，所以该链必为正常返链。所以该链必为正常返链。若链不为正常返（则为非常返，或零常返），则：若链不为正常返（则为非常返，或零常返），则：华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞必要性：必要性：设该马氏链是正常返的，所以有：设该马氏链是正常返的，所以有：华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞矛盾。矛盾。所以：所以：为该马氏链的平稳分布。为该马氏链的平稳分布。所以，马氏链存在平稳分布，且极限分布所以，马氏链存在平稳分布，且极限分布 华北
12、电力大学数理学院华北电力大学数理学院 何凤霞何凤霞定理：定理：则绝对分布也有极限分布，且：则绝对分布也有极限分布，且：证明证明 若转移概率具有极限分布：若转移概率具有极限分布：华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞例例1 1：设马尔科夫链的转移概率矩阵为：设马尔科夫链的转移概率矩阵为 求马尔科夫链的极限分布及各状态的平均返回时间求马尔科夫链的极限分布及各状态的平均返回时间 解解：这是一个不可约非周期，有限状态的马氏链，：这是一个不可约非周期，有限状态的马氏链，所以必有极限分布，且极限分布就是平稳分布。所以必有极限分布，且极限分布就是平稳分布。及及 华北电力大学数理学院华北电力大
13、学数理学院 何凤霞何凤霞由方程组：由方程组：解得：解得：状态状态1 1、2 2、3 3的平均返回时间依次是：的平均返回时间依次是：即：即：5.66575.6657、4.24994.2499、1.70011.7001 华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞带有两个反射壁的随机游动带有两个反射壁的随机游动,其转移概率阵为：其转移概率阵为：解解例例2 2这是一个不可约非周期，有限状态的马氏链，这是一个不可约非周期，有限状态的马氏链，所以必有极限分布，且极限分布就是平稳分布。所以必有极限分布，且极限分布就是平稳分布。求其极限分布求其极限分布.华北电力大学数理学院华北电力大学数理学院 何
14、凤霞何凤霞即：即：得：得：代入最后一个方程代入最后一个方程(归一条件归一条件),得唯一解得唯一解华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞所以极限分布为所以极限分布为这个这个分布表明分布表明经过长时间游动之后经过长时间游动之后,醉汉醉汉 Q 位于点位于点 2(或或 3 或或 4)的概率约为的概率约为 3/11,位于点位于点 1(或或 5)的概率约为的概率约为 1/11.华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞例例3 3 某地区有某地区有16001600户居民户居民,只有甲、乙、丙三个工厂只有甲、乙、丙三个工厂的某产品在该地区销售。据调查，的某产品在该地区销售。据调查，
15、8 8月份买甲乙丙产月份买甲乙丙产品的户数为别为品的户数为别为480480，320320，800800。9 9月份调查发现，原月份调查发现，原买甲的有买甲的有4848户转买乙产品，户转买乙产品，9696户转买丙产品；原买户转买丙产品；原买乙的有乙的有3232户转买甲产品，户转买甲产品，6464户转买丙产品；原买丙户转买丙产品；原买丙的有的有6464户转买甲产品，户转买甲产品，3232户转买乙产品；户转买乙产品；预测预测（1 1）9 9月份和月份和1212月份格产品的市场占有率月份格产品的市场占有率 （2 2）市场平稳后，各产品的市场占有率）市场平稳后，各产品的市场占有率解：解：若将此市场的变化
16、看作齐次马尔可夫链。状若将此市场的变化看作齐次马尔可夫链。状态态1 1，2 2，3 3分别表示甲、乙、丙工厂的产品。分别表示甲、乙、丙工厂的产品。华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞那么初始分布：那么初始分布：转移频数阵：转移频数阵：频数阵的第频数阵的第1 1，2 2，3 3行非别除以行非别除以480480，320320，800800，得转移概率阵：得转移概率阵：华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞市场平稳后，格产品的市场占有率即平稳分布。市场平稳后，格产品的市场占有率即平稳分布。9 9月份市场占有率月份市场占有率1212月份市场占有率月份市场占有率解得解得
17、市场平稳后，甲乙丙产品占市场的份额分别为：市场平稳后，甲乙丙产品占市场的份额分别为：21.9%,15.6%,62.5%21.9%,15.6%,62.5%华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞例例4：设农用拖拉机站每季度对拖拉机进行一次检查和设农用拖拉机站每季度对拖拉机进行一次检查和维修。根据零件磨损程度将拖拉机分为维修。根据零件磨损程度将拖拉机分为5类：类：状态状态12345运行效运行效率（率（%)%)90-10075-8960-74 40-59不运行不运行当拖拉机处于当拖拉机处于1，2，3，4，5时，估计一季度可获利时，估计一季度可获利润分别为润分别为5000、4000、30
18、00、2000和和0元。根据过去元。根据过去的资料，拖拉机的磨损状态的自然转移概率阵为：的资料，拖拉机的磨损状态的自然转移概率阵为：华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞有有3种维修策略，分别是：处于状态种维修策略，分别是：处于状态5时维修，处时维修，处于状态于状态4，5时维修，处于状态时维修，处于状态3，4，5时维修，处时维修，处于状态于状态3时维修，修理费用平均要时维修，修理费用平均要300元，处于状元，处于状态态4时维修，修理费用平均要时维修，修理费用平均要500元，处于状态元，处于状态5时时维修，修理费用平均要维修，修理费用平均要1000元。问，从长远考虑，元。问，从长
19、远考虑，为了得到更多的利润，哪种维修策略最好？为了得到更多的利润，哪种维修策略最好？华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞解解：对于第一种大修策略，处于状态：对于第一种大修策略，处于状态5时维修，转移时维修，转移概率阵为概率阵为的极限分布的极限分布由由解得解得平均利润平均利润平均维修费用：平均维修费用：平均净利润平均净利润:2722-199=2523华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞对于第二种大修策略，转移概率阵为对于第二种大修策略，转移概率阵为由由解得解得平均利润平均利润平均维修费用：平均维修费用：平均净利润平均净利润:2998-181=2817=2998
20、.6华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞对于第三种大修策略，转移概率阵为对于第三种大修策略，转移概率阵为由由解得解得平均利润平均利润平均维修费用：平均维修费用：平均净利润平均净利润:3539-169.5=3369.5=3539华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞所以第三种大修策略好，即在每年的检修中，发所以第三种大修策略好，即在每年的检修中，发现拖拉机到了现拖拉机到了3，4或或5状态，就要及时大修。状态，就要及时大修。华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞四、一般四、一般可约马氏链可约马氏链P P中的中的 分析分析对于不可约马尔科夫链，通过平
21、稳分布比较好地解决对于不可约马尔科夫链，通过平稳分布比较好地解决了的极限分布了的极限分布 问题。问题。对于一般可约马氏链，需要先对马氏链的状态空间对于一般可约马氏链，需要先对马氏链的状态空间进行分解，然后再讨论进行分解，然后再讨论设状态空间分解为：设状态空间分解为：一般一般可约马氏链可约马氏链P P中的中的 分析分析华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞解解 对应的平稳分布即得对应的平稳分布即得 ：（3)3)则利用下面的方法求极限：则利用下面的方法求极限：华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞123465例例5 马氏链的概率转移图所示，分析转移概率极限马氏链的概
22、率转移图所示，分析转移概率极限:d=2,=2,不存在不存在0.310.10.10.40.11110.50.5(用平稳分布求解）用平稳分布求解）d=1=1华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞例例6 6：设马尔科夫链的转移概率矩阵为：设马尔科夫链的转移概率矩阵为 （1 1）求每一个不可约闭集的极限分布（）求每一个不可约闭集的极限分布（2 2）求）求解解（1 1）：这是一个可约马氏链。根据状态空间的分解）：这是一个可约马氏链。根据状态空间的分解定理，状态空间分解为：定理，状态空间分解为：华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞其中其中是非常返集是非常返集对应的转移概率
23、矩阵为对应的转移概率矩阵为 得其平稳分布：得其平稳分布：由方程组由方程组 ：1234657是常返闭集，非周期是常返闭集，非周期华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞对应的转移概率矩阵为对应的转移概率矩阵为 得其平稳分布：得其平稳分布：华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞解（解（2 2）：）：由于由于故从上式可解得：故从上式可解得：1234657华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞注：注：前面的关于前面的关于MarkovMarkov链的链的极限研究中知道，极限研究中知道，有时不存在，有时不存在，但事实上，此时的但事实上，此时的 依然存在，并有一般结论：依然存在，并有一般结论：（见本章定理（见本章定理4.154.15）特别：特别：华北电力大学数理学院华北电力大学数理学院 何凤霞何凤霞上式的概率解释：上式的概率解释：为为状态状态i的平均返回时间，的平均返回时间，就表示就表示j在单位时间内的平均返回次数在单位时间内的平均返回次数而而表示自表示自i出发在前出发在前n步返回步返回i的平均次数，的平均次数，内返回内返回i的平均次数的平均次数就表示马氏链自状态就表示马氏链自状态i出发单位时间出发单位时间所以有：所以有：