马尔科夫决策

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个状态，描述各种状态下向其他状态转移的概率矩阵 p11 p12 p1

4、n 定义为 p21 p22 p2n : : : pn1 pn2 pnn 这是一个n阶方阵，满足概率矩阵性质 1） pij 0,i,j = 1,2, , n 非负性性质 2） pij = 1 行元素和为1 ,i=1,2,nnn p = 如： w1 = 1/4, 1/4, 1/2, 0 w2 = 1/3, 0, 2/3 w3 = 1/4, 1/4, 1/4, 1/2 w4 = 1/3, 1/3, -1/3,0, 2/3 3）若a和b分别为概率矩阵时，则ab为概率矩阵。 概率向量非概率向量 2.稳定性假设 若系统的一步状态转移概率不随时间变化，即转移矩阵在各个时刻都相同，称该系统是稳定的。 这个假设

5、称为稳定性假设。蛙跳问题属于此类，后面的讨论均假定满足稳定性条件。 3.k步状态转移矩阵 经过k步转移由状态i转移到状态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 = p p p 其中p为一步状态转移矩阵。 即当系统满足稳定性假设时，k步状态转移矩阵为一步状态转移矩阵的k次方.kk k 例：设系统状态为n = 3，求从状态1转移到状态2的 二步状态转移概率. 解：作状态

6、转移图 解法一：由状态转移图： 1 1 2: p11 p12 1 2 2: p12 p22 1 3 2: p13 p32 p12 = p11 p12 + p12 p22 +p13 p32 = p1i pi2 132p13p32 p11p12p12p22 解法二： k = 2, n = 3 p11(2) p12 (2) p13(2) p = p21(2) p22 (2) p23(2) p31(2) p32(2) p33(2) p11 p12 p13 p11 p12 p13 = pp = p21 p22 p23 p21 p22 p23 p31 p32 p33 p31 p32 p33 得： p12(

7、2) = p11 p12 + p12 p22 +p13 p32 = p1i pi2 例：味精销售问题 已连续统计六年共24个季度，确定畅销，滞销界限，即只允许出现两种状态，且具备无后效性。 设状态1为畅销，状态2为滞销,作出状态转移图: 图中: p11为当前畅销，连续畅销概率； p12为当前畅销，转滞销概率； p22为当前滞销，连续滞销概率； p21为当前滞销，转畅销概率。 12p22p11p12p21数据在确定盈亏量化界限后的统计表如下： t 1 2 3 4 5 6 7 8 9 10 11 12 13状态 t 14 15 16 17 18 19 20 21 22 23 24状态 进行概率计算

8、时，第二十四个季度为畅销，但后续是什么状态不知，故计算时不能采用，只用于第二十三季度统计。有： 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.5 0.5 0.78 0.22此式说明了：若本季度畅销，则下季度畅销和滞销的可能性各占一半 若本季度滞销，则下季度滞销有78%的把握，滞销风险22% p = 二步状态转移矩阵为： 0.5 0.5 0.5 0.5 0.78 0.22 0.78 0.22 0.64 0.36 0.5616 0.4384 p11(2)

9、 p11(2) p11(2) p11(2) =p = p =22 三.稳态概率： 用于解决长期趋势预测问题。 即：当转移步数的不断增加时，转移概率矩阵 p 的变化趋势。 1.正规概率矩阵。 定义：若一个概率矩阵p，存在着某一个正整数m,使p 的所有元素均为正数（pij o），则该矩阵称为正规概率矩阵 k例： 1/2 1/4 1/4 p = 1/3 1/3 1/3 为正规概率矩阵 2/5 1/5 2/5 0 1 p11 = 0 1/2 1/2 但当 m = 2， 有 有pij 0它也是正规概率矩阵。（p 每个元素均为正数） 但 1 0 0 1 就找不到一个正数m,使p 的每一个元素均大于0，所以

10、它不是正规概率矩阵。 p =22 p =m p =2 2.固定概率向量（特征概率向量） 设 p为nn概率矩阵,若u = u1, u2, un为概率向量,且满足up = u,称u为p的固定概率向量 例 0 1 1/2 1/2 为概率矩阵 p的固定概率向量 u = 1/3 , 2/3 检验 up = 1/3 2/3 0 1 1/2 1/2 =1/3 2/3p = 3.正规概率矩阵的性质 定理一 设p为nxn正规概率矩阵，则 a .p有且只有一个固定概率向量 u = u1,u2, un 且u的所有元素均为正数 ui 0 b.nxn方阵p的各次方组成序列 p, p, p, ,p 趋于方阵t，且t的每一

11、个行向量都是固定概率向量u。 即 u1 u2 un u lim pk = t = : : : = : u1 u2 un u 这个方阵t称稳态概率矩阵。23k 这个定理说明：无论系统现在处于何种状态，在经过足够多的状态转移之后，均达到一个稳态。 因此，欲求长期转移概率矩阵，即进行长期状态预测，只要求出稳态概率矩阵t； 而t的每个行向量都是固定概率向量，所以只须求出固定概率向量u就行了 ! 定理二：设x为任意概率向量，则xt = u 即任意概率向量与稳态概率矩阵之点积为固定概率向量。 事实上： u1 u2 un xt = x : : : = u1xi u1xi u1xi u1 u2 un = u1

12、 u2 un = u例：若 0.4 0.3 0.3 p = 0.6 0.3 0.1 求t 0.6 0.1 0.3 解：设 u = u1 u2 u3 = u1 u2 1u1u2 由 up = u 有 0.4 0.3 0.3u1 u2 1u1u2 0.6 0.3 0.1 = u1 u2 u3 0.6 0.1 0.3 即 -0.2u1 + 0.6 = u1 u1 = 0.5 0.2u1 + 0.2u2 + 0.1 =u2 u2 = 0.25 -0.2u2 + 0.3 = u3 u3 = 0.25 u = 0.5 0.25 0.25 则 0.5 0.25 0.25 t = 0.5 0.25 0.25

13、0.5 0.25 0.25 说明： 不管系统的初始状态如何，当系统运行时间较长时，转移到各个状态的概率都相等。（列向量各元素相等）即 各状态转移到1状态都为0.5; 2状态都为0.25 ; 3状态都为0.25 商品在市场上参与竞争，都拥有顾客，并由此而产生销售，事实上，同一商品在某一地区所有的n个商家（或不同品牌的n个同类产品）都拥有各自的顾客，产生各自销售额，于是产生了市场占有率定义：设某一确定市场某商品有n个不同品牌（或n个商家）投入销售，第i个商家在第j期的市场占有率 si(j) = xi(j)/x i =1,2, n 其中 xi(j)为第i个商家在第j期的销售额（或拥有顾客数） x为同

14、类产品在市场上总销售额（或顾客数）市场占有率所需数据可通过顾客抽样调查得到。 一般地,首先考虑初始条件,设当前状态（即j = 0 ） 为 s(0) = s1(0) s2(0) sn(0)第i个商家 si(0) = xi(0)/x xi(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) p1

15、i(k) = xs1(0) s2(0) sn(0) p2i(k) : pni(k) 有：si(k) = xi(k)/x p1i(k) = s1(0) s2(0) sn(0) p2i(k) : pni(k)故可用矩阵式表达所有状态: s1(k),s2(k), ,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)市场调查,求得目前状况,即初始

16、分布 c)调查流动状况;上月转本月情况,求出一步状态转移概率. 1)初始向量: 设 上海味精状况为1; 日本味精状况为2; 香港味精状况为3;有 s(0) = s1(0) s2(0) s3(0) = 0.4 0.3 0.32)确定一步状态转移矩阵 p11 p12 p13 0.4 0.3 0.3 p = p21 p22 p23 = 0.6 0.3 0.1 p31 p32 p33 0.6 0.1 0.33),3 步状态转移矩阵(假定要预测3个月后) p11(3) p12(3) p13(3) 0.496 0.252 0.252 p 3= p21(3) p22(3) p23(3) = p = 0.50

17、4 0.252 0.244 p31(3) p32(3) p33(3) 0.504 0.244 0.252 34)预测三个月后市场 0.496 0.252 0.252 s(3) = s(0)p3 =0.4 0.3 0.3 0.504 0.252 0.244 0.504 0.244 0.252 s1(3) = 0.40.496 +0.30.504 + 0.30.504 = 0.5008 s2(3) = 0.2496 s3(3) = 0.2496 二.长期市场占有率预测 这是求当 k 时 s(k) ? 我们知道: s(k) = s(0) p lim s(k) = s(0) lim p = s(0)t

18、 = u 因此,在已知初始条件下求长期市场占有率就是求稳态概率矩阵,也是求固定概率向量. 求固定概率向量的方法,我们在前一节已有例子,只不过说明了长期市场占有率也是只与稳态矩阵有关,与初始条件无关. kk 上面味精例子, 0.4 0.3 0.3 已知 p = 0.6 0.3 0.1 0.6 0.1 0.4 0.5 0.25 0.25 求出 t = 0.5 0.25 0.25 = lim pk 0.5 0.25 0.25 lim s(k) = 0.5 0.25 0.25 即中国味精可拥有50%的长期市场. 是考虑:一个与经济有关随机系统在进行状态转移时,利润要发生相应变化,例如商品连续畅销到滞销

19、,显然在这些过程变化时,利润变化的差距是很大的. 所以有如下的定义: 若马尔科夫链在发生状态转移时,伴随利润变化,称这个马尔科夫链为带利润的马尔科夫链. 设系统有n个状态 状态i经过一步转移到状态j时(即当事件发生时,pij = 1)所获得的利润为rij i,j = 1,2, n 于是有利润矩阵 r11 r12 r1n r = r21 r22 r2n : : : rn1 rn2 rnn 显然 ,rij 0 盈利 ;rij 0 亏损 ; rij = 0 平衡 由于系统状态转移为随机的,得到的利润也应当是随机的,这个利润只能是期望利润. 11、即时期望利润(一步状态转移期望利润) 考虑状态 i 状

20、态转移 i 1 i 2 i i i n 一步转移概率 pi1 pi2 pii pin 利润变化 ri1 ri2 rii rin 所以:从i转到1的期望利润值 p11r11 从i转到2的期望利润值 p12r12 : : 从i转到i的期望利润值 piirii : : 从i转到n的期望利润值 p1nr1n 而从状态i开始经过一步转移后所得到的期望利润值为 pijrij = pi1ri1 + pi2ri2 pinrin 这个值称为即时期望利润,又是一步状态转移期望利润,是概率定义下的利润均值. 记为 vi = vi = pijrij 特别地vi = 0 ,即当 k = 0, 未转移,没有利润变化. 1

21、0 2. k步转移期望利润递推公式 k步转移期望利润可以分解为两步,即一步和k1步, 一步转移期望利润为vi = pijrij 现考虑k1步 首先,从0时刻到1时刻发生了一步状态转移,假定 状态已转移1状态(令pij = 1)后,从1状态开始 k1 步转移后达到期望利润为v1k-1 . 而i状态转移到1状态的发生概率为pi1 , 因此i状态先转移到1状态后的k1步实际期望利润为 pi1 v1k-1 k1 同理 i状态先转到2状态后的k1步实际期望利润为 pi2 v2 即:各实际期望利润之和,构成了初始状态为i的 k1步转移后的转移期望利润 : pijvj k步转移期望利润 vi = vi +pijvj = pijrij + pijvj = pij (rij + vj )以上公式为k步转移期望利润递推公式此公式可改写为矩阵递推式:由 vi = vi + pijvjk1k1k1 k1k1k1kk1 v1定义 v = v2 为j步转移期望利润列向量 : vn v1 v = v2 为即时期望利润列向量 :. vn p11 p12 p1n : : : 为一步状态转移概率矩阵 pn1 pn2 pnn 有v = v +pvjjjjp =k k1例:设某商品销售状态分别为畅销(状态1)及滞销(状态2),销售状态转移概率矩阵为 p11 p12 0.5 0.5 p21 p22 0.4 0.6利润