马尔科夫链例题61页PPT

状态转换矩阵：
1 0 0 1 − ������ 0 ������ 0 1 − ������ 0 0 0 1 − ������ 0 0 0
0 0 ������ 0 0
0 0 0 ������ 1
0
赌徒问题（续）
• ������ =
0 ������ 1 − ������ 0 0 1 − ������ 0 0 0 0 0 ������ 0 0 0 0 1 − ������ 0 0 ������ 0 1 阵������的元素������������������ 等于从状态������������ 出发到达稳定时经过������������ 的次数的期望值。 推论：马尔可夫过程中，从非稳定状态������������ 出发，到达稳定状态时的步数期望值 等于矩阵������的������行元素的和。
赌徒问题
• 一个赌徒，假设拿两元钱，一次赌一美元，赢的概率是������，输的概率是1 − ������，当赢够4元，或者全部输光就不赌了。 • 状态转换图：
1 − ������ 1 1 − ������ 1 ������ 2 ������ 3 ������ 1 − ������ 1 4 ������ =
������
������������
.此矩阵
������������������ = 1, ������ = 1,2, … , ������.
������=1
重新标记这些状态的序号，把对角线是1的元素调整到右下角，也就是变成 ������������×������ ������������× ������−������ ������������×������ → ������ ������−������ × ������ ������(������−������)×(������−������) 矩阵������ = ������ − ������������×������

3、转移概率
定义 i, j S, 称 P Xn1 j Xn i
的一步转移概率。
pij n 为n时刻
若i, j S, pij n pij ，即pij与n无关，称转移概率
具有平稳性.此时称{Xn,n≥0}为齐次（或时齐的）马尔 可夫链。记P=(pij)，称P为{Xn,n≥0}的一步转移概率矩阵.
0
j!
j 0,1, i
pi0公式略有不同，它是服务台由有i个顾客转为空闲的
概率，即第n个顾客来到时刻到第n+1个顾客来到时刻之
间系统服务完的顾客数≥i+1。

pi0 P X n1 0 X n i P(Yn i 1) P(Yn k) k i1
et (t)k dG t ,

0 P{Yn
j Tn1 x}dG x
( x) j exdG x, j 0,1, 2,
0 j!
因此， {Xn，n≥1}是马尔可夫链。其转移概率为
P0 j P( X n1 j X n 0) P(Yn j X n 0)
P(Yn
P( X n1 in1 X n in )
所以{Xn,n≥0}是马尔可夫链，且
pij P( X n1 j X n i) P( f i,Yn1 j) P( f i,Y1 j)
二、切普曼-柯尔莫哥洛夫方程
1，随机矩阵 定义：称矩阵A=(aij)S×S为随机矩阵，若aij ≥0，且
一步转移概率矩阵

0.5009
0.0458 0.2559 0.1388 0.2134
0.0466 0.0988 0.36584 0.14264

8
2-SAT问题
观察(Xi表示当前赋值Ai中，与满足的赋值S有相同值的变量 数) 对于非满足字句，这表示Ai与S在这个字句中至少有1个 变量值不一致，子句中有不多于两个的变量(2-SAT),所 以增加匹配的个数的概率至少为1/2,即
Pr( Xi + 1 = j + 1 | Xi = j ) ≥ 1 / 2
fi , j = ∑ r ( t )
(t )
i, j
= Pr( Xt = j; 若1 ≤ s ≤ t − 1, Xs ≠ j | X 0 = i )
(t ) i, j
首达时间hi,j:从状态i首次到状态j的期望时间hi,j
hi , j = ∑ t • r
t >0
20
马尔可夫链定义及表示
23
马尔可夫链定义及表示
h1,1 = ∑ t ⋅ r
t =1
∞
∞
(t ) 1,1
1 1 3 = 1× + 2 × = < ∞ 2 2 2
1 1 = 1× 0 + 2 × + ... + n × 2 2
24
h 2, 2 = ∑ t ⋅ r2(,t2)
t =1
n −1
=3<∞
所以,状态1,2是正常返的
7
2-SAT问题-分析
分析：为了讨论算法的迭代次数 n个变量,S表示n个变量的满足的赋值 Ai表示经第i步算法后的变量赋值 Xi表示当前赋值Ai中，与满足的赋值S有相同值 的变量数，当Xi =n时，算法以满足赋值结束。 如果算法找到了另外的满足赋值，可能在Xi 达n之前就结束。最糟糕的是到Xi =n算法停 止。
马尔可夫链定义及表示
定义6.2,6.3 强连通图:在有向图G中,如果对于每一对顶点vi,vj,从vi 到vj和vj到vi都存在一条路径，则称G是连通图 强连通分量:有向图的极大强连通子图(i到j有路径，，从 j到i也有路径)

(k 1, 2 ),在从 k 经时段 r 转移到状态 j”等事
件的和事件, 如下图所示:
k
j
i
o
n
2021/6/29
nm
郑州大学信息工程学院
nmr t
14
• C-K方程是指(n)在n时处于状态i的条件下经过m+r步转移与
n+m+r时到达状态j，可以先在n时从状态i出发，经过m步于 n+m时到达某种中间状态k，再在n+m时从状态k出发经过r 步转移于n+m+r时到达最终状态j，而中间状态k要取遍整个 状态空间。 • C-K方程也可以用矩阵形式表示：
夫链，它的一步转移矩阵为 ：
P
p00 p10
p01 p11
1 1
设=0.7， =0.4，则一步转移概率矩阵为
P
0.7 0.4
0.3 0.6
2021/6/29
郑州大学信息工程学院
18
则两步转移概率矩阵： 四步转移概率矩阵：
由此可知，今日有雨且第四日仍有雨的概率为：P00(4)=0.5749
2021/6/29
10
齐次马尔可夫链
• 定义：如果在马尔可夫链中 P{ξ(k 1) j/ξk i} pij
即从ｉ状态转移到ｊ状态的概率与ｋ无关，则称这类马尔可 夫链为齐次马尔可夫链。 • 设Ｐ代表一步转移概率pij所组成的矩阵，且状态空间Ｉ由 状态０，１，２，…所组成，则
一步转移概率矩 阵P中每个元素为 非负，每行之和 均为1。
是如何到达ｉ的完全无关。所以它是一个齐次马尔可夫链， 其状态空间为I: {…,-2,-1,0,1,2,…}, 而其一步转移概率 为：
2021/6/29
郑州大学信息工程学院

马尔可夫链的状态分类
周期、非周期 常返、非常返 正常返、零常返 遍历状态

20
设马尔可夫链的状态空间I={1,2,3,4,5,6,7,8,9}，状态间的概率转移图如下 图
8
9
2
7
1
3
6
5
4
21
假设{Xn,n≥0}是齐次马尔可夫链，其状态空间I={0,1,2,3, …}，转移概率 是pij，i,j∈I，初始分布为{pj,j ∈I}。 定义 如集合{n: n≥1,pii(n)>0}非空，则称该集合的最大公约数 d=d(i)=G.C.D{n:pii(n)>0}为状态i的周期。 如d>1就称i为周期的，如d=1就称i为非周期的。 如果i有周期D，则对一切非零的n≠0(mod(D))都有pii(n)=0。 但这也并不是说对任意n有pii(nd)>0。例如上图中状态1的d=2，但 pii(2)=0。 引理 如i的周期为d，则存在正整数M，对一切n≥M，有pii(nd)>0。
例题：无限制随机游动 设质点在数轴上移动，每次移动一格，向右移动的概率为p，向左移动 的概率为q=1-p，这种运动称为无限制随机游动。以Xn表示时刻n质点 所处的位置，则{Xn,n∈T}是一个齐次马尔可夫链，求一步和k步转移概 率。
例题：有吸收壁随机游动 甲、乙进行赌博，甲有a元，乙有b元，每赌一局输家给赢家1元，没有 和局，直到一人输光为止。设每一局甲赢的概率为p，输的概率为q=1-p， 求甲输光的概率。
设Xn为第n(n=1,2,…,97)个时段的计算机状态，可以认为它是一个齐次马 氏链. 求 (1)一步转移概率矩阵; (2)已知计算机在某一时段(15分钟)的状态为0，问在此条件下，从此 时段起，该计算机能连续正常工作45分钟(3个时段)的条件概率.

**0
(1+2+3)/3=2
*1*
(2+3)/2=2.5
*00
1/1=1
9
6.1 模式定理
定理6.1(模式定理) 设 P ( t) { v 1 ( t)v 2 , ( t) , ,v N ( t)} 表示SGA在第t代时的种群，SGA的杂交概率和 变异概率分别为 p c 和 p m，H为任一模式，M(H,t) 表示第t代种群 P ( t ) 中与H匹配个体的个数，则有 估计式
对v的每一位相互独立地进行变异，当且仅当变 异算子在H的 o(H ) 个确定位置上不对v进行变异 时，经变异算子后所得到的个体仍然属于H。因 为对v的某一位进行变异的概率为 pm , 所以对某 一位不进行变异的概率为 1 pm, 于是属于模式H 中个体v经变异后仍然属于模式H的概率为
16
(1pm)o(H)
n
那么有 0 pij 1且有 pij 1,i 1,2,,n
j1
22
6.2基于有限马尔可夫链的收敛性分析
设{xt:t0,1,2, }是一有限齐次马尔可夫链，对任 一时刻 t(t0,1 ,2),该马尔可夫链在时刻t的一维 分布定义为
p j(t) p { x t a j}j ,1 ,2 , ,n
一维分布可以表示为向量形式
(H)o(H)
l1
pm
17
6.1 模式定理
推论6.1 在SGA中，定义长度较短、低阶且适应 值大于种群平均适应值的模式H，在种群中的数 目呈指数增长。
证 设对任意 t t, 都有
f (H,t) C f (t)
其中C为一个常数。并设
KC1pcl( H 1)o(H )pm
18
6.1 模式定理

p12 p22 0 0
p13 p23 1 0
p14 p24 0 1
三、马氏链的例子
例2 (0-1传输系统或简单信号模型)
X0 1 X1 2 X2 Xn-1 Xn
…
n
…
如图所示，只传输数字0和1的串联系统中，设每一级的传真率为p， 误码率为q=1-p。并设一个单位时间传输一级，X0是第一级的输入，Xn
n
P P X i |X ik k 1 和 1 P{ X n j | X n 1 i} 确定. {kX i} 分布 条件概率 0 k P X 0 i0，X 1 i1， ，X k 2 ik 2 马氏性
P X k 1 ik 1 | X 0 i0， ，X k 2 ik 2 P X k ik |X k 1 ik 1
则称 { X n，n 0}为齐次马尔可夫链，称 pij 为从状态 i
转移到状态 j 的一步转移概率. 若马尔科夫链 { X n，n 0}的状态空间是有限集，则
称 { X n，n 0}为有限状态的马尔科夫链；
若马尔科夫链 { X n，n 0}的状态空间是可列集，则 称 { X n，n 0} 为可列状态的马尔科夫链.

P X 0 i0 P X 1 i1 | X 0 i0 P X k ik |X k 1 ik 1
二、转移概率
定义1 设 { X n，n 0}是马尔可夫链，记
Байду номын сангаас
pij (n) P{X n 1 j | X n i}
称 pij 为马尔可夫链 { X n，n 0} 在时刻 n 时的一步转 移概率。 当 i，n 固定时，一步转移概率 pij (n) 实质上就是 在 X n i 的条件下，随机变量 X n 1的条件分布律，所以 条件分布律满足：