医学信息分析：第5章 马尔可夫预测与决策

1、第5章 马尔可夫预测与决策,安德雷马尔可夫（18561922） 俄国数学家，师从切比雪夫，主要研究领域在概率和统计方面。他的研究开创了随机过程这个新的领域，以他的名字命名的马尔可夫链在现代工程、自然科学和社会科学各个领域都有很广泛的应用。,时间参数集,状态空间,5.1 马尔可夫过程 1. 马尔可夫过程是一种随机过程: 当随机过程在t时刻所处的状态已知时， 在t+1时刻所处的状态仅与t时刻的 状态有关， 而与t时刻以前的状态无关。此特性称为随机过程的无后效性或马尔可夫性 过去只影响现在，而不影响将来。 P将来|现在、过去=P将来|现在 t1时刻 t2时刻 tn时刻,状态1,状态2,状态n,按其状

2、态空间和时间参数集是连续还是离散 可分成四类:,仅讨论马尔可夫链,2.马尔可夫链,定义：随机过程X(t)在tn时刻的状态为Xn=X(tn)，且Xn可能取得的状态必为a1 a2 an之一，其中 AI=a1 a2 an为有限的状态空间， 随机过程只在t1 t2 tn 可列个时刻发生状态转移。 若随机过程在tn+1时刻变成 任一状态aj的概率， 只与过程在tn时刻的状态ai有关，而与过程在 tn时刻以前的状态无关，则称此随机过程为马尔可夫链，简称为马氏链。 PX(tn+1)= aj| X(tn) = ai ,X(tn-1)= an-1 ,X(t0)= a0 = PX(tn+1)= aj| X(tn)

3、 = ai,1.一步转移概率矩阵 一步转移概率定义：马氏链在tn时刻处于状态ai条件下，到tn+1时刻转移到状态aj的条件概率，称为在tn时刻的一步转移概率，记为p(1)ij(n)或者pij(n)。 (1) 0 = pij(n) =1 N (2) pij(n) =1 j=1,5.2 状态转移矩阵,一步转移矩阵定义：由所有状态（N个）之间，在tn时刻的一步转移概率pij(n) 构成的矩阵，称为在tn时刻的一步转移矩阵。 p11 p12 . . p1N P= p21 p22 . . p2N : : ： : pN1 pN2 . . pNN 如果一步转移概率pij(n) 与时刻tn无关， pX(tn+

4、1)= aj| X(tn) = ai = pX(tn+1)= aj，则称该马尔可夫链是齐次的。,（P54)例5-2概率与任何时刻无关，只和位置有关，是齐次马尔可夫链，一步转移矩阵为： p11 p12 . . p14 p15 P= p21 p22 . . p24 p25 : : ： : : p51 p52 . . p54 p55 0 1 0 0 0 = 1/3 1/3 1/3 0 0 0 1/3 1/3 1/3 0 0 0 1/3 1/3 1/3 0 0 0 1 0,概率向量：任意行(列)向量，其每个元素非负且 总和等于1 概率矩阵：由概率向量作为行向量构成的方阵。 2. k步状态转移矩阵 k步

5、转移概率定义：齐次马氏链在tn时刻处于状态ai条件下，到tn+k时刻转移到状态aj的条件概率，称为在tn时刻的k步转移概率，记为p(k)ij(n)，由于马氏链是齐次的，这个概率与n无关，简记为p(k)ij (1) 0 = p(k)ij=1 N (2) p(k)ij =1 j=1,k步转移矩阵定义：所有状态之间的k步转移概率p(k)ij为元素构成的矩阵，记为P(k)或Pk p(k)11 p(k)12 . . p(k)1n Pk = p(k)21 p(k)22 . . p(k)2n : : ： p(k)n1 p(k)n2 . . p(k)nn 1 当i等于 j 规定P0 = （单位矩阵） 0 当i

6、不等于 j P1 为一步转移矩阵,2步转移概率可由一步转移概率求出： n p(2)ij = pik pkj (一步矩阵第i行乘以第j列元素的乘积和) k=1 含义：从状态ai出发，经一步到达状态ak ,然后再从ak经一步到达状态aj 的概率之和。 因此2步转移概率矩阵为： P(2) = P2 类似k步转移概率矩阵为: P(k) = Pk (k=1) 即当马氏链是齐次的（满足稳定性）， k步转移概率矩阵为一步转移概率矩阵的k次方。,矩阵相乘,P56 例5-3 设一步转移概率矩阵： 0.5 0.5 0.5 P = 0.6 0.4 0.6 0.5 0.55 0.45 则P(2)= P2= 0.54

7、0.46 0.4 P(2)11= 0.5*0.5 + 0.5*0.6 = 0.55 1 1 1 1 2 1,1,2,P56 例5-4 设一步转移概率矩阵： 0.7 0.7 0.3 P = 0.9 0.1 0.9 0.3 0.76 0.24 则P(2)= P2= 0.72 0.28 初始概率向量 P(0) = 0.8 0.2 0.1 求一步转移后机床无故障概率？(两种可能) p1(1) = p1(0)* p11+ p2(0)* p21 好 好 坏 好 0.8 * 0.7 + 0.2 * 0.9=0.74,1,2,P56 例5-4 设一步转移概率矩阵 0.7 0.3 P = 0.9 0.1 初始概

8、率向量 P(0) = 0.8 0.2 求一步转移后机床出现故障概率？(两种可能) p2(1) = p1(0)* p12+ p2(0)* p22 好 坏 坏 坏 0.8 * 0.3 + 0.2 * 0.1=0.26 因此一步转移后机床的概率向量为： P(1) = P(0)* P = 0.74 0.26,P56 例5-4 设一步转移概率矩阵 两步转移后机床的状态概率向量为： 0.76 0.24 P(2) = P(0)* P2 = 0.8 0.2 * 0.72 0.28 = 0.752 0.248 可见k步转移后状态概率向量(分布)为： P(k) = P(0)* Pk = P(k-1)* P 已知系

9、统的初始状态和概率转移矩阵，可得系统任意时刻的状态。,3.齐次马氏链的遍历性和稳态概率 通常讨论关于齐次马氏链的n步转移概率的两方面问题，一是其极限是否存在？二是如果此极限存在，那么它是否与初始状态无关，有关这两方面问题的定理，统称为遍历性定理。,齐次马氏链的n步转移概率,当n趋于无穷时,即过程的转移无限进行下去时,其极限可能存在，而且也可能与初始状态无关，例如只有两个状态的马氏链，其一步转移概率矩阵为,其任意步转移概率矩阵为 （每行概率相等，概 率与行数无关，只和列有关）,马氏链遍历性定义： 如果齐次马氏链的所有的状态 ai, aj，存在不依赖于ai的常数j，为其转移概率的极限，即 其相应的

10、转移矩阵有,称此齐次马氏链具有遍历性，j为状态aj的稳态概率， = 1 2 j n 称为稳态分布,定理5.1 齐次马氏链若存在正整数m，使对任意的状态ai, aj ，其m步转移概率均大于(不等于)0, 即,则此马氏链具有遍历性；且稳态概率满足下列方程组 (由 = P推得，其中 = 1 2 j n ),及概率分布条件,本定理不仅给出了判断马氏链的遍历性的方法,也给出了求其稳态概率的方法.,24,P58例5-5 设齐次马氏链的状态空间E=1,2,3，其一步转移概率为,试问此链是否具有遍历性?若有,试求其平稳分布.,25,解：注意到,即知其所有的二步转移概率均大于0，由定理5.1知，此链具有遍历性.

11、,由定理5.1可知 1 2 3 = 1 2 3 P ，带入数据,解之可得平稳分布为,5.3.1,市场占有率预测,例5-6设某地有1600户居民，某产品只有甲、乙、丙3厂家在该地销售。经调查，8月份买甲、乙、丙三厂的户数分别为480，320，800。9月份里，原买甲的有48户转买乙产品，有96户转买丙产品；原买乙的有32户转买甲产品，有64户转买丙产品；原买丙的有64户转买甲产品，有32户转买乙产品。用状态1、2、3分别表示甲、乙、丙三厂，试求,（1）转移概率矩阵； （2）9月份市场占有率的分布； （3）12月份市场占有率的分布； （4）若顾客流如此长期稳定，该地市场占有率的分布,5.3 马尔可

12、夫过程决策应用,解,（1）E1，2，3,状态1、2、3分别表示甲、乙、丙的用户,一步转移概率矩阵为,（2）以1600除8月份甲，乙，丙的户数，得初始概率分布（即初始市场占有率）,所以9月份市场占有率分布为,（3）12月份市场占有率分布为,（4）解方程组,即得当顾客流如此长期稳定下去是市场占有率的分布为,例5-7,例5-6中甲药厂的市场占有率从30%降至21.9%，为扭转不利趋势，提出2种销售策略： (1)保留策略：减少顾客向丙药厂的流失，使保留率从原来的70%提高到85%。 (2)争取策略：能从上一期向另外两家药厂购买板蓝根的顾客中分别争取15%与16%。,(1)采取保留策略后状态转移概率矩阵

13、为：,(2)采取争取策略后状态转移概率矩阵为：,结论：采取保留策略后，甲药厂最终的市场占有率从原来的21.9%-36.4%；而采取争取策略后市场占有率从21.9%-34.4%，因此在两种策略花费一样的情况下，甲药厂宜采取保留策略。,5.3.2 期望利润与决策,某商品市场状况有畅销和滞销两种。1代表畅销，2代表 滞销，如产品畅销获利50万元；滞销将亏损30万元。,一般地,设齐次马氏链的状态空间为 N,其转移矩阵为P= (pij)NN。设r(i)表示系统处于状态i时获得的报酬。r(i) 0时称为盈利，r(i)0时称为亏损。令 r =(r(1), r(2), . , r(N)T为表示盈利的列向量。,

14、设r( j )表示某周期系统处于状态 j 时获得的报酬。 对于稳态分布 = 1 2 j n ， 无限时段单位时间平均报酬与初始状态无关:,2. 无限时段期平均报酬,例5-8维修泵的过程中，把泵按其外壳及叶轮的腐蚀程度定为五种状态中的一种。这五种状态是： 状态1：优秀状态；状态2：良好状态；状态3：及格状态；状态4：可用状态； 状态5：不可运行状态。 公司可采用的维修策略有以下几种： 单状态策略：泵处于状态5时才进行修理，每次修 理费用为500元。 两状态策略：泵处于状态4和5时进行修理，处于 状态4时的修理费用每次为250元, 处于状态5时的每次修理费用为500元。 三状态策略：泵处于状态3,

15、4,5时进行修理，处于 状态3时的每次修理费用为200元,处于状态4和5时的修理费用同前。,假定不管处于何种状态，只要进行修理，泵的状态都将恢复为状态1。已知在不进行任何修理时的状态转移概率，如下表所示。,问题：确定哪个策略的费用最低。 目标为长期运行单位时间平均报酬。,单状态策略下： v (i ) = 99.5 两状态策略下： v (i ) = 90.50 三状态策略下： v (i ) = 94.25 因此，两状态策略为最优策略，平均每周期的费用为90.50元。,先选择B8：D8，保存矩阵相乘结果区间。,例5-9Excel操作,在上方的公式输入栏中输入“=MMULT(B5:D5,$G$3:$I$5)。,按下shift+Ctrl+Enter,得到矩阵相乘结果。,选择B9