-马尔可夫链.ppt

.Markov过程安德雷.安德耶维奇.马尔可夫(A.A.Markov):俄数学家，1856~1922概率和统计领域专家。当年Markov研究普希金诗歌里元音字母和辅音字母交替出现的规律时提出了Markov过程的数学模型Markov过程80年代兴起，在现代工程、自然科学、社会科学中应用广泛。1．马尔可夫性2.马尔可夫过程3.马尔可夫链时间离散状态离散的马尔科夫链1.转移概率特别当k=1时，定义称可数维的矩阵２.Chapman-kolmogorov方程２.Chapman-kolmogorov方程系统在n时从状态i的出发,经过k+m步转移,于n+k+m时到达状态j,可以先在n时从状态i出发，经过k步转移于n+k时到达某种中间状态l,再在n+k时从中间状态l出发经过m步转移于n+k+m时到达最终状态j,而中间状态l要取遍整个状态空间S.若取m=1,则由C-K方程的矩阵形式:定理马尔可夫链的k步转移概率由 其一步
转移概率所完全确定.1）初始分布2）有限维分布2）有限维分布又因为马尔可夫链的k步转移概率由一步转移概率所
完全确定.3）绝对分布3）绝对分布4.齐次马尔可夫链为方便，一般假定时间起点为零．即例１(天气预报问题)如果明天是否有雨仅与今天的天气(是否有雨)有关，而与过去的天气无关.并设
今天下雨、明天有雨的概率为a，
今天无雨而明天有雨的概率为b，又假设
有雨称为0状态天气，无雨称为1状态天气.
Xn表示时刻n时的天气状态，则例2(有限制随机游动问题)
设质点只能在{0，1，2，···，a}中的各点上作随机
游动，移动规则如下：设Xn表示质点在n时刻所处的位置，则设一个坛子中装有m个球，它们或是红色的，或是黑色的，从坛子中随机的摸出一球，并换入一个相反颜色的球.其一步转移概率矩阵为甲有赌资a元，乙有赌资b元，赌一局输者给赢者1元，无和局。甲赢的概率为p，
乙赢的概率为q=1-p，求甲输光的概率。
解状态空间I={0,1,2,,c}，c=a+b设ui表示甲从状态i出发转移到状态0的概率，求ua
显然u0=1，uc=0(u0表示已知甲输光情形下甲输光的概率，uc表示已知乙输光情形下甲输光的概率)
ui=pui+1+qui-1(i=1,2,,c-1)
（甲在状态i下输光：甲赢一局后输光或甲输一局后输光）

例5天气预报问题
RR表示连续两天有雨，记为状态0
NR表示第1天无雨第2天有雨，记为状态1
RN表示第1天有雨第2天无雨，记为状态2
NN表示连续两天无雨，记为状态3
p00=P{R今R明|R昨R今}=P{R明|R昨R今}=0.7
p01=P{N今R明|R昨R今}=0
p02=P{R今N明|R昨R今}=P{N明|R昨R今}=0.3
p03=P{N今N明|R昨R今}=0类似地得到其他转移概率，
于是转移概率矩阵为

若星期一、星期二均下雨，求星期四下雨的概率星期四下雨的情形如右，
星期四下雨的概率

2步转移概率矩阵为例6设解第一节基本概念练习设1基本概念一、基本概念定理1首达时间说明2状态i的周期1基本概念二、状态类别的划分及判别注将“不返回i”称为成功，2.判别2.判别2.判别1基本概念三、状态间的关系三、状态间的关系4.互通的两个状态的状态类型1基本概念四、状态空间的分解（1）定义（1）定义（1）定义A.有关闭集B.有关等价类例12/3例21（3）状态空间的分解定理6如果从某一非常返态出发，系统可能一直在非常返集中，也可能进入某个常返闭集，一旦进入某个常返闭集后，将一直停留在这个常返闭集中；如果系统从某一常返状态出发，则系统就一直停留在这个状态所在的常返闭集中。定理7定理8(周期链分解定理)转移概率矩阵的标准形式例解考虑状态1是否常返，类似地可求得例解因此只需考虑状态0是否正常返即可。一般情况一、极限定理所以定理：若i与j相通，则一、极限定理一、极限定理一、极限定理一、极限定理一、极限定理状态性质判别法例解…二、平稳分布与极限分布则平稳分布可表示为如下矩阵形式2，定义：若马尔可夫链是遍历的（即所有状态相通且均为周期为1的正常返态），则极限定理：一个不可约非周期的马尔可夫链属于下列两种情况之一：
1，状态或全是滑过的（非常返的）或全是零常返的。此时对一切的i,j有只证2，若马尔可夫链是遍历的,则利用C-K方程再证注：1，对于不可约的遍历链（不可约、正常返、周期为1）
因为2，对于不可约的遍历链，因为极限分布存在且等于平
稳分布，这意味着当n充分大时有，
例1设状态空间为S={0,1,2,}的马尔可夫链,其一步
转移概率矩阵为例2设齐次马尔可夫链的状态空间S={0,1,2,3,4},其一步转移概率矩阵为解易知是不可约链,且为遍历链.例3设有状态空间S={0,1,2,3,4,5,6}的齐次马尔可夫链
其一步转