第8章-马尔可夫决策

1第8章马尔可夫决策8.1马尔可夫链的定义定义8.1设是一个随机序列，状态空间E为有限集，对于任意的正整数m，n若，有则称为一个马尔可夫链（简称马氏链）。定义8.2设是一个马氏链，如果等式（13）的右边的条件概率与n无关，即则称为齐次的马氏链。称为系统由状态i经过m个时间间隔（或步）转移到状态j的转移概率。（14）式称为齐次性。它的含义是：系统由状态i到状态j的转移概率只依赖于时间间隔的长短，与起始的时刻无关。以后无特殊的说明，马氏链都是齐次的。8.2转移概率矩阵及柯尔莫哥洛夫定理},2,1,{nn1,,2,1,,nkEijikijPiiijPnmnnnnmn1111,,,},2,1,{nn（1）},2,1,{nnmpijPijnmn（2）},2,1,{nnmpij2（1）转移概率矩阵对于一个马尔可夫链，称为由状态i经过m步转移到状态j的概率。其概率为：式中；例已知一次转移矩阵试求二次转移矩阵。解由公式（15）得：)()(mpmPijmnnnnnnijmpppppppppmpP212222111211)(（3）10,,mpEjiij1,mpEiEjij2.04.04.02.05.03.05.04.01.01P32.044.024.029.045.026.023.044.033.02.04.04.02.05.03.05.04.01.02.04.04.02.05.03.05.04.01.02P3（2）柯尔莫哥洛夫-开普曼方程由递推关系：…所以8.3应用问题（1）市场占有率的计算PSSmm1PSS012012PSPSS101mmPSS12122221112110101mnnnnnnmmpppppppppSPSS（5）（4）4例假设市场上有A、B、C三种品牌的方便面，经市场调查：上月购买A品牌的顾客，有60%在本月仍购买A品牌，有20%转移购买C品牌，有20%转移购买B品牌；上月购买B品牌的顾客，有70%在本月仍购买B品牌，有20%转移购买C品牌，有10%转移购买A品牌；上月购买C品牌的顾客，有80%在本月仍购买C品牌，有10%转移购买B品牌，有10%转移购买A品牌。上月市场占有率为：=（0.3，0.4，0.3）。试求本月和下月三种方便面的市场占有率。解：由已知条件构造转移矩阵：由公式（5），本月市场占有率：本月购买ABCABC8.01.01.02.07.01.02.02.06.0CCCBCABCBBBAACABAAPPPPPPPPP上月购买38.037.025.08.01.01.02.07.01.02.02.06.03.04.03.001，，，，CCCBCABCBBBAACABAAPPPPPPPPPSS5同理，可算出下月的市场占有率：（2）占有率平衡态决策当处于平衡态时，上月各牌的市场占有率等于本月市场占有率。其平衡态模型为：左式=令左式=右式，有428.0347.0225.080.010.010.020.070.010.020.020.060.03.04.03.02，，，，001SPPPPPPPPPSSCCCBCABCBBBAACABAA000000,,),,(CBACCCBCABCBBBAACABAACBASSSPPPPPPPPPSSS),,(000000000CCCBCBACACBCBBBABACACBABAAAPSPSPSPSPSPSPSPSPS6将转移概率代入上式：经整理，得去掉第三个多余方程，则000000000000CCCCBCBACABCBCBBBABAACACBABAAASPSPSPSSPSPSPSSPSPSPS18.02.02.01.07.02.01.01.06.0000000000000000CBACCBABCBAACBASSSSSSSSSSSSSSS102.02.02.001.03.02.001.01.04.0000000000000CBACBACBACBASSSSSSSSSSSS5.03.02.01002/12/1010/310/15/15/15/25/110011111113210S7即得（3）人力资源决策例某高校对教师进行分类，可分为5种状态：助教、讲师、副教授、教授、流失(退休)。目前状态向量：S0=（135，240，115，60，0）。根据历史资料，各类职称的转移概率矩阵为：试分析三年后的教师结构及三年内为保持编制不变应进多少研究生充实教师队伍。解；一年后的人员分布为：20.001AASS30.001BBSS50.001CCSS1000020.080.000024.021.055.00015.0025.060.0000040.060.0P76,72,123,198,811000020.080.000024.021.055.00015.0025.060.0000040.060.0)0,60,115,240,135(01PSS8由于要保持135+240+115+60+0=550人的总编制，流失走76人，因而第一年需进76位研究生充实教师队伍。此时人员分布为：S1=（81+76，198，123，72，0）=（157，198，123，72，0）第二年人员分布：第二年流失74人，因而补充74位研究生。各类人员的结构为S2=（168，182，117，83，0）第三年人员分布：74,83,117,182,941000020.080.000024.021.055.00015.0025.060.0000040.060.0)0,72,123,198,157(02PSS72,91,111,176.1011000020.080.000024.021.055.00015.0025.060.0000040.060.00,83,117,182,16823PSS9第三年流失72人，因而补充72位研究生。各类人员的结构为S3=（173，176，110，91，0）（4）吸收态马尔可夫链及应用基本概念：设有一四个状态马尔可夫链，其转移概率矩阵P为根据转移矩阵可以画出状态转移图，方框代表状态，箭头指向转移方向，箭头上数字表示转移概率，见图1。图1状态转移图100000004141414121213231P12341/41/41/41/31/22/311/21/410●连通性：对于马尔可夫链的状态空间S=（S1，S2，…，Sn），若从Si状态可以转移到Sj状态而且也可以从Sj状态转移到Si状态，则称Si状态与Sj状态是连通的。例状态1、2。●封闭类：若连通状态空间内的任何一状态都不可能到达状态空间外的任何一状态，称为封闭类，例状态1、2。●过渡类：若一个连通空间之内的状态可以到达连通空间之外的状态，但外面的状态不可转入其内，称之为过渡类。例状态3。●吸收态：若封闭类仅由一个状态构成且只有转进没有转出称为吸收态，例状态4。含有吸收态的马尔可夫链，称为吸收态马尔可夫链马尔可夫链的标准形：或其中，I为单位阵；0为零矩阵；R为过渡态到吸收态转移概率矩阵，Q为过渡态之间的转移概率矩阵。QRIP0IRQP011例在转移矩阵：中过渡态分析：过渡态分析的目的：①在到达吸收态前的过渡态中停留的平均时间；②从某一过渡态出发，在其被吸收前所经历的期望步数；③转移过程从某一过渡态出发，最终为某特殊吸收态或为封闭类所吸收的概率。基本矩阵：。M的每一行和表示从某一状态出发，最终转至吸收态之前的总期望转移步数；M中的元素表示过渡态Si转到过渡态Sj平均次数。吸收态转移矩阵：00000000000010000013231525352531001I000000031530000R0000032525352Q1QIMijMRQIMRB1mnmmnnbbbbbbbbbB21222211121112式中，bij表示从过渡态Si出发，访问过渡态Sj后进入吸收态的概率。例已知试对其进行过渡态分析。解：将其标准化则有03.0007.0010000008.02.05.00005.000001P0003.07.05.00005.008.0002.00001000001P0005.00008.00Q3.07.005.002.0R1005.0104.08.011005.01008.0111QIM13m11表示状态3在吸收前平均有1个转移期花费在第3状态；m12表示状态3在吸收前平均有0.8个转移期花费在第4状态；m13表示状态3在吸收前平均有0.4个转移期花费在第5状态；m21表示状态4在吸收前不会经过第3状态；m22表示状态4在吸收前平均有1个转移期花费在第4状态；m23表示状态4在吸收前平均有0.5个转移期花费在第5状态；b11表明状态3进入吸收态1的概率为0.88；b12表明状态3进入吸收态2的概率为0.12；b21表明状态4进入吸收态1的概率为0.85；b22表明状态4进入吸收态2的概率为0.15；b31表明状态5进入吸收态1的概率为0.7；b32表明状态5进入吸收态2的概率为0.3。30.070.015.085.012.088.03.07.005.002.01005.0104.08.01MRB14应用：（1）银行短期贷款回收例某银行把它应收的短期贷款期限定为1个季度，即转移期为一季度，并规定超过3个季度不能回收的短期贷款划为呆帐，据以下资料，计算短期贷款回收率。贷款状态划分为：S=（结请，呆帐，欠1季，欠2季，欠3季）。假定未来应分期收回贷款向量K=（4，2，1），单位：千万元。据经验估计，转移概率矩阵为解：由已知M1表明处于欠一季度状态的短期贷款经2.2步便可望进入吸收态：结清或成呆帐；m11表明状态3（欠一季度款）在吸收态前，平均有1个转移期花费在欠一季状态上；m12表明状态3（欠一季度款）在吸收态前，平均有0.8个转移期花费在欠二季状态上；m13表明状态3（欠一季度款）在吸收态前，平均有0.4个转移期花费在欠三季状态上；结清呆帐欠1欠2欠3结清呆帐欠1欠2欠3100.20.50.701000.300000000.8000000.500005.00008.00Q3.07.005.002.0R