马尔科夫链.ppt

《马尔科夫链.ppt》由会员分享，可在线阅读，更多相关《马尔科夫链.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、目录目录目录目录回顾回顾马尔科夫链的状态空间分解马尔科夫链的状态空间分解马尔科夫链的渐近性质和平稳分布马尔科夫链的渐近性质和平稳分布马尔科夫链的运用实例马尔科夫链的运用实例一、马尔科夫链的定义一、马尔科夫链的定义回顾：回顾：回顾：回顾：马尔科夫马尔科夫马尔科夫马尔科夫链链链链的基本概念的基本概念的基本概念的基本概念 马尔可夫链，因安德烈马尔可夫（A.A.Markov，18561922）得名，是数学中具有马尔可夫性质的离散时间随机过程。有如下特点：系统在每个时期所处的状态是随机的从一时期到下时期的状态按一定概率转移下时期状态只取决于本时期状态和转移概率（无后效性）本节课主要介绍时间、状态均为离散

2、的马尔科夫链及其应用一、马尔科夫链的定义一、马尔科夫链的定义回顾：回顾：回顾：回顾：马尔科夫马尔科夫马尔科夫马尔科夫链链链链的基本概念的基本概念的基本概念的基本概念马尔科夫链定义马尔科夫链定义 设有随机过程 ，若对于任意的整数 和任意的 ，条件概率满足则称 为马尔科夫链，简称马氏链。二、一步转移概率和矩阵二、一步转移概率和矩阵回顾：回顾：回顾：回顾：马尔科夫马尔科夫马尔科夫马尔科夫链链链链的基本概念的基本概念的基本概念的基本概念 一步转移概率定义一步转移概率定义 称条件概率为马尔科夫链在时刻n的一步转移概率，其中 ，简称为转移概率。一步转移矩阵定义一步转移矩阵定义 设P表示一步转移概率 所组成

3、的矩阵，且状态空间I=1,2,3.。，则称为系统状态的一步转移概率矩阵。它具有性质：（1）（2）.回顾：回顾：回顾：回顾：马尔科夫马尔科夫马尔科夫马尔科夫链链链链的基本概念的基本概念的基本概念的基本概念三、三、n步转移概率和矩阵步转移概率和矩阵n步转移概率和矩阵定义步转移概率和矩阵定义 称条件概率为马尔科夫链 的n步转移概率，并称为马尔科夫链的n步转移矩阵，其中 ，即 也是随机矩阵。回顾：回顾：回顾：回顾：马尔科夫马尔科夫马尔科夫马尔科夫链链链链的的的的基本性质基本性质基本性质基本性质马尔科夫链的基本性质马尔科夫链的基本性质定理定理4.2 设 为马尔科夫链，则对任意整数 和 ，n步转移概率 具

4、有下列性质：（1）；（2）；（3）；（4）.说明：（1）式称为切普曼柯尔莫戈洛夫方程，简称C-K方程，他在马尔科夫链的转移概率的计算中起着重要的作用。（2）式说明n步转移概率完全由一步转移概率决定。（4）式说明齐次马尔科夫链的n步转移概率矩阵式一步转移概率矩阵的n次乘方。回顾：回顾：回顾：回顾：马尔科夫马尔科夫马尔科夫马尔科夫链链链链的基本概念的基本概念的基本概念的基本概念四、初始概率和绝对概率四、初始概率和绝对概率初始概率和绝对概率定义初始概率和绝对概率定义 设 为马尔科夫链，称 和 为 的初始概率初始概率和绝对概率绝对概率，并分别称 和 为 的初始分布和绝对分布，简记为 和 。称概率向量

5、为初始概率向量。定定 理理4.1 设 为马尔科夫链，则对任意 和 ，绝对概率 具有下列性质：（1）；（2）；（3）；（4）.回顾：回顾：回顾：回顾：马尔科夫马尔科夫马尔科夫马尔科夫链链链链的状态分类的状态分类的状态分类的状态分类一、周期态一、周期态马尔科夫链周期定义马尔科夫链周期定义 如集合 非空，则称该集合的最大公约数d=d（i）=G.C.D 为状态i的周期，如d1就称i为周期周期的的，如d=1就称i为非周期的非周期的。回顾：回顾：回顾：回顾：马尔科夫马尔科夫马尔科夫马尔科夫链链链链的状态分类的状态分类的状态分类的状态分类二、常返态二、常返态1、常返性概念、常返性概念 记显然由马氏性与齐次性

6、上式右方与m无关，它表示质点由i出发，经n步首次到达j的概率也称为首中概率首中概率 记它表示质点由i出发，经有限步终于到达j的概率。回顾：回顾：回顾：回顾：马尔科夫马尔科夫马尔科夫马尔科夫链链链链的状态分类的状态分类的状态分类的状态分类二、常返态二、常返态1、常返性概念、常返性概念常返性定义常返性定义 如 ，称状态i为常返的；如 ，称状态i为非常返的。对常返态i，由定义知 构成一概率分布，此分布的期望值表示由i出发再返回到i的平均返回时间。正常返、零常返和便利状态定义正常返、零常返和便利状态定义 如 ，则称常返态i为正常正常返返的；如 ，则称常返态i为零常返零常返的。非周期常返态成为遍遍历状态

7、历状态。回顾：回顾：回顾：回顾：马尔科夫马尔科夫马尔科夫马尔科夫链链链链的状态分类的状态分类的状态分类的状态分类二、常返态二、常返态2、常返性、常返性的判断的判断定定 理理4.3 状态i常返的充要条件为如i非常返，则定定 理理4.4 设i常返且有周期d，则其中 为i的平均返回时间。当 时，由上面定理立即得 推推 论论4.1 设i常返，则 （1）i零常返 ;（2）i遍历 .回顾：回顾：回顾：回顾：马尔科夫马尔科夫马尔科夫马尔科夫链链链链的状态分类的状态分类的状态分类的状态分类三、三、可达和互通可达和互通可达和互通定义可达和互通定义 如果存在n0,使 ，我们称自状态i可达状态j，并记为I j；如I

8、 j且j i，称状态i与j互通，并记为I j。定定 理理4.5 可达关系与互通关系都具有传递性，即如果I j，j k，则i k;如果I j，j k，则i k。定定 理理4.6 如I j则（1）i与j同为常返或非常返，如为常返，则他们同为正常返或零常返。（2）i与j由相同的周期。状态空间的分解状态空间的分解状态空间的分解状态空间的分解一、闭集和不可约一、闭集和不可约闭集定义闭集定义 如对任意I C及k C都有 =0，状态空间I的子集C称为（随机）闭集.闭集的意思是自C的内部不能到达C的外部.这意味着一旦质点进入闭集C中，它将永远留在C中运动.另如 =1，则称状态i为吸收的.显然状态i吸收等价于单

9、点集 为闭集.不可约定义不可约定义 如闭集C的状态互通，则闭集C称为不可约的。如马氏链 状态空间不可约，则马氏链 称为不可约的。状态空间的分解状态空间的分解状态空间的分解状态空间的分解一、闭集和不可约一、闭集和不可约闭集判断闭集判断 C是闭集的充要条件为对任意i C及k C都有 =0,n1.证证 只需证必要性.用归纳法，设C为闭集，由定义当n=1时结论成立.今设n=m 时，=0，i C,k C,则 引理得证.可以对整个马氏链进行分析，得知3是吸收的，故3是闭集.1，4，1，4，3，1，2，3，4都是闭集，其中3及1，4是不可约的.又I含有非不可约闭子集，故 不是不可约链.状态空间的分解状态空间

10、的分解状态空间的分解状态空间的分解一、闭集和不可约一、闭集和不可约例例4.1 设马氏链 的状态空间I=1，2，3，4，5，转移矩阵为画出结构图如图4.7 图图4.7 状态空间的分解状态空间的分解状态空间的分解状态空间的分解二、马尔科夫链状态空间分解定理二、马尔科夫链状态空间分解定理状态空间分解定理状态空间分解定理 任一马氏链的状态空间I，可唯一地分解成有限个或可列个互不相交的子集D,之和，使得 每一 是常返态组成的不可约闭集.中的状态同类，或全是正常返，或全是零常返.它们有相同的周期且 ,j,k .D由全体非常返状态组成.自 中的状态不能到达D中的状态.证证 记C为全体常返状态所成的集合，D=

11、I-C 为非常返状态全体.将C按互通关系进行分解，则其中每一个 是由常返状态组成的不可约的闭集，且由定理4.9知 中的状态同类型.显然，自 中的状态不能到达D中状态。状态空间的分解状态空间的分解状态空间的分解状态空间的分解二、马尔科夫链状态空间分解定理二、马尔科夫链状态空间分解定理 我们称 为基本常返闭集.分解定理中的集D不一定是闭集，但如I为有限集，D一定是非闭集.因此，如最初质点是自某一非常返状态出发，则它可能就一直在D中运动，也可能在某一时刻离开D转移到某一基本常返闭集 中.一旦质点进入 后，它将永远在此 中运动，在后面的定理中我们将进一步揭示质点在闭集 中的运动规律.下面我们看一个例子

12、.例例4.3 设I=1,2,6，转移矩阵为试分解此链并指出各状态的常返性及周期性.状态空间的分解状态空间的分解状态空间的分解状态空间的分解二、马尔科夫链状态空间分解定理二、马尔科夫链状态空间分解定理例例4.2 解解 先根据图4.8将不可约闭集 分解出来，得到图图4.8 和 状态空间的分解状态空间的分解状态空间的分解状态空间的分解二、马尔科夫链状态空间分解定理二、马尔科夫链状态空间分解定理 根据 中的状态同类，对每个 分析其周期和常返性。对 知 ,(,n 3).所以可见1为正常返状态且周期等于3.由于状态3和5同属于 ，根据状态同类，得知状态3及5也为正常返且周期为3.对 ，同理可知6为正常返状

13、态.，其周期为1，可见状态2和6是遍历状态.由于 ，(,n 1)故4非常返，周期为1，于是I可分解为 .状态空间的分解状态空间的分解状态空间的分解状态空间的分解三、随机矩阵三、随机矩阵随机矩阵定义随机矩阵定义 如矩阵 元素非负且对每i有 ，则称矩阵 为随机矩阵.显然k步转移矩阵 为随机矩阵.引引 理理4.1 设C为闭集，又G=，i,j C,是C上所得的（即与C相应的）k步转移子矩阵，则G仍是随机矩阵.证证 任取I C，由引理4.4我们有 ，显然 ，故G为随机矩阵.由此可见，对I的一个闭子集C，可考虑C上的原马氏链的子马氏链.其状态空间为C，转移矩阵G=,i,j ,是原马氏链转移矩阵P=,i,j

14、 I的子矩阵.下面我们研究质点在不可约闭集C中的运动情况.状态空间的分解状态空间的分解状态空间的分解状态空间的分解四、不可约马氏链的分解定理四、不可约马氏链的分解定理不可约马氏链的分解定理不可约马氏链的分解定理 周期为d的不可约马氏链，其状态空间C可唯一地分解为d个互不相交的子集之和，即 (4.31)且使得自 中任一状态出发，经一步转移必进入 中（其中 ）.证证 任意取定一状态i，对每一r=0,1，d-1，定义集.(4.32)因C不可约，故 图图4.9状态空间的分解状态空间的分解状态空间的分解状态空间的分解四、不可约马氏链的分解定理四、不可约马氏链的分解定理证证 其次，如存在 由（4.32）必

15、存在n及m使 ，又因j i，故必存在h，使 ，于是 ,.由此可见r+h及s+h都能被d除尽，从而其差（r+h）-（s+h）=r-s也可被d除尽.但0r，sd-1,故只能r-s=0，因而 ，这说明当rs时，下证对任一 ，有 ，实际上 .最后一个等式是因设 ，故当 时，由 知 .状态空间的分解状态空间的分解状态空间的分解状态空间的分解四、不可约马氏链的分解定理四、不可约马氏链的分解定理证证 最后证明分解的唯一性，这只需证 与最初i的选择无关，亦即如对某固定的i，状态j与k同属于某 ，则对另外选定的 ，状态j与k仍属于同一 ，（r与 可以不同）.实际上，设对i分得 ，对 分得 ，又假定j，则 当rs

16、时，自 出发，只能在r-s，r-s+d，r-s+2d，等步上到达j或k，故j与k都属于 .当rs时，自 出发，只能在d-（s-r）=r-s+d，r-s+2d，等步上到达j或k，故j与k都属于 .证毕.状态空间的分解状态空间的分解状态空间的分解状态空间的分解四、不可约马氏链的分解定理四、不可约马氏链的分解定理例例4.3 设不可约马氏链的状态空间为C=1，2，3，4，5，6，转移阵为试对其进行分解状态空间的分解状态空间的分解状态空间的分解状态空间的分解四、不可约马氏链的分解定理四、不可约马氏链的分解定理解解 画出状态转移图4.10易见各状态的周期d=3.今固定状态i=1，令故 .此链在C中的运动如

17、图4.11.图图4.10 图图4.11状态空间的分解状态空间的分解状态空间的分解状态空间的分解四、不可约马氏链的分解定理四、不可约马氏链的分解定理定定 理理4.7 设 是周期为d的不可约马氏链，则在不可约马不可约马氏链的分解定理氏链的分解定理的结论下有（1）如只在时刻0，d，2d，上考虑 ，即得一新马氏链，其转移阵 ，对此新链，每一 是不可约闭集，且 中的状态是非周期的.（2）如原马氏链 常返，也常返.状态空间的分解状态空间的分解状态空间的分解状态空间的分解四、不可约马氏链的分解定理四、不可约马氏链的分解定理证证 （1）由定理4.11得知 对 是闭集.其次对 ，因 不可约，故存在N使 .由定理

18、4.11知N只能是nd形，换言之，对 状态 ，同理 ，故 即 不可分.由引理4.1，存在M，对一切 ，有 ，可见对 状态j的周期为1.（2）设 常返，任取 ，由周期的定义知，当n 0(mod(d)时，因而 ，故即j对 也是常返的.状态空间的分解状态空间的分解状态空间的分解状态空间的分解四、不可约马氏链的分解定理四、不可约马氏链的分解定理例例4.5 设 为例4.4中的马氏链，已知d=3，则 的转移阵为有子链 的状态转移图（图4.12）知，各形成不可约闭集，周期为1.图图4.12定理定理4.8 如j非常返或零常返，则推论推论4.1 有限状态的马氏链，不可能全是非常返状态，也不可能有零常返状态。从而

19、不可约的有限马氏链是正常返的。推论推论4.2 如马氏链有一个零常返态，则必有无限多个零常返状态。渐近性质和平稳分布渐近性质和平稳分布渐近性质和平稳分布渐近性质和平稳分布一、一、的渐进性质的渐进性质定理定理4.9 如j正常返，周期为d，则对任意i及 有推论推论4.3 设不可约、正常返、周期d的马氏链，其状态空间为C，则对一切 ，有其中 ，为定理4.11中所给出。特别，如d=1，则对一切i，j有 。我们知道 表示自j出发，在n步之内返回到j的平均次数，故 表示每单位时间再回到j的平均次数，而 也表示自j出发每单位时间回到j的平均次数，所以应有 如果质点从i出发，则要考虑自i出发能否到达j的情况，即

20、要考虑 的大小。于是我们有渐近性质和平稳分布渐近性质和平稳分布渐近性质和平稳分布渐近性质和平稳分布一、一、的渐进性质的渐进性质定理定理4.10 对任意状态i，j，有推论推论4.4 如 不可约，常返，则对任意i，j，有 当 时，理解 。定理4.10及推论指出，当j正常返时，尽管 不一定存在，但其平均值的极限存在，特别是当链不可约时，其极限与i无关。在马氏链理论中，是一个重要的量，定理4.9,4.10的推论及定义都给出 的计算公式，下面我们通过平稳分布给出另一个计算 的方法。渐近性质和平稳分布渐近性质和平稳分布渐近性质和平稳分布渐近性质和平稳分布一、一、的渐进性质的渐进性质平稳分布定义平稳分布定义

21、 称概率分布 为马尔可夫链的平稳分布，若它满足 由定义知，若初始概率分布 是平稳分布，则由定理定理4.1有根据归纳法得到综上所述有渐近性质和平稳分布渐近性质和平稳分布渐近性质和平稳分布渐近性质和平稳分布二、平稳分布二、平稳分布将平稳分布的概念引入马尔科夫链中得到如下性质定理：定定 理理4.11 不可约非周期马尔可夫链是正常返的充要条件是存在平稳分布，且此平稳分布的就是极限分布 推推 论论4.5 有限状态的不可约非周期马尔可夫链必存在平稳分布。推推 论论4.6 若不可约马尔可夫链的所有状态是非常返的或零常返的，则不存在平稳分布。推推 论论4.7 若 是不可约非周期马氏链的平稳分布，则 运用上述定

22、理和推论，只要证明运用中构建的随机矩阵是不可约非周期马氏链，则可运用平稳分布定义平稳分布定义和推论推论4.4得到马氏链的稳定分布。下面就介绍几个马尔科夫链的例题。渐近性质和平稳分布渐近性质和平稳分布渐近性质和平稳分布渐近性质和平稳分布二、平稳分布二、平稳分布例题：设马尔科夫链的状态空间I=1，2，3，4，5，6，7，转移概率矩阵为：P=求状态的分类及各常返闭集的平稳分布 P=N=1，2非常返集，C1=3，4，5，C2=6，7是正常返闭集。由转移矩阵，分别解得 C1平稳分布为0，0，0，0 C2平稳分布为0，0，0，0，0，由于马尔科夫链具有的无后效性，下n个时期的状态完全取决于本时期的状态和转

23、移概率。完全排除了过去对未来的影响，因此在天气预报、股市和投资决策、地质分析等很多领域可以用来对未来的状态估计。下面我们举出两个运用实例：马尔科夫链运用实例马尔科夫链运用实例马尔科夫链运用实例马尔科夫链运用实例原理原理 我们把学生的学习成绩分为若干种有限状态，把教学的一个长阶段分为若干个小阶段，每个小阶段称为一个时刻，则从此一时刻到下一时刻学生学习状态的变化就可以反映由教师的主导作用而产生的教学效果，它具有稳定的转移趋势。这种转化是由学生现在所处的状态向下一时刻的转化，因而与其以前的状态无关，它具有无后效性，因此教学过程可以看成一个齐次马尔科夫链，利用马尔科夫链的平稳分布，就可以对教师在这教学

24、过程中的教学效果进行评价，也可以对若干名教师的教学效果进行比较。马尔科夫链运用实例马尔科夫链运用实例马尔科夫链运用实例马尔科夫链运用实例一一、运用马尔科夫链评价教学效果实例、运用马尔科夫链评价教学效果实例具体方法具体方法 1）把待考评的教师的一个长的教学过程分为若干个阶段（例如一个学期分为开学阶段，期中阶段和期末阶段），分别记为不同时刻，在每个阶段用标准化试题考试，把学生的学习成绩分为N个等级（如91100分为优，8190为良，7180为中，6070为及格，59分或以下为不及格），形成一个状态空间I=,然后归纳统计学生的学习成绩由每一时刻向下一时刻状态之间的转化的频率，以此为概率的近似值作为转

25、移概率。2）由转移概率确定转移概率矩阵 3）求方程组 ，即 的满足 的解。4）为了对于不同教师的教学效果的评价结果具有可比性，我们 定义一个数作为教学效果的评价指标，如可取每个状态分数范围的中间值 作为该状态的代表分数，则评价指标为M=马尔科夫链运用实例马尔科夫链运用实例马尔科夫链运用实例马尔科夫链运用实例一一、运用马尔科夫链评价教学效果实例、运用马尔科夫链评价教学效果实例实例实例 1）现有甲、乙、丙、丁四位教师，在教同一学期的过程中，由几次标准化测试所得各自的转移矩阵分别为：马尔科夫链运用实例马尔科夫链运用实例马尔科夫链运用实例马尔科夫链运用实例一一、运用马尔科夫链评价教学效果实例、运用马尔

26、科夫链评价教学效果实例2）解齐次线性方程组马尔科夫链运用实例马尔科夫链运用实例马尔科夫链运用实例马尔科夫链运用实例一一、运用马尔科夫链评价教学效果实例、运用马尔科夫链评价教学效果实例3）计算得出如下表：可见乙的教学效果最好，丙的教学效果最差。马尔科夫链运用实例马尔科夫链运用实例马尔科夫链运用实例马尔科夫链运用实例一一、运用马尔科夫链评价教学效果实例、运用马尔科夫链评价教学效果实例姓名姓名M序号序号甲甲0.0972050.1555290.2916160.3888210.06682973.27462乙乙0.1339210.2004810.3327990.2662390.06656075.68964

27、1丙丙0.0052470.0819880.3113800.4101850.19120067.9989704丁丁0.0318040.1209610.3378250.3389100.17049970.046533 现以某市某品牌彩电市场占有率预测为例说明马尔科夫预测法在实际市场占有率预测中的应用。将成千上万的彩电归纳为三大项目：即本企业、龙头企业和其他企业。根据马尔科夫预测法的预测步骤进行预测。马尔科夫链运用实例马尔科夫链运用实例马尔科夫链运用实例马尔科夫链运用实例二二、运用马尔科夫链预测市场占有率、运用马尔科夫链预测市场占有率 第一步，要调查目前市场的占有率情况，得到市场占有率向量A，若通过对本

28、市一万户彩电用户的随机调查，得出目前市场占有率向量A=(0.2,0.5,0.3),即目前，在一万户用户中，购买本企业彩电户数占20%，购买龙头企业品牌彩电用户数占50%，还有30%是购买其他品牌彩电。第二步，调查消费购买变动情况，得出整个市场彩电下一期的转移概率矩阵B，若经过调查，这一万户消费者，下一期购买彩电，在现在购买本企业彩电的消费者中，下一期仍然有50%购买本企业彩电，40%将购买龙头企业的彩电，10%将购买其他牌号的彩电；现在购买龙头企业彩电的消费者，下一期将有20%转移购买我公司生产的彩电，50%仍然购买龙头企业彩电，而30%将购买其他牌号的彩电；现在购买其他品牌彩电，有40%将转

29、移购买龙头企业产品，30%将购买本企业的彩电。据此可得出下期整个市场彩电购买情况变动的转移概率矩阵。马尔科夫链运用实例马尔科夫链运用实例马尔科夫链运用实例马尔科夫链运用实例二二、运用马尔科夫链预测市场占有率、运用马尔科夫链预测市场占有率第三步，用向量A乘以矩阵B即可得出下期本企业、龙头企业及其他企业市场占有率分别为29%、45%和26%。第四步，若这种变化成为相对稳定状况，也即转移概率矩阵将对市场占有率不起变动作用，我们就可以计算出竞争相对稳定以后的各种牌号彩电的市场占有率。运用平稳分布，联立方程组：解方程组得本企业在市场较为稳定情况下的市场占有 率为32.92%，龙头企业为36.36%，其他企业为30.69%。马尔科夫链运用实例马尔科夫链运用实例马尔科夫链运用实例马尔科夫链运用实例二二、运用马尔科夫链预测市场占有率、运用马尔科夫链预测市场占有率