马尔可夫过程和泊松过程课件.ppt

1、主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程第七章第七章 马尔可夫过程与泊松过程马尔可夫过程与泊松过程 马尔可夫链马尔可夫链 马尔可夫过程马尔可夫过程 泊松过程泊松过程马尔可夫过程是一类重要的随机过程，广泛应用马尔可夫过程是一类重要的随机过程，广泛应用在近代物理、生物（生灭过程）、公用事业、信在近代物理、生物（生灭过程）、公用事业、信号处理、自动控制等方面号处理、自动控制等方面 马尔可夫过程的基本特征是无后效应性，马尔可夫过程的基本特征是无后效应性，即未来状态只与现在有关，与过去无关。即未来状态只与现在有关，与过去无关。主讲教师主讲教师:罗鹏飞教授罗鹏飞教

2、授马尔可夫过程与泊松过程马尔可夫过程与泊松过程7.1 7.1 马尔可夫链马尔可夫链定义定义 状态和时间参量都是离散的随机过程，在状态和时间参量都是离散的随机过程，在t tr r时刻状态已知的条件下，其后时刻状态已知的条件下，其后t tr+1r+1时刻所处的状态时刻所处的状态只与只与t tr r时刻的状态有关，而与以前时刻的状态有关，而与以前t tr-1r-1、t tr-2r-2时刻时刻的状态无关，则该过程称为马尔可夫链。的状态无关，则该过程称为马尔可夫链。11121121;,;,;nnnnnnnnnntxtxPtttxxxtxP主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可

3、夫过程与泊松过程一维随机游动问题。设有一质点在一维随机游动问题。设有一质点在x x轴上作随机游动。轴上作随机游动。在在t=0t=0时质点属于时质点属于x x轴的原点，在轴的原点，在t=1,2,3.t=1,2,3.时质点可以时质点可以在轴上正向或反向移动一个单位距离。在轴上正向或反向移动一个单位距离。例：随机游动问题例：随机游动问题 p1-p011nkXk质点正向移动一个单位质点正向移动一个单位质点反向移动一个单位质点反向移动一个单位若给定时间若给定时间n-1n-1，质点偏离原点的距离为，质点偏离原点的距离为k k，可表示为，可表示为X Xn-1n-1=k=k，则质点在，则质点在n n时刻偏离时

4、刻偏离x x轴原点的距离只与轴原点的距离只与n-1n-1时刻质点所处的状态有关。时刻时刻质点所处的状态有关。时刻n n质点所处的状态可质点所处的状态可以表示以表示主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程马尔可夫链的统计特性马尔可夫链的统计特性状态转移概率状态转移概率),(isjnijaXaXPnsP状态转移矩阵状态转移矩阵),(),(),(),(),(),(),(),(),(),(212222111211nsPnsPnsPnsPnsPnsPnsPnsPnsPnsNNNNNNP1),(11NjisjnNjijaXaXPnsP每一行之和为每一行之和为1 1

5、状态概率状态概率(概率分布列概率分布列)(jnjaXPnpNjjnp11)(主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程状态概率与状态转移矩阵之间的关系状态概率与状态转移矩阵之间的关系)(),()(snsnTpPp111(),(,)()jnjNnjsiiNnjsisiiNijiip nP XaP XaXaP XaXa P XaP s n p s(,)ijP s nji主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程状态转移图状态转移图描述马尔可夫链的一种工具描述马尔可夫链的一种工具a1a2a3a4a511/21/21/21

6、/21/21/21反射壁反射壁010001 201 200,101 201 20001 201 200010n nP状态转移图和状态转移图和状态转移矩阵状态转移矩阵一一对应一一对应 1/21/2主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程切普曼切普曼-柯尔莫哥洛夫方程柯尔莫哥洛夫方程1111(,)|,(,)(,)ijnjsinjsisiNnjrksiksiNnjrksirksiksirksiNnjrksirksikrksisiikkjkP s nP xaxaP xaxaP xaP xaxaxaP xaP xaxaxaP xaxaP xaP xaxaP xa

7、xaxaP xaxaP xaxaP xaP s r P r nNP(s,n)=P(s,r)P(r,n)主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程几何解释几何解释t ts st tr rt tn nx xs s=a=ai ix xn n=a=aj ja an na ak ka al lp pik ik(s,r(s,r)p pkj kj(r,n(r,n)1(,)(,)(,)NijikkjkP s nP s r P r n主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程齐次马尔可夫链齐次马尔可夫链如果马尔可夫链的转移概率如果马

8、尔可夫链的转移概率P Pij ij(s,n(s,n)只取决于只取决于n-sn-s，而与，而与n n和和s s本身本身的值无关，则称为齐次马尔可夫链，简称齐次链。的值无关，则称为齐次马尔可夫链，简称齐次链。P(s,n)=P(n-s)()(,)()()()TTns nsnsspPpPp对于齐次链：对于齐次链：P(2)=P(1)P(1)=P 2(1)P(n)=P n(1)P(s,n)=P(s,r)P(r,n)由切普曼由切普曼-柯尔莫哥洛夫定理柯尔莫哥洛夫定理()(,)()()()()TTnnkk knknkkpPpPp p(1)TP(2)(1)pp主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与

9、泊松过程马尔可夫过程与泊松过程平稳链平稳链如果齐次链的状态概率都相同，即如果齐次链的状态概率都相同，即p(n)=p(1)p(n)=p(1)，则称为平稳链则称为平稳链只要只要p(2)=p(1),p(2)=p(1),则必定则必定p(n)=p(1)p(n)=p(1)因为因为 p(n)=Pp(n)=PT T(s,n)p(s)(s,n)p(s)，所以，所以p(2)=Pp(2)=PT T(1,2)p(1)(1,2)p(1)或者或者 p(2)=Pp(2)=PT T(1)p(1)(1)p(1)p(3)=PT(2,3)p(2)p(3)=PT(1)p(2)=PT(1)p(1)=p(2)=p(1)主讲教师主讲教师:

10、罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程平稳链状态概率的计算平稳链状态概率的计算对于平稳链：对于平稳链：P PT T(1)p(1)=p(1)(1)p(1)=p(1)在方程在方程 P PT T(1)p(1)=p(1)(1)p(1)=p(1)中中取取N-1N-1个方程个方程p1+p2+.+pN=1p(2)=PT(1)p(1)主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程计算举例计算举例-反射壁反射壁 01000210210002102100021021000101P1222225432145334223112ppppppppppppppp

11、p814151432ppppp(1)(1)(1)TPpp主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程马尔可夫链的状态分类马尔可夫链的状态分类1、到达和相通、到达和相通如果对状态如果对状态i i和和j,j,存在存在n(nn(n1),1),使得使得P Pij ij(n(n)0,)0,即由状态即由状态i i出发出发,经经n n次转移以正的概率到达状态次转移以正的概率到达状态j,j,则称自状态则称自状态i i到达状态到达状态j j。ij反之，反之，i i不能到达不能到达j j，记为，记为ij此时，对任意的此时，对任意的n(nn(n 1),1),P Pij ij(n

12、(n)=0)=0无限制的随机游动，每个状态都是可到达的，带吸收壁的随机无限制的随机游动，每个状态都是可到达的，带吸收壁的随机游动，吸收壁状态不能到达任何其它状态。游动，吸收壁状态不能到达任何其它状态。主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程如果如果,ij ji则称则称i i与与j j是相通的，记为是相通的，记为ij到达具有传递性到达具有传递性定理：如果定理：如果,ik kj则则ij无限制随机游动所有状态都是相通的，对于带吸收无限制随机游动所有状态都是相通的，对于带吸收壁的随机游动，除吸收壁外，其余状态都是相通的。壁的随机游动，除吸收壁外，其余状态都是相

13、通的。定理：如果定理：如果,ik kj则则ij相通也具有传递性相通也具有传递性主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程2、状态空间的分解、状态空间的分解如果两个状态相通，则称这两个状态处于同一类中。如果两个状态相通，则称这两个状态处于同一类中。可以根据相通的概念把状态空间分成一些隔离的类。可以根据相通的概念把状态空间分成一些隔离的类。如果状态空间有一个子集如果状态空间有一个子集C，对于任何，对于任何有有Pij=0,则则Pij(2)=0,Pij(n)=0.,iCjC即对任意即对任意 自自i不能到达不能到达j,iCjC主讲教师主讲教师:罗鹏飞教授罗鹏飞教授

14、马尔可夫过程与泊松过程马尔可夫过程与泊松过程定义：定义：设设C为状态空间的一个子集，如果从为状态空间的一个子集，如果从C内任内任何一个状态何一个状态i不能到达不能到达C以外的任何状态，则称以外的任何状态，则称C为为闭集。闭集。闭集的充分闭集的充分必要条件必要条件是，是，i C,j在在C外，恒有外，恒有Pij(n)=0,n 1如果单个状态如果单个状态i构成一个闭集，则称该闭集为吸状态。构成一个闭集，则称该闭集为吸状态。整个状态空间构成一个闭集，这是最大的闭集，吸状整个状态空间构成一个闭集，这是最大的闭集，吸状态也构成一个闭集，这是最小的闭集。态也构成一个闭集，这是最小的闭集。主讲教师主讲教师:罗

15、鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程不可约：不可约：只有整个状态空间一个闭集的马尔可夫链，只有整个状态空间一个闭集的马尔可夫链，这时所有状态都是相通的。这时所有状态都是相通的。定理：如果在定理：如果在Pn中仅保留同类中各状态间的转移概中仅保留同类中各状态间的转移概率，而其它所有行和列的元素都删去，则剩下的矩率，而其它所有行和列的元素都删去，则剩下的矩阵仍满足阵仍满足1ikk CPiC所有主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程举例：设有三个状态举例：设有三个状态(0,1,2)的马尔可夫链，它的的马尔可夫链，它的一步转移概率矩阵

16、为一步转移概率矩阵为1/21/20(1)1/21/41/401/32/3P01221212141314132三个状态均相通，三个状态均相通，所以是不可约的。所以是不可约的。主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程举例：设有四个状态的马尔可夫链举例：设有四个状态的马尔可夫链(0,1,2,3)，一，一步转移概率矩阵为步转移概率矩阵为1/21/2001/21/2001/41/41/41/40001023212141112121414411P33=1,P32=P31=P30=0状态状态3为闭集，它是一个吸状态。为闭集，它是一个吸状态。0，1两个状态与其它状态也

17、不相通，两个状态与其它状态也不相通，0，1两个状态两个状态也是一个闭集。也是一个闭集。主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程3、常返态和滑过态（非常返态）、常返态和滑过态（非常返态）定义定义Tij为自为自i出发首次到达状态出发首次到达状态j的时刻的时刻0min:,;1ijnTn xi xj n对于某个状态对于某个状态j,xn可能永远也不为可能永远也不为j,那么上式就不存在那么上式就不存在n,这时规定这时规定 。ijT 永不出现永不出现 终身等待终身等待ijT为一随机变量，取值范围为为一随机变量，取值范围为1,2,.,N主讲教师主讲教师:罗鹏飞教授罗鹏

18、飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程定义：定义：0();,1,2,.,1|ijnmfnP xj xj mnxi自状态自状态i出发，在时刻出发，在时刻n首次到达状态首次到达状态j的概率的概率很显然，很显然，10(1)|ijijfP xj xiP一步转移概率一步转移概率0();1|ijnfP xjnxi 对一切自自i出发，永远也不能到达状态出发，永远也不能到达状态j的概率。的概率。主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程定义：定义：011()|ijijijijnnffnP Tn xiP T 自状态自状态i出发，迟早要到达状态出发，迟早要到达状

19、态j的概率的概率()1ijijijP Tff 永远也不能到达状态永远也不能到达状态j的概率的概率很显然很显然,0()1ijijfnf主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程定理定理:对任意的对任意的 及及,i jI1n 1()()()nijijj jmP nfm Pnm给出了给出了fij(n)和和Pij(n)的联系的联系()ijfn-自状态自状态i出发出发,经经n步首次到达状态步首次到达状态j的概率。的概率。()ijP n-自状态自状态i出发出发,经经n步到达状态步到达状态j的概率。的概率。定理：定理：fij0的充要条件是的充要条件是ij主讲教师主讲教

20、师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程Tii-自自i出发首次返回状态出发首次返回状态i所需要的时间。所需要的时间。fii-自自i出发经有限步迟早要返回状态出发经有限步迟早要返回状态i的概率。的概率。根据根据fii的取值不同，将状态的取值不同，将状态i分成如下两类：分成如下两类：（1）如果）如果fii=1,则称状态则称状态i为常返态；为常返态；（2）如果）如果fii1,则称状态则称状态i为非常返态，或滑过态；为非常返态，或滑过态；定理：状态定理：状态i是常返的充要条件是是常返的充要条件是1()iinP n 主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程

21、马尔可夫过程与泊松过程如果状态如果状态i为非常返态，则为非常返态，则11()1iiniiP nf 上述定理可说明如下：上述定理可说明如下：如果如果i状态为常返态，则从状态为常返态，则从i状态出发，经过有限状态出发，经过有限步的转移迟早要返回状态步的转移迟早要返回状态i，即，即fii=1,这样，过程自这样，过程自i状态出发，返回，再出发，再返回，周而复始，如状态出发，返回，再出发，再返回，周而复始，如果过程无限地进行下去，那么，访问果过程无限地进行下去，那么，访问i的次数也无的次数也无限地增加。限地增加。主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程如果如果i

22、状态为非常返的，则自状态为非常返的，则自i状态出发，经过有限步状态出发，经过有限步转移返回状态转移返回状态i的概率的概率fii0,4-1但但0-4,1-4，0，1组成一个闭集，也组成一个闭集，也是常返态，而是常返态，而4为非常返的。为非常返的。闭集，闭集，常返的常返的非常非常返的返的闭集，闭集，常返的常返的主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程4、周期状态和非周期状周期状态和非周期状态态定义：如果有正数定义：如果有正数d,d1，只有当，只有当n=d,2d,3d,时，时，Pii(n)0，则称，则称i是周期的。是周期的。无限制随机游动是周期的，周期为无限

23、制随机游动是周期的，周期为2。主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程例例 设有四个状态（设有四个状态（0，1，2，3）的马尔可夫链，）的马尔可夫链，其一步转移概率矩阵为其一步转移概率矩阵为002/12/1002/12/13/13/2003/23/100)1(P01221212121313132332-24个状态可以分成个状态可以分成0,1和和2,3两个类，该过程具有两个类，该过程具有确定性周期转移。确定性周期转移。0,12,30,12,3周期为周期为2主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程5、遍历性、遍历性

24、定义：对于齐次马尔可夫链，如果对一切定义：对于齐次马尔可夫链，如果对一切i和和j，存在不依赖，存在不依赖i的极限，的极限，lim()ijjnP np含义：当转移步数足够长时，不论含义：当转移步数足够长时，不论n步之前是处于哪步之前是处于哪种状态，种状态，n步后转移到状态步后转移到状态j的概率接近的概率接近pj。定理：对于有限状态的马尔可夫链，如存在正整定理：对于有限状态的马尔可夫链，如存在正整数数s，使，使 ，则该链具有遍历性。，则该链具有遍历性。()0ijP s 一个不可约的、非周期的有限状态马氏链一定一个不可约的、非周期的有限状态马氏链一定是遍历的。是遍历的。主讲教师主讲教师:罗鹏飞教授罗

25、鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程例：下面的马尔可夫链是遍历的。例：下面的马尔可夫链是遍历的。pqpqpq000)1(P2222222)2(ppqpqqppqqppqpqqP不遍历的例子不遍历的例子 10011P 10011)(nnPP主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程7.2 7.2 马尔可夫过程马尔可夫过程),(),(11121121nnnnnnnntxtxFtttxxxtxF条件分布函数的特条件分布函数的特点点),(),(),(111211212121nnnnnnnntxtxFtttxxxFtttxxxF),(),(),()

26、,(111122112121nnnnnntxtxFtxtxFtxFtttxxxF定义定义:t0已知的条件下已知的条件下,未来的状态只与未来的状态只与t0有关有关,与与t0时刻时刻以前无关。以前无关。主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程),(),(),(),(111122112121nnnnnntxtxftxtxftxftttxxxf切普曼切普曼柯尔莫哥洛夫方程柯尔莫哥洛夫方程rssrrrrnnssnndxtxtxftxtxftxtxf,1(,)(,)(,)NijikkjkP s nP s r P r n主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫

27、过程与泊松过程马尔可夫过程与泊松过程齐次过程齐次过程1(|)nnf xx与与n无关无关条件概率密度条件概率密度f(xf(xn n|x|xn-1n-1)与与n n无关，表明当原点移动无关，表明当原点移动时条件概率密度时条件概率密度f(xf(xn n|x|xn-1n-1)不变，但一维概率密度不变，但一维概率密度f(xf(xn n)可能与可能与n n有关。所以，一般说来齐次过程不一有关。所以，一般说来齐次过程不一定是平稳过程。定是平稳过程。主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程高斯高斯马尔可夫过程马尔可夫过程高斯马尔可夫序列高斯马尔可夫序列X(n)=AX(

28、n-1)+W(n)X(n)=AX(n-1)+W(n)这是一个一阶这是一个一阶ARAR模型模型()()()X tX tW t W(t)W(t)的均值为的均值为mmWW(t(t)2()()()()()()WWWE W tmtW tmtttt 主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程()()()()()tttttX t eeX teW tdeX teW tdt 11()()nnnnttttttdeX tdteW t dtdt111()()()nnnnttttnnteX teX teW t dt11()()1()()()nnnnnttttnntX teX te

29、Wd可见可见X(t)X(t)是马尔可夫过程，当是马尔可夫过程，当W(t)W(t)是正态的，是正态的，X(t)X(t)的起始状态也是正态随机变量，则的起始状态也是正态随机变量，则X(t)X(t)是高是高斯斯-马尔可夫过程。马尔可夫过程。主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程维纳维纳-列维过程列维过程设正态随机过程的起始值和均值均为零，即设正态随机过程的起始值和均值均为零，即 X(0)=EX(t)=0X(0)=EX(t)=0自相关函数为自相关函数为则称该过程为维纳则称该过程为维纳-列维过程。列维过程。11212212(,)XtttRt tttt例例:一积

30、分器的输入为一积分器的输入为N(t)N(t)，输出为，输出为X(t)X(t)，则，则0()()tX tN t dt若若N(t)N(t)为平稳正态随机过程，均值为零，功率谱为平稳正态随机过程，均值为零，功率谱密度为密度为NN0 0/2/2，则，则X(t)X(t)为维纳为维纳-列维过程。列维过程。主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程12121212012121212000001120212(,)()()()()()222XttttRt tE X t X tNE NNd dd dNtttNttt 主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过

31、程马尔可夫过程与泊松过程独立增量过程：不同时间间隔（互不重叠）独立增量过程：不同时间间隔（互不重叠）的增量过程彼此独立的增量过程彼此独立 12231222132300002233,02222XXXXEX tX tX tX tRt tRt tRt tRt tNNNNtttt 21tXtX 32tXtX相互独立相互独立维纳维纳-列维过程是一个独立增量过程列维过程是一个独立增量过程 21tXtX 32tXtX相互独立相互独立主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程7.3 7.3 泊松过程泊松过程有许多物理现象要求在一定的时间间隔有许多物理现象要求在一定的时间

32、间隔(t(t0 0,t),t)内内统计事件出现的个数，如到某商店或售票处的统计事件出现的个数，如到某商店或售票处的顾客数，通过某交叉路口的车辆数，电话交换顾客数，通过某交叉路口的车辆数，电话交换台的呼唤次数等，通常都可用泊松过程来描述。台的呼唤次数等，通常都可用泊松过程来描述。在这些现象中，个数变化的时刻是随机的。在这些现象中，个数变化的时刻是随机的。这这些过程可以用泊松过程来描述。些过程可以用泊松过程来描述。主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程定义：设随机过程定义：设随机过程X(t),tX(t),t t t0 0,)(t)(t0 0 0)0)，其

33、状态，其状态只取非负整数值，且满足下列三个条件：只取非负整数值，且满足下列三个条件：(1)PX(t(1)PX(t0 0)=0=1)=0=1(2)X(t)(2)X(t)为独立增量过程为独立增量过程(3)(3)对任意的对任意的t t1 1和和t t2 2(t(t1 1ttt1 1 2121112211112211121211 2,(),(),()()XRt tE XtE X tX t tttE X tE X t tttttttt t 21221 2,XRt ttt t t1t2主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程7.4 7.4 隐马尔可夫过程隐马尔可夫

34、过程(Hidden Markov)(Hidden Markov)隐马尔可夫模型作为信号处理的一种统计模型，隐马尔可夫模型作为信号处理的一种统计模型，今天正在信号处理的各个领域得到广泛应用。今天正在信号处理的各个领域得到广泛应用。HMMHMM是一个输出符号序列的统计模型，具有是一个输出符号序列的统计模型，具有NN个状态个状态S S1 1,S,S2 2,.,S,.,SNN,它按一定的周期从一个状态转移到另一个状它按一定的周期从一个状态转移到另一个状态，每次转移时，输出一个符号。转移到什么状态，转态，每次转移时，输出一个符号。转移到什么状态，转移时输出什么符号，分别由状态转移概率和转移时的符移时输出

35、什么符号，分别由状态转移概率和转移时的符号输出概率来确定。因为只能观测到输出符号序列，而号输出概率来确定。因为只能观测到输出符号序列，而不能观测到状态转移序列（即模型输出符号序列时，是不能观测到状态转移序列（即模型输出符号序列时，是通过了哪些状态路径，不能知道），所以称为隐马尔可通过了哪些状态路径，不能知道），所以称为隐马尔可夫模型。夫模型。主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程S1S2S3p11=0.3ab0.80.2p22=0.4ab0.30.7p13=0.2ab10 p12=0.5ab10 p23=0.6ab0.50.5有三个状态：初始态有三个

36、状态：初始态S S1 1,中中间态间态S S2 2,终了态终了态S S3 3，HMMHMM只只输出两个符号输出两个符号a a和和b b。主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程假定从假定从S1S1出发到出发到S3S3截止，输出的符号截止，输出的符号序列为序列为aabaab，试求输出，试求输出aabaab的概率。的概率。S1S2S3p11=0.3ab0.80.2p22=0.4ab0.30.7p13=0.2ab10 p12=0.5ab10 p23=0.6ab0.50.5从S1到S3，并且输出aab，可能的路径有三条S1-S1-S2-S3S1-S2-S2-S

37、3S1-S1-S1-S3主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程S1S2S3p11=0.3ab0.80.2p22=0.4ab0.30.7p13=0.2ab10 p12=0.5ab10 p23=0.6ab0.50.5S1-S1-S2-S3 0.3*0.8*0.5*1*0.6*0.5=0.036S1-S2-S2-S3 0.5*1*0.4*0.3*0.6*0.5=0.018S1-S1-S1-S3 0.3*0.8*0.3*0.8*0.2*1=0.01152由于不知道输出路径，所以，由于不知道输出路径，所以，输出输出aabaab有三种可能路径，输有三种可能路径，

38、输出出aabaab的概率为的概率为0.036+0.018+0.011520.036+0.018+0.01152=0.06552=0.06552如果知道路径，如果知道路径，那么输出那么输出aabaab的的概率就是该路概率就是该路径的输出概率。径的输出概率。主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程A concrete exampleAssume you have a friend who lives far away and who you call daily to talk about what each of you did that day.You

39、r friend has only three things hes interested in:walking in the park,shopping,and cleaning his apartment.The choice of what to do is determined exclusively by the weather on a given day.You have no definite information about the weather where your friend lives,but you know general trends.Based on wh

40、at he tells you he did each day,you try to guess what the weather must have been like.主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程You believe that the weather operates as a discrete Markov chain.There are two states,Rainy and Sunny,but you cannot observe them directly,that is,they are hidden from you.O

41、n each day,there is a certain chance that your friend will perform one of the following activities,depending on the weather:walk,shop,or clean.Since your friend tells you about his activities,those are the observations.The entire system is that of a hidden Markov model(HMM).主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程

42、与泊松过程马尔可夫过程与泊松过程You know the general weather trends in the area and you know what your friend likes to do on average.In other words,the parameters of the HMM are known.In fact,you can write them down in the Python programming language:states=(Rainy,Sunny)observations=(walk,shop,clean)start_probabili

43、ty=Rainy:0.6,Sunny:0.4 transition_probability=Rainy:Rainy:0.7,Sunny:0.3,Sunny:Rainy:0.4,Sunny:0.6,emission_probability=Rainy:walk:0.1,shop:0.4,clean:0.5,Sunny:walk:0.6,shop:0.3,clean:0.1,主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程In this fragment,start_probability refers to your uncertainty about whic

44、h state the HMM is in when your friend first calls you(all you know is that it tends to be rainy on average).The transition_probability refers to the change of the weather in the underlying Markov chain.In this example,there is only a 30%chance that tomorrow will be sunny if today is rainy.The emiss

45、ion_probability tells you how likely your friend is to perform a certain activity on each day.If its rainy,there is a 50%chance that he is cleaning his apartment;if its sunny,there is a 60%chance that he will go outside for a walk.主讲教师主讲教师:罗鹏飞教授罗鹏飞教授马尔可夫过程与泊松过程马尔可夫过程与泊松过程雨天s1睛天s2p11=0.7p12=0.3p22=0.6p21=0.4雨天:Walk 0.1 Shop 0.4 clean 0.5 睛天:Walk 0.6 Shop 0.3 clean 0.1