x3:1/2 s3
相通
s4
x2:1/2 x3:1/2
x4:1 x5:1
s2 x2:1/2
非周期性的：对于 pii(k)＞0的所有k值， 其最大公约数为1。
x2:1/2 x1:1/4
过渡态
s1
s6
x6:1
x6:1/4
吸收态
x4:1/4
s5
周期性的：在常返态中, 有些状态仅当k能被某整
数d＞1整除时才有pii(k)＞16 0, 图中的周期为2；
0.3W1 0.7W1
0.2W2 0.8W2
W0 W1
W2
W0 W1 W2 1
W0 0.3571, W1 0.1429, W2 0.5
0/0.4
1/0.6
so
1/0.2
s1
0/0.3 1/0.7
s2
0/0.8
0.6 0.4 0 p(sj | si ) 0.3 0 0.7
0.2 0 0.8
21
1
1
W
W
21
23
W 1
1
3
W
W p i ij
W j
i
4 1
1W
W 43 1W
W 2
W
32
54
3
2 W
32
4W 54
W 4
W W W W 1
1
2
3
4
• 稳态分布概率
W1
3 35
,
W2
6 35
,
W3
6 35
,
W4
4 7
• 稳态后的符号概率分布
p(a1)
i
p(a1
|
si
)
p(si
)
1 2
3、吸收态：一个只能从自身返回到自身而不能到 达其他任何状态的状态；
4、常返态：经有限步后迟早要返回的状态； 5、周期性的：在常返态中，有些状态仅当k能被 某整数d＞1整除时才有pii(k)＞0； 6、非周期性的：对于pii(k)＞0的所有k值，其最大 公约数为1。
15
常返态：经有限 步后迟早要返回 的状态，
s1 s2 s3
s1 1/ 2 1/ 2 0
p(s
j
|
si
)
s2 s3 s4
0
1/ 4
0
0 3/4
0
1/ 3 0 1/ 5
(0)1/2
(1)1/2
s2 01
00 s1
(0)1/4
(0)1/3 (1)3/4
10 s3
(1)2/3
s4 0 2 / 3 0 4 / 5
11 (0)1/5 s4
(1)4/5
0：0.5 1：0.5
0：0.5 0：0.2
1：0.2
14
齐次马尔可夫链中的状态可以根据其性质进行
分类: 1、如状态si经若干步后总能到达状态sj，即存在k,
使pij(k)＞0，则称si可到达sj; 若两个状态相互可到达, 则称此二状态相通；
2、过渡态：一个状态经过若干步以后总能到达某 一其他状态，但不能从其他状态返回；
1：0.75
：
：
1 0.5 0 0.25
0：0.5
12
• 例3 设有一个二元二阶马尔科夫信源，其信源 符号集X={0,1}，信源输出符号的条件概率为
P(0|00)=p(1|11)=0.8, p(1|00)=0.2
p(0|01)=p(0|10)=p(1|01)=p(1|10)=0.5 求状态转移概率矩阵，画出状态转移图
4
马氏链的基本概念
• 一阶马尔可夫信源：
p(x1, x2, x3,xL ) p(x1) p(x2 | x1) p(xL1 | xL2 ) p(xL | xL1)
• 若把有限个字母记作一个状态S，则信源发出 某一字母的概率除与该字母有关外，只与该时 刻信源所处的状态有关。
• 信源将来的状态及其送出的字母将只与信源现 在的状态有关，而与信源过去的状态无关。
p(0|0)=0.25, p(0|1)=0.5, p(1|0)=0.75, p(1|1)=0.5 求状态转移概率，画出状态转移图。
q 2,m 1,qm 2 s1 0; s2 1 p(s1 | s1) 0.25, p(s1 | s2) 0.5; p(s2 | s1) 0.75, p(s2 | s2) 0.5
• pij(m)：基本转移概率（一步转移概率）
• 若pij(m)与m 的取值无关,则称为齐次马尔可夫链
pij= p{Sm+1=sj| Sm= si}= p{S2=sj| S1= si} • pij具有下列性质：
pij≥0
pij 1
j
7
• 若处信 状源 态处 就于 变某 了一,任状何态时s候i ,当信它源发处出于一什个么符状号态后完,全所 由前一时刻的状态和发出符号决定。
00 s3
01 s4
10 s5 11 s6
25
• 信源发完第2个符号后再发第3个及以后的符号。 • 从第3单位时间以后信源必处在s3 s4 s5 s6四种状态
之一。在i≥3后,信源的状发状态出态0转转、移1移变概化率可相相用同同，下图表示:
• 状态s1和s5功能是完全相同
• 状态s2和s6功能是完全相同
s5
• 可将二图合并成
10
(0)0.5
(0)0.3 s3
(0)0.4
00
• s0是过渡状态 • s3 s4 s5 s6组成一个不
可约闭集,并且具有 遍历性。
(1)0.7
s0
(0)0.4 (0)0.2
(1)0.6
(1)0.5 11
01
(1)0.6
s6 (1)0.8
s4
26
• 由题意,此马尔可夫信源的状态必然会进入这个 不可约闭集,所以我们计算信源熵时可以不考虑 过渡状态及过渡过程。
xL2 )
3
2.1.3 马尔可夫信源
• 马尔可夫信源
–一类相对简单的离散平稳有记忆信源 –该信源在某一时刻发出字母的概率除与该
字母有关外,只与此前发出的有限个字母有 关
• m阶马尔可夫信源：
– 信源输出某一符号的概率仅与以前的m个符 号有关，而与更前面的符号无关。
• 条件概率
p(xL | xL1,x1) p(xL | xL1,xLm )
解： q 2, m 2, qm 4
s1 00; s2 01; s3 10; s4 11
由于信源只可能发出0或者1，所以信源下一时刻只
可能转移到其中的两种状态之一。如目前所处状态
为00，那么下一时刻信源只可转移到00或者01。而不
会转到10或者11状态。
13
p(s1 | s1) p(s4 | s4) 0.8,
马尔可夫信源
• 遍历状态：
– 非周期的、常返的状态,如图中的状态s2和s3
• 闭集：
–状态空间中的某一子集中的任何一状态都不 能到达子集以外的任何状态
• 不可约的：
–闭集中除自身全体外再没有其他闭集
特殊结论
17
马尔可夫信源
• 一个不可约的、非周期的、状态有限的马尔可
夫链其k步转移概率pij(k)在k→∞时趋于一个和 初始状态无关的极限概率Wj，它是满足方程组
p(x2|x1)
x2
x1
0
1
0
0.3
0.4
1
0.7
0.6
再下一单位时间：输出随机变量X3与X2X1有依赖关系
p(x3|x1x2) x3
00
x1 x2 01 10
11
0 0.4 0.2 0.3 0.4
1 0.6 0.8 0.7 0.6
23
• 从第四单位时间开始，随机变量Xi只与前面二 个单位时间的随机变量Xi-2Xi-1有依赖关系:
第二章
信源与信息熵
1
信源分类
1、连续信源
{ 2、离散 离散无记忆信源
{ { 信源 离散有记忆信源
发出单个符号的无记忆信源 发出符号序列的无记忆信源 发出符号序列的有记忆信源
发出符号序列的马尔可夫信源
2
• 表述有记忆信源需在N维随机矢量的联合概率 分布中，引入条件概率分布来说明它们之间的 关联。
p(x1, x2 , x3, xL ) p(xL | xL1, x1) p(x1, x2 , xL1) p(xL | xL1, x1) p(xL1 | xL2 , x1) p(x1, x2 ,
• s1 = 00 s2 = 01 s3 = 10 s4 = 11 • 变换成对应的状态序列为
…s2 s3 s2 s4 s4 s3 s1…
6
马尔可夫信源
• 设信源在时刻m处于si状态,它在下一时刻(m+1)状 态转移到sj的转移概率为：
pij(m) = p{Sm+1=sj| Sm= si}=p{sj | si}
• 系中统 的在 任任 意一 一时 个刻状可态处,状于态状转态移空时间,转S移={概s率1,s2矩,…阵,sQ}
P
p(s j
|
si )
p11
p1Q
pQ1 pQQ
• 符号条件概率矩阵
p11 p1n
P
p( x j
|
si )
pQ1 pQn
区 别
8
马尔可夫信源
• 状态转移图
• 得稳态分布概率
p(s3 )
1 9
p(s4 )
2 9
p(s5 )
2 9
p(马尔可夫信源达到稳定后,符号0和符号1的
概率分布：
• 由 p(s3 ) 0.4 p(s3 ) 0.3 p(s5 )
Wj=p(sj) p(s4 ) 0.6 p(s3 ) 0.7 p(s5 ) p(s5 ) 0.2 p(s4 ) 0.4 p(s6 )