第三章 马尔可夫链 关键词： 马尔可夫性 时齐马尔可夫链 n步转移概率 C-K方程 马氏链的有限维分布律 常返 暂留 正常返 零常返 第三章 马尔可夫链 关键词： 马尔可夫性 时齐马尔可夫链 n步转移概率 C-K方程 马氏链的有限维分布律 常返 暂留 正常返 零常返 互达 周期 不可约 平稳分布 极限分布 可逆Markov链

5

… n 2 1 X0 X1 X2 Xn Xn-1

… n 2 1 X0 X1 X2 Xn Xn-1

1 3 4 5 2

1 3 4 5 2

1 3 4 5 2 如果把1这点改为吸收壁，即Q一旦到达1这一点， 则永远留在点1时，此时的转移概率矩阵为：

等候室 服务台 系统 随机到达者 离去者 例4：排队模型 设服务系统由一个服务员和只可以容纳两个人的等候室组成。服务规则为：先到先服务，后来者需在等候室依次排队，假设一个需要服务的顾客到达系统时发现系统内已有3个顾客，则该顾客立即离去。 设时间间隔⊿t内有一个顾客进入系统的概率为q，有一接受服务的顾客离开系统(即服务完毕)的概率为p,又设当⊿t充分小时，在这时间间隔内多于一个顾客进入或离开系统实际上是不可能的，再设有无顾客来到与服务是否完毕是相互独立的。

等候室 服务台 系统 随机到达者 离去者 现用马氏链来描述这个服务系统： 设Xn=X(n⊿t)表示时刻n⊿t时系统内的顾客数，即系统的状态。{Xn,n=0,1,2…}是一随机过程，状态空间I={0,1,2,3},且如前例1、例2的分析可知，它是一个时齐马氏链，它的一步转移概率矩阵为：

取出一球放入另一袋(若袋中无球则不取)。Xn表示 第n次抽取后甲袋的球数，n=1,2,….{Xn,n=1,2,…} 例5：设甲、乙两袋共装5个球，每次任取一袋,并从袋中 取出一球放入另一袋(若袋中无球则不取)。Xn表示 第n次抽取后甲袋的球数，n=1,2,….{Xn,n=1,2,…} 是一随机过程，状态空间I={0,1,2,3,4,5},当Xn=i 时，Xn+1=j的概率只与i有关，与n时刻之前如何取到 i值是无关的，这是时齐马氏链，一步转移矩阵为： 甲 乙

例6：卜里耶（Polya)罐子模型。设一罐子装有r个红球， t个黑球，现随机从罐中取出一球，记录其颜色，然后将 球放回，并加入a个同色球。持续进行这一过程，Xn表示 第n次试验结束时罐中的红球数，n=0，1,2,…. {Xn,n=0，1,2,…}是一随机过程， 状态空间I={r,r+a,r+2a,…},当Xn=i 时，Xn+1=j的概率只 与i有关，与n时刻之前如何取到i值是无关的， 这是一马氏链，但不是时齐的,一步转移概率为：

当前状态 下一状态 状态 年保险金 0个理赔 1个理赔 2个理赔 2个以上理赔 1 2000 2 3 4 2500 4000 6000

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

平稳分布的意义

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

例6：设有6个球(2个红球,4个白球)随机平分放入甲, 乙两个盒中.今每次从两盒中各任取一球并进行交换. 表示开始时甲盒中的红球数, 表示经n次交换 后甲盒中的红球数. (1)求此马氏链的初始分布; (2)求一步转移矩阵; (3)计算

浙大数学随机过程

状态 年保险金 0个理赔 1个理赔 2个理赔 2个以上理赔 1 200 2 3 4 250 400 600 当前状态 下一状态 浙大数学随机过程

浙大数学随机过程

Markov链的应用—PageRank PageRank, 就是网页排名，又称网页级别，是一种由搜索引擎根据网页之间相互的超链接计算的网页排名技术，Google用它来体现网页的重要性。是Google的创始人拉里·佩奇和谢尔盖·布林在斯坦福大学发明了这项技术, 并最终以拉里·佩奇（Larry Page）之姓来命名。

Markov链的应用--PageRank

链接源I D 链接目标 1 1 2,3,4,5, 7 2 1 3 1,2 4 2,3,5 5 1,3,4,6 6 1,5 7 5

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

用R语言模拟状态空间为{1,2,...n}，初始分布为u， 一步转移矩阵为P的Markov链 Homo_Markov<-function(n,u,P,T){ x<-rep(0,T+1) #令x为长度为T+1的0向量 U<-runif(1) #令U服从U(0,1) k<-1 F<-u[1] while (U>=F){ k<-k+1 F<-F+u[k] } x[1]<-k #生成x0

U<-runif(1) #令U服从U(0,1) k<-1 i<-x[j] F<-P[i,1] for(j in 1:T){ U<-runif(1) #令U服从U(0,1) k<-1 i<-x[j] F<-P[i,1] while (U>=F){ k<-k+1 F<-F+P[i,k] } x[j+1]<-k #生成xj return(x) #返回向量x

n<-4 u<-c(0.5,0,0,0.5) P<-matrix(c(0,1/3,1/3,1/3,1/2,0,1/2,0,1/2,1/2,0,0,1,0,0,0),ncol=4,byrow=TRUE) T<-30 P x<-Homo_Markov(n,u,P,T) x t<-c(0:T) plot(t,x,"b")

> P [,1] [,2] [,3] [,4] [1,] 0.0 0.3333333 0.3333333 0.3333333 [2,] 0.5 0.0000000 0.5000000 0.0000000 [3,] 0.5 0.5000000 0.0000000 0.0000000 [4,] 1.0 0.0000000 0.0000000 0.0000000 > x [1] 4 1 3 1 4 1 2 3 2 1 2 3 1 2 1 3 1 2 3 2 1 4 1 4 1 3 1 3 1 3 1

#P是一步转移矩阵 #计算P的i步转移矩阵i=1：n n=40 P=matrix(c(0,1/3,1/3,1/3,1/2,0,1/2,0,1/2,1/2,0,0,1,0,0,0),ncol=4,byrow=TRUE) print(P) Q=P for(i in 1:n){ Q=Q%*%P print(i+1) print(Q) }

浙大数学随机过程

浙大数学随机过程

浙大数学随机过程

#模拟一维随机游动 par(mfrow=c(3,2)) n=100 x=0:(n-1) q=runif(n) z=2*(q>0.8)-1 y=numeric(n) for(i in 1:(n-1)){ y[i+1]=y[i]+z[i] } plot(xlab="n",ylab="Sn",main="随机游动p=0.2的一条样本函数",x,y,type="b",pch=16)

x1=0:(n-1) q1=runif(n) z1=2*(q1>0.6)-1 y1=numeric(n) for(i in 1:(n-1)){ y1[i+1]=y1[i]+z1[i] } plot(xlab="n",ylab="Sn",main="随机游动p=0.4的一条样本函数",x1,y1,type="b",pch=16) x5=0:(n-1) q5=runif(n) z5=2*(q5>0.5)-1 y5=numeric(n) y5[i+1]=y5[i]+z5[i] plot(xlab="n",ylab="Sn",main="随机游动p=0.5的一条样本函数",x5,y5,type="b",pch=16)

x2=0:(n-1) q2=runif(n) z2=2*(q2>0.4)-1 y2=numeric(n) for(i in 1:(n-1)){ y2[i+1]=y2[i]+z2[i] } plot(xlab="n",ylab="Sn",main="随机游动p=0.6的一条样本函数",x2,y2,type="b",pch=16) x3=0:(n-1) q3=runif(n) z3=2*(q3>0.2)-1 y3=numeric(n) y3[i+1]=y3[i]+z3[i] plot(xlab="n",ylab="Sn",main="随机游动p=0.8的一条样本函数",x3,y3,type="b",pch=16)

x4=0:(n-1) q4=runif(n) z4=2*(q4>0.1)-1 y4=numeric(n) for(i in 1:(n-1)){ y4[i+1]=y4[i]+z4[i] } plot(xlab="n",ylab="Sn",main="随机游动p=0.9的一条样本函数",x4,y4,type="b",pch=16)

#模拟爬梯子模型 n=200 x=0:(n-1) par(mfrow=c(3,1)) q=runif(n) y=numeric(n) for(i in 1:(n-1)){ y[i+1]=(y[i]+1)*(q[i]<exp(-1/((y[i]+1)^2))) } plot(xlab="n",ylab="Xn",main="爬梯子模型p_i=exp(-1/(i+1)^2)一条样本函数",x,y,type="o",pch=16)

q1=runif(n) y1=numeric(n) for(i in 1:(n-1)){ y1[i+1]=(y1[i]+1)*(q1[i]<(y1[i]+1)/(y1[i]+2)) } plot(xlab="n",ylab="Xn",main="爬梯子模型p_i=(i+1)/(i+2)的一条样本函数",x,y1,type="o",pch=16) q2=runif(n) y2=numeric(n) y2[i+1]=(y2[i]+1)*(q2[i]<(y2[i]+1)^2/((y2[i]+2)^2)) plot(xlab="n",ylab="Xn",main="爬梯子模型p_i=(i+1)^2/(i+2)^2的一条样本函数",x,y2,type="o",pch=16)