马尔科夫预测与决策ppt课件

1、1.根本原理概述2.马尔科夫预测与决策3.案例分析 一、根本概念 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有关，这种性质为无后效性，又叫马尔科夫假设。 简例：设x(t)为大米在粮仓中t月末的库存量，那么 x(t) = x(t1)y(t) +G(t) t月的转出量 第t1月末库存量 ,G(t)为当月转入量 x(t)可看作一个马尔科夫过

3、程。 3、马尔科夫链 时间和形状都是离散的马尔科夫过程称为马尔科夫链。例：蛙跳问题 假定池中有N张荷叶，编号为1，2，3,N，即蛙跳能够有N个形状形状确知且离散。青蛙所属荷叶，为它目前所处的形状；因此它未来的形状，只与如今所处形状有关，而与以前的形状无关无后效性成立 1234P33P22P44P41P42P31P32 写成数学表达式为： 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的条件概率，是

4、从 i形状一步转移到j形状的概率，因此它又称一步形状转移概率。 由形状转移图，由于共有N个形状，所以有 二形状转移矩阵 1.一步形状转移矩阵 系统有N个形状，描画各种形状下向其他形状转移的概率矩阵 P11 P12 P1N 定义为 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,

5、1/3, -1/3,0, 2/3 3假设A和B分别为概率矩阵时，那么AB为概率矩阵。 概率向量非概率向量 2.稳定性假设 假设系统的一步形状转移概率不随时间变化，即转移矩阵在各个时辰都一样，称该系统是稳定的。 这个假设称为稳定性假设。蛙跳问题属于此类，后面的讨论均假定满足稳定性条件。 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

6、 = P = P P P 其中P为一步形状转移矩阵。 即当系统满足稳定性假设时，k步形状转移矩阵为一步形状转移矩阵的k次方.kk k 例：设系统形状为N = 3，求从形状1转移到形状2的 二步形状转移概率. 解：作形状转移图 解法一：由形状转移图： 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

7、) 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(2) = P11 P12 + P12 P22 +P13 P32 = P1i Pi2 三.稳态概率： 用于处理长期趋势预测问题。 即：当转移步数的不断添加时，转移概率矩阵 P 的变化趋势。 1.正规概率矩阵。 定义：假设一个概率矩阵P，存在着某一个正整数m,使P 的一切元素均为正数Pij o，那么该矩阵称为正规概率矩阵 k例： 1/2 1/4 1/4 P = 1/3 1/3 1/3

8、 为正规概率矩阵 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，所以它不是正规概率矩阵。 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.正规

9、概率矩阵的性质 定理一 设P为NXN正规概率矩阵，那么 A .P有且只需一个固定概率向量 U = U1,U2, UN 且U的一切元素均为正数 Ui 0 B.NXN方阵P的各次方组成序列 P, P, P, ,P 趋于方阵T，且T的每一个行向量都是固定概率向量U。 即 U1 U2 UN U lim Pk = T = : : : = : U1 U2 UN U 这个方阵T称稳态概率矩阵。23k 这个定理阐明：无论系统如今处于何种形状，在经过足够多的形状转移之后，均到达一个稳态。 因此，欲求长期转移概率矩阵，即进展长期形状预测，只需求出稳态概率矩阵T； 而T的每个行向量都是固定概率向量，所以只须求出固定

10、概率向量U就行了 ! 定理二：设X为恣意概率向量，那么XT = U 即恣意概率向量与稳态概率矩阵之点积为固定概率向量。 现实上： U1 U2 UN XT = X : : : = U1Xi U1Xi U1Xi U1 U2 UN = U1 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 =

11、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 0.5 0.25 0.25 阐明： 不论系统的初始形状如何，当系统运转时间较长时，转移到各个形状的概率都相等。列向量各元素相等即 各形状转移到1形状都为0.5; 2形状都为0.25 ; 3形状都为0.25 马尔科夫决策方法就是根据某些变量的如今形状及其变化趋向，来预测它在未来某一特定期间能够出现的形状，从而提供某种决策的根据。 马尔科夫决策根本方法是用转移概率

12、矩阵进展预测和决策。 转移概率矩阵模型为：11121( )2122212.kkknkkkknkkkmmmnPPPPPPPPPP 其中Pij 表示概率， 表示转移概率矩阵。( )kP1转移概率矩阵中的元素是根据近期市场 或顾客的保管与得失流向资料确定的。2下一期的概率只与上一期的预测结果有 关，不取决于更早期的概率。 3利用转移概率矩阵进展决策，其最后结 果取决于转移矩阵的组成，不取决于原 始条件，即最初占有率。转移概率矩阵决策的步骤如下： 1、建立转移概率矩阵。 2、利用转移概率矩阵进展模拟预测。3、求出转移概率矩阵的平衡形状，即稳定形状。4、运用转移概率矩阵进展决策 商品在市场上参与竞争，都

13、拥有顾客，并由此而产生销售，现实上，同一商品在某一地域一切的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(0) = xi(0)/x xi(0) = Si(0)

14、 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)/x P1i(k) = S1(0) S2(0) SN(0) P2i(k) : PNi(k)故可用矩阵式表达一切形状: S1(k),S2(k),

15、 ,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.4 0.3 0.32)确定一步形状转移矩阵 P11 P

16、12 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.504 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

17、.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 = U 因此,在知初始条件下求长期市场占有率就是求稳态概率矩阵,也是求固定概率向量. 求固定概率向量的方法,我们在前一节已有例子,只不过阐明了长期市场占有率也是只与稳态矩阵有关,与初始条件无关. kk 上面味精例子, 0.4 0.3 0.3 知 P = 0

18、.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%的长期市场. 是思索:一个与经济有关随机系统在进展形状转移时,利润要发生相应变化,例如商品延续畅销到滞销,显然在这些过程变化时,利润变化的差距是很大的. 所以有如下的定义: 假设马尔科夫链在发生形状转移时,伴随利润变化,称这个马尔科夫链为带利润的马尔科夫链. 设系统有N个形状 形状i经过一步转移到形状j时(即当事件发生时,Pij = 1)所获得的利润为rij i,

19、j = 1,2, N 于是有利润矩阵 r11 r12 r1N R = r21 r22 r2n : : : rN1 rN2 rNN 显然 ,rij 0 盈利 ;rij 0 亏损 ; rij = 0 平衡 由于系统形状转移为随机的,得到的利润也该当是随机的,这个利润只能是期望利润. 11、即时期望利润(一步形状转移期望利润) 思索形状 i 形状转移 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 :

20、: 从i转到N的期望利润值 P1Nr1N 而从形状i开场经过一步转移后所得到的期望利润值为 Pijrij = Pi1ri1 + Pi2ri2 PiNriN 这个值称为即时期望利润,又是一步形状转移期望利润,是概率定义下的利润均值. 记为 Vi = Vi = Pijrij 特别地Vi = 0 ,即当 k = 0, 未转移,没有利润变化. 10 2. k步转移期望利润递推公式 k步转移期望利润可以分解为两步,即一步和k1步, 一步转移期望利润为Vi = Pijrij 现思索k1步 首先,从0时辰到1时辰发生了一步形状转移,假定 形状已转移1形状(令Pij = 1)后,从1形状开场 k1 步转移后到

21、达期望利润为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利润矩阵 r11 r12 5 1