教学第十一章-马尔可夫链课件

第十一章马尔可夫链主要内容：1.定义（与记号）

2.

转移概率与矩阵3.遍历性

返回目录第十一章马尔可夫链主要内容：1.定义（与记号）

1．马尔可夫性的定义：

⑴语言描述（一般性解释）：由时刻系统的状态，可以决定系统在t>时所处的状态，而与以前系统的历史状态无关。如微分方程的定解问题。对于随机现象，可以描述如下：系统在时刻所处的状态为已知的条件下，系统在时刻t>所处状态的条件分布与在时刻之前所处的状态无关。1．马尔可夫性的定义：⑴语言描述（一般性解释）：由⑵数学表达式：

先做一些假设：随机过程设为X(t),状态空间I={}，任选T中n个时刻,，对应的状态为，则的马氏性就是这样一个条件分布函数：=⑵数学表达式：先做一些假设：随机过程设为X(t),

⑶

马尔可夫链：

时间和状态都离散的马尔可夫过程称为马尔可夫链。记为，状态空间I=而相应的马尔可夫性用条件分布律示如下：=⑶马尔可夫链：时间和状态都离散的马尔可夫过程称为马2．转移概率：记上面的条件概率为：称为转移概率，它表示马氏链在时刻m处于状态的条件下，经过n步变化后，在时刻m+n处于状态的条件概率。2．转移概率：记上面的条件概率为：称为转移概率，它表示马氏3．转移概率矩阵：当上式中取遍状态空间I时(此时假设I有限)，会得到N×N个转移概率,它们可以组成一个N×N的矩阵，称为转移概率矩阵，记为它表现了马氏链经过n步后所有可能发生的状态之间的转移。由概率的规范性，容易得到P(m,m+n)的一个性质:每一行元素横向相加等于1。3．转移概率矩阵：当上式中取遍状态空间I时(此时假设I有4.

齐次马氏链：

当只与步数n有关，与起始时刻m无关时，称此转移概率具有平稳性，或称此链是齐次马氏链。可以记为4.齐次马氏链：当只与步数n有关，与起始时刻m无关我们特别要掌握一步转移概率：以及由它们组成的一步转移概率矩阵：我们特别要掌握一步转移概率：以及由它们组成的一步转移概率5．例题：

例2（）：在0—1传输系统中，设每一级的传真率为p，误码率为q=1-p,并设一个单位时间传输一级，是第一级的输入，是第n级的输出。那么｛｝是一个马氏链，而且还是齐次的，其状态空间I={0,1}。5．例题：例2（）：在0—1传输系统中，设每一级的传例3．（）一维随机游动：设一质点在图示直线的点集I={1,2,3,4,5}上作随机游动，且仅在1秒﹑2秒等时刻发生游动。游动的概率规则是：如果点Q现在位于点i（1<i<5)，则下一时刻各以1/3的概率向左或向右移动一格，或以1/3的概率留在原处；如果Q现在位于1（或5）这点上，则下一时刻就以概率1移动到2（或4）这一点上。若以表示时刻n时Q的位置,则是一齐次马氏链，它的一步转移概率矩阵为：例3．（）一维随机游动：设一质点在图示直线的点集I=例4．

排队模型：设服务系统由一个服务员和只可以容纳两个人的等侯室组成。服务规则是先到先服务，后来者需在等候室排队。假定一个顾客到达系统时发现系统内已有板有3个顾客，则该顾客即离去。设时间间隔Δt内有一个顾客进入系统的概率为q,有一原来被服务的顾客离开系统的概率为p。又设当Δt充分小时，在这时间间隔内多于一个顾客进入或离开系统是不可能的。可用马氏链来描述这个服务系统图形例4．排队模型：设服务系统由一个服务员和只可以容纳两个人

例6：（续例5）已知计算机在某一时段（15分钟）的状态为0，问在此条件下从此时段起此计算机能连续正常工作3个时段的条件概率为多少？例6：（续例5）已知计算机在某一时段（15分钟）6．齐此马氏链的有限维分布：⑴先看初始分布：是一个离散型的随机变量，其分布律称为初始分布，可以表为：也可以用表格式：……P……6．齐此马氏链的有限维分布：⑴先看初始分布：是一个离散型的（2）再来看任意时刻n的一维分布：

显然，由规范性有：另外，可以用行向量来表示分布律：（2）再来看任意时刻n的一维分布：显然，由规范性有：另外

⑶初始分布律与任意时刻n的分布律之间的关系:以的各状态值分布为划分，运用全概率公式，即可得到：用矩阵乘法来表达如下：back⑶初始分布律与任意时刻n的分布律以第二节多步转移概率的确定

内容提要：

1.C--K方程形式2.方程的意义

3.方程的证明

4.例题

back第二节多步转移概率的确定内容提要：1.C--1．C--K方程：

设是一齐次马氏链，对任意的u,vT，有：用矩阵表示即：

P(u+v)=P(u)＊P(v)back1．C--K方程：设是一齐次马氏链，对

2．方程的意义：

如果设初始时刻s，终止时刻是s+u+v。

引入中间时刻s+u，C--K方程的意义在于：“从s时刻的状态出发,经u+v步后转移到状态＂这一事件等价于“从出发，先经u步转移到中间状态，再从经时段v转移到＂的和事件。back2．方程的意义：如果设初始时刻s，终止时刻是s+u+v。

3．证明：

back3．证明：back例1：设是具有三个状态0，1，2的齐次马氏链，一步转移矩阵为：P=初始分布试求：例1：设是具有三个状态0，1，例2．（1）在§1例2中，设p=0.9，求系统二级传输后的传真率与三级传输后的误码率；（2）设初始分布，。又已知系统经n级传输后输出为1，问原发字符也是1的概率是多少？back例2．（1）在§1例2中，设p=0.9，求系统二级传输后（2第三节遍历性主要内容：

1.举例2.定义

3.有限链的遍历性充分条件4.平稳分布

5.总结6.例题back第三节遍历性主要内容：1.举例21．举例：在上面例2中的一步转移矩阵P=,计算其n步转移矩阵P(n)为，它存在着极限（矩阵的两行完全相同）back1．举例：在上面例2中的一步转移矩阵P=,计算其n步转移2．定义：

（1）语言描述：对固定状态j，无论链从什么状态出发（即与左边的列无关），经过长时间的转移后，到达状态j的概率都趋近于。这个性质称为遍历性。2．定义：（1）语言描述：对固定状态j，无论链从什么状（2）数学式子表达：

或者：（与i无关）特别地，将行向量提出来，由于它构成了一个分布律，即，称它为极限分布。back（2）数学式子表达：或者：（与i无关）特别地，将行向量3．遍历性的充分性条件：

定理：对齐次马氏链，状态空间I=,一步转移矩阵P(1)。如果存在正整数m，使对任意的，都有，即矩阵P(m)=中无零元素，则此链具有遍历性。且其极限分布就是方程组π=πP(1)的满足的唯一解。back3．遍历性的充分性条件：定理：对齐次马氏链4．平稳分布：

在上述定理的条件下，π又称为平稳分布。其意义在于：π=是所有状态分布中的平衡值，一旦链的状态分布达到了π=，则链的一维状态分布不会再发生变化了。back4．平稳分布：在上述定理的条件下，π又称为平稳分布。其

5．总结：

π的多重意义：(1)代表了遍历性的存在。(2)极限分布。(3)在充分条件下，也是链的平稳分布。back5．总结：π6．例题：例1：试说明§1例3中的随机游动是遍历的，并求其极限分布。例2：试说明§1例4排队模型中的链是遍历的，并求其极限分布。例3：设一马氏链的一步转移矩阵为，试讨论它的遍历性。6．例题：例1：试说明§1例3中的随机游动是遍历的，并例2：补充例题：若顾客的购买是无记忆的。现在市场上供应A,B,C三个不同厂家生产的50g袋装味精。用分别表示事件“顾客第n次购买A,B,C三厂的味精”，则是一个马氏链。已知顾客第一次购买三种味精的概率依次为0.2，0.4，0.4。又知道一般顾客购买的倾向表如下：求：（1）顾客第二次购买各厂味精的概率。（2）经过三次购买后的倾向表。（3）长时间的购买活动后，A，B，C三厂的市场占有率如何？back补充例题：若顾客的购买是无记忆的。现在市场上供应A,B,C三解：（1）(0.56，0.18，0.26)（2）（3）π=(60/84，11/84，13/84)解：（1）(0.56，0.18，0.26)（2）（BackBack第十一章马尔可夫链主要内容：1.定义（与记号）

2.

转移概率与矩阵3.遍历性

返回目录第十一章马尔可夫链主要内容：1.定义（与记号）

1．马尔可夫性的定义：

⑴语言描述（一般性解释）：由时刻系统的状态，可以决定系统在t>时所处的状态，而与以前系统的历史状态无关。如微分方程的定解问题。对于随机现象，可以描述如下：系统在时刻所处的状态为已知的条件下，系统在时刻t>所处状态的条件分布与在时刻之前所处的状态无关。1．马尔可夫性的定义：⑴语言描述（一般性解释）：由⑵数学表达式：

先做一些假设：随机过程设为X(t),状态空间I={}，任选T中n个时刻,，对应的状态为，则的马氏性就是这样一个条件分布函数：=⑵数学表达式：先做一些假设：随机过程设为X(t),

⑶

马尔可夫链：

时间和状态都离散的马尔可夫过程称为马尔可夫链。记为，状态空间I=而相应的马尔可夫性用条件分布律示如下：=⑶马尔可夫链：时间和状态都离散的马尔可夫过程称为马2．转移概率：记上面的条件概率为：称为转移概率，它表示马氏链在时刻m处于状态的条件下，经过n步变化后，在时刻m+n处于状态的条件概率。2．转移概率：记上面的条件概率为：称为转移概率，它表示马氏3．转移概率矩阵：当上式中取遍状态空间I时(此时假设I有限)，会得到N×N个转移概率,它们可以组成一个N×N的矩阵，称为转移概率矩阵，记为它表现了马氏链经过n步后所有可能发生的状态之间的转移。由概率的规范性，容易得到P(m,m+n)的一个性质:每一行元素横向相加等于1。3．转移概率矩阵：当上式中取遍状态空间I时(此时假设I有4.

齐次马氏链：

当只与步数n有关，与起始时刻m无关时，称此转移概率具有平稳性，或称此链是齐次马氏链。可以记为4.齐次马氏链：当只与步数n有关，与起始时刻m无关我们特别要掌握一步转移概率：以及由它们组成的一步转移概率矩阵：我们特别要掌握一步转移概率：以及由它们组成的一步转移概率5．例题：

例2（）：在0—1传输系统中，设每一级的传真率为p，误码率为q=1-p,并设一个单位时间传输一级，是第一级的输入，是第n级的输出。那么｛｝是一个马氏链，而且还是齐次的，其状态空间I={0,1}。5．例题：例2（）：在0—1传输系统中，设每一级的传例3．（）一维随机游动：设一质点在图示直线的点集I={1,2,3,4,5}上作随机游动，且仅在1秒﹑2秒等时刻发生游动。游动的概率规则是：如果点Q现在位于点i（1<i<5)，则下一时刻各以1/3的概率向左或向右移动一格，或以1/3的概率留在原处；如果Q现在位于1（或5）这点上，则下一时刻就以概率1移动到2（或4）这一点上。若以表示时刻n时Q的位置,则是一齐次马氏链，它的一步转移概率矩阵为：例3．（）一维随机游动：设一质点在图示直线的点集I=例4．

排队模型：设服务系统由一个服务员和只可以容纳两个人的等侯室组成。服务规则是先到先服务，后来者需在等候室排队。假定一个顾客到达系统时发现系统内已有板有3个顾客，则该顾客即离去。设时间间隔Δt内有一个顾客进入系统的概率为q,有一原来被服务的顾客离开系统的概率为p。又设当Δt充分小时，在这时间间隔内多于一个顾客进入或离开系统是不可能的。可用马氏链来描述这个服务系统图形例4．排队模型：设服务系统由一个服务员和只可以容纳两个人

例6：（续例5）已知计算机在某一时段（15分钟）的状态为0，问在此条件下从此时段起此计算机能连续正常工作3个时段的条件概率为多少？例6：（续例5）已知计算机在某一时段（15分钟）6．齐此马氏链的有限维分布：⑴先看初始分布：是一个离散型的随机变量，其分布律称为初始分布，可以表为：也可以用表格式：……P……6．齐此马氏链的有限维分布：⑴先看初始分布：是一个离散型的（2）再来看任意时刻n的一维分布：

显然，由规范性有：另外，可以用行向量来表示分布律：（2）再来看任意时刻n的一维分布：显然，由规范性有：另外

⑶初始分布律与任意时刻n的分布律之间的关系:以的各状态值分布为划分，运用全概率公式，即可得到：用矩阵乘法来表达如下：back⑶初始分布律与任意时刻n的分布律以第二节多步转移概率的确定

内容提要：

1.C--K方程形式2.方程的意义

3.方程的证明

4.例题

back第二节多步转移概率的确定内容提要：1.C--1．C--K方程：

设是一齐次马氏链，对任意的u,vT，有：用矩阵表示即：

P(u+v)=P(u)＊P(v)back1．C--K方程：设是一齐次马氏链，对

2．方程的意义：

如果设初始时刻s，终止时刻是s+u+v。

引入中间时刻s+u，C--K方程的意义在于：“从s时刻的状态出发,经u+v步后转移到状态＂这一事件等价于“从出发，先经u步转移到中间状态，再从经时段v转移到＂的和事件。back2．方程的意义：如果设初始时刻s，终止时刻是s+u+v。

3．证明：

back3．证明：back例1：设是具有三个状态0，1，2的齐次马氏链，一步转移矩阵为：P=初始分布试求：例1：设是具有三个状态0，1，例2．（1）在§1例2中，设p=0.9，求系统二级传输后的传真率与三级传输后的误码率；（2）设初始分布，。又已知系统经n级传输后输出为1，问原发字符也是1的概率是多少？back例2．（1）在§1例2中，设p=0.9，求系统二级传输后（2第三节遍历性主要内容：

1.举例2.定义

3.有限链的遍历性充分条件4.平稳分布

5.总结6.例题back第三节遍历性主要内容：1.举例21．举例：在上面例2中的一步转移矩阵P=,计算其n步转移矩阵P(n)为，它存在着极限（矩阵的两行完全相同）back1．举例：在上面例2中的一步转移矩阵P=,计算其n步转移2．定义：

（1）语言描述：对固定状态j，无论链从什么状态出发（即与左边的列无关），经过长时间的转移后，到达状态j的概率都趋近于。这个性质称为遍历性。2．定义：（1）语言描述：对固定状态j，无论链从什么状（2）数学式子表达：

或者：（与i无关）特别地，将行向量提出来，由于它构成了一个分布律，即，称它为极限分布。back（2）数学式子表达：或者：（与i无关）特别地，将行向量3．遍历性的充分性条件：

定理：对齐次马氏链，状态空间I=,一步转移矩阵P(1)。如果存在正整数m，使对任意的，都有，即矩阵P(m)=中无零元素，则此链具有遍历