马尔科夫链详解

1马尔科夫Markov链Markov原名A.A.Markov（俄，1856－1922）于1906年开始研究此类问题.2现实世界中有很多这样的现象，某一系统在已知现在情况的条件下，系统未来时刻的情况只与现在有关，而与过去的历史无直接关系。比如，研究一个商店的累计销售额，如果现在时刻的累计销售额已知，则未来某一时刻的累计销售额与现在时刻以前的任一时刻累计销售额无关。描述这类随机现象的数学模型称为马尔科夫模型，简称马氏模型。1马尔可夫链的定义3引例假定某大学有1万学生，每人每月用1支牙膏，并且只使用“中华”牙膏与“黑妹”牙膏两者之一。根据本月（12月）调查，有3000人使用黑妹牙膏，7000人使用中华牙膏。又据调查,使用黑妹牙膏的3000人中，有60％的人下月将继续使用黑妹牙膏，40％的人将改用中华牙膏；使用中华牙膏的7000人中，有70％的人下月将继续使用中华牙膏，30％的人将改用黑妹牙膏。据此，可以得到如表所示的统计表拟用黑妹牙膏中华牙膏现用黑妹牙膏60％40％中华牙膏30％70％4基本概念状态和状态转移状态是指客观事物可能出现或存在的状况。如企业的产品在市场上可能畅销，也可能滞销。状态转移是指客观事物由一种状态到另一种状态的变化。客观事物的状态不是固定不变的，它可能处于这种状态，也可能处于那种状态，往往条件变化，状态也会发生变化。如某种产品在市场上本来是滞销的，但是由于销售渠道变化了，或者消费心理发生了变化等，它便可能变为畅销产品。5定义1设{,1,2,}nXn是一个随机序列，状态空间E为有限或可列集，对于任意的正整数,mn，若,,(1,,1)kijiEkn，有1111{|,,,}{|}nmnnnnmnPXjXiXiXiPXjXi（1）则称{,1,2,}nn为一个马尔可夫链（简称马氏链），（1）式称为马氏性。6事实上，可以证明若等式（1）对于1m成立，则它对于任意的正整数m也成立。因此，只要当1m时（1）式成立，就可以称随机序列{,1,2,}nXn具有马氏性，即{,1,2,}nXn是一个马尔可夫链。7定义2设{,1,2,}nXn是一个马氏链。如果等式（1）右边的条件概率与n无关，即{|}()nmnijPXjXipm（2）则称{,1,2,}nn为时齐的马氏链。称()ijpm为系统由状态i经过m个时间间隔（或m步）转移到状态j的转移概率。（2）式称为时齐性，它的含义是系统由状态i到状态j的转移概率只依赖于时间间隔的长短，与起始的时刻无关。本章介绍的马氏链假定都是时齐的，因此省略“时齐”二字。8转移概率与转移概率矩阵假定某大学有1万学生，每人每月用1支牙膏，并且只使用“中华”牙膏与“黑妹”牙膏两者之一。根据本月（12月）调查，有3000人使用黑妹牙膏，7000人使用中华牙膏。又据调查,使用黑妹牙膏的3000人中，有60％的人下月将继续使用黑妹牙膏，40％的人将改用中华牙膏；使用中华牙膏的7000人中，有70％的人下月将继续使用中华牙膏，30％的人将改用黑妹牙膏。据此，可以得到如表所示的统计表拟用黑妹牙膏中华牙膏现用黑妹牙膏60％40％中华牙膏30％70％9上表中的4个概率就称为状态的转移概率，而这四个转移概率组成的矩阵B＝称为转移概率矩阵。可以看出，转移概率矩阵的一个特点是其各行元素之和为１10对于一个马尔可夫链{,1,2,}nXn，称以m步转移概率()ijpm为元素的矩阵()(())ijPmpm为马尔可夫链的m步转移矩阵。当1m时，记(1)PP称为马尔可夫链的一步转移矩阵，或简称转移矩阵。它们具有下列三个基本性质2转移概率矩阵及柯尔莫哥洛夫定理11（1）对一切,ijE，0()1ijpm；（2）对一切iE，()1ijjEpm；（3）对一切,ijE，1,,(0)0.ijijijpij当时，当时12当实际问题可以用马尔可夫链来描述时，首先要确定它的状态空间及参数集合，然后确定它的一步转移概率。关于这一概率的确定，可以由问题的内在规律得到，也可以由过去经验给出，还可以根据观测数据来估计。13（1）转移概率矩阵中的元素是根据近期市场或顾客的保留与得失流向资料确定的。（2）下一期的概率只与上一期的预测结果有关，不取决于更早期的概率。（3）利用转移概率矩阵进行决策，其最后结果取决于转移矩阵的组成，不取决于原始条件，即最初占有率。用马尔科夫链方法进行决策的特点：主要用于企业产品的市场占有率预测14转移概率矩阵决策的应用步骤1）建立转移概率矩阵。2）利用转移概率矩阵进行模拟预测。3）求出转移概率矩阵的平衡状态，即稳定状态。4）应用转移概率矩阵进行决策。15例1某计算机机房的一台计算机经常出故障，研究者每隔15min观察一次计算机的运行状态，收集了24h的数据（共作97次观察）。用1表示正常状态，用0表示不正常状态，所得的数据序列如下：11100100111111100111101111110011111111100011011011110110110101111011101111011111100110111111001111）建立转移概率矩阵16解设(1,,97)nXn为第n个时段的计算机状态，可以认为它是一个时齐马氏链，状态空间{0,1}E。要分别统计各状态一步转移的次数，即0→0，0→1，1→0，1→1的次数，也就是要统计数据字符串中‘00’，‘01’，‘10’，‘11’四个子串的个数。利用Matlab软件，求得96次状态转移的情况是0→0，8次；0→1，18次；1→0，18次；1→1，52次.17因此，一步转移概率可用频率近似地表示为(程序略)00184{0|0}81813nnpPXX，011189{1|0}81813nnpPXX，101189{0|1}185235nnpPXX，1115226{1|1}185235nnpPXX.18将上述数据序列保存到纯文本文件msdata.txt中，存放在Matlab程序文件所在目录下。见ex1.m19例2设一随机系统状态空间{1,2,3,4}E，记录观测系统所处状态如下4321431123212344331113321222442323112431若该系统可用马氏模型描述，估计转移概率ijp。20解记ijn是由状态i到状态j的转移次数，行和41iijjnn是系统从状态i转移到其它状态的次数，ijn和in的统计数据见表。表ij转移数统计表1234行和in14411102324211344211140142721一步状态转移概率ijp的估计值ˆijijinpn，计算得一步状态转移矩阵的估计为（程序略）2/52/51/101/103/112/114/112/11ˆ4/114/112/111/1101/74/72/7PMatlab程序见ex2.m2260%40%A=30%70%黑妹中华30007000本月市场占有情况转移概率矩阵下月市场占有情况60%40%300070003900610030%70%2）利用转移概率矩阵进行模拟预测23定理1（柯尔莫哥洛夫—开普曼定理）设{,1,2,}nXn是一个马尔可夫链，其状态空间{1,2,}E，则对任意正整数,mn有()()()ijikkjkEpnmpnpm，其中的,ijE。24定理2设P是一步马氏链转移矩阵（P的行向量是概率向量），(0)P是初始分布行向量，则第n步的概率分布为()(0)nnPPP.25例3若顾客的购买是无记忆的，即已知现在顾客购买情况，未来顾客的购买情况不受过去购买历史的影响，而只与现在购买情况有关。现在市场上供应A、B、C三个不同厂家生产的50g袋装味精，用“1n”、“2n”、“3n”分别表示“顾客第n次购买A、B、C厂的味精”。显然，{,1,2,}nn是一个马氏链。若已知第一次顾客购买三个厂味精的概率依次为0.2、0.4、0.4。又知道一般顾客购买的倾向由表所示。求顾客第四次购买各家味精的概率。26表状态转移概率下次购买ABC上次购买ABC0.80.50.50.10.10.30.10.40.227解第一次购买的概率分布为(1)[0.2,0.4,0.4]P，一步状态转移矩阵0.80.10.10.50.10.40.50.30.2P，则顾客第四次购买各家味精的概率为(4)(1)3[0.7004,0.136,0.1636]PPP.283）求出转移概率矩阵的平衡状态，即稳定状态。12121260%40%xxxx30%70%xx1123x74x729现在考虑，随n的增大，nP是否会趋于某一固定向量？先考虑一个简单例子。转移矩阵0.50.50.70.3P，当n时，751212751212nP.又若取751212u，则uPu，Tu为矩阵TP的对应于特征值1的特征（概率）向量，u也称为P的不动点向量。哪些转移矩阵具有不动点向量？为此给出正则矩阵的概念。3转移概率的渐近性质—极限概率分布30定义3一个马氏链的转移矩阵P是正则的，当且仅当存在正整数k，使kP的每一元素都是正数。31定理3若P是一个马氏链的正则阵，那么（1）P有唯一的不动点向量W，W的每个分量为正。（2）P的n次幂nP（n为正整数）随n的增加趋于矩阵W，W的每一行向量均等于不动点向量W。32一般地，设时齐马氏链的状态空间为E，如果对于所有,ijE，转移概率()ijpn存在极限lim()ijjnpn（不依赖于i），或1212()12()jjnnjPnP，则称此链具有遍历性。又若1jj，则同时称12(,,)为链的极限分布。33下面就有限链的遍历性给出一个充分条件。定理4设时齐马氏链{,1,2,}nXn的状态空间为1{,,}NEaa，()ijPp是它的一步转移概率矩阵，如果存在正整数m，使对任意的,ijaaE，都有()0ijpm，,1,2,,ijN则此链具有遍历性；且有极限分布1[,,]N，它是方程组P或1,1,,NjiijiPjN满足条件10,1Njjj的唯一解。34例4根据例3中给出的一般顾客购买三种味精倾向的转移矩阵，预测经过长期的多次购买之后，顾客的购买倾向如何？解这个马氏链的转移矩阵满足定理的条件，可以求出其极限概率分布。为此，解下列方程组：，1123212331231230.80.50.50.10.10.30.10.40.21ppppppppppppppp求得1235/7,11/84,13/84ppp。35这说明，无论第一次顾客购买的情况如何，经过长期过次购买以后，A厂产的味精占有市场的5/7，B、C两厂产品分别占有市场11/84,13/84。Matlab程序见ex3.m或者利用求转移矩阵P的转置矩阵的特征值1对应的特征概率向量，求得极限概率。Matlab程序见ex4.m36马尔科夫决策方法实例例:设某地区有甲、乙、丙三家企业，生产同一种产品，共同供应1000家用户。假定在10月末经过市场调查得知，甲、乙、丙三家企业拥有的用户分别是：250，300，450户，而11月份用户可能的流动情况如下：现要求我们根据这些市场调查资料预测11、12两个月三家企业市场用户各自的拥有量。到从甲乙丙合计甲乙丙23010102503004502025030301041037步骤：根据调查资料，确定初始状态概率向量为：根据市场调查情况，确定一次转移概率矩阵为：0000123250300450XXXX0.250.300.45100010001000