马尔可夫链预测

1、马尔可夫预测马尔可夫预测马尔可夫链的基本原理马尔可夫预测方法及应用1马尔可夫过程指满足无后效性的随机过程一、马尔可夫链1. 1. 马尔可夫链的基本概念马尔可夫链的基本概念2马尔可夫过程指满足无后效性的随机过程定义定义1 1 若非负随机序列X(tn),nN满足条件一、马尔可夫链1. 1. 马尔可夫链的基本概念马尔可夫链的基本概念则称随机序列X(tn)为马尔科夫链，简称马氏链。3马尔可夫过程指满足无后效性的随机过程定义定义1 1 若非负随机序列X(tn),nN满足条件无后效性指“将来”取什么值只与“现在”的取值有关，而与“过去”取什么值无关。一、马尔可夫链1. 1. 马尔可夫链的基本概念马尔可夫链

2、的基本概念则称随机序列X(tn)为马尔科夫链，简称马氏链。4二、状态转移概率矩阵二、状态转移概率矩阵5二、状态转移概率矩阵二、状态转移概率矩阵当系统由一种状态变为另一种状态时，称为状态转移状态转移。 6二、状态转移概率矩阵二、状态转移概率矩阵当系统由一种状态变为另一种状态时，称为状态转移状态转移。 定义定义2 2 一步状态转移概率一步状态转移概率(1)1ijijnnppP Xj Xi10, 1Nijijjpp1nnXiXjij若由转移到的概率p 与n无关,则称该马尔可夫链是齐次的。7几个概念：几个概念：8几个概念：几个概念： 概率向量：概率向量：对于任意的行向量（或列向量），如果其每个元素均非

3、负且总和等于1，则称该向量为概率向量。 9几个概念：几个概念： 概率向量：概率向量：对于任意的行向量（或列向量），如果其每个元素均非负且总和等于1，则称该向量为概率向量。 (0.4,0.25,0.25,0.1)u 10几个概念：几个概念： 概率向量：概率向量：对于任意的行向量（或列向量），如果其每个元素均非负且总和等于1，则称该向量为概率向量。 (0.4,0.25,0.25,0.1)u 概率向量概率向量11几个概念：几个概念： 概率向量：概率向量：对于任意的行向量（或列向量），如果其每个元素均非负且总和等于1，则称该向量为概率向量。 概率矩阵概率矩阵 由概率向量作为行向量行向量所构成的方阵称为

4、概率矩阵。 (0.4,0.25,0.25,0.1)u 概率向量概率向量0.70.30.50.5A12概率矩阵的性质：如果A、B 皆是概率矩阵，则AB也是概率矩阵；如果A是概率矩阵，则A的任意次幂 也是概率矩阵。 (1)mAm 13概率矩阵的性质：如果A、B 皆是概率矩阵，则AB也是概率矩阵；如果A是概率矩阵，则A的任意次幂 也是概率矩阵。 (1)mAm 一步状态转移概率矩阵一步状态转移概率矩阵ijp与n n无关假设：（齐次性）（齐次性）111212122212NNNNNNppppppPpppLLLLLLL14k步状态转移概率 ,kijn knkkijN NpP Xj XiPp1k 称 为k步状

5、态转移概率， 为k步状态转移概率矩阵， kijp kP( )( )( )11121( )( )( )( )21222( )( )( )12kkkNkkkkNkkkNNNNppppppPpppLLLLLLL15 马尔可夫链中任何k步状态转移概率都可由1步状态转移概率求出。 16 马尔可夫链中任何k步状态转移概率都可由1步状态转移概率求出。 全概率公式17 马尔可夫链中任何k步状态转移概率都可由1步状态转移概率求出。 PPPkk)1()( 1,kPPkkP 一步状态转移概率矩阵( )kP k 步状态转移概率矩阵全概率公式18三、平稳分布与稳态分布三、平稳分布与稳态分布19三、平稳分布与稳态分布三、

6、平稳分布与稳态分布1. 1. 平稳分布平稳分布20三、平稳分布与稳态分布三、平稳分布与稳态分布1. 1. 平稳分布平稳分布 如 为一状态概率向量，P P为状态转移概率矩阵。若XPX则称 X X 为马尔可夫链的一个平稳分布平稳分布。12,NXxxxL211. 1. 平稳分布平稳分布 如 为一状态概率向量，P P为状态转移概率矩阵。若XPX则称 X X 为马尔可夫链的一个平稳分布平稳分布。12,NXxxxL 若随机过程某时刻的状态概率向量为平稳分布，则称过程处于平衡状态平衡状态。 一旦过程处于平衡状态，则过程经过一步或多步状态转移之后，其状态概率分布保持不变，即，过程一旦处于平衡状态后将永远处于平

7、衡状态。 三、平稳分布与稳态分布三、平稳分布与稳态分布222. 稳态分布问题：问题：对于系统的状态P P( (m m) )，当 m m 趋于无穷时，是否存在极限？232. 稳态分布问题：问题：对于系统的状态P P( (m m) )，当 m m 趋于无穷时，是否存在极限？1212lim( )lim( )( )( )(,.,)NmmNP mp mp mpm （，.,）若存在，设其极限为 ，242. 稳态分布问题：问题：对于系统的状态P P( (m m) )，当 m m 趋于无穷时，是否存在极限？1212lim( )lim( )( )( )(,.,)NmmNP mp mp mpm （，.,） lim

8、jjmpm若存在，设其极限为 ，252. 稳态分布问题：问题：对于系统的状态P P( (m m) )，当 m m 趋于无穷时，是否存在极限？1212lim( )lim( )( )( )(,.,)NmmNP mp mp mpm （，.,） limjjmpm ()()11limlim00 limNNmmjiijiijmmmiipmpppp若存在，设其极限为 ，26则称 为稳态分布稳态分布。 定义定义 对于概率向量 ，如对任意的 ，均有12,.,N Sji,()limmijjmp27则称 为稳态分布稳态分布。 定义定义 对于概率向量 ，如对任意的 ，均有12,.,N Sji,()limmijjmp

9、()()11limlim00 limNNmmjiijiijmmmiipmpppp此时，不管初始状态概率向量如何，均有 11(0)(0)NNijjijiipp这也是称 为稳态分布的理由。 28 设存在稳态分布 ，则由于下式恒成立12,.,N 1P kP kP29 设存在稳态分布 ，则由于下式恒成立12,.,N 1P kP kPkP令 ，得30 设存在稳态分布 ，则由于下式恒成立12,.,N 1P kP kPkP令 ，得即，有限状态马尔可夫链的稳态分布如存在，那么它也是平稳分布。31 1.对非周期的马尔可夫链，稳态分布必存在。两个结论：2.对不可约非周期的马尔可夫链，稳态分布和平稳分布相同且均唯一

10、。(),1,2,0,miji jSSNpL不可约（不可分）：存在自然数m,对使称马尔可夫链是不可约的。( ) |01kiik pi非周期：若正整数集的最大公约数为 ，则称状态 是非周期的。若所有状态均为非周期的，则称该马氏链为非周期的。322. 2. 马尔可夫预测方法及应用马尔可夫预测方法及应用 马尔可夫预测是应用随机过程中马尔可夫链的理论和方法，研究分析有关现象的变化规律并借此对未来进行预测的一种方法。市场占有率预测高速公路交通量分布预测期望利润预测332. 2. 马尔可夫预测方法及应用马尔可夫预测方法及应用一、市场占有率预测一、市场占有率预测34一、市场占有率预测一、市场占有率预测 例例

11、公司A、B、C产品销售额的市场占有率分别为50%，30%，20%。由于C公司实行了改善销售与服务方针的经营管理决策，使其产品销售额逐期稳定上升，而A公司却下降。通过市场调查发现三个公司间的顾客流动情况如表所示。其中产品销售周期是季度。问题：按照目前的趋势发展下去，A公司的产品销售额或客户转移的影响将严重到何种程度？更全面的，三个公司的产品销售额的占有率将如何变化？2. 2. 马尔可夫预测方法及应用马尔可夫预测方法及应用35周期周期 1 的供应公司的供应公司 公司公司 周期周期 0 的的顾客数顾客数 A B C A 5000 3500 500 1000 B 3000 300 2400 300 C

12、 2000 100 100 1800 周期周期 1 的的顾客数顾客数 3900 3000 3100 36公司公司 A B C A 3500/5000=0.7 500/5000=0.1 1000/5000=0.2 B 300/3000=0.1 2400/3000=0.8 300/3000=0.1 C 100/2000=0.05 100/2000=0.05 1800/2000=0.95 周期周期 1 的供应公司的供应公司 公司公司 周期周期 0 的的顾客数顾客数 A B C A 5000 3500 500 1000 B 3000 300 2400 300 C 2000 100 100 1800 周

13、期周期 1 的的顾客数顾客数 3900 3000 3100 37公司公司 A B C A 3500/5000=0.7 500/5000=0.1 1000/5000=0.2 B 300/3000=0.1 2400/3000=0.8 300/3000=0.1 C 100/2000=0.05 100/2000=0.05 1800/2000=0.95 ABCA0.70.10.2B0.10.80.1C0.050.050.9P(0)(0.5 0.3 0.2)P周期周期 1 的供应公司的供应公司 公司公司 周期周期 0 的的顾客数顾客数 A B C A 5000 3500 500 1000 B 3000 3

14、00 2400 300 C 2000 100 100 1800 周期周期 1 的的顾客数顾客数 3900 3000 3100 38未来各期的市场占有率： 100.70.10.20.5,0.3,0.20.10.80.10.050.050.90.39,0.3,0.31PPP39未来各期的市场占有率： 100.70.10.20.5,0.3,0.20.10.80.10.050.050.90.39,0.3,0.31PPP(2)(1)(0.319,0.294,0.387)PPP40未来各期的市场占有率： 100.70.10.20.5,0.3,0.20.10.80.10.050.050.90.39,0.3,

15、0.31PPP(2)(1)(0.319,0.294,0.387)PPP(3)(2)(0.272,0.286,0.442)PPP41未来各期的市场占有率： 100.70.10.20.5,0.3,0.20.10.80.10.050.050.90.39,0.3,0.31PPPC保销政策。C的市场份额不断增大。是否可以持续下去？(2)(1)(0.319,0.294,0.387)PPP(3)(2)(0.272,0.286,0.442)PPP42稳态市场占有率 43稳态市场占有率 1231231230.70.10.2,0.10.80.1,0.050.050.91x xxx xxxxx44稳态市场占有率 1

16、231231230.70.10.2,0.10.80.1,0.050.050.91x xxx xxxxx1230.1765,0.2353,0.5882xxx解得45(0)(0.5 0.3 0.2)P1230.1765,0.2353,0.5882xxx46(0)(0.5 0.3 0.2)P1230.1765,0.2353,0.5882xxx上述结果对A厂不利。A厂制定两套方案：47(0)(0.5 0.3 0.2)P1230.1765,0.2353,0.5882xxx上述结果对A厂不利。A厂制定两套方案：甲方案甲方案 保留策略，拉住老顾客。48(0)(0.5 0.3 0.2)P1230.1765,0

17、.2353,0.5882xxx上述结果对A厂不利。A厂制定两套方案：甲方案甲方案 保留策略，拉住老顾客。0.850.100.050.100.800.100.050.050.90P甲ABCA0.70.10.2B0.10.80.1C0.050.050.9P49 新的平衡状态下、三公司的市场占有率分别为31.6，26.3，42.1，公司的市场占有率从17.65提高到31.6。 50 新的平衡状态下、三公司的市场占有率分别为31.6，26.3，42.1，公司的市场占有率从17.65提高到31.6。 乙方案乙方案 争取策略，挖客户。0.700.100.200.150.750.100.150.050.80

18、P乙51 新的平衡状态下、三公司的市场占有率分别为31.6，26.3，42.1，公司的市场占有率从17.65提高到31.6。 乙方案乙方案 争取策略，挖客户。0.700.100.200.150.750.100.150.050.80P乙 在新的平衡状态下，、三家公司的市场占有率分别为33.3，22.2，44.5。 52二、高速公路交通量分布预测二、高速公路交通量分布预测 为研究高速公路收费标准调整对交通量的影响，我们选取京珠高速公路郑州十八里河至漯河陈桥段和与之平行的107国道2003年4月份、5月份和6月份的交通量，用车牌号调查法进行调查，得到数据如表1所示。 53 可以算出，5月份的状态概率

19、矩阵为P(5月)=（0.351,0.469,0.180）转移概率矩阵为转移概率矩阵为6月份的状态概率矩阵为P(6月)=（0.350,0.470,0.180）5月份与6月份的转移概率矩阵近似相等，因而系统可以近似看作是一个齐次马氏链。54取初始状态概率为P(0)=（0.35,0.47,0.18）转移概率矩阵为由初始状态概率和初始状态概率矩阵可以算出一个月后的状态概率为P(1)=P(0)P=（0.313,0.477,0.210）两个月后的状态概率为P(2)=P(0)P2=（0.290,0.481,0.229）55同理可以算出几个月后的状态概率,如表2所示：56从表2可以看出，高速公路在交通量分配中

20、所占比例是在逐步降低，国道所占比例略有上升，交通量大多转移到了其它路线或其它运输方式。 当时间充分大时，转移概率将趋于稳定，设稳定状态的概率矩阵为（P1,P2,P3），由遍历性定理得解得P1=0.249,P2=0.481,P3=0.270从上述分析可以看出，在各种情况都不改变的条件下，最终车流量的分布将稳定在高速公路占24.9%、国道占48.1%、其它占27%的比例。57 结论：交通量的大小决定高速公路效益的高低。当从起点到终点的运输方式和运输线路不唯一时，收费标准将直接影响到交通量的大小。收费率越高，用户选择高速公路机会就越低。从上面的研究结果可以看出高速公路在交通量分配中所占比例大约降低了

21、10%。58三、期望利润预测三、期望利润预测59三、期望利润预测三、期望利润预测设 是状态空间为 的齐次马氏链，其转移矩阵为 。设r(i)表示某周期系统处于状态i时获得的报酬。称如此的马尔可夫链是具有报酬的。r(i)0时称为盈利，报酬，收益等；r(i)0时称为亏损，费用等。nX1,2,.,SN()ijN NPp60 有限时段期望总报酬有限时段期望总报酬 61记 表示初始状态为 i i 的条件下，到第k步状态转移前所获得的期望总报酬(k k11，i iS S)： ( )kv i 有限时段期望总报酬有限时段期望总报酬 62记 表示初始状态为 i i 的条件下，到第k步状态转移前所获得的期望总报酬(

22、k k11，i iS S)： ( )kv i10( )kknv in第 期的期望报酬100 ()knnE r XXi1( )01( )kNnijnjpr j 有限时段期望总报酬有限时段期望总报酬 63(1),(2),.,()TkkkkVvvvN( (1), (2),()Trrrr NL ，记64(1),(2),.,()TkkkkVvvvN( (1), (2),()Trrrr NL ，1210()knkknVP rIPPPrL记有65(1),(2),.,()TkkkkVvvvN( (1), (2),()Trrrr NL ，1210()knkknVP rIPPPrL11( )( )( ),0,1,

23、2,Nkijkjvir ip vjkiNL ，0( )0,1,2,v iiN，L记有66 例例 某商品每月市场状况有畅销和滞销两种。如果产品畅销则获利50万元；滞销将亏损30万元。已知状态转移概率矩阵如下：试问：如当前月份该产品畅销，则第四月前所获得的期望总利润为多少？111221220.50.50.780.22ppPpp67(1)50(2)30rrr0.50.50.780.22P解：由题意知68(1)50(2)30rrr0.50.50.780.22P4 12340()()nnVP rIP PP r41.8750.8755067.51.862950.279053084.776V解：由题意知69

24、(1)50(2)30rrr0.50.50.780.22P4 12340()()nnVP rIP PP r41.8750.8755067.51.862950.279053084.776V4(1)67.5v结果为：如当前月份该产品畅销，第四月前所结果为：如当前月份该产品畅销，第四月前所获得的期望总利润为获得的期望总利润为67.567.5万。万。解：由题意知70 无限时段单位时间平均报酬无限时段单位时间平均报酬 71 对iS，定义初始状态为i的无限时段单位时间平均报酬为：( )lim( )/kkv iv ik 无限时段单位时间平均报酬无限时段单位时间平均报酬 72 对iS，定义初始状态为i的无限时段

25、单位时间平均报酬为：( )lim( )/kkv iv ik(1),(2),.,()TkkkkVvvvN (1) (2) . ()Tvvvv N记 无限时段单位时间平均报酬无限时段单位时间平均报酬 73 对iS，定义初始状态为i的无限时段单位时间平均报酬为：( )lim( )/kkv iv ik21(.)limlimkkkkVIPPPrvkk(1),(2),.,()TkkkkVvvvN (1) (2) . ()Tvvvv N记则1210()knkknVP rIPPPrL 无限时段单位时间平均报酬无限时段单位时间平均报酬 7421(.)limlimkkkkVIPPPrvkk可以证明：limkkP

26、r121212.(1).(2).()NNNrrr N111( )( ).( )NjjNjjNjjr jr jr j7521(.)limlimkkkkVIPPPrvkk可以证明：limkkP r121212.(1).(2).()NNNrrr N111( )( ).( )NjjNjjNjjr jr jr j即，无限时段单位时间平均报酬与初始状态无关，均为1( )( )Njjv ir j76 无限时段期望折扣总报酬无限时段期望折扣总报酬77考虑资金的时间价值 无限时段期望折扣总报酬无限时段期望折扣总报酬78如将钱存于银行，年息为 ，则 与 有如下关系： 考虑资金的时间价值 (0,1)r11r 无限时

27、段期望折扣总报酬无限时段期望折扣总报酬 ，称 为折扣因子折扣因子。r79 0ttvitiS第 期的期望报酬，对有报酬的马氏链，定义从状态i i 出发的无限时段期望折扣总报酬为80 0ttvitiS第 期的期望报酬， ( )0ttijjtvip r j对有报酬的马氏链，定义从状态i i 出发的无限时段期望折扣总报酬为于是，81 0ttvitiS第 期的期望报酬， ( )0ttijjtvip r j 1 ,2 ,.,TVvvvN10tttVP rIPr对有报酬的马氏链，定义从状态i i 出发的无限时段期望折扣总报酬为于是，记则82称 为具有报酬的马氏链的三种目标函数。利用其中的任一个目标函数，可以

28、讨论不同策略的优劣。 ,kviv ivi 例例 最佳维修策略的选择。研究一化工企业对循环泵进行季度维修的过程。每次检查中，把泵按其外壳及叶轮的腐蚀程度定为五种状态中的一种。这五种状态是： 状态状态1 1：优秀状态，无任何故障或缺陷；：优秀状态，无任何故障或缺陷； 状态状态2 2：良好状态，稍有腐蚀；：良好状态，稍有腐蚀； 状态状态3 3：及格状态，轻度腐蚀；：及格状态，轻度腐蚀； 状态状态4 4：可用状态，大面积腐蚀；：可用状态，大面积腐蚀； 状态状态5 5：不可运行状态，腐蚀严重。：不可运行状态，腐蚀严重。83该公司可采用的维修策略有以下几种： 单状态策略：单状态策略：泵处于状态5时才进行修

29、理，每次修理费用为500元。 两状态策略两状态策略：泵处于状态4和5时进行修理，处于状态4时的修理费用每次为250元, 处于状态5时的每次修理费用为500元。 三状态策略：三状态策略：泵处于状态3,4,5时进行修理，处于状态3时的每次修理费用为200元,处于状态4和5时的修理费用同前。 目前，该公司采用的维修策略为“单状态”策略。 假定不管处于何种状态，只要进行修理，泵的状态都将恢复为状态1。已知在不进行任何修理时的状态转移概率，如下表所示。84泵在周期泵在周期 n+1 的状态的状态 泵在周期泵在周期n 的状态的状态 1 2 3 4 5 1 0.00 0.60 0.20 0.10 0.10 2

30、 0.00 0.30 0.40 0.20 0.10 3 0.00 0.00 0.40 0.40 0.20 4 0.00 0.00 0.00 0.50 0.50 5 0.00 0.00 0.00 0.00 1.00 8500.60.20.10.100.30.40.20.1000.40.40.20000.50.500001P 1( )( )Njjv ir j需知 r 和 P.P不维修时的状态转移概率矩阵：泵在周期泵在周期 n+1 的状态的状态 泵在周期泵在周期n 的状态的状态 1 2 3 4 5 1 0.00 0.60 0.20 0.10 0.10 2 0.00 0.30 0.40 0.20 0.

31、10 3 0.00 0.00 0.40 0.40 0.20 4 0.00 0.00 0.00 0.50 0.50 5 0.00 0.00 0.00 0.00 1.00 861P(0 0 0 0 500)Tr 单状态策略下单状态策略下：100.60.20.10.100.30.40.20.1000.40.40.20000.50.510000P 871P0.199,0.170,0.180,0.252,0.199(0 0 0 0 500)Tr 单状态策略下单状态策略下：100.60.20.10.100.30.40.20.1000.40.40.20000.50.510000P 解得：881P0.199,0.170,0.180,0.252,0.199 500 0.19999.5jv ir j(0 0 0 0 500)Tr 单状态策略下单状态策略下：100.60.20.10.100.30.40.20.1000.40.40.20000.50.510000P 解得：从而89(0 0 0 250 500)Tr 两状态策略下：两状态策略下：2P90(0 0 0 250 500)Tr 两状态策略下：两状态策略下：200.60.20.10.100.30.40.20.1000.40.40.21000010000P 00.60.20.10.10