马尔科夫预测与决策法

马尔科夫预测与决策法2010年6月6日Sunday2Š马尔科夫预测与决策法——是应用随机过程中马尔科夫链的理论和方法研究分析有关经济现象变化规律并借此对未来进行预测和决策的一种方法。Š池塘里有三张荷叶，编号为1，2，3，假设有一只青蛙随机地在荷叶上跳来跳去。在初始时刻t0，它在第二张荷叶上。在时刻t1，它有可能跳到第一张或者第三张荷叶上，也有可能在原地不动。我们把青蛙某个时刻所在的荷叶称为青蛙所处的状态。这样，青蛙在未来处于什么状态，只与它现在所处的状态有关，与它以前所处的状态无关。实际上青蛙在一段时间内在荷叶间跳或不跳的过程就是一个马尔科夫过程。2010年6月6日Sunday3马尔可夫性与转移概率矩阵一个过程或系统在未来时刻的状态只依赖于现状时刻的状态，而与以往更前的时刻无关，这一特性就成为无后效性（无记忆性）或马尔可夫性（简称马氏性）。换一个说法，从过程演变或推移的角度上考虑，如果系统在时刻的状态概率，仅依赖于当前时刻的状态，而与如何达到这个状态的初始概率无关，这一特性即马尔可夫性。2010年6月6日Sunday4设随机变量序列，{X1,X2,···,Xn,···},它的状态集合记为S={s1,s2,···,sn,···}若对任意的k和任意的正整数i1,i2,···,ik,ik+1,有下式成立：P{Xk+1=sik+1|X1=si1,X2=si2,···Xk=sik}=P{Xk+1=sik+1|Xk=sik}则称随机变量序列{X1,X2,···,Xn,···}为一个马尔可夫链（Markovchains）。2010年6月6日Sunday5如果系统从状态si转移到状态sj，我们将条件概率P{si|sj}称为状态转移概率，记作：P(si|sj)=pij简单地说，pij是从i到j的转移概率。对于条件概率,()njissXPPjikkijL,2,1,,1)(===+称为从状态si到sj的k步转移概率。当k=1时，称为从si到状态sj的一步转移概率。2010年6月6日Sunday6如果一个经济现象有n状态s1,s2,···,sn,状态的转移是每隔单位时间才可能发生，而且这种转移满足马氏性的要求，那么我们就可以把所研究的经济现象视为一个马尔可夫链。虽然一个经济现象是复杂的，但只要具有马氏性，我们便可以简单而方便的进行预测和决策。需要指出的是，马尔可夫链适用于近期资料的预测和决策。例如，在对某公司的一种商品的市场占有率进行预测时，就可以利用这种模型加以解决。又如对一个工厂转产的前景进行预测时，也同样可以利用这种方法来处理。在预测的基础上，在利用这种方法进行决策，即马尔可夫决策。需要指出的是，这里我们只限于研究一种特殊的马尔可夫链，即齐次马尔可夫链。所谓齐次是指状态转移概率与状态所在的时间无关，而且这里只考虑状态集是有限的情形。2010年6月6日Sunday7假设系统的状态为s1,s2,···,sn共n个状态，而且任一时刻系统只能处于一种状态si，那么下一个单位时间，它可能由si转向s1,s2,···,si,···,sn中之一状态；相应的转移概率为pi1,pi2,···,pii,···,pin。因此有)1(,,2,1,1101nippnjijijL==≤≤∑=2010年6月6日Sunday8不难看出，一般的矩阵并不一定满足式（1），因此我们称式（2）的矩阵P(或P(k))为随机矩阵，或概率矩阵。)2(212222111211⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=nnnnnnpppppppppPLLLLLLL并称矩阵为状态转移概率矩阵。对于k步转移概率矩）也满足式（其中1,)()()()(kijnmkijkppP×=2010年6月6日Sunday9稳态概率定义设{Xn,n≥0}为有限状态齐次马尔科夫链，对所有的i,j=1,2,···,N,存在与i无关的极限jkijkPπ=∞→)(lim其中πj为常数，则称此{Xn,n≥0}为具有遍历性的马尔科夫链。2010年6月6日Sunday10举例：讨论转移概率矩阵的遍历性。定理设{Xn,n≥0}为有限状态齐次马尔科夫链，P为其一步转移概率矩阵，若存在正整数s0，使对所有的i,j=1,2,···,N，有0)(sijp则此马尔科夫链满足遍历性。⎟⎟⎠⎞⎜⎜⎝⎛=⎟⎟⎠⎞⎜⎜⎝⎛=⎟⎟⎠⎞⎜⎜⎝⎛=5.05.001)3(,6.04.010)2(,4.06.06.04.0)1(321PPP2010年6月6日Sunday11设P是标准概率矩阵，则必存在非零向量π=(π1,π2,···,πn)使得πP=π称π为P的平衡向量。如果进一步满足：π1+π2+···+πn=1称此πj为状态sj的稳态（平衡）概率。P的这一特性在实用中有重要的价值。通常在市场预测中，所讨论的用户转移概率矩阵就属于标准概率矩阵，它可以通过几步转移达到稳定（平衡）状态。在这种情况下，各厂家的用户占有率不再发生变化，此时的π称为最终用户的占有率P向量。2010年6月6日Sunday12例1某地区有甲、乙、丙三家食品厂生产同一食品，有1000个用户（或订购点）。假设在研究期间无新用户加入业务老用户退出，只有用户的转移。已知2009年5月份有500户是甲厂的顾客；400户是乙厂的顾客；100户是丙厂的顾客。6月份，甲厂有400户原来的顾客，上月的顾客有50户转乙厂，50户转丙厂；乙厂有300户原来的顾客，上月的顾客有20户转甲厂，80户转丙厂；丙厂有80户原来的顾客，上月的顾客有10户转乙厂，10户转甲厂。试计算其状态转移概率。2010年6月6日Sunday13解：由题意得6月份的顾客转移表（表1）1000210360430合计100801010丙4008030020乙5005050400甲合计丙乙甲从2010年6月6日Sunday14由表1可知，6月份有430户是甲厂的顾客，360户是乙厂的顾客，210户是丙厂的顾客。于是，8.0100801.0100101.0100102.04008075.040030005.0400201.0500501.0500508.0500400333231232221131211==================PPPPPPPPP2010年6月6日Sunday15故转移矩阵⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛=8.01.01.02.075.005.01.01.08.0P2010年6月6日Sunday16一般地，马尔可夫链的二步转移概率阵P(2)中任一元素p(2)ij可以用下一公式来计算：p(2)ij=PTi*Pj∑==++=++=++=⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛=312331323121311213321322121211212311321121111211333231232221131211KKjiKijPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP即设2010年6月6日Sunday17用矩阵表示⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛=⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛=333231232221131211333231232221131211)2(33)2(32)2(31)2(23)2(22)2(21)2(13)2(12)2(11)2(PPPPPPPPPPPPPPPPPPPPPPPPPPPP即P(2)=P·P=P2,从而可得P(n)=P·P·P···P=Pn=PP(n-1)=P(n-1)P2010年6月6日Sunday18例2某经济系统有三种状态（比如畅销、一般，滞销）。系统状态转移情况见表2。试求系统的两步和五步转移概率矩阵。状态次数状态系统本部所处状态系统下步所处状态E1E1E3E2E2E321714168108122表2系统状态转移情况表解：按照与例1相同的步骤可得一步状态转移概率矩阵⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛=1.04.05.0334.0222.0444.0333.0167.05.0P2010年6月6日Sunday19于是⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛=⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛=31.021.048.025.026.049.026.025.049.01.04.05.0334.0222.0444.0333.0167.05.02)2(P⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛=⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛==27.024.049.027.024.049.027.024.049.031.021.048.025.026.049.026.025.049.02)2()2()4(PPP⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛=⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛=⋅=27.024.049.027.024.049.027.024.049.027.024.049.027.024.049.027.024.049.01.04.05.0333.0222.0444.0333.0167.05.0)4()5(PPP2010年6月6日Sunday20马尔可夫分析方法马尔可夫分析方法是用近期资料进行预测和决策的方法，目前已广泛用于市场需求的预测和销售市场的决策。这里只讨论这种方法的主要用途，即利用它来进行决策。其基本思想方法主要是利用转移概率矩阵和它的收益（或利润）矩阵进行决策。设市场销售的转移概率矩阵为⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=nnnnnnpppppppppPLLLLLLL2122221112112010年6月6日Sunday21其中pij表示从状态i经过一个单位时间（比如一个月、一个度、一年等）转移到状态j的概率（即一步转移概率）,又设在经营过程中，从每一状态转移到另一状态时都会带来赢利（负值表示亏损），用rij表示从销售状态i转移到j的赢利。这时赢利矩阵为⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=nnnnnnrrrrrrrrrRLLLLLLL2122221112112010年6月6日Sunday22在现时为销售状态i，下一步的销售期望赢利为qi=pi1ri1+pi2ri2+···+pinrin,i=1,2,···,n现设有k个可能采取的措施（即策略），则在第k个措施下的转移概率矩阵、赢利矩阵分别为⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=)()()()()()()()()()()()()()()()()()(212222111211212222111211krkrkrkrkrkrkrkrkrRkpkpkpkpkpkpkpkpkpPnnnnnnknnnnnnkLLLLLLLLLLLLLL2010年6月6日Sunday23用fi(N)表示现在状态i，经N个时刻并选择最优策略的总期望赢利，则有[]niNNfkpkqNfkrkpnfnjjijimknjjijijmki,,2,1;,2,1)()()()()()()1(1111maxmaxLL==⎭⎬⎫⎩⎨⎧+=⎭⎬⎫⎩⎨⎧+=+∑∑=≤≤=≤≤)()()(1krkpkqijnjiji∑==当现时为状态i，采取第k个策略，经一步转移后的期望赢利为2010年6月6日Sunday24马尔科夫决策案例例3某地区有甲、乙、丙三家公司，过去的历史资料表明，这三家公司某产品的市场占有率分别为50%，30%和20%。不久前，丙公司制定了一项把甲、乙两公司的顾客吸引到本公司来的销售和服务措施。设三家公司的销售和服务是以季度为单位考虑的。市场调查表明，在丙公司新的经营方针的影响下，顾客的转移概率矩阵为⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛=90.005.005.010.080.010.020.010.070.0P使用马尔科夫分析方法研究此销售问题，并分别求出三家公司在第一、二季度各拥有的市场占有率和最终的市场占有率。2010年6月6日Sunday25解：设随机变量Xt=1,2,3(t=1,2,3)分别表示顾客在t季度购买甲、乙和丙公司的产品，显然{Xt}是一个有限状态的马尔科夫链。已知P(X0=1)=0.5,P(X0=2)=0.3,P(X0=3)=0.2，又已知马尔科夫链的一步转移概率矩阵，于是第一季度的销售份额为()()31.030.039.090.005.005.010.080.010.020.010.070.020.030.050.0=⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛即第一季度甲、乙、丙三公司占有市场的销售份