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

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

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

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

86

87

88

89 浙大数学随机过程

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

91 浙大数学随机过程

92 平稳分布的意义

93

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

95 Markov链的应用--PageRank

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

97

98

99

100

101

102 浙大数学随机过程

103 浙大数学随机过程

104 浙大数学随机过程

105 浙大数学随机过程

106 浙大数学随机过程

107 浙大数学随机过程

108 浙大数学随机过程

109 浙大数学随机过程

110 浙大数学随机过程

111 浙大数学随机过程

112 浙大数学随机过程

113 浙大数学随机过程

114 浙大数学随机过程