马尔科夫决策课件

《马尔科夫决策课件》由会员分享，可在线阅读，更多相关《马尔科夫决策课件（43页珍藏版）》请在金锄头文库上搜索。

1、第一节 基本原理 一、基本概念1.随机变量、随机函数与随机过程一变量x，能随机地取数据（但不能准确地预言它取何值），而对于每一个数值或某一个范围内的值有一定的概率，那么称x为随机变量。假定随机变量的可能值xi发生概率为Pi即P(x=xi)=Pi对于xi的所有n个可能值，有离散型随机变量分布列：Pi=1 对于连续型随机变量，有P(x)dx=1马尔科夫决策课件在试验过程中，随机变量可能随某一参数（不一定是时间）的变化而变化.如测量大气中空气温度变化x=x(h),随高度变化。这种随参变量而变化的随机变量称为随机函数。而以时间t作参变量的随机函数称为随机过程。也就是说：随机过程是这样一个函数，在每次试

2、验结果中，它以一定的概率取某一个确定的，但预先未知的时间函数。马尔科夫决策课件2、马尔科夫过程随机过程中，有一类具有“无后效性性质”，即当随机过程在某一时刻to所处的状态已知的条件下，过程在时刻tto时所处的状态只和to时刻有关，而与to以前的状态无关，则这种随机过程称为马尔科夫过程。即是：ito为确知,it(tto)只与ito有关，这种性质为无后效性，又叫马尔科夫假设。马尔科夫决策课件3、马尔科夫链时间和状态都是离散的马尔科夫过程称为马尔科夫链。例：蛙跳问题假定池中有N张荷叶，编号为1，2，3,N，即蛙跳可能有N个状态（状态确知且离散）。青蛙所属荷叶，为它目前所处的状态；因此它未来的状态，只

3、与现在所处状态有关，而与以前的状态无关（无后效性成立）马尔科夫决策课件写成数学表达式为：P(xt+1=j|xt=it,xt-1 = it1,x1=i1)=P(xt+1=j|xt=it)定义：Pij=P(xt+1=j|xt=i)即在xt=i的条件下，使xt+1=j的条件概率，是从i状态一步转移到j状态的概率，因此它又称一步状态转移概率。 由状态转移图，由于共有N个状态，所以有马尔科夫决策课件1234P33P22P44P41P42P31P32马尔科夫决策课件二状态转移矩阵1.一步状态转移矩阵系统有N个状态，描述各种状态下向其他状态转移的概率矩阵P11P12P1N定义为P21P22P2N:PN1PN

4、2PNN这是一个N阶方阵，满足概率矩阵性质1）Pij0,i,j=1,2,N非负性性质2）Pij=1行元素和为1,i=1,2,NNNP=马尔科夫决策课件如：W1=1/4,1/4,1/2,0W2=1/3,0,2/3W3=1/4,1/4,1/4,1/2W4=1/3,1/3,-1/3,0,2/33）若A和B分别为概率矩阵时，则AB为概率矩阵。概率向量非概率向量马尔科夫决策课件2.稳定性假设若系统的一步状态转移概率不随时间变化，即转移矩阵在各个时刻都相同，称该系统是稳定的。这个假设称为稳定性假设。蛙跳问题属于此类，后面的讨论均假定满足稳定性条件。马尔科夫决策课件3.k步状态转移矩阵经过k步转移由状态i转

5、移到状态j的概率记为P(xt+k=j|xt=i)=Pij(k)i,j=1,2,N定义：k步状态转移矩阵为：P11(k)P12(k)P1N(k)P=:PN1(k)PN2(k)PNN(k)当系统满足稳定性假设时P=P=PPP其中P为一步状态转移矩阵。 即当系统满足稳定性假设时，k步状态转移矩阵为一步状态转移矩阵的k次方.kkk马尔科夫决策课件例：设系统状态为N=3，求从状态1转移到状态2的二步状态转移概率.解：作状态转移图解法一：由状态转移图：112:P11P12122:P12P22132:P13P32P12=P11P12+P12P22+P13P32=P1iPi2132P13P32P11P12P1

6、2P22马尔科夫决策课件解法二：k=2,N=3P11(2)P12(2)P13(2)P=P21(2)P22(2)P23(2)P31(2)P32(2)P33(2)P11P12P13P11P12P13=PP=P21P22P23P21P22P23P31P32P33P31P32P33得：P12(2)=P11P12+P12P22+P13P32=P1iPi2马尔科夫决策课件例：味精销售问题已连续统计六年共24个季度，确定畅销，滞销界限，即只允许出现两种状态，且具备无后效性。设状态1为畅销，状态2为滞销,作出状态转移图:图中:P11为当前畅销，连续畅销概率；P12为当前畅销，转滞销概率；P22为当前滞销，连续

7、滞销概率；P21为当前滞销，转畅销概率。12P22P11P12P21马尔科夫决策课件数据在确定盈亏量化界限后的统计表如下：t12345678910111213状态t1415161718192021222324状态进行概率计算时，第二十四个季度为畅销，但后续是什么状态不知，故计算时不能采用，只用于第二十三季度统计。有：P11=7/(7+7)=0.5;P12=7/(7+7)=0.5;P21=7/(7+2)=0.78;P22=2/(7+2)=0.22则0.50.50.780.22此式说明了：若本季度畅销，则下季度畅销和滞销的可能性各占一半若本季度滞销，则下季度滞销有78%的把握，滞销风险22%P=马

8、尔科夫决策课件二步状态转移矩阵为：0.50.50.50.50.780.220.780.220.640.360.56160.4384P11(2)P11(2)P11(2)P11(2)=P=P=22马尔科夫决策课件三.稳态概率：用于解决长期趋势预测问题。即：当转移步数的不断增加时，转移概率矩阵P的变化趋势。1.正规概率矩阵。定义：若一个概率矩阵P，存在着某一个正整数m,使P的所有元素均为正数（Pijo），则该矩阵称为正规概率矩阵k马尔科夫决策课件例：1/21/41/4P=1/31/31/3为正规概率矩阵2/51/52/501P11=01/21/2但当m=2，有有Pij0它也是正规概率矩阵。（P每个元

9、素均为正数） 但1001就找不到一个正数m,使P 的每一个元素均大于0，所以它不是正规概率矩阵。P=22P=mP=2马尔科夫决策课件2.固定概率向量（特征概率向量）设P为NN概率矩阵,若U=U1,U2,UN为概率向量,且满足UP=U,称U为P的固定概率向量例011/21/2为概率矩阵P的固定概率向量U=1/3,2/3检验UP=1/32/3011/21/2=1/32/3P=马尔科夫决策课件3.正规概率矩阵的性质定理一设P为NXN正规概率矩阵，则A.P有且只有一个固定概率向量U=U1,U2,UN且U的所有元素均为正数Ui0B.NXN方阵P的各次方组成序列P,P,P,P趋于方阵T，且T的每一个行向量

10、都是固定概率向量U。即U1U2UNUlimPk=T=:=:U1U2UNU这个方阵T称稳态概率矩阵。23k马尔科夫决策课件这个定理说明：无论系统现在处于何种状态，在经过足够多的状态转移之后，均达到一个稳态。因此，欲求长期转移概率矩阵，即进行长期状态预测，只要求出稳态概率矩阵T；而T的每个行向量都是固定概率向量，所以只须求出固定概率向量U就行了!马尔科夫决策课件定理二：设X为任意概率向量，则XT=U即任意概率向量与稳态概率矩阵之点积为固定概率向量。事实上：U1U2UNXT=X:=U1XiU1XiU1XiU1U2UN=U1U2UN=U马尔科夫决策课件例：若0.40.30.3P=0.60.30.1求T

11、0.60.10.3解：设U=U1U2U3=U1U21U1U2由UP=U有0.40.30.3U1U21U1U20.60.30.1=U1U2U30.60.10.3马尔科夫决策课件即-0.2U1+0.6=U1U1=0.50.2U1+0.2U2+0.1=U2U2=0.25-0.2U2+0.3=U3U3=0.25U=0.50.250.25则0.50.250.25T=0.50.250.250.50.250.25说明：不管系统的初始状态如何，当系统运行时间较长时，转移到各个状态的概率都相等。（列向量各元素相等）即各状态转移到1状态都为0.5;2状态都为0.25;3状态都为0.25马尔科夫决策课件第二节 市场

12、占有率预测 商品在市场上参与竞争，都拥有顾客，并由此而产生销售，事实上，同一商品在某一地区所有的N个商家（或不同品牌的N个同类产品）都拥有各自的顾客，产生各自销售额，于是产生了市场占有率定义：设某一确定市场某商品有N个不同品牌（或N个商家）投入销售，第i个商家在第j期的市场占有率 Si(j) = xi(j)/x i =1,2, N 其中 xi(j)为第i个商家在第j期的销售额（或拥有顾客数） x为同类产品在市场上总销售额（或顾客数）市场占有率所需数据可通过顾客抽样调查得到。 马尔科夫决策课件一般地,首先考虑初始条件,设当前状态（即j=0）为S(0)=S1(0)S2(0)SN(0)第i个商家Si

13、(0)=xi(0)/xxi(0)=Si(0)x即当前第i个商家市场占有率与初始市场占有率及市场总量有关.同时假定满足无后效性及稳定性假设.由于销售商品的流通性质,有第i个商家第j期销售状况为马尔科夫决策课件xi(k)=x1(0)P1i(k)+x2(0)P2i(k)+xN(0)PNi(k)=xS1(0)P1i(k)+xS2(0)P2i(k)+xSN(0)PNi(k)P1i(k)=xS1(0)S2(0)SN(0)P2i(k):PNi(k)有：Si(k)=xi(k)/xP1i(k)=S1(0)S2(0)SN(0)P2i(k):PNi(k)马尔科夫决策课件故可用矩阵式表达所有状态:S1(k),S2(k

14、),SN(k)=S1(0),S2(0),SN(0)P即S(k)=S(0)P当满足稳定性假设时,有S(k)=S(0)P这个公式称为已知初始状态条件下的市场占有率k步预测模型.kkk马尔科夫决策课件例:东南亚各国味精市场占有率预测,初期工作:a)行销上海,日本,香港味精,确定状态1,2,3.b)市场调查,求得目前状况,即初始分布c)调查流动状况;上月转本月情况,求出一步状态转移概率.1)初始向量:设上海味精状况为1;日本味精状况为2;香港味精状况为3;有S(0)=S1(0)S2(0)S3(0)=0.40.30.3马尔科夫决策课件2)确定一步状态转移矩阵P11P12P130.40.30.3P=P21

15、P22P23=0.60.30.1P31P32P330.60.10.33),3步状态转移矩阵(假定要预测3个月后)P11(3)P12(3)P13(3)0.4960.2520.252P3=P21(3)P22(3)P23(3)=P=0.5040.2520.244P31(3)P32(3)P33(3)0.5040.2440.2523马尔科夫决策课件4)预测三个月后市场0.4960.2520.252S(3)=S(0)P3=0.40.30.30.5040.2520.2440.5040.2440.252S1(3)=0.40.496+0.30.504+0.30.504=0.5008S2(3)=0.2496S3(

16、3)=0.2496马尔科夫决策课件二.长期市场占有率预测这是求当k 时S(k) ?我们知道:S(k)=S(0)PlimS(k)=S(0)limP=S(0)T=U因此,在已知初始条件下求长期市场占有率就是求稳态概率矩阵,也是求固定概率向量. 求固定概率向量的方法,我们在前一节已有例子,只不过说明了长期市场占有率也是只与稳态矩阵有关,与初始条件无关.kk马尔科夫决策课件上面味精例子,0.40.30.3已知P=0.60.30.10.60.10.40.50.250.25求出T=0.50.250.25=limPk0.50.250.25limS(k)=0.50.250.25 即中国味精可拥有50%的长期市

17、场.马尔科夫决策课件第三节 期望利润预测 是考虑:一个与经济有关随机系统在进行状态转移时,利润要发生相应变化,例如商品连续畅销到滞销,显然在这些过程变化时,利润变化的差距是很大的.所以有如下的定义:若马尔科夫链在发生状态转移时,伴随利润变化,称这个马尔科夫链为带利润的马尔科夫链.马尔科夫决策课件设系统有N个状态状态i经过一步转移到状态j时(即当事件发生时,Pij=1)所获得的利润为riji,j=1,2,N于是有利润矩阵r11r12r1NR=r21r22r2n:rN1rN2rNN显然,rij0盈利;rij0亏损;rij=0平衡 由于系统状态转移为随机的,得到的利润也应当是随机的,这个利润只能是期

18、望利润.马尔科夫决策课件11、即时期望利润(一步状态转移期望利润)考虑状态i状态转移i1i2i iiN一步转移概率Pi1Pi2PiiPiN利润变化ri1ri2riiriN所以:从i转到1的期望利润值P11r11从i转到2的期望利润值P12r12 : :从i转到i的期望利润值Piirii : : 从i转到N的期望利润值P1Nr1N马尔科夫决策课件而从状态i开始经过一步转移后所得到的期望利润值为Pijrij=Pi1ri1+Pi2ri2PiNriN这个值称为即时期望利润,又是一步状态转移期望利润,是概率定义下的利润均值.记为Vi=Vi=Pijrij 特别地Vi = 0,即当k=0,未转移,没有利润变

19、化.10马尔科夫决策课件2.k步转移期望利润递推公式k步转移期望利润可以分解为两步,即一步和k1步,一步转移期望利润为Vi=Pijrij现考虑k1步首先,从0时刻到1时刻发生了一步状态转移,假定状态已转移1状态(令Pij = 1)后,从1状态开始k1步转移后达到期望利润为V1k-1. 而i状态转移到1状态的发生概率为Pi1,因此i状态先转移到1状态后的k1步实际期望利润为Pi1V1k-1k1马尔科夫决策课件同理i状态先转到2状态后的k1步实际期望利润为Pi2V2即:各实际期望利润之和,构成了初始状态为i的k1步转移后的转移期望利润:PijVj k步转移期望利润 Vi = Vi +PijVj=P

20、ijrij + PijVj = Pij (rij + Vj )以上公式为k步转移期望利润递推公式此公式可改写为矩阵递推式:由Vi=Vi+PijVjk1k1k1k1k1k1kk1马尔科夫决策课件 V1定义 V = V2 为j步转移期望利润列向量 :VNV1V=V2为即时期望利润列向量:.VNP11P12P1N:为一步状态转移概率矩阵PN1PN2PNN有V=V+PVjjjjP=Kk1马尔科夫决策课件例:设某商品销售状态分别为畅销(状态1)及滞销(状态2),销售状态转移概率矩阵为P11P120.50.5P21P220.40.6利润矩阵r11r1251r21r221-1试预测三个月后的期望利润.=P=

21、R=马尔科夫决策课件解:利用递推公式顺序推出,即时期望利润Vi=PijrijV1=P1jr1j=P11r11+P12r12=0.55+0.51=3(百万元)V2=P2jr2j=P21r21+P22r22=0.41 + 0.6(-1)= -0.2(百万元)V1:本月畅销,一月后可期望获利300万V2:本月滞销,一个月后预测亏损20万由V1=P1j(r1j+Vj)kk-1马尔科夫决策课件V1=P1j(r1j+Vj)=P11(r11+V1)+P12(r12+V2)=0.5(5+3)+0.5(10.2)=4.4(百万)即本月畅销,预计两个月后可期望获利440万元V2=P2j(r2j+Vj)=P21(r21+V1)+P22(r22+V2)=0.4(1+3)+0.6(-10.2)=0.88(百万)即本月滞销,两月后可期望获利88万元.22马尔科夫决策课件由此,可推出本题结果:V1=P1j(r1j+Vj)=P11(r11+V1)+P12(r12+V2)=0.5(5+4.4)+0.5(1+0.8)=5.64(百万)V2=P2j(r2j+Vj)=P21(r21+V1)+P22(r22+V2)=0.4(1+4.4)+0.6(-1+0.88)=2.088(百万)答案:若本月畅销,三月后将期望盈利564万元若本月滞销,三月后将期望盈利208.8万元. 32223222马尔科夫决策课件