马尔科夫分析

1、9.5 马尔柯夫分析马尔柯夫过程（Markov process）的基本概念是俄国数学家AA马尔柯夫在1907年提出的，最初马尔柯夫用这种概念来描述物理学中的布朗运动。 基本思想是：事物的第n步状态仅取决于第n-1步所处的状态，在这种状态的转移过程中存在一转移概率，这一转移概率可依据其相邻接的前步状态和概率推算出来。这种无后效性的转移过程称为马尔柯夫过程，一连串这种转移过程的集合，称为马尔柯夫链。 马尔柯夫分析已经成为市场预测的有效工具，用来预测顾客的购买行为和商品的市场占有率，还可以用来确定企业劳动力的需求、引进新产品、选择广告计划等。第一节第一节 基本原理基本原理 一、基本概念 1.随机变量

2、 、 随机函数与随机过程 一变量x，能随机地取数据（但不能准确地预言它取何值），而对于每一个数值或某一个范围内的值有一定的概率，那么称x为随机变量。 假定随机变量的可能值xi发生概率为Pi 即P(x = xi) = Pi 对于xi的所有n个可能值，有离散型随机变量分布 列： Pi = 1 对于连续型随机变量，有 P(x)dx = 1 在试验过程中，随机变量可能随某一参数（不一定是时间）的变化而变化. 如测量大气中空气温度变化x = x(h),随高度变化。这种随参变量而变化的随机变量称为随机函数。而以时间t作参变量的随机函数称为随机过程。 也就是说：随机过程是这样一个函数，在每次试验结果中，它以

3、一定的概率取某一个确定的，但预先未知的时间函数。 2、马尔科夫过程 随机过程中，有一类具有“无后效性性质”，即当随机过程在某一时刻to所处的状态已知的条件下，过程在时刻tto时所处的状态只和to时刻有关，而与to以前的状态无关，则这种随机过程称为马尔科夫过程。 即是：ito为确知,it(tto)只与ito有关，这种性质为无后效性，又叫马尔科夫假设。 3、马尔科夫链 时间和状态都是离散的马尔科夫过程称为马尔科夫链。例：蛙跳问题 假定池中有N张荷叶，编号为1，2，3,N，即蛙跳可能有N个状态（状态确知且离散）。青蛙所属荷叶，为它目前所处的状态；因此它未来的状态，只与现在所处状态有关，而与以前的状态

4、无关（无后效性成立） 写成数学表达式为： 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 P1N 定义为 P21 P22

5、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.稳定性假设 若系统的一步状态转移概率不随时间变化，即转移矩阵在各个时刻都相同，称该系统是稳定的。 这个假设称为稳定性假设。蛙跳问题属于

6、此类，后面的讨论均假定满足稳定性条件。 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的 二步状态转移概率. 解：作状态转移图 解法一：由状态转

7、移图： 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(2) = P11 P12

8、 + 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状态 进行概率计算时，第二十四个季度为

9、畅销，但后续是什么状态不知，故计算时不能采用，只用于第二十三季度统计。有： 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) P11(2) P1

10、1(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，所以它不是正规概率矩阵。

11、 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的每一个行向量都是固定概率

12、向量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 U2 UN = U

13、例：若 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 0.5 0.25 0

14、.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期的销售额（

15、或拥有顾客数） x为同类产品在市场上总销售额（或顾客数）市场占有率所需数据可通过顾客抽样调查得到。 一般地,首先考虑初始条件,设当前状态（即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

16、)PNi(k) P1i(k) = xS1(0) S2(0) P2i(k) : PNi(k) 有：Si(k) = xi(k)/x P1i(k) = S1(0) S2(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)市场调查,求得目前状况,即初始

17、分布 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 P3= P21(3) P22(3) P23(3) = P = 0.504

18、 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.252S1(3) = 0.40.496 +0.30.504 + 0.30.504 = 0.5008S2(3) = 0.2496S3(3) = 0.2496 二.长期市场占有率预测 这是求当 k 时 S(k) ? 我们知道: S(k) = S(0) P lim S(k) = S(0) lim P = S(0)T = U

19、 因此,在已知初始条件下求长期市场占有率就是求稳态概率矩阵,也是求固定概率向量. 求固定概率向量的方法,我们在前一节已有例子,只不过说明了长期市场占有率也是只与稳态矩阵有关,与初始条件无关. 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%的长期市场. 案例一案例一: :假设有N个相互独立的房间，编号为1，2，N。假设有一个人随机地从这个房间走到那个

20、房间，在时刻 时，它所在的那个房间，我们称 为其所处的状态。那么这个人未来将处于什么样的状态只与他现在所处的状态 （i=1,2,N）有关，与他之前所处在哪个房间无关（即无后效性）。记 为时刻 时人所处的状态， 就是一个均匀的马尔柯夫链，则:表示在时刻 人在第i个房间，在下一时刻 走到第j个房间的可能性，又称为从状态 经一步转移到 的概率，简称为一步转移概率，将所有的 依次排列起来，就构成了一个转移概率矩阵。nt12 ,nx xx1(|), ,1,2,njniijP xSxSP i jnnt1ntiSjSijP案例二案例二: :设某种商品的销售情况分为“畅销”和“滞销”两种，“1”表示畅销，“2

21、”表示滞销。以 表示第n年的销售状态，则 可取值为1或2。若未来的商品销售状态只与现在的市场状态有关，而与以前的市场状态无关，则该商品的市场状态 ,n=1就构成了一个马尔柯夫链。设：则其中 （连续畅销的可能性） （由畅销转入滞销的可能性） （由滞销转入畅销的可能性） （连续滞销的可能性）则转移概率矩阵为 nxnxnx1(|)( ,1,2, )njnjijP xSxSP i jn110.5P 120.5P 210.4P 220.5P 2.2.带利润的马尔柯夫带利润的马尔柯夫链链在案例二中，商品的销售状态有畅销和滞销两种，多数情况下畅销就意味着盈利，而滞销就意味着亏本，因此随着商品销售状态的转移，

22、伴随着利润的产生，这种随着马尔柯夫链状态转移，赋予一定的利润，称为带利润的马尔柯夫链。 对于有N个状态的马尔柯夫过程，当系统由状态i转移到状态j时，假定获得相应的 “利润”为 ，则称 为系统的利润矩阵，表示了对应于全部可能状态转移的利润和效益联系。ijr由于状态转移是随机的，因此一系列利润是随机变量，其概率关系由马尔柯夫链的转移概率决定。我们假设对于马尔柯夫链，如果系统现在处于状态i，在经过n次状态转移之后的期望利润是多少？设对于每个概率转移矩阵 ，有一个利润矩阵 与之相对应。我们定义 为系统现在处于状态i ，经过n次转移之后所获利润的期望总值，则有： i=1,2,N； n=1,2,。 9-1

23、5） 重新整理得到： 记： i=1,2,N 这里 可以解释为由状态i作出一次转移的期望利润，称为状态i的期望直接利润。定义 为期望值向量，令 ，则式9-15可以记为： ()ijPP( )ijRr( )iv n1( )(1)Niijijjjv nP rv n11( )(1)NNiij ijijjjjv nP rP v n1Niij ijjqP riq12( )( ( ),( ),( )TNv nv n v nvn12(,)TNqq qq( )(1)v nqPv n 案例三：案例三：某商品的畅销（状态1）滞销（状态2）情况如案例二中所描述，其过程的概率转移矩阵为： 其利润关系如下：如果某年处于状态

24、1，下一年仍然处于状态1，则其利润为9单位；若下一年处于状态2，则利润为3单位。若某年处于状态2，下一年仍处于状态2，则其损失为7单位；若下一年转移到状态1，则利润为3单位。得到报酬矩阵为 则由得到 若设 ，则由 得依次可以计算出v(4)、v(5)，如下表所示从上表可以看出不同周期销售商的获益情况，并可以得知：v1(n)与v2(n)的差值约为10。这表明，由状态1开始与从状态2开始其经营过程的利润期望值之差为10个单位。3.3.马尔柯夫分析马尔柯夫分析实例实例马尔柯夫预测法在市场分析预测特别是对客户流动性强的商品市场情况预测中有重要的作用。案例案例四：四：随着人们生活水平的提高，咖啡越来越受到人们的喜好，现在某种速溶咖啡的销售商委托信息分析人员作一次预测。市场上流行有三种速溶咖啡：雀巢、麦斯威尔和摩卡咖啡，需要预测在未来若干个月以后的市场占有情况。进行此次预测需要若干个步骤，具体如下：步骤一：进行市场调查，包括以下两方面： 当前的市场占有情况，我们假设调查的结果是：雀巢咖啡的市场占有率40%，麦斯威尔和摩卡的占有率各为30%。 调查顾客的流动情况，假设调查结果为： 上一月份购买雀巢咖啡的顾客本月仍有40%买雀巢咖啡，各有30%转向购买麦斯威尔和摩卡。 上一月份购买麦斯威尔咖啡的顾客本月仍有30%买麦斯