第6章-马尔可夫预测方法课件

第6章马尔可夫预测方法6.1马尔可夫预测的基本原理6.2马尔可夫预测的应用思考与练习第6章马尔可夫预测方法6.1马尔可夫预测的基本原理1

6.1马尔可夫预测的基本原理 6.1.1马尔可夫链 为了表征一个系统在变化过程中的特性（状态）,可以用一组随时间进程而变化的变量来描述。如果系统在任何时刻上的状态是随机的,则变化过程就是一个随机过程。 设有参数集T(-∞,+∞),如果对任意的t∈T,总有一随机变量Xt与之对应,则称{Xt,t∈T}为一随机过程。如若T为离散集（不妨设T={t0,t1,t2,…,tn,…}）,同时Xt的取值也是离散的,则称{Xt,t∈T}为离散型随机过程。6.1马尔可夫预测的基本原理 6.1.1马尔可夫链2 设有一离散型随机过程,它所有可能处于的状态的集合为S={1,2,…,N},称其为状态空间。系统只能在时刻t0,t1,t2,…改变它的状态。为简便计,以下将Xtn等简记为Xn。 一般地说,描述系统状态的随机变量序列不一定满足相互独立的条件,也就是说,系统将来的状态与过去时刻以及现在时刻的状态是有关系的。在实际情况中,也有具有这样性质的随机系统：系统在每一时刻（或每一步）上的状态,仅仅取决于前一时刻（或前一步）的状态。这个性质称为无后效性,即所谓马尔可夫假设。具备这个性质的离散型随机过程,称为马尔可夫链。用数学语言来描述就是： 设有一离散型随机过程,它所有可能处于的状态的集合为S={3 如果对任一n>1,任意的i1,i2,…,in-1,j∈S,恒有

P{Xn=j|X1=i1,X2=i2,…,Xn-1=in-1}=P{Xn=j|Xn-1=in-1} (6.1) 则称离散型随机过程{Xt,t∈T}为马尔可夫链。 例如,在荷花池中有N张荷叶,编号为1,2,…,N。假设有一只青蛙随机地从这张荷叶上跳到另一张荷叶上。青蛙的运动可看作一随机过程。在时刻tn,青蛙所在的那张荷叶,称为青蛙所处的状态。那么,青蛙在未来处于什么状态,只与它现在所处的状态i(i=1,2,…,N)有关,与它以前在哪张荷叶上无关。此过程就是一个马尔可夫链。 由于系统状态的变化是随机的,因此,必须用概率描述状态转移的各种可能性的大小。 如果对任一n>1,任意的i1,i2,…,in-14 6.1.2状态转移矩阵 马尔可夫链是一种描述动态随机现象的数学模型,它建立在系统“状态”和“状态转移”的概念之上。所谓系统,就是我们所研究的事物对象；所谓状态,是表示系统的一组记号。当确定了这组记号的值时,也就确定了系统的行为,并说系统处于某一状态。系统状态常表示为向量,故称之为状态向量。例如,已知某月A、B、C三种牌号洗衣粉的市场占有率分别是0.3、0.4、0.3,则可用向量P=(0.3,0.4,0.3)来描述该月市场洗衣粉销售的状况。 6.1.2状态转移矩阵5 当系统由一种状态变为另一种状态时,我们称之为状态转移。例如,洗衣粉销售市场状态的转移就是各种牌号洗衣粉市场占有率的变化。显然,这类系统由一种状态转移到另一种状态完全是随机的,因此必须用概率描述状态转移的各种可能性的大小。如果在时刻tn系统的状态为Xn=i的条件下,在下一个时刻tn+1系统状态为Xn+1=j的概率pij(n)与n无关,则称此马尔可夫链是齐次马尔可夫链,并pij=P{Xn+1=j|Xn=i}i,j=1,2,…,N称pij为状态转移概率。显然,我们有 当系统由一种状态变为另一种状态时,我们称之为状态转移。例6 转移矩阵设系统的状态转移过程是一齐次马尔可夫链,状态空间S={1,2,…,N}为有限,状态转移概率为pij,则称矩阵 为该系统的状态转移概率矩阵,简称转移矩阵。 为了论述和计算的需要,引入下述有关概念。(6.2) 转移矩阵设系统的状态转移过程是一齐次马尔可夫链,状态空间7 概率向量对于任意的行向量（或列向量）,如果其每个元素均非负且总和等于1,则称该向量为概率向量。 概率矩阵由概率向量作为行向量所构成的方阵称为概率矩阵。对于一个概率矩阵P,若存在正整数m,使得Pm的所有元素均为正数,则称矩阵P为正规概率矩阵。 例如,矩阵 中每个元素均非负,每行元素之和皆为1,行数和列数相同,为2×2方阵,故矩阵A为概率矩阵。 概率向量对于任意的行向量（或列向量）,如果其每个元素均8 概率矩阵有如下性质：如果A、B皆是概率矩阵,则AB也是概率矩阵；如果A是概率矩阵,则A的任意次幂Am(m≥0)也是概率矩阵。对k≥1,记

p(k)ij=P{Xn+k=j|Xn=i}

P(k)=(p(k)ij)N×N

称p(k)ij为k步状态转移概率,P(k)为k步状态转移概率矩阵,它们均与n无关（从式(6.4)也可看出）。 特别地,当k=1时,p

(1)

ij=pij为1步状态转移概率。马尔可夫链中任何k步状态转移概率都可由1步状态转移概率求出。(6.3) 概率矩阵有如下性质：如果A、B皆是概率矩阵,则AB也是9 由全概率公式可知,对k≥1,有（其中P(0)表示单位矩阵）

p

(k)

ij=P{Xn+k=j|Xn=i} =P{Xn+k-1=l|Xn=i}·P{Xn+k=j|Xn+k-1=l} =p

(k-1)

ilplji,j=1,2,…,N 其中用到马尔可夫链的“无记忆性”和齐次性。用矩阵表示,即为

p

(k)=P

(k-1)

P,从而可得 p

(k)=Pkk≥1 记t0为过程的开始时刻,pi(0)=P{X0=X(t0)=i},则称

P(0)=(p1(0),p2(0),…,pN(0))(6.4) 由全概率公式可知,对k≥1,有（其中P(0)表示单10 为初始状态概率向量。 如已知齐次马尔可夫链的转移矩阵P=(pij)以及初始状态概率向量P(0),则任一时刻的状态概率分布也就确定了： 对k≥1,记pi(k)=P{Xk=i},则由全概率公式有

pi(k)=pj(0)·p

(k)

jii=1,2,…,N;k≥1(6.5) 若记向量P(k)=(p1(k),p2(k),…,pN(k)),则上式可写为 P(k)=P(0)P(k)=P(0)Pk(6.6) 由此可得

P(k)=P(k-1)P(6.7) 为初始状态概率向量。11 例6.1考察一台机床的运行状态。机床的运行存在正常和故障两种状态。由于出现故障带有随机性,故可将机床的运行看作一个状态随时间变化的随机系统。可以认为,机床以后的状态只与其以前的状态有关,而与过去的状态无关,即具有无后效性。因此,机床的运行可看作马尔可夫链。 设正常状态为1,故障状态为2,即机床的状态空间由两个元素组成。机床在运行过程中出现故障,这时从状态1转移到状态2；处于故障状态的机床经维修,恢复到正常状态,即从状态2转移到状态1。 例6.1考察一台机床的运行状态。机床的运行存在正常和故12 现以1个月为时间单位。经观察统计,知从某月份到下月份机床出现故障的概率为0.2,即p12=0.2。其对立事件,保持正常状态的概率为p11=0.8。在这一时间,故障机床经维修返回到正常状态的概率为0.9,即p21=0.9；不能修好的概率为p22=0.1。机床的状态转移情形见图6.1。 现以1个月为时间单位。经观察统计,知从某月份到下月份机床13图6.1机床的状态转移图6.1机床的状态转移14 由机床的一步转移概率得状态转移概率矩阵

若已知本月机床的状态向量P(0)=(0.85,0.15),现要预测机床两个月后的状态。先求出两步转移概率矩阵 矩阵的第一行表明,本月处于正常状态的机床,两个月后仍处于正常状态的概率为0.82，转移到故障状态的概率为0.18。第二行说明,本月处于故障状态的机床,两个月后转移到正常状态的概率为0.81,仍处于故障状态的概率为0.19。 由机床的一步转移概率得状态转移概率矩阵15 于是,两个月后机床的状态向量 6.1.3稳态概率矩阵 1．平稳分布 若存在非零概率向量X=(x1,x2,…,xN),使得XP=X,其中P为一概率矩阵,则称X为P的固定概率向量。 特别地,设X=(x1,x2,…,xN)为一状态概率向量,P为状态转移概率矩阵。若

XP=X 于是,两个月后机床的状态向量16

即 则称X为马尔可夫链的一个平稳分布。若随机过程某时刻的状态概率向量P(k)为平稳分布,则称过程处于平衡状态。一旦过程处于平衡状态,则过程经过一步或多步状态转移之后,其状态概率分布保持不变,也就是说,过程一旦处于平衡状态后将永远处于平衡状态。 对于我们所讨论的状态有限（即N个状态）的马尔可夫链,平稳分布必定存在。特别地,当状态转移矩阵为正规概率矩阵时,平稳分布惟一。此时,求解方程(6.8),即可得到系统的平稳分布。j=1,2,…,N 即j=1,2,…,N17 2．稳态分布 对概率向量π=(π1,π2,…,πN),如对任意的i,j∈S,均有 或

这也是称π为稳态分布的理由。 设存在稳态分布π=(π1,π2,…,πN),则由于下式恒成立: P(k)=P(k-1)P 2．稳态分布18 令k→+∞,就得

π=πP(6.10) 即有限状态马尔可夫链的稳态分布如存在,那么它也是平稳分布。 对任一状态i,如果{k|p

(k)ii>0}的公约数为1,则称状态i为非周期状态。 如果一个马尔可夫链的所有状态均是非周期的,则称此马尔可夫链是非周期的。 对非周期的马尔可夫链,稳态分布必存在,对不可约非周期的马尔可夫链,稳态分布和平稳分布相同且均惟一。 令k→+∞,就得19 例6.2设一马尔可夫链的状态转移矩阵为 求其平稳分布及稳态分布。 解（1）P不可约。pij>0,仅当i≠2且j≠2时。又p(2)22>0,由定义可知,P是不可约的。 例6.2设一马尔可夫链的状态转移矩阵为20 （2）P非周期。 由p

(1)

11>0,p

(2)11>0,而1、2的公约数为1,故状态1为非周期状态。同理可得状态2、3均为非周期状态。故P是非周期的 （3）由于P不可约且是非周期的,求解如下方程组: 得X=［0.40.20.4］,这就是该马尔可夫链的稳态分布,而且也是平稳分布。 （2）P非周期。216.2马尔可夫预测的应用 6.2.1市场占有率的预测 我们结合例题来说明如何预测市场占有率。 例6.3伍迪公司、布卢杰.里维公司、雷恩公司(分别用符号A、B、C代表)是美国中西部地区生产灭虫剂的三家主要厂商。根据历史资料得知,公司A、B、C产品销售额的市场占有率分别为50%、30%、20%。由于C公司实行了改善销售与服务方针的经营管理决策,使其产品销售额逐期稳定上升,而A公司的产品销售额却在下降。通过市场调查发现三个公司间的顾客流动情况如表6.1所示。6.2马尔可夫预测的应用 6.2.1市场占有率的预测22 其中产品销售周期是季度。现在的问题是,按照目前的趋势发展下去,A公司的产品销售额或客户转移的影响将严重到何种程度？更全面地,三个公司的产品销售额的占有率将如何变化？ 其中产品销售周期是季度。现在的问题是,按照目前的趋势发展23表6.1A、B、C三公司的顾客流动情况表6.1A、B、C三公司的顾客流动情况24 将表6.1中的数据化为转移概率将对研究分析未来若干周期的顾客流向更为有利。表6.2列出了各公司顾客流动的转移概率。表6.2中的数据是每家厂商在一个周期中的顾客数与前一周期的顾客数相除所得。表中每一行表示某公司从一个周期到下一个周期将能保住的顾客数的百分比,以及将要丧失给竞争对手的顾客数的百分比。表中每一列表示各公司在下一周期将能保住的顾客数的百分比,以及该公司将要从竞争对手那里获得顾客数的百分比。 将表6.1中的数据化为转移概率将对研究分析未来若干周期的25表6.2顾客流动的转移概率表6.2顾客流动的转移概率26 如用矩阵来表示表6.2中的数据,就得到了如下的状态转移矩阵: P中数据表示一个随机挑选的某公司的顾客,到下一个周期购买该公司或另一公司产品的可能性或概率。如随机挑选一名A公司的顾客,他在下一周期仍购买A公司产品的概率为0.7,购买B公司产品的概率为0.1,购买C公司产品的概率为0.2。(6.11) 如用矩阵来表示表6.2中的数据,就得到了如下的状态转移矩27 1.未来各周期市场占有率的计算 以A、B、C公司作为我们要分析的系统的状态,那么状态概率向量就分别为三家公司的产品销售额的市场占有率。初始状态概率向量为 P(0)=(p1(0),p2(0),p3(0))=(0.5,0.3,0.2) 转移矩阵由式（6.11）给出。于是可用式（6.6）来计算未来各期的市场占有率。如状态转移一次后第1周期的市场占有率向量为 1.未来各周期市场占有率的计算28

2.稳态市场占有率 计算未来各期的市场占有率向量P(k)可以看出,A公司的市场占有率将逐期下降,而C公司的市场占有率则将逐期上升。从经营决策和管理的角度来看,自然希望了解各公司的市场占有率最终将达到什么样的水平,亦即需要知道稳态市场占有率。

29 由于式(6.11)中的P是不可约非周期的,因此稳态市场占有率即为平衡状态下的市场占有率,亦即马尔可夫链的平稳分布。 由前面的讨论知道,我们求解如下方程组： 由于式(6.11)中的P是不可约非周期的,因此稳态市场占30 解得

x1=0.1765,x2=0.2353,x3=0.5882 亦即,A、B、C三家公司的市场占有率最终将分别达到17.65%、23.53%、58.82%。 对本例来说,当销售份额达到平衡时,各公司分别占总销售额中的那一部分均保持不变。 但在某些情况下,参与竞争的公司或厂商中可能会有一个或多个被完全逐出市场。例如对于转移矩阵 解得31 3.销售策略对市场占有率的影响 (1)保留策略：指尽力保留公司原有顾客的各种经营方针与对策。如采用提供优质服务或对连续两期购货的顾客实行折价优惠等方法。设Ａ公司采用这样的保留策略后,减少了其原有顾客向Ｃ公司的流失,使保留率从原来的70％提高到85％,则转移矩阵成为 3.销售策略对市场占有率的影响32 新的平衡状态下Ａ、Ｂ、Ｃ三公司的市场占有率分别为31.6％、26.3％、42.1％,Ａ公司的市场占有率从17.65％提高到31.6％。 (2)争取策略：指从竞争者拥有的顾客中争取顾客的各种经营方针与对策。如通过广告等方法。设Ａ公司通过争取策略,能从上一周期内向另外两家公司购货的顾客中各争取15％,则转移矩阵成为 新的平衡状态下Ａ、Ｂ、Ｃ三公司的市场占有率分别为31.33 6.2.2期望报酬预测 在一个与经济有关的马尔可夫型随机系统中,系统获得的报酬(或称收益)也会随状态的不同而不同。设有一台机器,它在第n周期的状态用Xn表示： 0第n周期正常 1第n周期失效 进一步假定,机器正常时,每一个周期可带来v元的收益,并且在下一周期失效的概率为p； Xn= 6.2.2期望报酬预测Xn=34 当机器失效时,需对其进行更换,更换的费用为d,修理时间为一个周期,下一个周期初修好并开始正常工作,于是{Xn}是一个齐次马尔可夫链,其状态空间为S={0,1},转移矩阵为 但这是一个带报酬(或称收益、费用)的马尔可夫链。 当机器失效时,需对其进行更换,更换的费用为d,修理时间为35 一般地,设{Xn}是状态空间为S={1,2,…,N}的齐次马尔可夫链,其转移矩阵为P=(pij)N×N。设r(i)表示某周期系统处于状态i时获得的报酬。我们称如此的马尔可夫链是具有报酬的。显然,r(i)＞0时,称为盈利、报酬、收益等；r(i)＜0时,称为亏损、费用等。对于这样一个带报酬的马尔可夫链,n时的报酬是一个随机变量。 1．有限时段期望总报酬 记vk(i)表示初始状态为i的条件下,到第k步状态转移前所获得的期望总报酬(k≥1,i∈S)： 一般地,设{Xn}是状态空间为S={1,2,…,36

若记列向量Vk=［vk(1)vk(2)…vk(N)］T,r=［r(1)r(2)…r(N)］T,则上式可写为 (6.12) (6.12)37 这里,I表示单位矩阵。进而,可证明有如下递推式：

v0(i)=0i=1,2,…,N 于是可用上式递推求得vk(i)。 2．无限时段单位时间平均报酬 对i∈S,定义初始状态为i的无限时段单位时间平均报酬为k≥0;i=1,2,…,N

(6.13) 这里,I表示单位矩阵。进而,可证明有如下递推式：k38 记 矩阵P*=(p*ij),则由式(6.12)可证得 于是为求v(i),只须求得P*即可,但一般地要求出P*并不是件容易的事。这里我们只讨论如下的特殊情况。 我们考虑稳态分布π=［π1

π2…πN］存在的这种特殊情况。i,j=1,2,…,N

(6.14) 记i,j=1,2,…,N(6.14)39 由上节可知,转移矩阵P非周期即可保证π存在。当π存在时,它也是平稳分布。注意到数学分析中的一个结论：设数列an有极限a,则 于是,我们有如下结论。 结论设所考虑的马尔可夫链存在稳态分布π,则

p*ij=πj,j=1,2,…,N。进而若式(6.10)有惟一解X=［x1

x2…xN］,则有 p*ij=πj=xjj=1,2,…,N(6.15) 由上节可知,转移矩阵P非周期即可保证π存在。当π存在时,40 实际上,如果π存在,当式(6.10)有惟一解X时,由于稳态分布必为平稳分布,故πj=xj。 特别地,对于不可约非周期的马尔可夫链,式(6.15)恒成立。于是可先求解式(6.10)得X,进而由式(6.15)求得v(i)。 3．无限时段期望折扣总报酬 在现实生活中,今年的一元钱将大于明年的一元钱,其实将钱存于银行即可。也就是说明年的一元钱折算到现在计算,就不值一元钱了,如为β∈(0,1),这个β就称为折扣因子。 实际上,在企业管理中当考虑贷款、折旧等时都必须考虑到钱的增值问题。 实际上,如果π存在,当式(6.10)有惟一解X时,由于稳41 如将钱存于银行,年息为ρ,则ρ与β有如下关系： 如果一个周期为一个月,那么只须将ρ理解为月息即可。这里折扣因子β一般在区间(0,1)中。 对有报酬的马尔可夫链,定义从状态i出发的无限时段期望折扣总报酬为(6.16)(6.17) 如将钱存于银行,年息为ρ,则ρ与β有如下关系：42 若记向量Vβ=［vβ(1)vβ(2)…vβ(N)］T,则上式的向量或矩阵形式为 与有限时段中的式(6.13)类似,由式(6.17)可得(6.18)(6.19) 若记向量Vβ=［vβ(1)vβ(2)…vβ(N)］43 例6.4最佳维修策略的选择。我们研究一化工企业对循环泵进行季度维修的过程。该化工企业对泵进行定期检查,每次检查中,把泵按其外壳及叶轮的腐蚀程度定为五种状态中的一种。这五种状态是： 状态1：优秀状态,无任何故障或缺陷； 状态2：良好状态,稍有腐蚀； 状态3：及格状态,轻度腐蚀； 状态4：可用状态,大面积腐蚀； 状态5：不可运行状态,腐蚀严重。 该公司可采用的维修策略有以下几种。 例6.4最佳维修策略的选择。我们研究一化工企业对循环泵44 单状态策略：泵处于状态5时才进行修理,每次修理费用为500元。 两状态策略：泵处于状态4和5时进行修理,处于状态4时的修理费用每次为250元,处于状态5时的每次修理费用为500元。 三状态策略：泵处于状态3、4、5时进行修理,处于状态3时的每次修理费用为200元,处于状态4和5时的修理费用同前。 目前,该公司采用的维修策略为“单状态”策略。 假定不管处于何种状态,只要进行修理,泵的状态都将在本周期内恢复为状态1。已知在不进行任何修理时的状态转移概率,如表6.3中所示。 单状态策略：泵处于状态5时才进行修理,每次修理费用为545表6.3不修理时的状态转移概率表6.3不修理时的状态转移概率46 现在我们要确定哪个策略的费用最低。目标为长期运行单位时间平均报酬。容易看出,在单状态、两状态、三状态下的转移概率矩阵分别为 现在我们要确定哪个策略的费用最低。目标为长期运行单位时间47第6章-马尔可夫预测方法课件48 下面我们分别来求三种策略下的v(i)。 (1)单状态策略。此时r(1)＝r(2)＝r(3)＝r(4)＝0,r(5)＝500,将P1代入式(6.8)可解得惟一的平稳分布为

X=(x1,x2,…,x5)=(0.199,0.170,0.180,0.252,0.199) 而P1显然是不可约非周期的,从而X亦为稳态分布,由此及式(6.14)、(6.15)可得 下面我们分别来求三种策略下的v(i)。49 (2)两状态策略。r(1)＝r(2)＝r(3)＝0,r(4)＝250,r(5)＝500,与(1)中类似,可知

X=π=(0.266,0.228,0.241,0.168,0.097) 从而由式(6.14)、(6.15)有

(3)三状态策略。r(1)＝r(2)＝0,r(3)＝200,r(4)＝250,r(5)＝500,于是 X=π=(0.35,0.30,0.19,0.095,0.065)

v(i)=xjr(j)=0.19×200+0.095×250+0.065×500=94.25(元) (2)两状态策略。r(1)＝r(2)＝r(3)＝0,r50

因此,两状态策略为最优策略,平均每周期的费用为90.50元。从上面的计算发现,v(i)均与i无关。其实,若式(6.15)成立,则由式(6.14)知v(i)总与i无关,亦即单位时间平均报酬(或费用)与起始状态无关。 因此,两状态策略为最优策略,平均每周期的费用为90.5051思考与练习 １．马尔可夫链应具备哪些性质？如何描述系统状态的转移情况？ ２*．试用无限时间期望折扣总报酬准则讨论例6.4中的三个策略的优劣。假定ρ=0.07。 ３*．在具有报酬的马尔可夫链中,如果对有限阶段也考虑折扣,试给出有限时间段期望折扣总报酬的定义及其递推公式。 ４．你认为马尔可夫预测方法的应用受到哪些条件的限制？为什么？思考与练习 １．马尔可夫链应具备哪些性质？如何描述系统状52 ５．某市场销售甲、乙、丙三种牌号的同类型产品,购买该产品的顾客变动情况如下： 过去购买甲牌产品的顾客,在下一季度中有15%的转而购买乙牌产品,10%的转而购买丙牌产品。 原购买乙牌产品的顾客,有30%的转而购买甲牌产品,同时有10%的转而购买丙牌产品。 原购买丙牌产品的顾客中有5%的转而购买甲牌产品,同时有15%的转而购买乙牌产品。问经营甲种产品的工厂在当前的市场条件下是否有利于扩大产品的销售？

５．某市场销售甲、乙、丙三种牌号的同类型产品,购买该产53 ６．某产品每月的市场状态有畅销和滞销两种,三年来有如下表所示的记录。“1”代表畅销,“2”代表滞销,试求市场状态转移的一步和二步转移概率矩阵。 ６．某产品每月的市场状态有畅销和滞销两种,三年来有如下表54 ７．某市三种主要品牌彩电甲、乙、丙的市场占有率分别为23%、18%、29%,其余市场为其它各种品牌的彩电所占有。根据抽样调查,顾客对各类彩电的爱好变化为 其中矩阵元素aij表示上月购买i品牌彩电而下月购买j品牌彩电的概率；i=1,2,3,4分别表示甲、乙、丙和其它品牌彩电。 ７．某市三种主要品牌彩电甲、乙、丙的市场占有率分别为255 (1)试建立该市各品牌彩电市场占有率的预测模型,并预测未来3个月各种品牌彩电市场占有率变化的情况； (2)假定该市场彩电销售总量为4.7万台,预测未来三个月各品牌彩电的销售量； (3)分析各品牌彩电市场占有率变化的平衡状态； (4)假定生产甲品牌彩电的企业采取某种经营策略（例如广告宣传等）,竭力保持了原有顾客爱好不向其它品牌转移,其余不变。分析彩电市场占有率的平衡状态。 (1)试建立该市各品牌彩电市场占有率的预测模型,并预测56 ８．某高校教师队伍可分为助教,讲师,副教授,教授,流失及退休五个状态。2004年有助教150人,讲师280人,副教授130人,教授80人。根据历史资料分析,可得各类职称教师的转移概率矩阵如下： 要求分析三年后的教师结构及三年内为保持编制不变应进多少研究生充实教师队伍。 ８．某高校教师队伍可分为助教,讲师,副教授,教授,流失及57第6章马尔可夫预测方法6.1马尔可夫预测的基本原理6.2马尔可夫预测的应用思考与练习第6章马尔可夫预测方法6.1马尔可夫预测的基本原理58

6.1马尔可夫预测的基本原理 6.1.1马尔可夫链 为了表征一个系统在变化过程中的特性（状态）,可以用一组随时间进程而变化的变量来描述。如果系统在任何时刻上的状态是随机的,则变化过程就是一个随机过程。 设有参数集T(-∞,+∞),如果对任意的t∈T,总有一随机变量Xt与之对应,则称{Xt,t∈T}为一随机过程。如若T为离散集（不妨设T={t0,t1,t2,…,tn,…}）,同时Xt的取值也是离散的,则称{Xt,t∈T}为离散型随机过程。6.1马尔可夫预测的基本原理 6.1.1马尔可夫链59 设有一离散型随机过程,它所有可能处于的状态的集合为S={1,2,…,N},称其为状态空间。系统只能在时刻t0,t1,t2,…改变它的状态。为简便计,以下将Xtn等简记为Xn。 一般地说,描述系统状态的随机变量序列不一定满足相互独立的条件,也就是说,系统将来的状态与过去时刻以及现在时刻的状态是有关系的。在实际情况中,也有具有这样性质的随机系统：系统在每一时刻（或每一步）上的状态,仅仅取决于前一时刻（或前一步）的状态。这个性质称为无后效性,即所谓马尔可夫假设。具备这个性质的离散型随机过程,称为马尔可夫链。用数学语言来描述就是： 设有一离散型随机过程,它所有可能处于的状态的集合为S={60 如果对任一n>1,任意的i1,i2,…,in-1,j∈S,恒有

P{Xn=j|X1=i1,X2=i2,…,Xn-1=in-1}=P{Xn=j|Xn-1=in-1} (6.1) 则称离散型随机过程{Xt,t∈T}为马尔可夫链。 例如,在荷花池中有N张荷叶,编号为1,2,…,N。假设有一只青蛙随机地从这张荷叶上跳到另一张荷叶上。青蛙的运动可看作一随机过程。在时刻tn,青蛙所在的那张荷叶,称为青蛙所处的状态。那么,青蛙在未来处于什么状态,只与它现在所处的状态i(i=1,2,…,N)有关,与它以前在哪张荷叶上无关。此过程就是一个马尔可夫链。 由于系统状态的变化是随机的,因此,必须用概率描述状态转移的各种可能性的大小。 如果对任一n>1,任意的i1,i2,…,in-161 6.1.2状态转移矩阵 马尔可夫链是一种描述动态随机现象的数学模型,它建立在系统“状态”和“状态转移”的概念之上。所谓系统,就是我们所研究的事物对象；所谓状态,是表示系统的一组记号。当确定了这组记号的值时,也就确定了系统的行为,并说系统处于某一状态。系统状态常表示为向量,故称之为状态向量。例如,已知某月A、B、C三种牌号洗衣粉的市场占有率分别是0.3、0.4、0.3,则可用向量P=(0.3,0.4,0.3)来描述该月市场洗衣粉销售的状况。 6.1.2状态转移矩阵62 当系统由一种状态变为另一种状态时,我们称之为状态转移。例如,洗衣粉销售市场状态的转移就是各种牌号洗衣粉市场占有率的变化。显然,这类系统由一种状态转移到另一种状态完全是随机的,因此必须用概率描述状态转移的各种可能性的大小。如果在时刻tn系统的状态为Xn=i的条件下,在下一个时刻tn+1系统状态为Xn+1=j的概率pij(n)与n无关,则称此马尔可夫链是齐次马尔可夫链,并pij=P{Xn+1=j|Xn=i}i,j=1,2,…,N称pij为状态转移概率。显然,我们有 当系统由一种状态变为另一种状态时,我们称之为状态转移。例63 转移矩阵设系统的状态转移过程是一齐次马尔可夫链,状态空间S={1,2,…,N}为有限,状态转移概率为pij,则称矩阵 为该系统的状态转移概率矩阵,简称转移矩阵。 为了论述和计算的需要,引入下述有关概念。(6.2) 转移矩阵设系统的状态转移过程是一齐次马尔可夫链,状态空间64 概率向量对于任意的行向量（或列向量）,如果其每个元素均非负且总和等于1,则称该向量为概率向量。 概率矩阵由概率向量作为行向量所构成的方阵称为概率矩阵。对于一个概率矩阵P,若存在正整数m,使得Pm的所有元素均为正数,则称矩阵P为正规概率矩阵。 例如,矩阵 中每个元素均非负,每行元素之和皆为1,行数和列数相同,为2×2方阵,故矩阵A为概率矩阵。 概率向量对于任意的行向量（或列向量）,如果其每个元素均65 概率矩阵有如下性质：如果A、B皆是概率矩阵,则AB也是概率矩阵；如果A是概率矩阵,则A的任意次幂Am(m≥0)也是概率矩阵。对k≥1,记

p(k)ij=P{Xn+k=j|Xn=i}

P(k)=(p(k)ij)N×N

称p(k)ij为k步状态转移概率,P(k)为k步状态转移概率矩阵,它们均与n无关（从式(6.4)也可看出）。 特别地,当k=1时,p

(1)

ij=pij为1步状态转移概率。马尔可夫链中任何k步状态转移概率都可由1步状态转移概率求出。(6.3) 概率矩阵有如下性质：如果A、B皆是概率矩阵,则AB也是66 由全概率公式可知,对k≥1,有（其中P(0)表示单位矩阵）

p

(k)

ij=P{Xn+k=j|Xn=i} =P{Xn+k-1=l|Xn=i}·P{Xn+k=j|Xn+k-1=l} =p

(k-1)

ilplji,j=1,2,…,N 其中用到马尔可夫链的“无记忆性”和齐次性。用矩阵表示,即为

p

(k)=P

(k-1)

P,从而可得 p

(k)=Pkk≥1 记t0为过程的开始时刻,pi(0)=P{X0=X(t0)=i},则称

P(0)=(p1(0),p2(0),…,pN(0))(6.4) 由全概率公式可知,对k≥1,有（其中P(0)表示单67 为初始状态概率向量。 如已知齐次马尔可夫链的转移矩阵P=(pij)以及初始状态概率向量P(0),则任一时刻的状态概率分布也就确定了： 对k≥1,记pi(k)=P{Xk=i},则由全概率公式有

pi(k)=pj(0)·p

(k)

jii=1,2,…,N;k≥1(6.5) 若记向量P(k)=(p1(k),p2(k),…,pN(k)),则上式可写为 P(k)=P(0)P(k)=P(0)Pk(6.6) 由此可得

P(k)=P(k-1)P(6.7) 为初始状态概率向量。68 例6.1考察一台机床的运行状态。机床的运行存在正常和故障两种状态。由于出现故障带有随机性,故可将机床的运行看作一个状态随时间变化的随机系统。可以认为,机床以后的状态只与其以前的状态有关,而与过去的状态无关,即具有无后效性。因此,机床的运行可看作马尔可夫链。 设正常状态为1,故障状态为2,即机床的状态空间由两个元素组成。机床在运行过程中出现故障,这时从状态1转移到状态2；处于故障状态的机床经维修,恢复到正常状态,即从状态2转移到状态1。 例6.1考察一台机床的运行状态。机床的运行存在正常和故69 现以1个月为时间单位。经观察统计,知从某月份到下月份机床出现故障的概率为0.2,即p12=0.2。其对立事件,保持正常状态的概率为p11=0.8。在这一时间,故障机床经维修返回到正常状态的概率为0.9,即p21=0.9；不能修好的概率为p22=0.1。机床的状态转移情形见图6.1。 现以1个月为时间单位。经观察统计,知从某月份到下月份机床70图6.1机床的状态转移图6.1机床的状态转移71 由机床的一步转移概率得状态转移概率矩阵

若已知本月机床的状态向量P(0)=(0.85,0.15),现要预测机床两个月后的状态。先求出两步转移概率矩阵 矩阵的第一行表明,本月处于正常状态的机床,两个月后仍处于正常状态的概率为0.82，转移到故障状态的概率为0.18。第二行说明,本月处于故障状态的机床,两个月后转移到正常状态的概率为0.81,仍处于故障状态的概率为0.19。 由机床的一步转移概率得状态转移概率矩阵72 于是,两个月后机床的状态向量 6.1.3稳态概率矩阵 1．平稳分布 若存在非零概率向量X=(x1,x2,…,xN),使得XP=X,其中P为一概率矩阵,则称X为P的固定概率向量。 特别地,设X=(x1,x2,…,xN)为一状态概率向量,P为状态转移概率矩阵。若

XP=X 于是,两个月后机床的状态向量73

即 则称X为马尔可夫链的一个平稳分布。若随机过程某时刻的状态概率向量P(k)为平稳分布,则称过程处于平衡状态。一旦过程处于平衡状态,则过程经过一步或多步状态转移之后,其状态概率分布保持不变,也就是说,过程一旦处于平衡状态后将永远处于平衡状态。 对于我们所讨论的状态有限（即N个状态）的马尔可夫链,平稳分布必定存在。特别地,当状态转移矩阵为正规概率矩阵时,平稳分布惟一。此时,求解方程(6.8),即可得到系统的平稳分布。j=1,2,…,N 即j=1,2,…,N74 2．稳态分布 对概率向量π=(π1,π2,…,πN),如对任意的i,j∈S,均有 或

这也是称π为稳态分布的理由。 设存在稳态分布π=(π1,π2,…,πN),则由于下式恒成立: P(k)=P(k-1)P 2．稳态分布75 令k→+∞,就得

π=πP(6.10) 即有限状态马尔可夫链的稳态分布如存在,那么它也是平稳分布。 对任一状态i,如果{k|p

(k)ii>0}的公约数为1,则称状态i为非周期状态。 如果一个马尔可夫链的所有状态均是非周期的,则称此马尔可夫链是非周期的。 对非周期的马尔可夫链,稳态分布必存在,对不可约非周期的马尔可夫链,稳态分布和平稳分布相同且均惟一。 令k→+∞,就得76 例6.2设一马尔可夫链的状态转移矩阵为 求其平稳分布及稳态分布。 解（1）P不可约。pij>0,仅当i≠2且j≠2时。又p(2)22>0,由定义可知,P是不可约的。 例6.2设一马尔可夫链的状态转移矩阵为77 （2）P非周期。 由p

(1)

11>0,p

(2)11>0,而1、2的公约数为1,故状态1为非周期状态。同理可得状态2、3均为非周期状态。故P是非周期的 （3）由于P不可约且是非周期的,求解如下方程组: 得X=［0.40.20.4］,这就是该马尔可夫链的稳态分布,而且也是平稳分布。 （2）P非周期。786.2马尔可夫预测的应用 6.2.1市场占有率的预测 我们结合例题来说明如何预测市场占有率。 例6.3伍迪公司、布卢杰.里维公司、雷恩公司(分别用符号A、B、C代表)是美国中西部地区生产灭虫剂的三家主要厂商。根据历史资料得知,公司A、B、C产品销售额的市场占有率分别为50%、30%、20%。由于C公司实行了改善销售与服务方针的经营管理决策,使其产品销售额逐期稳定上升,而A公司的产品销售额却在下降。通过市场调查发现三个公司间的顾客流动情况如表6.1所示。6.2马尔可夫预测的应用 6.2.1市场占有率的预测79 其中产品销售周期是季度。现在的问题是,按照目前的趋势发展下去,A公司的产品销售额或客户转移的影响将严重到何种程度？更全面地,三个公司的产品销售额的占有率将如何变化？ 其中产品销售周期是季度。现在的问题是,按照目前的趋势发展80表6.1A、B、C三公司的顾客流动情况表6.1A、B、C三公司的顾客流动情况81 将表6.1中的数据化为转移概率将对研究分析未来若干周期的顾客流向更为有利。表6.2列出了各公司顾客流动的转移概率。表6.2中的数据是每家厂商在一个周期中的顾客数与前一周期的顾客数相除所得。表中每一行表示某公司从一个周期到下一个周期将能保住的顾客数的百分比,以及将要丧失给竞争对手的顾客数的百分比。表中每一列表示各公司在下一周期将能保住的顾客数的百分比,以及该公司将要从竞争对手那里获得顾客数的百分比。 将表6.1中的数据化为转移概率将对研究分析未来若干周期的82表6.2顾客流动的转移概率表6.2顾客流动的转移概率83 如用矩阵来表示表6.2中的数据,就得到了如下的状态转移矩阵: P中数据表示一个随机挑选的某公司的顾客,到下一个周期购买该公司或另一公司产品的可能性或概率。如随机挑选一名A公司的顾客,他在下一周期仍购买A公司产品的概率为0.7,购买B公司产品的概率为0.1,购买C公司产品的概率为0.2。(6.11) 如用矩阵来表示表6.2中的数据,就得到了如下的状态转移矩84 1.未来各周期市场占有率的计算 以A、B、C公司作为我们要分析的系统的状态,那么状态概率向量就分别为三家公司的产品销售额的市场占有率。初始状态概率向量为 P(0)=(p1(0),p2(0),p3(0))=(0.5,0.3,0.2) 转移矩阵由式（6.11）给出。于是可用式（6.6）来计算未来各期的市场占有率。如状态转移一次后第1周期的市场占有率向量为 1.未来各周期市场占有率的计算85

2.稳态市场占有率 计算未来各期的市场占有率向量P(k)可以看出,A公司的市场占有率将逐期下降,而C公司的市场占有率则将逐期上升。从经营决策和管理的角度来看,自然希望了解各公司的市场占有率最终将达到什么样的水平,亦即需要知道稳态市场占有率。

86 由于式(6.11)中的P是不可约非周期的,因此稳态市场占有率即为平衡状态下的市场占有率,亦即马尔可夫链的平稳分布。 由前面的讨论知道,我们求解如下方程组： 由于式(6.11)中的P是不可约非周期的,因此稳态市场占87 解得

x1=0.1765,x2=0.2353,x3=0.5882 亦即,A、B、C三家公司的市场占有率最终将分别达到17.65%、23.53%、58.82%。 对本例来说,当销售份额达到平衡时,各公司分别占总销售额中的那一部分均保持不变。 但在某些情况下,参与竞争的公司或厂商中可能会有一个或多个被完全逐出市场。例如对于转移矩阵 解得88 3.销售策略对市场占有率的影响 (1)保留策略：指尽力保留公司原有顾客的各种经营方针与对策。如采用提供优质服务或对连续两期购货的顾客实行折价优惠等方法。设Ａ公司采用这样的保留策略后,减少了其原有顾客向Ｃ公司的流失,使保留率从原来的70％提高到85％,则转移矩阵成为 3.销售策略对市场占有率的影响89 新的平衡状态下Ａ、Ｂ、Ｃ三公司的市场占有率分别为31.6％、26.3％、42.1％,Ａ公司的市场占有率从17.65％提高到31.6％。 (2)争取策略：指从竞争者拥有的顾客中争取顾客的各种经营方针与对策。如通过广告等方法。设Ａ公司通过争取策略,能从上一周期内向另外两家公司购货的顾客中各争取15％,则转移矩阵成为 新的平衡状态下Ａ、Ｂ、Ｃ三公司的市场占有率分别为31.90 6.2.2期望报酬预测 在一个与经济有关的马尔可夫型随机系统中,系统获得的报酬(或称收益)也会随状态的不同而不同。设有一台机器,它在第n周期的状态用Xn表示： 0第n周期正常 1第n周期失效 进一步假定,机器正常时,每一个周期可带来v元的收益,并且在下一周期失效的概率为p； Xn= 6.2.2期望报酬预测Xn=91 当机器失效时,需对其进行更换,更换的费用为d,修理时间为一个周期,下一个周期初修好并开始正常工作,于是{Xn}是一个齐次马尔可夫链,其状态空间为S={0,1},转移矩阵为 但这是一个带报酬(或称收益、费用)的马尔可夫链。 当机器失效时,需对其进行更换,更换的费用为d,修理时间为92 一般地,设{Xn}是状态空间为S={1,2,…,N}的齐次马尔可夫链,其转移矩阵为P=(pij)N×N。设r(i)表示某周期系统处于状态i时获得的报酬。我们称如此的马尔可夫链是具有报酬的。显然,r(i)＞0时,称为盈利、报酬、收益等；r(i)＜0时,称为亏损、费用等。对于这样一个带报酬的马尔可夫链,n时的报酬是一个随机变量。 1．有限时段期望总报酬 记vk(i)表示初始状态为i的条件下,到第k步状态转移前所获得的期望总报酬(k≥1,i∈S)： 一般地,设{Xn}是状态空间为S={1,2,…,93

若记列向量Vk=［vk(1)vk(2)…vk(N)］T,r=［r(1)r(2)…r(N)］T,则上式可写为 (6.12) (6.12)94 这里,I表示单位矩阵。进而,可证明有如下递推式：

v0(i)=0i=1,2,…,N 于是可用上式递推求得vk(i)。 2．无限时段单位时间平均报酬 对i∈S,定义初始状态为i的无限时段单位时间平均报酬为k≥0;i=1,2,…,N

(6.13) 这里,I表示单位矩阵。进而,可证明有如下递推式：k95 记 矩阵P*=(p*ij),则由式(6.12)可证得 于是为求v(i),只须求得P*即可,但一般地要求出P*并不是件容易的事。这里我们只讨论如下的特殊情况。 我们考虑稳态分布π=［π1

π2…πN］存在的这种特殊情况。i,j=1,2,…,N

(6.14) 记i,j=1,2,…,N(6.14)96 由上节可知,转移矩阵P非周期即可保证π存在。当π存在时,它也是平稳分布。注意到数学分析中的一个结论：设数列an有极限a,则 于是,我们有如下结论。 结论设所考虑的马尔可夫链存在稳态分布π,则

p*ij=πj,j=1,2,…,N。进而若式(6.10)有惟一解X=［x1

x2…xN］,则有 p*ij=πj=xjj=1,2,…,N(6.15) 由上节可知,转移矩阵P非周期即可保证π存在。当π存在时,97 实际上,如果π存在,当式(6.10)有惟一解X时,由于稳态分布必为平稳分布,故πj=xj。 特别地,对于不可约非周期的马尔可夫链,式(6.15)恒成立。于是可先求解式(6.10)得X,进而由式(6.15)求得v(i)。 3．无限时段期望折扣总报酬 在现实生活中,今年的一元钱将大于明年的一元钱,其实将钱存于银行即可。也就是说明年的一元钱折算到现在计算,就不值一元钱了,如为β∈(0,1),这个β就称为折扣因子。 实际上,在企业管理中当考虑贷款、折旧等时都必须考虑到钱的增值问题。 实际上,如果π存在,当式(6.10)有惟一解X时,由于稳98 如将钱存于银行,年息为ρ,则ρ与β有如下关系： 如果一个周期为一个月,那么只须将ρ理解为月息即可。这里折扣因子β一般在区间(0,1)中。 对有报酬的马尔可夫链,定义从状态i出发的无限时段期望折扣总报酬为(6.16)(6.17) 如将钱存于银行,年息为ρ,则ρ与β有如下关系：99 若记向量Vβ=［vβ(1)vβ(2)…vβ(N)］T,则上式的向量或矩阵形式为 与有限时段中的式(6.13)类似,由式(6.17)可得(6.18)(6.19) 若记向量Vβ=［vβ(1)vβ(2)…vβ(N)］100 例6.4最佳维修策略的选择。我们研究一化工企业对循环泵进行季度维修的过程。该化工企业对泵进行定期检查,每次检查中,把泵按其外壳及叶轮的腐蚀程度定为五种状态中的一种。这五种状态是： 状态1：优秀状态,无任何故障或缺陷； 状态2：良好状态,稍有腐蚀； 状态3：及格状态,轻度腐蚀； 状态4：可用状态,大面积腐蚀； 状态5：不可运行状态,腐蚀严重。 该公司可采用的维修策略有以下