2004-12-27
应用随机过程讲义 第三讲
1
第三讲
2004-12-27
应用随机过程讲义 第三讲
2
作业题
1,4,7,8,18,20(1,3),22
2004-12-27
应用随机过程讲义 第三讲
3
离散时间的Markov链预备知识：条件独立性
2004-12-27
应用随机过程讲义 第三讲
4
.,
)|()|()|(
,,,
条件独立关于称若设事件
BCA
BCPBAPBACP
CBA
=
∈
==
==
)|()|()|(
)|()|()|(
BCPABCPBACP
BAPCBAPBCAP
.,条件独立关于 BCA?
2004-12-27
应用随机过程讲义 第三讲
5
定义，背景与例指标集离散条件独立
2004-12-27
应用随机过程讲义 第三讲
6
已知现在，将来关于过去条件独立,
可推广到
)|(
),,,|(
1,10,
)|(
),,|(
11
110011
11
nnnn
nnnnnn
k
nnknkn
nnknkn
iXBXP
iXBXBXBXP
nknkSB
iXiXP
iXiXiXP
=∈=
=∈∈∈
+=?≤≤?
===
===
++
++
++
++
K
K
设状态子集
2004-12-27
应用随机过程讲义 第三讲
7
“过去,和,将来,都可以是状态子集 ;但,现在,
必须是特定状态,
2004-12-27
应用随机过程讲义 第三讲
8
2004-12-27
应用随机过程讲义 第三讲
9
2004-12-27
应用随机过程讲义 第三讲
10
即 n时刻的分布律
2004-12-27
应用随机过程讲义 第三讲
11
2004-12-27
应用随机过程讲义 第三讲
12
2004-12-27
应用随机过程讲义 第三讲
13
全概率公式的思想
2004-12-27
应用随机过程讲义 第三讲
14
2004-12-27
应用随机过程讲义 第三讲
15
简称 C-K方程
2004-12-27
应用随机过程讲义 第三讲
16
(由时齐性 )
2004-12-27
应用随机过程讲义 第三讲
17
2004-12-27
应用随机过程讲义 第三讲
18
2004-12-27
应用随机过程讲义 第三讲
19
失效后无法自然恢复
2004-12-27
应用随机过程讲义 第三讲
20
2004-12-27
应用随机过程讲义 第三讲
21
2004-12-27
应用随机过程讲义 第三讲
22
T
ij
是ω的函数,是随机变量.
},,1:inf{
0
iXjXnnT
nij
==≥=
2004-12-27
应用随机过程讲义 第三讲
23
.)(
,})(,,0:{
.1,
)(,0
1)|(
:
0
)0(
00
)0(
+∞=
===≥
≥=
≠=
====
ω
ω
ij
n
ij
ij
ii
T
jXiXnn
Tij
jiP
iXiXPP
则规定若时当约定
Φ
2004-12-27
应用随机过程讲义 第三讲
24
首达时间的条件分布
)|(
0
1
)(
iXTPff
ii
k
k
iiii
=∞<==
∑
∞
=
2004-12-27
应用随机过程讲义 第三讲
25
从 i出发,经过有限步,可以以概率 1返回,
2004-12-27
应用随机过程讲义 第三讲
26
2004-12-27
应用随机过程讲义 第三讲
27
在常返的前提下
2004-12-27
应用随机过程讲义 第三讲
28
2004-12-27
应用随机过程讲义 第三讲
29
2004-12-27
应用随机过程讲义 第三讲
30
2004-12-27
应用随机过程讲义 第三讲
31
从图上直观地看,状态 1带自环,一定是非周期的
2004-12-27
应用随机过程讲义 第三讲
32
2004-12-27
应用随机过程讲义 第三讲
33
事件的转化与分解体现,首达,的意义
这一步有何依据
2004-12-27
应用随机过程讲义 第三讲
34
},{}{},{
}.{},{
.}{
,)(},{
0
1
0
1
0
1
0
jXiXlTjXiX
lTjXiX
lT
jjXiX
n
l
ijn
l
ijn
l
ij
n
====∩==∴
=?==
=
==
∞
=
∞
=
∞
=
U
U
U
因此有必然会发生事件时即通过有限步到达发生事件
2004-12-27
应用随机过程讲义 第三讲
35
全概率公式
2004-12-27
应用随机过程讲义 第三讲
36
2004-12-27
应用随机过程讲义 第三讲
37
)( jX
n
I
=
2004-12-27
应用随机过程讲义 第三讲
38
递减事件序列
2004-12-27
应用随机过程讲义 第三讲
39
T
ij
=l表明在前 l步之内没有到达 j状态
S
m
(j)表示时刻 m之后到达状态 j的次数
2004-12-27
应用随机过程讲义 第三讲
40
2004-12-27
应用随机过程讲义 第三讲
41
2004-12-27
应用随机过程讲义 第三讲
42
2004-12-27
应用随机过程讲义 第三讲
43
以下命题等价
+∞==
+∞=
==+∞==
===
=
∑
∑
∞
=
∞
=
=
∞
=
)|)(()5(;)4(
.1)|)((),()()3(
1}}|{{)2(
11
01
1
)(
01(
1
0
iXiSE
P
iXiSPIiS
iXiXP
if
n
n
ii
nm
iXn
n
n
ii
m
ω
）
令；
为常返态）；（）
U
（
2004-12-27
应用随机过程讲义 第三讲
44
一维直线上的简单随机游动 (p,q)游动
p=q 常返链（所有状态均为常返态）
p≠q 非常返链
2004-12-27
应用随机过程讲义 第三讲
45
2004-12-27
应用随机过程讲义 第三讲
46
2004-12-27
应用随机过程讲义 第三讲
47
2004-12-27
应用随机过程讲义 第三讲
48
推论,
.0lim
,,
,,
)(
1
)(
1
)(
=?
+∞<∈?
+∞=→
∞→
∞
=
∞
=
∑
∑
n
ij
n
n
n
ij
n
n
ij
P
PSij
Pjij
则为非常返态若则且为常返态若
2004-12-27
应用随机过程讲义 第三讲
49
对解题很有帮助
2004-12-27
应用随机过程讲义 第三讲
50
2004-12-27
应用随机过程讲义 第三讲
51
2004-12-27
应用随机过程讲义 第三讲
52
2004-12-27
应用随机过程讲义 第三讲
53
2004-12-27
应用随机过程讲义 第三讲
54
2004-12-27
应用随机过程讲义 第三讲
55
2004-12-27
应用随机过程讲义 第三讲
56
渐近平稳?
2004-12-27
应用随机过程讲义 第三讲
57
2004-12-27
应用随机过程讲义 第三讲
58
2004-12-27
应用随机过程讲义 第三讲
59
2004-12-27
应用随机过程讲义 第三讲
60
推论 有限不可约非周期 M.C.存在唯一的平稳分布,
2004-12-27
应用随机过程讲义 第三讲
61
在马氏链蒙特卡罗随机模型方法中的应用定义为要模拟服从给定分布的随机变量,用生成一个易于实现的不可约遍历链 作为随机样本,
使其平稳分布为 的方法，称为马氏链蒙特卡罗方法.
}0,{ ≥= nXX
n
π
蒙特卡罗方法的一个首要步骤是产生服从给定的概率分布函数的随机变量 (或称为随机样本 ),由概率论知识,熟知下面的结论,
π
2004-12-27
应用随机过程讲义 第三讲
62
引理生成随机变量 U,使其分布满足 U[0,1],记为 U~U[0,1],
F(x)是给定的一个分布函数,记为 F(x)的反函数,则 X=F
-1
(U)分布函数为 F(x).
)}1,0(,)(:sup{)(
1
∈<=
yyxFxyF
2004-12-27
应用随机过程讲义 第三讲
63
).(~).1(;,
)(
)(
)2(
];1,0[~),(~)1(
:,
),()(,0)(
,)(
:
xZYZ
YMg
Y
U
UUygY
Zx
xMgxMxg
x
π
π
π
π
则否则返回步骤取若抽取量由下列步骤生成随机变满足和常数的分布函数选取一个易于生成是给定的分布函数假设
=≤
≤>
命题
2004-12-27
应用随机过程讲义 第三讲
64
米特罗波利斯 (Metropolis)等人在 1953年最早给出了通过生成一马氏链实现从分布 中采样 (生成相关的样本 )这一重要基本思想,随后,
哈斯汀 (Hastings)将其推广到更一般的形式,
下面仅叙述状态空间 S为至多可数的情形,
π
2004-12-27
应用随机过程讲义 第三讲
65
.,}0,{
).1(,;),,(],1,0[~)2(
};
),()(
),()(
,1min{),(
,),().0,()1(
:
}0,{).(
),),,((
},),({
π
ρ
π
π
ρ
ππ
平稳分布为是不可约遍历马氏链则返回步骤否则舍去则令若抽取并计算抽取由给定由下列步骤生成为参照矩阵称概率转移矩阵件为任选的易于实现的条而为将要生成的概率分布记
≥=
=<
=
≥∈
≥=
∈=
∈=
nXX
Y
YXYXUUU
YXTx
XYTY
YX
YXTnSXX
nXX
SjijiT
Sii
n
nn
n
n
n
nnn
n
T
T
2004-12-27
应用随机过程讲义 第三讲
66
.)()},()(),,()(min{
}
),()(
),()(
,1min{),()(),(),()()(
).,()()(,
),)(,(),(
,:
ji
ij
jiij
ij
PjijTjjiTi
jiTi
ijTj
jiTijijiTiPi
SjiPjPi
SjijijiTP
X
πππ
π
π
πρππ
ππ
ρ
==
==
∈?=
∈=
事实上即性有对称转移概率矩阵起一步是不可约遍历马氏链易证证明梗概
.)),((
.)()(
,
的平稳分布是由上式即证得求和上式两边对
XSii
Pji
Sj
Sj
ji
∈=
=
∈
∑
∈
ππ
ππ
2004-12-27
应用随机过程讲义 第三讲
67
2004-12-27
应用随机过程讲义 第三讲
68
2004-12-27
应用随机过程讲义 第三讲
69
母函数
ePIgE
1
1
)(|)(
=
=
′
= αλτ
λ
2004-12-27
应用随机过程讲义 第三讲
70
2004-12-27
应用随机过程讲义 第三讲
71
2004-12-27
应用随机过程讲义 第三讲
72
2004-12-27
应用随机过程讲义 第三讲
73
2004-12-27
应用随机过程讲义 第三讲
74
例,简单随机游动
.
},24,1:min{
1,,0
,0,1,0)1(
,0)1(.,..},1,{
1
00
0
的分布求或
τ
τ?==≥=
≥+==
==+≥=?=
≥==≥
∑
=
nn
n
k
kn
n
nn
XXnn
nYXXX
YqpqYP
pYPdiinY
2004-12-27
应用随机过程讲义 第三讲
75
思路,将,缩成,吸收态
),4[]2,(
因为一旦质点到达 -2或 4,我们就不用考虑这之后的活动,
+∞∪∞
2004-12-27
应用随机过程讲义 第三讲
76
一步转移概率矩阵
100000
p0q
p0q
p0q
p0q
qp0
-1 0 1 2 3 -2(4)
-1
0
1
2
3
-2(4)
2004-12-27
应用随机过程讲义 第三讲
77
应用随机过程讲义 第三讲
1
第三讲
2004-12-27
应用随机过程讲义 第三讲
2
作业题
1,4,7,8,18,20(1,3),22
2004-12-27
应用随机过程讲义 第三讲
3
离散时间的Markov链预备知识：条件独立性
2004-12-27
应用随机过程讲义 第三讲
4
.,
)|()|()|(
,,,
条件独立关于称若设事件
BCA
BCPBAPBACP
CBA
=
∈
==
==
)|()|()|(
)|()|()|(
BCPABCPBACP
BAPCBAPBCAP
.,条件独立关于 BCA?
2004-12-27
应用随机过程讲义 第三讲
5
定义，背景与例指标集离散条件独立
2004-12-27
应用随机过程讲义 第三讲
6
已知现在，将来关于过去条件独立,
可推广到
)|(
),,,|(
1,10,
)|(
),,|(
11
110011
11
nnnn
nnnnnn
k
nnknkn
nnknkn
iXBXP
iXBXBXBXP
nknkSB
iXiXP
iXiXiXP
=∈=
=∈∈∈
+=?≤≤?
===
===
++
++
++
++
K
K
设状态子集
2004-12-27
应用随机过程讲义 第三讲
7
“过去,和,将来,都可以是状态子集 ;但,现在,
必须是特定状态,
2004-12-27
应用随机过程讲义 第三讲
8
2004-12-27
应用随机过程讲义 第三讲
9
2004-12-27
应用随机过程讲义 第三讲
10
即 n时刻的分布律
2004-12-27
应用随机过程讲义 第三讲
11
2004-12-27
应用随机过程讲义 第三讲
12
2004-12-27
应用随机过程讲义 第三讲
13
全概率公式的思想
2004-12-27
应用随机过程讲义 第三讲
14
2004-12-27
应用随机过程讲义 第三讲
15
简称 C-K方程
2004-12-27
应用随机过程讲义 第三讲
16
(由时齐性 )
2004-12-27
应用随机过程讲义 第三讲
17
2004-12-27
应用随机过程讲义 第三讲
18
2004-12-27
应用随机过程讲义 第三讲
19
失效后无法自然恢复
2004-12-27
应用随机过程讲义 第三讲
20
2004-12-27
应用随机过程讲义 第三讲
21
2004-12-27
应用随机过程讲义 第三讲
22
T
ij
是ω的函数,是随机变量.
},,1:inf{
0
iXjXnnT
nij
==≥=
2004-12-27
应用随机过程讲义 第三讲
23
.)(
,})(,,0:{
.1,
)(,0
1)|(
:
0
)0(
00
)0(
+∞=
===≥
≥=
≠=
====
ω
ω
ij
n
ij
ij
ii
T
jXiXnn
Tij
jiP
iXiXPP
则规定若时当约定
Φ
2004-12-27
应用随机过程讲义 第三讲
24
首达时间的条件分布
)|(
0
1
)(
iXTPff
ii
k
k
iiii
=∞<==
∑
∞
=
2004-12-27
应用随机过程讲义 第三讲
25
从 i出发,经过有限步,可以以概率 1返回,
2004-12-27
应用随机过程讲义 第三讲
26
2004-12-27
应用随机过程讲义 第三讲
27
在常返的前提下
2004-12-27
应用随机过程讲义 第三讲
28
2004-12-27
应用随机过程讲义 第三讲
29
2004-12-27
应用随机过程讲义 第三讲
30
2004-12-27
应用随机过程讲义 第三讲
31
从图上直观地看,状态 1带自环,一定是非周期的
2004-12-27
应用随机过程讲义 第三讲
32
2004-12-27
应用随机过程讲义 第三讲
33
事件的转化与分解体现,首达,的意义
这一步有何依据
2004-12-27
应用随机过程讲义 第三讲
34
},{}{},{
}.{},{
.}{
,)(},{
0
1
0
1
0
1
0
jXiXlTjXiX
lTjXiX
lT
jjXiX
n
l
ijn
l
ijn
l
ij
n
====∩==∴
=?==
=
==
∞
=
∞
=
∞
=
U
U
U
因此有必然会发生事件时即通过有限步到达发生事件
2004-12-27
应用随机过程讲义 第三讲
35
全概率公式
2004-12-27
应用随机过程讲义 第三讲
36
2004-12-27
应用随机过程讲义 第三讲
37
)( jX
n
I
=
2004-12-27
应用随机过程讲义 第三讲
38
递减事件序列
2004-12-27
应用随机过程讲义 第三讲
39
T
ij
=l表明在前 l步之内没有到达 j状态
S
m
(j)表示时刻 m之后到达状态 j的次数
2004-12-27
应用随机过程讲义 第三讲
40
2004-12-27
应用随机过程讲义 第三讲
41
2004-12-27
应用随机过程讲义 第三讲
42
2004-12-27
应用随机过程讲义 第三讲
43
以下命题等价
+∞==
+∞=
==+∞==
===
=
∑
∑
∞
=
∞
=
=
∞
=
)|)(()5(;)4(
.1)|)((),()()3(
1}}|{{)2(
11
01
1
)(
01(
1
0
iXiSE
P
iXiSPIiS
iXiXP
if
n
n
ii
nm
iXn
n
n
ii
m
ω
）
令；
为常返态）；（）
U
（
2004-12-27
应用随机过程讲义 第三讲
44
一维直线上的简单随机游动 (p,q)游动
p=q 常返链（所有状态均为常返态）
p≠q 非常返链
2004-12-27
应用随机过程讲义 第三讲
45
2004-12-27
应用随机过程讲义 第三讲
46
2004-12-27
应用随机过程讲义 第三讲
47
2004-12-27
应用随机过程讲义 第三讲
48
推论,
.0lim
,,
,,
)(
1
)(
1
)(
=?
+∞<∈?
+∞=→
∞→
∞
=
∞
=
∑
∑
n
ij
n
n
n
ij
n
n
ij
P
PSij
Pjij
则为非常返态若则且为常返态若
2004-12-27
应用随机过程讲义 第三讲
49
对解题很有帮助
2004-12-27
应用随机过程讲义 第三讲
50
2004-12-27
应用随机过程讲义 第三讲
51
2004-12-27
应用随机过程讲义 第三讲
52
2004-12-27
应用随机过程讲义 第三讲
53
2004-12-27
应用随机过程讲义 第三讲
54
2004-12-27
应用随机过程讲义 第三讲
55
2004-12-27
应用随机过程讲义 第三讲
56
渐近平稳?
2004-12-27
应用随机过程讲义 第三讲
57
2004-12-27
应用随机过程讲义 第三讲
58
2004-12-27
应用随机过程讲义 第三讲
59
2004-12-27
应用随机过程讲义 第三讲
60
推论 有限不可约非周期 M.C.存在唯一的平稳分布,
2004-12-27
应用随机过程讲义 第三讲
61
在马氏链蒙特卡罗随机模型方法中的应用定义为要模拟服从给定分布的随机变量,用生成一个易于实现的不可约遍历链 作为随机样本,
使其平稳分布为 的方法，称为马氏链蒙特卡罗方法.
}0,{ ≥= nXX
n
π
蒙特卡罗方法的一个首要步骤是产生服从给定的概率分布函数的随机变量 (或称为随机样本 ),由概率论知识,熟知下面的结论,
π
2004-12-27
应用随机过程讲义 第三讲
62
引理生成随机变量 U,使其分布满足 U[0,1],记为 U~U[0,1],
F(x)是给定的一个分布函数,记为 F(x)的反函数,则 X=F
-1
(U)分布函数为 F(x).
)}1,0(,)(:sup{)(
1
∈<=
yyxFxyF
2004-12-27
应用随机过程讲义 第三讲
63
).(~).1(;,
)(
)(
)2(
];1,0[~),(~)1(
:,
),()(,0)(
,)(
:
xZYZ
YMg
Y
U
UUygY
Zx
xMgxMxg
x
π
π
π
π
则否则返回步骤取若抽取量由下列步骤生成随机变满足和常数的分布函数选取一个易于生成是给定的分布函数假设
=≤
≤>
命题
2004-12-27
应用随机过程讲义 第三讲
64
米特罗波利斯 (Metropolis)等人在 1953年最早给出了通过生成一马氏链实现从分布 中采样 (生成相关的样本 )这一重要基本思想,随后,
哈斯汀 (Hastings)将其推广到更一般的形式,
下面仅叙述状态空间 S为至多可数的情形,
π
2004-12-27
应用随机过程讲义 第三讲
65
.,}0,{
).1(,;),,(],1,0[~)2(
};
),()(
),()(
,1min{),(
,),().0,()1(
:
}0,{).(
),),,((
},),({
π
ρ
π
π
ρ
ππ
平稳分布为是不可约遍历马氏链则返回步骤否则舍去则令若抽取并计算抽取由给定由下列步骤生成为参照矩阵称概率转移矩阵件为任选的易于实现的条而为将要生成的概率分布记
≥=
=<
=
≥∈
≥=
∈=
∈=
nXX
Y
YXYXUUU
YXTx
XYTY
YX
YXTnSXX
nXX
SjijiT
Sii
n
nn
n
n
n
nnn
n
T
T
2004-12-27
应用随机过程讲义 第三讲
66
.)()},()(),,()(min{
}
),()(
),()(
,1min{),()(),(),()()(
).,()()(,
),)(,(),(
,:
ji
ij
jiij
ij
PjijTjjiTi
jiTi
ijTj
jiTijijiTiPi
SjiPjPi
SjijijiTP
X
πππ
π
π
πρππ
ππ
ρ
==
==
∈?=
∈=
事实上即性有对称转移概率矩阵起一步是不可约遍历马氏链易证证明梗概
.)),((
.)()(
,
的平稳分布是由上式即证得求和上式两边对
XSii
Pji
Sj
Sj
ji
∈=
=
∈
∑
∈
ππ
ππ
2004-12-27
应用随机过程讲义 第三讲
67
2004-12-27
应用随机过程讲义 第三讲
68
2004-12-27
应用随机过程讲义 第三讲
69
母函数
ePIgE
1
1
)(|)(
=
=
′
= αλτ
λ
2004-12-27
应用随机过程讲义 第三讲
70
2004-12-27
应用随机过程讲义 第三讲
71
2004-12-27
应用随机过程讲义 第三讲
72
2004-12-27
应用随机过程讲义 第三讲
73
2004-12-27
应用随机过程讲义 第三讲
74
例,简单随机游动
.
},24,1:min{
1,,0
,0,1,0)1(
,0)1(.,..},1,{
1
00
0
的分布求或
τ
τ?==≥=
≥+==
==+≥=?=
≥==≥
∑
=
nn
n
k
kn
n
nn
XXnn
nYXXX
YqpqYP
pYPdiinY
2004-12-27
应用随机过程讲义 第三讲
75
思路,将,缩成,吸收态
),4[]2,(
因为一旦质点到达 -2或 4,我们就不用考虑这之后的活动,
+∞∪∞
2004-12-27
应用随机过程讲义 第三讲
76
一步转移概率矩阵
100000
p0q
p0q
p0q
p0q
qp0
-1 0 1 2 3 -2(4)
-1
0
1
2
3
-2(4)
2004-12-27
应用随机过程讲义 第三讲
77
