第八讲-马尔科夫预测法

马尔科夫链及转移概率 转移概率矩阵的固定点 马尔科夫链在经济预测 等方面的应用 吸收态马尔科夫链及其应用6.1.1 随机过程随机过程 定义 如果对每个给定的时间 tT，Z(t)都是一随机变量，我们就称 Z(t),tT是一个随机过程 类型 随机过程可分为以下四类：连续型随机过程；离散型随机过程；连续型随机序列；离散型随机序列，离散型随机序列也称时间序列。6.1.2 马尔科夫链马尔科夫链 定义 具有“无后效性”的时间序列 Z(t)，tT称为马尔科夫链。马尔科夫链的时间参数空间通常取T=0，1，2，Z(t)习惯上记为Zt,Zt的所有可能取值构成的集合称为时间序列的状态空间，记为S。通常设S是一个整数集合。“无后效性”定义 “无后效性”是指时间序列将来处于什么状态只与它现在所处的状态有关，与它过去处于什么状态无关。马尔科夫预测方法就是根据某些变量的现在状态及其变化趋向，来预测它在未来某一特定期间可能出现的状态，从而提供某种决策的依据。马尔科夫预测基本方法是用转移概率矩阵进行预测和决策。6.1.3 一步转移概率矩阵一步转移概率 定义 设 Zt,tT 是一马尔科夫链，其中T=0，1，2，；S=1，2，n,则称在Zt=i的条件下，Zt+1=j的条件概率PZt+1=j Zt=i称为由状态i到状态j的一步转移概率。平稳的马尔科夫链 定义 如果马尔科夫链的一步转移概率PZt+1=j Zt=i与时间t无关，则称马尔科夫链是平稳的。以后我们提到的马尔科夫链都是平稳的马尔科夫链。并记一步转移概率PZt+1=j Zt=i=为pij 一步转移概率矩阵 定义 设 Zt,tT 是一平稳的马尔科夫链，其中T=0，1，2，；S=1，2，n,则称由一步转移概率pij构成的矩阵P为一步转移概率矩阵。性质 一步转移概率矩阵P具有如下两条性质：pij0；含义 一步转移概率矩阵P的第i 行元素描述了t 时刻状态 i 向t+1 时刻系统内各状态转移的可能性。1nijjp11nijjp6.1.4 k步转移概率矩阵K步转移概率矩阵 定义 设 Zt,tT 是一平稳的马尔科夫链，状态空间为 S=1，2，n,称pij（k）=PZt+k=j Zt=i 为马尔科夫链的k步转移概率，由pij（k），i=1,2,，n,j=1,2,，n 构成的矩阵P(k)为马尔科夫链的k步转移概率矩阵。即 kPkPkPkPkPkPkPkPkPkPNN2N1NN22221N11211 其中P(k)的第i 行元素描述的是在t 时刻Zt 处于i 状态的条件下，t+k 时刻Zt 处于各状 态的概率。性质 设P是马尔科夫链的一步转移概率矩 阵，P(k)是马尔科夫链的K步转移概率矩 阵，则 P(k)=Pk举例 例6.7（130页）为了解顾客对A，B，C三种不同品牌洗衣粉的购买倾向，市场调查小组进行了购买倾向调查。在本月购买A，B，C品牌的顾客中分别调查了100人，150人和120人，了解他们在下月的购买倾向。调查结果用矩阵表示如下：122140303026030603603030ABBABC 其中，第一行表示在本月购买A品牌的100 人中有40人在下月仍打算购买A品 牌，而打 算转向购买B和C品牌的人都是30。第二行 ，第三行类同。要求:写出状态转移概率矩阵；求购买 C品牌的顾客在未来第二个月购 买A品牌和B品牌的概率。解：题中所给的矩阵也称状态转移频数矩阵，用频数矩阵的各行频数分别除以各行频数之 和，得状态转移概率矩阵如下：因为12210.40.30.320.40.20.430.50.250.25ABBABC20.40.30.30.40.30.3(2)0.40.20.40.40.20.40.50.250.250.50.250.25PP0.430.2550.3150.440.260.30.4250.26250.3125 所以，购买C品牌的顾客在未来第二个月购买A品牌、B品牌的概率分别为0.425，0.2625.6.2.1 初始分布与绝对分布初始分布与绝对分布 定义 设马尔科夫链Zt,tT=0,1,2,的状态空间为 S=1，2，n，则Z0的概率分布0010201,2,pP ZpP Z 称为马尔科夫链Zt,tT的初始分布；Zt的概率分布121,2,ttttpP ZpP Z 称为马尔科夫链Zt,tT在t时刻的绝对分布。初始 分布和t时刻的绝对分布分别用行向量 和 表示。并称概率分布构成的行向量为概率向量。结论 马尔科夫链Zt,tT在t 时刻的绝对分布等于初始分布与一步转移概率矩阵t次幂的乘积，即 其中P是一步转移概率矩阵。000012(,)npppp12(,)ttttnpppp0ttpp P 举例 例6.8（133页）设马尔科夫链的一步转移概率矩阵为 （1）若初始分布为（0.2，0.2，0.6），求t=1 时的绝对分布。（2）初始分布为（0.5，0.25，0.25），求任意时刻t 时的绝对分布。0.40.30.30.60.30.10.60.10.3P 解：（1）因为 所以，t=1 时刻，马尔科夫链的绝对分布为 100.40.30.3(0.2,0.2,0.6)0.60.30.10.60.10.3pp P(0.56,0.18,0.26)(0.56,0.18,0.26)（2）因为 所以，所以，t 时刻马尔科夫链的绝对分布为 即，该马尔科夫链在任意时刻的绝对分布与初始分布相同。100.40.30.3(0.5,0.25,0.25)0.60.30.10.60.10.3pp P0(0.5,0.25,0.25)p2100(0.5,0.25,0.25)pp Pp Pp0(0.5,0.25,0.25)p 6.2.2 固定点与正规矩阵固定点 定义6.2 设P是马尔科夫链的一步转移概率矩阵。如果存在概率向量u，使得uP=u,则称u为P的固定概率向量，或称u为P的固定点（或均衡点）。如果马尔科夫链的转移概率矩阵P的所有行向量等于同一向量u，则称P是由u构成的稳态矩阵。比如：在例6.8中，u=(0.5,0.25,0.25)是所给矩阵的固定点。正规矩阵 定义6.3 设P是马尔科夫链的一步转移概率矩阵，如果存在自然数k，使得Pk 的所有元素都是正数，则称P为正规概率矩阵。结论 定理6.1 设P为正规概率矩阵，则（a）P有唯一的由正数构成的固定概率向量u。（b）设方阵V的每一行向量都是P的固定概率向量u，则由P的各次幂构成的矩阵序列P，P2，P3，Pk，当k趋于无穷时，以V为极限，即（c）设p0是任意概率向量，则向量序列p0 P，p0 P2，p0 P3，p0 Pk，当k趋于无穷时，以u为极限,即limkkPV 0limkkp Pu 注 定理6.1又称马尔科夫链的基本定理。该定理表明：（1）如果马尔科夫链的一步转移概率矩阵P是正规矩阵，那么P一定存在固定点u，而且当k趋于无穷时，k步转移概率矩阵P(k)收敛于由u构成的稳态矩阵V。这说明一个系统经过无穷多次的状态转移后，系统将表现出稳态之势。（2）不论马尔科夫链的初始分布如何，经充分多次状态转移后，绝对分布会趋于同一分布，即固定概率向量u给出的分布。换句话说，不论最初系统处于什么状态，最终都会以分布u处于系统内的各个状态，即系统最终会处于均衡状态。例6.11 设马尔科夫链的一步转移概率矩阵为 对充分大的k，求k步转移概率矩阵P(k)的近似矩阵。解 因为P是正规概率矩阵，所以有固定点u。设V是由u构成的P的稳态矩阵，由定理6.2知：因此，对充分大的k，有 解线性方程组：得固定点 。因此，对充分大的k，有lim()limkkkPkPV ()PkV0.40.30.30.60.30.10.60.10.3P(0.5,0.25,0.25)u 0.50.250.25()0.50.250.250.50.250.25P kV123()01TTPIuuuu6.3.1 市场占有率预测市场占有率预测方法 第一步 市场调查 （1）在全体消费此种产品的消费者中，调查目前购买n种品牌的消费者各占的比率，获得初始分布 。（2）调查在n种品牌之间消费者的流动情况，获得转移概率矩阵。000012(,)npppp 第二步 预测未来k时刻的市场占有率 计算初始分布与k步转移概率矩阵的乘积，就可得到未来k时刻的绝对分布。第三步 预测均衡状态下的市场占有率 如果转移概率矩阵P是正规矩阵，那么P有唯一的固定点 ，于是，在市场最终达到均衡的状态下，各种品牌的最终市场占有率将分别为 。12(,)nuuuu12,nuuu 例题 例6.12 在北京地区销售的鲜牛奶主要由三个厂家提供。分别用1，2，3表示。去年12月份对2000名消费者进行了调查。购买厂家1，2，3的消费者分别为800，600和600.同时得到的转移频数矩阵为 其中第一行表示，在12月份购买厂家1产品的800个消费者中，有320名消费者继续购买厂家1的产品，转向购买厂家2和产品的消费者都是240人。N的第二行和第三行的含义同第一行。（1）试对3个厂家17月份的市场占有率进行预测；（2）试求市场处于均衡状态时，各厂家的市场占有率。1231 3202402402 360180603 36060180N 解（1）用800，600和600分别除以2000，得到去年12月份各厂家的市场占有率，即初始分布 用800，600和600分别去除矩阵N的第一行，第二行和第三行的各元素，的状态转移概率矩阵 于是，第k月的绝对分布，或第k月的市场占有率为 0(0.4,0.3,0.3)p 0.40.30.30.60.30.10.60.10.3P00(),(1,2,3,7)kkppP kpPk将 k=1，2，7 代入上式，把计算结果绘制成市场占有率变动表，如表6.2所示。从表6.2中可以看出，（1）厂家1的市场占有率随着时间的推移，逐渐稳定在50%，厂家2和厂家3的市场占有率 都逐渐稳定在25%。（2）由于转移概率矩阵P是正规矩阵，所以有唯一的均衡点u。由例6.11知，由定理6.2知，。即随着时间的推移，3个厂家的市场占有率逐渐趋于稳定。当市场达到均衡状态时，各厂家的市场占有率分别为50%，25%和25%。由表6.2可以看出，第三个月时，市场基本上已经达到了均衡状态，此时各厂家的市场占有率与均衡状态时的市场占有率的误差已经不足千分之一。(0.5,0.25,0.25)u lim(0.5,0.25,0.25)kkpu6.3.2 人力资源预测人力资源预测举例 例6.13 某高校为编制师资发展规划，需要预测未来教师队伍的结构。现在对教师状况进行如下分类：青年、中年、老年和流退（流失或退休）。根据资料，各类教师（按1年为1期）的转移概率矩阵为 目前青年教师400人，中年教师360人，老年教师300人，试分析三年后，教师的结构以及为保持编制不变，三年内 应进多少硕士和博士充实教师队伍。0.80.1500.0500.750.20.05000.80.20001P青中老流 退 解：设目前的教师结构为 ，则一年后教师结构为：流退人员98人，为保持编制不变，第一年学校需进98人。此时青年教师为320+98=418人，教师结构为 。两年后的教师结构为：第二年流退100人，因此第二年需进100人，此 时青年教师为334+100=434人，教师结构为：，三年后的教师结构为：第三年流退100人，因此第三年应进100人。此时青年教师为347+100=447人。因此，三年内需进298人，三年后教师结构为3*(447,298,315,0)n 32*(347,298,315,100)nnP0(400,360,300,0)n 00(320,330,312,98)nnP2*(434,310,316,0)n 1*(418,330,312,0)n 21*(334,310,316,100)nnP6.3.3 期望利润预测 利润矩阵 定义 马尔可夫链的状态变化时常伴随着某种报酬或利润。设市场的状态空间为S=1，2，n，转移概率矩阵为P，当市场由状态 i 转移至状态 j 时，厂家的利润为 ij,（i=1，2，n；j=1，2，n），则称由ij构成的n阶方阵（ij）为利润矩阵。称这种马尔可夫链为带利润的马尔可夫链。期望利润预测公式 公式 设v i（k）为从状态 i 开始，经 k 步转移到各状态所获得的期望利润（i=1，2，n），记 规定v（0）=0。当k=1 时，当k 1 时，有如下递推公式 K步转移后的期望利润为两次转移(一步转移和K-1步转移)期望利润之和,即()(1)(1),1,2,v kvP v kk1122(1)iiiiiininvppp12()(),(),(),1,2,Tnv kvkvkvkk应用举例 例6.14 设一生产厂家的产品每月市场状态有畅销和滞销两种，用1表示畅销，用2表示滞销。假设从畅销到畅销可获利30万元；从畅销到滞销可获利10万元；从滞销到畅销可获利20万元；从滞销到滞销将亏损10万元。现有30个月的市场销售记录。如表6.3所示 （1）求销售市场状态转移概率矩阵。（2）分别预测下个月和未来3个月的期望利润。解 （1）在30个状态中，畅销(15-1)到畅销有6个，滞销(15)到滞销有7个，所以 于是，概率转移矩阵为 （2）由已知条件知，利润矩阵为 由于本月处于畅销状态，所以下月的期望利润为：11126/140.43,8/140.57pp30102010 0.430.570.530.47P111111212(1)30 0.43 10 0.57 18.6()vpp万元。47.015/753.015/82221pp 又因 所以，由递推公式得 由于本月是畅销，且 所以，下一个月的期望利润为18.6万元，未来3个 月的期望利润为42.04万元。12(1)(1),(1)(18.6,5.9)Tvvv(2)(1)(1)(29.96,18.53)TvvP v2(1)200.53100.475.9()v万 元。11(1)18.6,(3)42.04vv(3)(1)(2)(42.04,30.49)TvvP v6.3.4 马尔科夫链在其他方面的应用举例 项目选址问题 例6.15 某汽车维修公司在北京市有甲、乙、丙3个维修厂。由于公司注重对员工的技术培训，树立顾客至上、信誉第一的理念，采用先进的管理模式，公司在本行业具有良好的形象。形成了一定规模和稳定的客户群。对客户的调查显示，客户在甲、乙、丙3个维修厂之间的转移概率矩阵为：由于资金的原因，公司打算只对其中一个维修厂进行改造，并扩大规模。试分析应选择哪个维修厂。0.80.200.200.80.20.20.6P甲乙丙 解 由于 的所有元素都大于0，所以P是正规矩阵。因此，P存在唯 一的固定概率向量 。解线性方程组：得唯一解 由此可以看出，长期趋势表明，当公司的客户在3个维修厂之间的转移达到均衡状态时，大约有50%的客户在甲厂维修，大约有16.67%的客户在乙厂维修，大约有33.33%的客户在丙厂维修。因此，应选择甲厂进行项目投资。123(,)uu u u123()01TTPI uuuu20.680.160.160.320.200.480.320.160.52P(1/2,1/6,1/3)u 最佳经营策略选择 例6.16 北京地区销售的鲜牛奶是由3个厂家提供的。该地区客户总数为100万户。假定厂家从每个客户那里每年平均获利50元。厂家2的市场调查显示，状态转移概率矩阵为：均衡状态下的市场占有率分别为50%，25%和25%（参见例6.11和例6.12），厂家2认为应采取积极的营销策略，提高自己的市场占有率，为此设计了两套方案。方案一旨在吸引老客户，实施需花费约450万元。实施方案一后，估计转移概率矩阵为：0.40.30.30.60.30.10.60.30.1P10.40.30.30.30.70.00.60.10.3P 方案二希望吸引厂家1和厂家2的客户，实施方案二需花费约400万元。实施方案二后，估计转移概率矩阵为 试选择最佳方案。解：（方案一）显然 的所有元素都大于0，所以 为正规矩阵。故 有唯一的固定点 解方程组 得唯一解 。因此，当市场达到均衡状态时，厂家2的市场占有率达到44%，比原来增加了19个百分点，由此增加的利润为：0.1910050=950（万元）。(0.39,0.44,0.17)u 21P20.30.50.20.60.30.10.40.50.1P1P1P123(,)uu u u123()01TTPI uuuu 方案一的成本为450万元，因而实际比原来多获利500万元。（方案二）类似地可得到 固定向量 即，当市场达到均衡状态时，厂家2的市场占有率为42%，比原来增加了17个百分点，由此增加的利润为 0.1710050=850（万元）。实施方案二的成本为400万元，因此实际比原来多获利450万元。比较方案一和方案二可知，实施方案一要比实施方案二多获利50万元，因此选择方案一。(0.44,0.42,0.14)u 2P6.4.1 状态的分类状态的分类 定义 设马尔科夫链的状态转移空间为 从状态 i 到状态 j 的 k 步转移概率为1,2,Sn(),1,2,ijpk k（2）如果S的子集 ，的任意两个状态都是相通的，则称S是一个相通类。（3）如果一个相通类S的任何一个状态都不能达到S之外的任何一个状态，则称S是一个封闭类。(即只进不出)如果一个封闭类仅由一个状态构成，则称此状态为吸收态。（4）若在一个相通类S中存在一状态可达到S之外的某一状态，则称S是一过渡类。流向只能由过渡类到封闭类。例6.18 设马尔科夫链 的转移概率矩阵为：12,rSiii状态空间为 ，试对其状态分类。解 先作马尔科夫链状态传递图。如图6.2所示。由图6.2可以看出，S的子集1，2与4，5都是相通类，同时也是封闭类。状态3是过渡态。此马尔科夫链没有吸收态。定理 设S是马尔科夫链的过渡类，则S中的任意状态都必然被某一封闭类所吸收。（证明从略）1,2,3,4,5S 6.4.2 过渡分析过渡分析 过渡分析要解决如下问题：（1）从过渡态i开始，在被某一封闭类吸收之前，访问过渡态j的平均次数是多少？（2）从过渡态i开始，在被某一封闭类吸收之前，在过渡类停留的平均次数是多少？（3）从过渡态i开始，被某一封闭类吸收的概率是多少？马尔科夫链的标准型 定义6.5 如果将马尔科夫链的转移概率矩阵的行列重排得到如下形式的矩阵 或 （6.3）则称形如（6.3）的矩阵为马尔科夫链的标准型。其中P1是r阶方阵，r是封闭类中状态的个数，Q是n-r 阶方阵，n-r是过渡类中状态的个数。10PRQ10QRP 例6.19 设马尔科夫链的转移概率矩阵为试写出马尔科夫链的标准型。解 作状态传递图，如6.3所示。由图6.3知，状态2，3，4构成过渡类，状态1和5都是吸收态。先排列状态1和5，后排列2，3，4，得如下标准型。基本矩阵 定义6.6 设马尔科夫链的标准型为 则称 为马尔科夫链的基本矩阵。可以证明马尔科夫链的基本矩阵一定存在（略）。定理6.3 设 是马尔科夫链的过渡类。是基本矩阵，则 的第s行第t列的元素等于从状态i s 开始，在被吸收(进入封闭类）之前访问过渡态i t的期望次数或平均次数。定理6.4 设 是马尔科夫链的过渡类，M是马尔科夫链的基本矩阵，则从过渡态i s出发，在最终进入一个封闭类之前转移的期望总步数等于M的第s行元素之和再减1.1()MIQ10PRQMI12,n rSi ii1()MIQ12,n rSi ii 定理6.5 设 是马尔科夫链的过渡类。是封闭类的并集。M是基本矩阵，R是标准型中的R。则矩阵B=MR的第s行第t列的元素bst恰好等于马尔科夫链从过渡态is开始，通过访问一封闭类中的状态jt而被吸收的概率。12,rSjjj12,n rSi ii 例6.20 设马尔科夫链的状态转移概率矩阵为：试对过渡态被吸收的情况进行分析。解 作状态转移图。如图6.4所示。图6.4 状态转移图 由图6.4可以看出，状态1和状态 2，状态5和状态6分别构成封闭 类。状态3和状态4都是过渡态。按封闭类，过渡类的顺序重新排 列转移概率矩阵，得右边的标准 型。其中 由矩阵M I 可知，从过渡态3开始，在被封闭类吸收之前访问过渡态3和4的平均次数分别为1/4次和1/2次；在过渡类停留的平均次数为1/4+1/2=3/4次。过渡态4的情况类同。由矩阵B=MR可知，从状态3开始，转移到封闭类1，2的概率为0.75，被封闭类5，6吸收的概率为0.25.从状态4开始，分别被1，2和5，6吸收的概率分别为0.375和0.625.6.4.3 吸收态马尔科夫链的应用举例 银行贷款回收问题 例6.21 某商业银行在结算时发现，账目未结清的客户共有800户，其中欠款1年的有400户，2年的有250户，3年的有150户。银行还规定，如果3年后仍不还款，则将其列入呆账（指无法收回的应收账款）。根据以往经验，还款情况随时间转移的概率分布如表6.4所示。（1）试分析2年后应收账款的分布情况。（2）试分析应收账款的最终分布情况。解 这是一个马尔科夫链问题。状态空间S=1，2，3，4，5，其中状态4是还清，状态5是呆 账。由题设，一步转移概率矩 阵为右侧的矩阵。其恰好是标 准型。其中（1）因为连续两年的转移概率 矩阵为右侧的矩阵，所以，2年 后未结清欠款的客户的构成为00.30000.5000Q0.60.10.30.20.40.6R2000.150.690.160000.50.50000.40.60001000001P(400,250,150,0,0)(2)(0,0,60,461,279)P这说明，2年后，800户中平均有461户已经结清，279户已经变为呆账，还有60户尚未还清。（2）由于 所以 由矩阵B可以看出，处于状态1，即欠款1年的400个应收账款中，有 75%将被状态4吸收，其余25%将被状态5吸收。也就是说，平均有 300个应收账款将结清，其余100个将成为呆账。同理，欠款2年的 250个应收账款中，平均有一半会结清，另一半会成为呆账。欠款 3年的150个应收账款中，平均有60个将结清，其余90个将成为呆账。因此，在总共800个应收账款中，平均来说，最终将有485个结清，其余315个成为呆账。保修费估计问题 例6.22 某手机生产厂家出售的手机有3年的保修期。假设保修期内，一旦产品需要修理，修理后就能保证在保修期内不在修理。对出售的产品分5种状态进行考察。状态i表示产品出售时间在第i年内（i=1,2,3）,状态4表示保修期满，状态5表示产品需要修理。根据以往经验，一步转移概率矩阵如下 假设最近3年已出售产 品的情况为：出售时间 在1年内的有30万个，满1年不到2年的有20 万个，满2年不足3年的 有10万个，用向量v=(30,20,10)表示。试对已售出产品所需的保修费进行估计（假设平均每部手机的修理费为20元）。解 这是一个马尔科夫链问题。转移概率矩阵恰好是标准型，其中 基本矩阵为 于是 由矩阵B可以看出，在出售时间不满1年的30万个手机中，约有3031.6%=9.48万个需要修理；满1年不足2年的20万个手机中，约有2028%=5.6万个需要修理；满2年不足3年的10万个手机中，约有1020%=2万个需要修理。因此，在已出售的60万个手机中，约有17.08万个需要修理。通过如下的计算 可直接得到需要修理的手机为17.08万个，修理费用约为17.0820=341.6万元。