建模马尔科夫链.ppt

,马尔可夫链定义,定义,设随机过程的状态空间为,则称为离散时间、离散状态的马尔可夫过程，或简称为马尔可夫链.,若对任意的，及有,,,,,,,,,,,,,,马尔可夫链的等价定义,设随机过程是一马尔可夫链，则对任意的，及,有,条件概率回顾,设是随机事件,①,②,条件概率的乘法公式,条件独立性,若有,则称事件与关于条件独立.,马尔可夫链的本质特征,已知系统当前状态的条件下即，,系统将来的状态与其过去的历史状态无关独立.,马尔可夫链的一些简单例子,例1,假设甲乙两人以抛硬币的方式进行赌博，每次抛同一枚硬币；若出现正面，则甲付给乙一元钱，若出现反面，则乙付给甲一元钱.记为第局之后甲赢的总数.则是马尔可夫链.,例2,马尔可夫链的研究内容,对马尔可夫链的状态空间按照某种规则进行分类.,①,②,计算马尔可夫链的有限维分布.,③,研究马尔可夫链的极限性质.,设是马尔可夫链，对任意的，计算的联合分布律,,即马尔可夫链的有限维分布完全由初始分布和一步转移概率确定.,,,,马尔可夫链的一步转移概率,设是马尔可夫链，记,定义,称为马尔可夫链在时刻时的一步转移概率.,注,当固定时，一步转移概率实质上就是在的条件下，随机变量的条件分布律，所以条件分布律满足,①,②,齐次马尔可夫链,定义,设是马尔可夫链，若其一步转移概率与时间无关，即,则称为齐次马尔可夫链，称为从状态转移到状态的一步转移概率.,若马尔科夫链的状态空间是有限集，则称为有限状态的马尔科夫链；,若马尔科夫链的状态空间是可列集，则称为可列状态的马尔科夫链.,一步转移概率矩阵,定义,设是齐次马尔可夫链，其一步转移概率为，记,则称矩阵为齐次马尔科夫链的一步转移概率矩阵.,记称为齐次马尔科夫链的初始分布.,齐次马尔科夫链的有限维分布族完全由其一步转移概率矩阵和初始分布确定.,例1,假设甲乙两人以抛硬币的方式进行赌博，每次抛同一枚硬币；若出现正面，则甲付给乙一元钱，若出现反面，则乙付给甲一元钱.记为第局之后甲赢的总数.则是齐次马尔可夫链.,试求马尔科夫链的转移概率矩阵.,解,假设硬币出现正面的概率是，则出现反面的概率是.,,转移概率矩阵为,,2切普曼－柯尔莫哥洛夫方程,记号,设是马尔科夫链，其状态空间为,①,②,记马尔科夫链的步转移概率为,称为马尔科夫链在时刻时处于状态经过时间后转移到状态的概率.,定理,称式为切普曼－柯尔莫哥洛夫方程,设是马尔科夫链，其状态空间为，则对任意的，有,直观意义,从状态出发经过步到达状态，可分成两步走,①,②,先从状态出发经过步到达状态；,然后再先从状态出发经过步到达状态；,由马氏性知，后一阶段的状态转移与前一阶段的状态转移独立，故两个阶段的转移概率相乘,证明,i,k,j,0,,n,,,,,,,,,,,,,,注,若是齐次马尔科夫链，则切普曼－柯尔莫哥洛夫方程可写成如下形式,记齐次马尔科夫链的步转移概率矩阵为,则齐次马尔科夫链的切普曼－柯尔莫哥洛夫方程可用如下矩阵形式表示,,,天气预测简单模型假设明天是否下雨仅与今天的天气是否下雨有关，而与过去的天气无关.假设今天下雨、明天有雨的概率为，今天无雨而明天有雨的概率为；又假设把有雨称为状态天气，把无雨称为状态天气.记表示第天的天气状态.则是状态有限的马尔科夫链.,,3马尔科夫链的一些简单例子,例2,求其一步转移概率矩阵；,①,②,若，且今天有雨，求第四天有雨的概率.,解,①,,,,一步状态概率矩阵为,,,②,因为,,所以若今天无雨，第四天下雨的概率为,,例3,简单信号模型在某数字通讯系统中，只传输0、1两种信号，且传输要经过很多级.每级中由于噪声的存在会引起误差.假设每级输入0、1信号后，其输出不产生误差的概率为.记为第级的输出信号.则是状态有限的马尔科夫链，求其一步转移概率矩阵.,1,2,,,n-1,,,n,,,,解,马尔科夫链的的状态空间为,易知其一步转移概率矩阵为,例4,无限制随机游动质点在直线上作随机游动.在某一时刻质点位于，则下一步质点以概率向右移动一格到达；或以概率向左移动一格到达.以表示质点在时刻的位置.则是状态无限的马尔科夫链，求其一步转移概率矩阵.,解,马尔科夫链的的状态空间为,一步状态概率为,一步状态概率矩阵为,例5,带有一个吸收壁的随机游动质点在直线上作随机游动.在某一时刻质点位于，则下一步质点以概率向右移动一格到达；或以概率,向左移动一格到达.但当质点一旦到达原点，则质点永远停留在原点，不再移动.状态称为吸收态.以表示质点在时刻的位置.则是齐次马尔科夫链，称其为带一个吸收壁的随机游动.求其一步转移概率矩阵.,解,马尔科夫链的的状态空间为,一步状态概率为,一步状态概率矩阵为,例6,带有两个吸收壁的随机游动设随机游动的状态空间为，其中和是两个吸收壁，即质点一旦到达状态或，则永远停留在该处.以表示质点在时刻时的位置，则是齐次马尔可夫链，称为带有两个吸收壁的随机游动.求其一步转移概率矩阵.,解,一步状态概率为,一步状态概率矩阵为,例7,赌徒输光问题甲、乙两人进行一系列赌博.在每局赌博中，甲赢的概率为，乙赢的概率为.每局赌博后，输者付给赢者一元钱.设每局赌博的结果都是相互独立的.假设在赌局开始时，甲有初始赌博为元，乙有初始赌本为元.赌博一直进行到一个人输光为止.求甲输光的概率.,随机游动的简单应用,解,设赌博进行了局之后，甲拥有的总赌本.,故一步状态概率矩阵为,则是一状态有限的齐次马尔可夫链，其状态空间为.,由题意知，是带有两个吸收壁的随机游动.,,马尔可夫链的初始状态为,对任意的,设为事件“最终是甲先输光”,设为事件“质点到达吸收态”,则事件与事件等价，即,记为质点从状态出发到达状态的概率，即,则有,①,②,,对任意的,,要求的概率是,,,,由此得到差分方程,边界条件为,,,令，得,则有,当，即时，有,,所以当时，即赌博不公平时，甲最终输光的概率为,,所以甲最终输光的概率是,当时，即，此时赌博是公平的，有,,,,当赌博是公平赌博时，赌徒最终输光的概率与其拥有的赌本成正比.,综上可知，甲最终输光的概率是,当时；,,当时.,,,,,例8,带有一个反射壁的随机游动设随机游动的状态空间为，当质点到达状态时，以概率返回到状态，以概率停留在状态.状态称为反射壁.记表示质点在时刻时的位置，则是齐次马尔可夫链，求其一步转移概率.,解,一步转移概率为,,,,,,,,,,例9,带有两个反射壁的随机游动设随机游动的状态空间为，当质点到达状态时，下一步以概率返回到状态，以概率停留在状态；当质点到达状态时，下一步以概率停留在状态，以概率返回到状态.状态和状态称为反射壁.记表示质点在时刻时的位置，则是齐次马尔可夫链，求其一步转移概率.,解,一步转移概率为,,,,,,,,,,,,,,,一步转移概率矩阵为,例10,Ehrenfest模型设一个坛子里共装有红球和黑球个.每次从坛子中随机摸一个球出来不放回，并放入一个另一种颜色的球.记为摸了次后，坛子中黑球的个数，则是齐次马尔可夫链，求其一步转移概率.,解,马尔科夫链的的状态空间为,一步转移概率为,,,,,当时,当时,当时,当时,当时,第次摸球时，坛子里有个黑球，个红球.,,,,,,,,当或时,一步转移概率矩阵为,例11,Polya坛子模型设一个坛子里共装有个红球和个黑球.每次从坛子中随机摸一个球出来并放回，然后再放入与刚所摸球同颜色的球个.如此不断地进行下去.记为摸了次后，坛子中黑球的个数，则是齐次马尔可夫链，求其一步转移概率.,,解,马尔科夫链的的状态空间为,,,,,,,,,,,,,,对任意的，事件表示,第次取球之后，坛子里有个球，其中黑球个,,,则在此条件下，第次摸到黑球的概率是,,同时若第次摸到黑球，则坛子里有个黑球,,由上分析得到其一步转移概率为,例12,离散分支过程考虑一生物种群的繁殖.假设开始时种群的个体数为，称之为第代.由第代个体繁殖产生的后代称为第一代，第一代个体的数目记为.如此继续下去，第代个体繁殖产生的个体称为第代，第代个体的数目记为.假设同一代中各个个体繁殖产生的后代个数是相互独立的，且与种群以前的繁殖过程无关.每一个个体均可产生个后代，是非负整数值随机变量.则是齐次马尔科夫链.,解,第代个体,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,第代个体,即第代个体总数是第代各个个体繁殖的后代个体数之和.所以第代个体的总数完全由第代的个体数决定.,,记为第代个体中第个个体产生的后代数.,,,,由题意知，随机变量序列相互独立且与同分布，且有,称此形式的马氏链,,为分支过程.,分支过程主要关心的问题是,种群灭绝的概率及时间.,种群是否会爆炸,一步转移概率,,上式涉及独立随机变量和的分布律，计算复杂，通常采用母函数的方法进行研究.,试求出的母函数,,,,,,,