第三章 马尔可夫链 关键词： 马尔可夫性 时齐马尔可夫链 n步转移概率 C-K方程 马氏链的有限维分布律 常返 暂留 正常返 零常返

Presentation on theme: "第三章 马尔可夫链 关键词： 马尔可夫性 时齐马尔可夫链 n步转移概率 C-K方程 马氏链的有限维分布律 常返 暂留 正常返 零常返"— Presentation transcript:

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

2

3

4

5 5

6

7

8

9

10

11 … n 2 1 X0 X1 X2 Xn Xn-1

12 … n 2 1 X0 X1 X2 Xn Xn-1

13 1 3 4 5 2

14 1 3 4 5 2

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

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

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

18 取出一球放入另一袋(若袋中无球则不取)。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值是无关的，这是时齐马氏链，一步转移矩阵为： 甲 乙

19 例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值是无关的， 这是一马氏链，但不是时齐的,一步转移概率为：

20

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

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64 浙大数学随机过程

65 浙大数学随机过程

66

67

68

69 浙大数学随机过程

70 浙大数学随机过程

71 浙大数学随机过程

72

73 浙大数学随机过程

74

75

76 浙大数学随机过程

77 浙大数学随机过程

78 浙大数学随机过程

79 浙大数学随机过程

80

81

82 平稳分布的意义

83

84

85

86

87 浙大数学随机过程

88

89 浙大数学随机过程

90

91

92

93

94

95

96

97

98 浙大数学随机过程

99 浙大数学随机过程

100

101

102

103

104

105

106

107

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

109

110

111

112 浙大数学随机过程

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

114 浙大数学随机过程

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

116 Markov链的应用--PageRank

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

118

119

120

121

122

123 浙大数学随机过程

124 浙大数学随机过程

125 浙大数学随机过程

126 浙大数学随机过程

127 浙大数学随机过程

128 浙大数学随机过程

129 浙大数学随机过程

130 浙大数学随机过程

131 浙大数学随机过程

132 浙大数学随机过程

133 浙大数学随机过程

134 浙大数学随机过程

135 浙大数学随机过程

136 浙大数学随机过程

137 浙大数学随机过程

138 浙大数学随机过程

139 浙大数学随机过程

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155 浙大数学随机过程

156 浙大数学随机过程

157

158

159

160 用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

161 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

162 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")

163 > P [,1] [,2] [,3] [,4] [1,] [2,] [3,] [4,] > x [1]

164

165 #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) }

166 浙大数学随机过程

167 浙大数学随机过程

168 浙大数学随机过程

169

170 #模拟一维随机游动 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)

171 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)

172 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)

173 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)

174

175 #模拟爬梯子模型 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)

176 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)

177