第3章
CHAPTER 3


离 散 信 源





3.1离散信源的数学模型
信源是产生消息和消息序列的源头，它可以是人、生物、机器或其他事物。信源发出的消息有语音、图像、文字等。信源发出的是消息而不是信息，这是因为信息看不见摸不着，只能通过消息来研究它，消息上带有信息。
离散信源的数学模型是

X
P=x1x2…xn
p(x1)p(x2)…p(xn)

其中，共有n个信源符号，

p(xi)≥0(i=1,2,…,n)且∑ni=1p(xi)=1

在信源中，我们不再称x1, x2, …, xn为事件，而称为符号。
离散信源的数学模型表明信源总共可以发出n个符号，一次(或每一时刻)只能发出这n个符号中的一个，发出的这个符号到底是这n个符号中的哪一个，这是随机的，但每个符号出现的概率已知。这样信源就能够源源不断地发出一个符号序列，这个符号序列记为xi1, xi2, xi3,…，即第1次(时刻1)发出的符号是xi1，第2次(时刻2)发出的符号是xi2，第3次(时刻3)发出的符号是xi3，…。在不引起混淆的情况下，序列xi1, xi2, xi3,…常常简记为x1x2x3…。
【例31】某信源只发出两个符号“0”和“1”，两个符号出现的概率相等，该信源的数学模型是

X
P=01
1212

这个信源在不断地按照相等的概率发出0和1两个符号，形成一个01序列。“001100010011001100110101”是其中一个可能的序列，其中有13个0、11个1。
“010101110001010001100100101111010110100110010001001011001110”也是一个可能的序列，其中有31个0、29个1。
【例32】老师在讲课时不断地发出一个一个的汉字，老师就是一个信源。该信源发出的符号包括所有的汉字，每个汉字按照一定的概率出现，所有的已经发出的汉字构成了信源序列。
3.2信源的分类
信源可以分为无记忆信源和有记忆信源。
3.2.1无记忆信源
如果信源将要发出的符号，与已经发出的符号序列中的任何一个符号都没有关系，或者说已经出现的符号序列对将要出现的符号没有影响，那么这个信源是无记忆信源。
“已经出现的符号序列对将要出现的符号没有影响”用数学的方式表达出来就是

p(xi|x1x2…xi－1)=p(xi)

即已经出现的符号序列对将要出现的这个符号出现的概率没有影响，其中，x1x2…xi-1是信源已经发出的符号序列，xi是将要出现的信源符号。






【例33】例31中的信源是一个无记忆信源。这是因为无论信源已经发出的符号是什么，它总是按照各为1/2的概率发出0或1中的一个。
3.2.2有记忆信源
无记忆信源相对比较简单，但在日常生活和工程实践中并不常见。通常情况下，已经出现的符号对将要出现的符号有影响，这种信源称为有记忆信源。实际问题中的信源往往是有记忆的。下面看两个例子。


图31有记忆信源


【例34】老师上课的例子中，老师是一个有记忆信源。这是因为汉语是有记忆的，如图31所示，出现第一个汉字“我”之后，“们”“要”“的”“把”“看”等汉字出现的概率上升，而“碗”“机”“水”“书”“框”等汉字出现的概率下降。即如果假设p(们)=0.01，p(碗)=0.01，则出现“我”之后，“们”和“碗”出现的概率有可能变为p(们|我)=0.05，p(碗|我)=0.001。

有记忆信源又可以分为有限记忆信源和无限记忆信源。如果信源将要发出的消息符号只与前面m个符号有关，与更前面的符号无关，即

p(xi|xi－1xi－2…xi－mxi－m－1…x1)=p(xi|xi－1xi－2…xi－m)

则该信源为有限记忆信源，即记忆长度有限，为m。
如果信源将要发出的消息符号与前面已经发出的所有符号都有关，即

p(xi|xi－1xi－2xi－3…)

则该信源为无限记忆信源，即记忆长度无限。
工程实践中遇到的有记忆信源一般都是有限记忆信源。
【例35】试判断图32中两个信源的记忆特性，是无记忆信源还是有记忆信源。


图32两个信源序列


无论哪一个信源序列，其中黑色格子和白色格子出现的概率都相等，即信源模型均为

X
P=黑白
1212

对于信源序列1，条件概率为

p(黑|黑)=p(黑|白)=p(黑)=12
p(白|黑)=p(白|白)=p(白)=12

这说明，无论前一个格子是黑色还是白色，下一个格子是黑色或者白色的概率均不发生变化，总是12，因此这是一个无记忆信源。
对于信源序列2，条件概率为

p(黑|黑)=15,p(黑|白)=45
p(白|黑)=45,p(白|白)=15

这说明，前一个格子的颜色对下一个格子的颜色有影响，由12变为15或者45，因此这是一个有记忆信源。
3.3离散无记忆信源
3.3.1离散无记忆信源及其熵

离散无记忆信源是最简单，也是最基本的一类信源。
【定义31】设信源X的符号集为{x1, x2, …, xn}，n为信源能发出的符号个数，每个符号发生的概率为p(xi), i=1,2,…,n，这些符号彼此互不相关，且有

X
P=x1x2…xn
p(x1)p(x2)…p(xn)
(31)

其中，

p(xi)≥0(i=1,2,…,n)且∑ni=1p(xi)=1

则称X为离散无记忆信源。
【定义32】信源X中消息符号xi的自信息量定义为

I(xi)=－logp(xi)(32)

【定义33】信源X的平均自信息量，即信源熵定义为

H(X)=－∑ni=1p(xi)logp(xi)(33)

信源中一个消息符号的自信息量表示该符号带有的信息量的多少，而信源熵是所有符号带有的信息量的平均值，因此信源熵表示的是平均每个信源符号带有的信息量的多少，所以信源熵的单位为比特/符号。
【例36】计算机中常见的信源是二元信源，二元信源可以描述为

X
P=01
p1－p0≤p≤1

则二元信源的熵为

H(X)=－plogp－(1－p)log(1－p)

可见，二元信源的熵是p的函数，函数图形如图33所示。


图33二元信源的熵


例31中描述的信源的熵为

H(X)=－12log12－12log12=1比特/符号

即在该信源中，平均每个信源符号上带有1比特的信息量。
再如： 
【例37】有一个三元信源

X
P=x1x2x3
121414

则该信源的熵为

H(X)=－∑3i=1p(xi)logp(xi)=－12log12－2×14log14=1.5比特/符号

【例38】请从信息论的角度说明，为什么玩扑克牌的时候需要先洗牌？
是否洗牌，得到的信源模型是不同的。假设不考虑大小王，且自己先摸对方后摸，摸到的第一张牌是A。
洗牌使得牌的分布是均匀的，则对方也摸到A的概率是351，摸到其他牌的概率各为451，则此时猜测对方的牌，所需的信息量是

H洗牌=－351log351－12×451log451=3.6968比特

如果不洗牌，则容易出现几张同样大小的牌连续出现的情况。此时自己摸到A之后，假设对方也摸到A的概率上升为3951，摸到其他牌的概率各为151，则此时猜测对方的牌，所需的信息量是

H不洗牌=－3951log3951－12×151log151=1.6306比特

3.6968＞1.6306，所以洗过牌之后，在摸牌环节猜测对方的牌将更加困难。
3.3.2离散无记忆信源的扩展信源及其熵
在3.3.1节中，我们给出的信源模型是X
P=x1x2…xn
p(x1)p(x2)…p(xn)，这其实是在一个符号一个符号地研究信源，但有时这样不能满足实际应用的需要，例如，汉语中更多地考察的是句子，而不是汉字； 英语中更多地考察的是单词，而不是字母； 图像中更多地考察的是整幅图像，而不是单个像素。因此有必要研究N次扩展信源。
【例39】N次扩展信源的例子。
(1) 二进制信源： X={00,01,10,11}，则N=2
(2) 汉语： X={我们在上课，张三睡着了，…}，则N=5
(3) 英语： X={the, car, ear, she, you, …}，则N=3
为了给出N次扩展信源的数学定义，先来看看离散无记忆二进制信源X
P=01
p1－p的二次扩展信源和三次扩展信源。
1. 二次扩展信源
X的二次扩展信源记作X2，其中包含4个长度为2的序列{00, 01, 10, 11}，这4个序列分别记为a1, a2, a3, a4。由于原始信源X是无记忆的，因此每个序列出现的概率为序列中两个符号出现概率的乘积，因此二次扩展信源为

X2
P=a1a2a3a4
p(a1)p(a2)p(a3)p(a4)=00011011
p2p(1－p)p(1－p)(1－p)2

其中ai是原信源X的一个长度为2的序列，又是二次扩展信源X2的一个信源符号。
2. 三次扩展信源
X的三次扩展信源记作X3，其中包含8个长度为3的序列{000, 001, 010, …, 111}，这8个序列分别记为a1, a2, …, a8，每个序列出现的概率为序列中三个符号出现概率的乘积，因此三次扩展信源为

X3
P=a1a2…a8
p(a1)p(a2)…p(a8)=000001…111
p3p2(1－p)…(1－p)3

其中ai是原信源X的一个长度为3的序列，又是三次扩展信源X3的一个信源符号。
3. N次扩展信源
看过前面的例子，更容易理解N次扩展信源的概念。
【定义34】离散无记忆信源X
P=x1x2…xn
p(x1)p(x2)…p(xn)的N次扩展信源XN包含全部nN个长度为N的序列，每一个序列出现的概率为序列中各个符号出现的概率的乘积，即

XN
P=a1a2…anN
p(a1)p(a2)…p(anN)(34)

其中，

XN=X×X×…×X，ai=xi1xi2…xiN

p(ai)=∏Nk=1p(xik)=∏Nk=1pik

【定理31】离散无记忆信源X的N次扩展信源XN的熵等于信源X的熵的N倍，即

H(XN)=NH(X)(35)

证明： 


H(XN)=－∑XNp(ai)logp(ai)=－∑XNp(ai)log∏Nk=1pik=－∑XNp(ai)∑Nk=1logpik

=－∑Nk=1∑XNp(ai)logpik=－∑Nk=1∑XNpi1…pik…piNlogpik

=－∑Nk=1∑XNpi1…(piklogpik)…piN=－∑Nk=1∑nik=1piklogpik∑ni1=1pi1…∑niN=1piN

=－∑Nk=1∑nik=1piklogpik=∑Nk=1－∑nik=1piklogpik=∑Nk=1H(X)=NH(X)


这说明扩展信源中平均一个符号(即长度为N的序列)上带有的信息量是原信源中平均一个符号上带有的信息量的N倍。
【例310】接例37，求X
P=x1x2x3
121414的二次扩展信源的熵。
方法一： 二次扩展信源为

X2
P=x1x1x1x2x1x3x2x1x2x2x2x3x3x1x3x2x3x3
1418181811611618116116

则

H(X2)=14log4+18log8+…+116log16=3比特/符号

方法二： 利用定理31

H(X2)=2H(X)=2×1.5=3比特/符号

可见，两种方法求出的熵是相等的。
3.4马尔可夫信源(有限记忆信源)
3.4.1马尔可夫信源的定义

在3.2.2节中我们说过，工程实践中遇到的有记忆信源基本上都属于有限记忆信源，这种信源有一个名字，称为马尔可夫信源。

【定义35】在信源X中，如果将要出现的符号仅与刚刚出现的m个符号有关，与更早出现的符号无关，则称X为m阶马尔可夫信源，即

p(xi|xi－1xi－2…xi－m…x1)=p(xi|xi－1xi－2…xi－m)(36)

【例311】信源X={0, 1, 2, 3}，信源将要发出的符号是前面两个符号的和对4的余数，即

xi≡(xi－1+xi－2)mod 4

显然这是一个2阶马尔可夫信源，因为将要出现的符号只与前面的两个符号有关。


p(xi|xi－1xi－2)=1,(xi≡(xi－1+xi－2)mod 4)
p(xi|xi－1xi－2)=0,其他



图34马尔可夫信源


如图34所示，假设时刻i信源已经发出的两个符号是1、2，则时刻i或者说第i次发出的符号是

(1+2)mod 4≡3


时刻i+1发出的符号与1已经无关，只与2和3有关，时刻i+1发出的符号是

(2+3)mod 4≡1

以此类推，信源发出序列是…12310112…。
在例311中，每一个将要发出的符号只与前面的两个符号相关，将这两个符号连在一起，看成一个整体，我们把它称为“状态”。时刻i发出的符号与状态“12”有关，发出符号3之后，状态变为“23”，时刻i+1发出的符号与该状态“23”有关，……。
“状态”是马尔可夫信源中的一个重要概念，m阶马尔可夫信源的状态由m个信源符号构成。如果信源有n个符号，则m阶马尔可夫信源共有nm种状态。假设当前所处的状态为Sk=xi-1xi-2…xi-m，则发出符号xi之后，状态变为Sl=xixi-1…xi-m+1。因此，式(36)所定义的马尔可夫信源中符号对符号序列的依赖关系就变为状态对状态的依赖关系，即


p(xi|xi－1xi－2…xi－m+1xi－m)=p(xixi－1…xi－m+1|xi－1xi－2…xi－m+1xi－m)

=p(Sl|Sk)(37)


3.4.2有限状态马尔可夫链
马尔可夫链并不是信源，它体现的是一种状态和状态之间的“一环扣一环”的性质，因此称为“链”。之所以要在介绍信源的时候介绍马尔可夫链，是因为马尔可夫信源是具有马尔可夫链性质的信源，这点将在3.4.3节中讲解。
【定义36】一个状态序列： S1, S2, …, Sl, …，若满足以下条件： 
(1) 有限性： 可能的状态数目J＜∞，即只有有限个可能的状态； 
(2) 马氏性： 系统将要达到的状态，只与当前的状态有关，与更早的状态无关，即

p(Sl|Sl－1Sl－2…S1)=p(Sl|Sl－1)(38)

则称此随机状态序列为有限状态马尔可夫链。
由式(38)能够看出马尔可夫链中将要出现的状态只与它前面的一个状态有关系，体现了状态和状态之间的“一环扣一环”的性质。
描述马尔可夫链的数学工具是状态转移矩阵和状态转移图。已知系统当前处于状态Sk，则系统将要到达的状态为Sl的概率为

pkl=p(Sl|Sk)

由于所有可能的状态有J个，因此这样的概率共有J×J个，所有这些概率组成一个矩阵

P=p11p12…p1J
p21p22…p2J
︙︙︙
pJ1pJ2…pJJ(39)


由于pkl表示由状态Sk转移为状态Sl的概率，因此矩阵P称为状态转移矩阵。
状态转移矩阵中每一行元素的和均为1，这是因为第i行元素的和为

∑Jj=1pij=∑Jj=1p(Sj|Si)=p(S1,S2,…,SJ|Si)=1

它的含义是，当前状态Sk必然转移为所有可能状态{S1, S2, …, SJ}中的一个。
概率pkl还可以用图形化的方式表示，如图35所示，该图称为状态转移图，表示由状态Sk转移为状态Sl的概率是pkl。

状态转移矩阵P中所有元素都可以表示为图35的样子，所有状态之间的转移关系连在一起，构成了整个系统的状态转移图。
【例312】一个系统有2个状态{S1, S2}，状态转移矩阵为

P=0.250.75
0.50.5


则状态转移图（见图36）为


图35状态转移图




图36例312的状态转移图



可见状态转移矩阵和状态转移图之间有一一对应的关系，根据状态转移矩阵可以画出状态转移图，根据状态转移图也能写出状态转移矩阵。
3.4.3马尔可夫信源的马尔可夫链性质
在式(37)中，已经将m阶马尔可夫信源中1个符号对m个符号的依赖关系转换为状态和状态之间的“一环扣一环”的关系，因此马尔可夫信源是具有马尔可夫链性质的信源，这样就能用描述马尔可夫链的工具——状态转移矩阵和状态转移图，来描述马尔可夫信源，而且还可以从另一个角度来定义马尔可夫信源。
【定义37】若信源输出的符号和状态满足下列条件，则称此信源为m阶马尔可夫信源。
(1) 某一时刻，将要出现的信源符号只与当时信源所处的状态有关，与以前的状态无关，即

p(xi|xi－1xi－2…xi－m)=p(xi|Sk)(310)

(2) 信源的状态只由当前输出符号和前一时刻信源的状态唯一确定，即

p(Sl|xi,Sk)=0，Sl≠xixi－1…xi－m+1
1，Sl=xixi－1…xi－m+1(311)

该定义与定义35是一致的，只不过用了另外一种描述方法。
【例313】接例311，因为2阶马尔可夫信源X={0, 1, 2, 3}有4个符号，因此该信源共有

nm=42=16

个状态，其状态转移矩阵为
00010203101112132021222330313233

P=00
01
02
03
10
11
12
13
20
21
22
23
30
31
32
33

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1


状态转移图（见图37）为


图37例313的状态转移图


3.4.4马尔可夫信源的熵
1. 平稳马尔可夫信源

有的时候，马尔可夫信源输出的状态序列与系统的初始状态有关系，这点可以从下面的例314看出。
【例314】接例313，从表31能够看出，信源的初始状态不同，产生的状态序列是不一样的，这直接导致状态分布和信源分布发生变化，从而使得信源熵发生变化。


表31初始状态对信源熵的影响



初始
状态状态
序列状 态 分 布符号
序列信 源 分 布信源熵
(比特/符号)
0000S
P=00其他
10
0000000X
P=0123
1000
H(X)=0
0202 22 20S
P=02/22/20其他
130
022022

022…
X
P=0123
130230
H(X)=0.9183
1010 01 11
12 23 31
S
P=10/01/11
/12/23/31其他
160
101123
101123…
X
P=0123
16121616
H(X)=1.7925
30
30 03 33
32 21 13
S
P=30/03/33
/32/21/13其他
160
303321

303321…
X
P=0123
16161612
H(X)=1.7925

这个例子说明，当信源输出的状态序列受初始状态影响的时候，无法给出信源熵的一个确定的值。因此本课程中，我们只研究状态序列不受初始状态影响的情况。这种马尔可夫信源称为平稳马尔可夫信源。
平稳马尔可夫信源的含义包括两点： 
(1) 经过足够长的时间之后，信源的nm个状态出现的概率逐渐稳定下来，不再发生变化。
(2) 状态的稳定分布与初始状态无关，即无论信源一开始处在什么状态，最终都将达到同样的稳定分布。
为了求得平稳马尔可夫信源的熵，首先要判断一个马尔可夫信源是否平稳。我们不加证明给出如下定理。
【定理32】遍历的马尔可夫信源是平稳马尔可夫信源。
所谓遍历的马尔可夫信源指的是状态转移图中各个状态是互相可达的，即从任何一个状态出发都可以到达其他任何状态，即能将所有状态遍历一遍。像图37所示的信源就不是遍历的，因为有些状态之间不连通。
在3.4.2节介绍马尔可夫链的时候说过，状态转移图和状态转移矩阵是等价的，我们已经知道了如何根据状态转移图判断信源是否为遍历的马尔可夫信源，那如何从状态转移矩阵的角度判断信源是否为遍历的马尔可夫信源呢？这需要将状态转移矩阵做进一步的划分。
式(39)描述的状态转移矩阵表示一个状态经过1步转移到另外一个状态的矩阵，即转移1次的概率，因此称为一步转移矩阵。如果要描述一个状态经过多次转移，转移到另外一个状态的概率，则需要多步转移矩阵P(r)，

P(r)=p(r)ij,i,j=1,2,…,nm(312)


其中，p(r)ij表示从状态Si经过r次转移，转移到状态Sj的概率。
多步转移矩阵之间存在下述切普曼柯尔莫格洛夫方程

P(r+t)=P(r)P(t)(r,t≥1)(313)


从式(313)不难得到如下结论

P(r)=Pr(314)


即r步转移矩阵等于一步转移矩阵的r次方。
有了多步转移矩阵的概念，可以从状态转移矩阵的角度给出遍历的马尔可夫信源，或者说平稳马尔可夫信源的判定定理。
【定理33】设P为马尔可夫信源的一步状态转移矩阵，该信源为平稳马尔可夫信源的充要条件是存在一个正整数N，使矩阵PN中的所有元素均大于0。
定理33中，PN的含义是最多经过N步，“所有元素均大于0”的含义是各个状态是互相可达的。因此定理33与定理32本质上是一致的，区别在于定理33是从状态转移矩阵角度给出结论，定理32是从状态转移图角度给出结论。通常一步转移矩阵简称为转移矩阵。
【例315】设有一个二进制二阶马尔可夫信源，其信源符号集为{0, 1}，条件概率为


p(0 | 00)=p(1 | 11)=0.8

p(1 | 00)=p(0 | 11)=0.2

p(0 | 01)=p(0 | 10)=p(1 | 01)=p(1 | 10)=0.5


试判断这个信源是否为平稳马尔可夫信源。
解： 这是一个二进制二阶马尔可夫信源，因此共有nm=22=4个状态： 00、01、10、11。状态转移概率为

p(00 | 00)=p(0 | 00)=0.8p(10 | 01)=p(0 | 01)=0.5

p(01 | 00)=p(1 | 00)=0.2p(11 | 01)=p(1 | 01)=0.5

p(00 | 10)=p(0 | 10)=0.5p(10 | 11)=p(0 | 11)=0.2

p(01 | 10)=p(1 | 10)=0.5p(11 | 11)=p(1 | 11)=0.8

其余的为0。因此状态转移矩阵为

P=0.80.200
000.50.5
0.50.500
000.20.8


存在正整数N=2，使矩阵PN中的所有元素均大于0，

P2=0.640.160.10.1
0.250.250.10.4
0.40.10.250.25
0.10.10.160.64


因此该信源为平稳马尔可夫信源。


图38例315的状态转移图


从状态转移图，可以得到同样的结论。从图38能够看出，从4个状态中的任何一个出发，最多经过2步，都能够到达其他任何一个状态，即能够遍历所有状态，因此该信源为平稳马尔可夫信源。

2. 平稳马尔可夫信源的熵
平稳马尔可夫信源中nm个状态出现的概率能够逐渐稳定下来，不再发生变化。设达到稳定分布之后，各个状态的概率为p(S1),p(S2),…,p(Snm)，那马尔可夫信源的熵是－∑nmi=1p(Si)logp(Si)吗？当然不是。
这是因为信源的熵指的是信源符号带有的信息量的平均值，而不是状态带有的信息量的平均值。如何求得信源符号带有的信息量的平均值呢？是否像离散无记忆信源那样，求出所有符号出现的概率，套入熵的公式就可以了呢？也不是。
这是因为对马尔可夫信源这样的有记忆信源，信源符号出现的概率与已经出现的符号有关。因此m阶平稳马尔可夫信源的熵是在知道了已经出现的m个符号的条件下，信源符号带有的信息量的平均值，换句话说，平稳马尔可夫信源的熵实际上是一个条件熵。

Hm+1(X)=H(Xm+1|X1X2…Xm)(315)

将该条件熵记作Hm+1(X)，其中X, X1, …, Xm, Xm+1均来自于集合X。
根据条件熵的定义和马尔可夫信源中对状态的定义，有

Hm+1(X)=H(X|X1X2…Xm)

=H(X|S)
=－∑Sj∑ip(xi,Sj)logp(xi|Sj)

=－∑Sj∑ip(Sj)p(xi|Sj)logp(xi|Sj)(316)



在式(316)中，p(xi| Sj)是用来描述马尔可夫信源的转移概率，是必然要给出的。这样在式(316)中，只有p(Sj)是未知量。下面给出求得各个p(Sj)的方法。
因为p(Sj)表示的是平稳之后各个状态出现的概率，因此马尔可夫信源再输出一个信源符号之后，即状态转移一次之后，p(Sj)是不变的。假设S=［p(S1)p(S2)…p(Snm)］，因此有

SP=S(317)

其中P是状态转移矩阵。而且有

p(S1)+p(S2)+…+p(Snm)=1(318)

根据式(317)和式(318)可以求得各个p(Sj)。
【例316】接例315。试求该平稳马尔可夫信源的熵。
解： 设S=［p(00)p(01)p(10)p(11)］，有

SP=S0.80.200
000.50.5
0.50.500
000.20.8=S

p(00)+p(01)+p(10)+p(11)=1


求得p(00)=p(11)=514,p(01)=p(10)=17，因此信源熵

Hm+1(X)=－∑Sj∑ip(Sj)p(xi|Sj)logp(xi|Sj)

=－2514(0.8log0.8+0.2log0.2)+17(0.5log0.5+0.5log0.5)

=0.8014比特/符号


总结求马尔可夫信源熵的过程，分为三个步骤： 
(1) 判断是否为平稳马尔可夫信源。
(2) 对平稳马尔可夫信源，求出状态的平稳分布。
(3) 根据式(316)求得马尔可夫信源的熵。
求平稳马尔可夫信源的熵，有很多应用领域，下面给出两个例子。
【例317】俄裔美国经济学家列昂惕夫提出了“投入产出”模型，并因此获得了1973年诺贝尔经济学奖。假设一个经济体系由煤炭、电力和钢铁三个部门组成，各部门之间的分配如表32所示。


表32一个简单的“投入产出”模型



产 出 部 门
采 购 部 门
煤炭电力钢铁

煤炭0.0
0.6
0.4
电力
0.4
0.1
0.5
钢铁
0.6
0.2
0.2

比如表中的第2行，它的意思是电力部门的总产出有40%用来购买煤炭、10%用来满足自己的用电需求、50%用来购买钢铁。因为所有的产出都分配出去了，所以每一行的百分比之和为1。求出平衡价格，使每个部门的收支平衡。
答： 这是一个马尔可夫链，其状态转移矩阵为

P=0.00.60.4
0.40.10.5
0.60.20.2


则P2中每一个元素均大于0，这是一个平稳马尔可夫链。
设pC、pE、pS分别表示煤炭、电力和钢铁部门的平衡价格，S=［pCpEpS］，则

SP=S

解得

S=［0.94pS0.85pSpS］


这意味着，如果钢铁部门的平衡价格是1亿元(pS=1亿元)，则煤炭部门的平衡价格是9400万元，电力部门的平衡价格是8500万元。再进一步，如果煤炭部门生产1.88万吨煤，则每吨的价格应该是5000元； 如果电力部门生产1.7亿度电，则每度电的价格应该是0.5元。这就是国民生产中，确定每种商品单价的一个基本原则。
【例318】通常一次网络攻击包括信息收集、权限获取、实施攻击、扩大影响、消除痕迹5个步骤。信息收集阶段利用主机扫描、操作系统探测程序等方法收集IP地址、操作系统版本、用户标识等信息。权限获取阶段利用系统漏洞或者特洛伊木马等方法获取目标系统的读、写、执行等权限。实施攻击包括窃取信息、破坏系统、安装后门等。扩大影响是以目标系统为“跳板”，对目标所属网络的其他主机进行攻击。消除攻击痕迹是为了防止被识别、追踪。


图39攻击步骤的状态转移图


该过程并不绝对，不同的网络攻击会呈现出不同的形式。有的攻击收集完信息之后直接消除痕迹退出，有的不需要扩大影响……。但是，从统计角度来看，这5个步骤仍然有一定规律，可以用转移矩阵来描述。假设某类攻击的转移矩阵为

P=00.5000.5
000.50.50
0000.50.5
0.50000.5
000.50.50


矩阵第一行说明这类攻击在执行完信息收集阶段后，有0.5的概率进入权限获取阶段，有0.5的概率进入扩大影响阶段。攻击的转移矩阵可以作为特征来用，不同的攻击，其转移矩阵是不一样的。有时可以根据转移矩阵的不同，区分不同的攻击。
对上述转移矩阵为P的攻击而言，试计算为了确定攻击所处的步骤，所需要的信息量。
答： 可以将该类攻击看作一个一阶马尔可夫信源，状态转移图如图39所示。

因此这是一个平稳信源。假设各个步骤出现的概率为S=［p(S1)p(S2)…p(S5)］，由SP=S，以及p(S1)+p(S2)+…+p(S5)=1，得S=［0.14290.07140.19050.28570.3095］。因此信源熵


Hm+1(X)=－∑Sj∑ip(Sj)p(xi|Sj)logp(xi|Sj)

=0.1429+0.0714+0.1905+0.2857+0.3095=1比特/步骤


也就是说，为了确定攻击所处的步骤，需要1比特的信息量。这与P所表示的攻击矩阵完全相符： 知道当前步骤之后，下次只可能出现两个步骤之一，且两个步骤出现的概率各为0.5。
3. 极限熵
上一节指出，马尔可夫信源的熵是条件熵Hm+1(X)，这种思想可以扩展到所有平稳有记忆信源，无论是有限记忆的还是无限记忆的。对无限记忆信源，记忆长度无限，此时的熵称为极限熵

H∞(X)=limm→∞Hm+1(X)=limm→∞H(X|X1X2…Xm)(319)

其中的“m→∞”体现了无限记忆信源记忆长度无限的特点。
实际上，无记忆信源的熵H(X)和马尔可夫信源(有限记忆信源)的熵Hm+1(X)都可以看成极限熵H∞(X)的特殊情况。多数情况下，马尔可夫信源的熵Hm+1(X)一般也写为H∞(X)，即式(316)多数情况下写为

H∞(X)=－∑Sj∑ip(Sj)p(xi|Sj)logp(xi|Sj)(320)

此时极限熵H∞(X)表示平稳马尔可夫信源的熵。
极限熵又称为实际熵，这与极限熵的含义有很大的关系。从极限熵的式(319)可以看出，无论信源是无记忆的、有限记忆的、还是无限记忆的，极限熵都可以理解为在已知信源已经输出的所有符号的条件下，再输出一个符号能够获得的信息量，这与信源的实际输出过程是一致的，我们就是在已经知道前面的符号条件下才知道当前符号，因此极限熵又称为实际熵，即当前符号实际上能够带给我们的信息量。
3.5离散平稳信源
3.5.1平稳信源的概念

在讲马尔可夫信源的时候提到了“平稳”的概念，但是平稳不是马尔可夫信源特有的性质。信源除了可以从记忆的角度分为无记忆信源和有记忆信源之外，还可以从平稳的角度分为平稳信源和非平稳信源。
【定义38】如果信源输出各个符号的概率与时间无关，即

P(Xi=x)=P(Xj=x)=p(x)(321)

则称此信源为一维平稳信源。
【定义39】如果信源输出长度为N的符号序列的概率与时间无关，即


P(Xi1=x1,Xi2=x2,…,XiN=xN)

=P(Xj1=x1,Xj2=x2,…,XjN=xN)(322)


则称此信源为N维平稳信源。
能够看出，一维平稳信源包含在N维平稳信源中。平稳信源的实质是无论i时刻还是j时刻，信源输出同一个信源符号或者符号序列的概率相同，即信源输出信源符号或者符号序列的概率不随时间发生变化。
回忆3.3节介绍的离散无记忆信源及其N次扩展信源，实际上都是平稳的，因为各个符号或者序列出现的概率均不随时间发生变化。平稳马尔可夫信源也是平稳信源，因为各个状态(即符号序列)出现的概率也会稳定下来，不随时间发生变化。
3.5.2平稳信源的熵
熵可以分为熵、条件熵、共熵等多种形式，同样，对平稳信源，也有多种度量信息量的方法。
【定义310】平稳信源输出的长度为N的符号序列的联合熵为

H(X1X2…XN)=－∑X1X2…XNp(x1x2…xN)logp(x1x2…xN)(323)

【定义311】长度为N的信源符号序列中平均每个符号所携带的信息量为平均符号熵，即

HN(X)=1NH(X1X2…XN)(324)

HN(X)的含义是这样理解的： H(X1X2…XN)表示平均每个长度为N的序列所携带的信息量，除以N之后就是序列中平均每个符号所携带的信息量。
在介绍马尔可夫信源的时候我们定义过Hm+1(X)=H(Xm+1|X1X2…Xm)，即HN(X)=H(XN|X1X2…XN－1)，现在又定义HN(X)=1NH(X1X2…XN)，这样定义有问题吗？后面将会证明，这两个定义从极限熵的角度是等价的。
【定义312】设信源记忆长度为N-1，若已知前面N-1个符号，则第N个符号所携带的平均信息量为条件熵，即

H(XN|X1…XN－1)=－∑X1X2…XNp(x1x2…xN)logp(xN|x1x2…xN－1)(325)

对于离散平稳信源，当H1(X)=H(X)＜∞时，具有以下性质： 
性质1
条件熵H(XN| X1X2…XN-1)随N的增加是非递增的，即

H(X1)≥H(X2|X1)≥H(X3|X1X2)≥…
≥H(XN－1|X1X2…XN－2)≥H(XN|X1X2…XN－1)(326)

证明： 第2章中已经给出条件熵和熵之间的关系H(X|Y)≤H(X)，该关系表明对于任意的X和Y，在已知Y的条件下关于X的平均不确定性不会超过X本身的不确定性，因此当N=2，即平稳信源输出二维随机矢量(X1, X2)时，有

H(X2)≥H(X2|X1)

由于X1, X2∈X且具有相同的概率分布，则

H(X1)=H(X2)=H(X)

因此

H(X1)≥H(X2|X1)

当N≥3，即平稳信源输出N维随机矢量(X1, X2, …, XN)时，考察

H(XN|X1X2…XN－1)－H(XN－1|X1X2…XN－2)

=－∑X1…XN－1XNp(x1x2…xN－1xN)logp(xN|x1x2…xN－2xN－1)

+∑X1…XN－2XN－1p(x1x2…xN－2xN－1)logp(xN－1|x1x2…xN－2)

由于离散平稳信源的联合概率分布和条件概率分布与时间无关，有

∑X1…XN－2XN－1p(x1x2…xN－2xN－1)logp(xN－1|x1x2…xN－2)
=∑X2…XN－1XNp(x2…xN－1xN)logp(xN|x2x3…xN－1)
=∑X1…XN－1XNp(x1x2…xN－1xN)logp(xN|x1x2…xN－2)

因此

H(XN|X1X2…XN－1)－H(XN－1|X1X2…XN－2)
=∑X1…XN－1XNp(x1x2…xN－1xN)logp(xN|x2…xN－1)p(xN|x1x2…xN－1)×p(x1x2…xN－1)p(x1x2…xN－1)
=∑X1…XN－1XNp(x1x2…xN－1xN)logp(xN|x2…xN－1)×p(x1x2…xN－1)p(x1x2…xN－1xN)

已知对数函数是上凸函数，于是

H(XN|X1X2…XN－1)－H(XN－1|X1X2…XN－2)

≤log∑X1…XNp(x1x2…xN－1xN)p(xN|x2…xN－1)×p(x1x2…xN－1)p(x1x2…xN－1xN)
=log∑X1…XNp(xN|x2…xN－1)×p(x1x2…xN－1)

=log∑X1…XN－1p(x1x2…xN－1)∑XNp(xN|x2…xN－1)

=log∑X1…XN－1p(x1x2…xN－1)=log1=0

因此有

H(XN|X1X2…XN－1)≤H(XN－1|X1X2…XN－2)

性质1的含义是： 我们知道的条件越多，越容易判断事件的结果，即该事件包含的信息量越少。这与我们的生活经验是一致的。
性质2

HN(X)≥H(XN|X1X2…XN－1)(327)

证明： 由平均符号熵的定义知

NHN(X)=H(X1X2…XN)=－∑X1…XNp(x1…xN)logp(x1…xN)

因为

p(x1…xN)=p(x1)p(x2|x1)p(x3|x1x2)…p(xN|x1x2…xN－1)

所以


NHN(X)=-∑X1…XNp(x1…xN)logp(x1)+∑X1…XNp(x1…xN)logp(x2|x1)+…

+∑X1…XNp(x1…xN)logp(xN|x1x2…xN－1)

其中


∑X1…XNp(x1…xN)logp(x1)=∑X1∑X2…XNp(x1…xN)logp(x1)

=∑X1p(x1)logp(x1)=－H(X1)

∑X1…XNp(x1…xN)logp(x2|x1)=∑X1X2∑X3…XNp(x1…xN)logp(x2|x1)

=∑X1X2p(x1x2)logp(x2|x1)

=－H(X2|X1)


∑X1…XNp(x1…xN)logp(xN|x1x2…xN－1)=－H(XN|X1X2…XN－1)

于是有

H(X1X2…XN)=H(X1)+H(X2|X1)+…+H(XN|X1X2…XN－1)

性质1表明

H(X1)≥H(X2|X1)≥…≥H(XN|X1X2…XN－1)

故必有

HN(X)=1NH(X1X2…XN)≥H(XN|X1X2…XN－1)

即

HN(X)≥H(XN|X1X2…XN－1)

平均符号熵HN(X)以简单的算术平均表示每一个符号所携带的平均信息量，而条件熵H(XN| X1X2…XN-1)描述的是已知前面N-1个符号时关于符号XN的信息量。可见，平均符号熵HN(X)和条件熵H(XN| X1X2…XN-1)均为单个符号平均信息量的度量方法。但是条件熵是在已经知道一些条件的前提下，进一步获得的信息量，因此条件熵小于或等于平均符号熵。
性质3

HN(X)≤HN－1(X)(328)

证明： 


NHN(X)=H(X1X2…XN)

=H(XN|X1X2…XN－1)+H(X1X2…XN－1)

=H(XN|X1X2…XN－1)+(N－1)HN－1(X)

≤HN(X)+(N－1)HN－1(X)


于是

(N－1)HN(X)≤(N－1)HN－1(X)

因此

HN(X)≤HN－1(X)

性质3表明，平均符号熵HN(X)也是随着N的增加而非递增。

进一步分析： 
对于熵H(X)＜∞的平稳信源X，由于熵具有非负性，即HN(X)≥0，因此由性质3可以看出，信源符号序列长度不同时，平稳信源输出的每一个符号所携带的信息量，即平均符号熵，满足

∞＞H(X)=H1(X)≥H2(X)≥…≥HN－1(X)≥HN(X)≥0(329)

可见，随着信源符号序列长度N的增加，HN(X)将单调非递增地收敛于某有限值。
对于平稳信源X，当其输出的符号序列足够长(N→∞)时，每一个信源符号所携带的信息有效地反映出了信源输出的实际信息量。
因此，定义H∞=limN→∞HN(X)为离散平稳信源X的极限信息量或者极限熵。
性质4
H∞=limN→∞HN(X)存在，且

H∞=limN→∞HN(X)=limN→∞H(XN|X1X2…XN－1)(330)

证明： 对于一个任意的正整数k，有


HN+k(X)=1N+kH(X1X2…XNXN+1…XN+k)

=1N+kH(X1X2…XN－1)+H(XN|X1X2…XN－1)+

H(XN+1|X1X2…XN)+…+H(XN+k|X1X2…XN+k－1)

≤1N+kH(X1X2…XN－1)+(k+1)H(XN|X1X2…XN－1)

=1N+kH(X1X2…XN－1)+k+1N+kH(XN|X1X2…XN－1)


固定N，令k→∞，得

limk→∞HN+k(X)≤0+H(XN|X1X2…XN－1)

已知N→∞时，HN(X)的极限存在且为H∞，故有

limk→∞HN+k(X)=H∞

综合性质2给出的关系可知，条件熵H(XN| X1X2…XN-1)满足

H∞(X)≤H(XN|X1X2…XN－1)≤HN(X)

令N→∞，因为limN→∞HN(X)=H∞，所以

limN→∞H(XN|X1X2…XN－1)=H∞

于是

H∞=limN→∞HN(X)=limN→∞H(XN|X1X2…XN－1)


性质2、3、4说明，当平稳信源输出的符号序列长度达到无限大时，平均符号熵HN(X)和条件熵H(XN| X1X2…XN-1)都非递增地收敛于平稳信源的极限熵。因此，对于一个实际的平稳信源，当经过足够长的时间后，信源输出每一个符号所携带的信息量，即信源的极限熵，可以用平均符号熵或者条件熵加以度量。
3.6信源的相关性和剩余度
前面已经讨论了多类离散信源，包括离散无记忆信源及其N次扩展信源、马尔可夫信源、离散平稳信源。由于这些信源的统计特性各不相同，它们输出信息的能力也各不相同。

根据式(328)能够得到

H(XN|X1X2…XN－1)≤H(XN－1|X1X2…XN－2)≤…≤H(X2|X1)≤H(X1)

当离散平稳信源输出符号是等概分布时熵最大，记此时的熵为H0，则H0 =logn。而且当N→∞时，H(XN| X1X2…XN-1)收敛于极限熵。于是，有

H0≥H1≥H2≥…≥Hm+1≥…≥H∞(331)

这就是信源的相关性。为什么叫作“相关性”？是因为由于信源符号间的依赖关系，使得信源熵减小。也就是说由于信源符号间存在相关性，知道的信源符号越多，越容易猜测将要出现的符号是什么，即不确定性减小。
为了衡量信源的相关性程度，引入信源剩余度(冗余度)的概念。
【定义313】信源剩余度定义为

R=1－H∞H0(332)

前面我们说过，极限熵H∞表示当前符号实际上能够带给我们的信息量，而H0是熵的最大值，因此H∞/H0表示实际值占最大值的比例，该比例称为熵的相对率，记作η

η=H∞H0(333)

可见，信源剩余度


图310信源相关性和剩余度


R=1－η

信源剩余度越小，说明熵的实际值占最大值的比例越大，即一个信源符号上实际带有的信息量越接近于信源符号能够带有信息量的最大值，即信源符号的利用率越高。利用率越高，当然剩余未用的部分越少，即“剩余度越小”。反之亦然。

怎样才能减小信源剩余度呢？要回答这个问题，首先要明确剩余度的来源。剩余度来源于信源符号之间的相关性。这是因为如图310所示，以长度为2的序列为例，由于信源符号之间存在相关性，因此输出X1之后，带来的信息量中包括部分关于X2的信息量，再输出X2时，这部分信息量被重复输出，即X2上这部分携带信息的能力被浪费了，或者说这部分携带信息的能力没有用上，因此就产生了剩余。信源符号之间相关性越大，剩余的就越多。究竟剩余了多少，由信源剩余度来衡量。

可见，要减小信源剩余度，就要减小信源相关性。第6章和第7章要研究的信源编码是减少信源相关性的有效方法。
3.7本章小结
本书内容主要包括信源、信道、信源编码、信道编码四部分。本章研究了信源，主要是离散信源，主要内容见表33。
信源可以从不同的角度分类。从记忆特性分可以分为无记忆信源和有记忆信源，从平稳特性可以分为平稳信源和非平稳信源。因此信源总共可以分为四类： 平稳无记忆信源、平稳有记忆信源、非平稳无记忆信源、非平稳有记忆信源。重点研究的是前两类。
平稳无记忆信源相对简单，给出了信源及扩展信源的模型和熵。
平稳有记忆信源中重点研究平稳有限记忆信源，即平稳马尔可夫信源。包括m阶马尔可夫信源的定义、状态转移矩阵、状态转移图、熵(包括熵的求解方法)。
最后是信源的相关性和剩余度。


表33本章小结




平稳无记忆信源

信源

模型
X
P=x1x2…xn
p(x1)p(x2)…p(xn)


熵： H(X)=－∑ni=1p(xi)logp(xi)
N次扩展信源

模型：
 
XN
P=x1…x1x1x1…x1x2…xn…xnxn
p(x1)Np(x1)N－1p(x2)…p(xn)N

熵： H(XN)=NH(X)

非平稳无记忆信源


平稳有记忆信源


平稳有限记忆信源(平稳马尔可夫信源)

定义： p(xi|xi－1xi－2…xi－m…x1)=p(xi|xi－1xi－2…xi－m)

状态转移矩阵

状态转移图

熵： H∞(X)=Hm+1(X)=－∑Sj∑ip(Sj)p(xi|Sj)logp(xi|Sj)

熵的求解方法： 

1. 判断是否为平稳马尔可夫信源； 

2. 对平稳马尔可夫信源，求出状态的平稳分布； 

3. 根据上式求得马尔可夫信源的熵
平稳无限记忆信源非平稳有记忆信源

信源相关性： H0≥H1≥H2≥…≥Hm+1≥…≥H∞

熵的相对率： η=H∞H0信源剩余度： R=1－H∞H0=1－η

3.8习题
31某信源先后发出两个符号x1和x2，如果该信源是无记忆的，则p(x2|x1)=。

32无记忆信源X的熵为1.25比特，则它的4次扩展信源X4的熵为比特。
33假设某一信源的转移矩阵为P=p11p12p13
p21p22p23
p31p32p33，则∑3i=1p2i=。
34如果用表示一个马尔可夫信源，则该信源是阶的。
35设一离散无记忆信源为

X
P=0123
3/81/41/41/8

信源输出一条消息为(202120130213001203210110321010021032011223210)，求
(1) 此消息的自信息量是多少？
(2) 在此消息中平均每个符号携带的信息量是多少？
36信源X中只有两个消息符号，画出信源熵的曲线并求解Hmax(X)。
37某一无记忆信源的符号集为{0, 1}，已知信源的概率空间为

X
P=01
1434

(1) 求该信源的熵。
(2) 由100个符号构成的序列，求每一特定序列(例如有m个“0”和(100-m)个“1”构成)的自信息量的表达式。
38设某离散平稳信源X，概率空间为

X
P=012

11/364/91/4

并设信源发出的符号只与前一个符号有关，其联合概率为p(ai,aj)，如题表31所示。


题表31联合概率




ajai012
01/41/18011/181/31/18
201/187/36


求信源的信息熵、条件熵与联合熵，并比较信息熵与条件熵的大小。
39设离散无记忆信源为

X
P=a1a2a3a4a5a6

0.20.190.180.170.160.17

求该信源的熵，并解释为什么H(x) ＞ log6不能满足信源的极值性。
310有一离散无记忆信源

X
P=012
141412

设计两个独立实验去观察它，其结果分别为Y1∈{0, 1}，Y2∈{0, 1}，已知条件概率如题表32所示。 


题表32实验结果



p(y1 | x)01p(y2 | x)01
010010
101110
21/21/2201

求I(X;Y1)和I(X;Y2)，并判断哪一个实验好一些。
311二次扩展信源的熵为H(X2)，而一阶马尔科夫信源的熵为H(X2|X1)，试比较两者的大小，并说明原因。
312一个马尔可夫过程的基本符号为0, 1, 2，这3个符号等概率出现，并且具有相同的转移概率。
(1) 画出一阶马尔可夫过程的状态图，并求稳定状态下的一阶马尔可夫信源熵H2和信源剩余度； 
(2) 画出二阶马尔可夫过程的状态图，并求稳定状态下的二阶马尔可夫信源熵H3和信源剩余度。
313设有一个信源，它产生01序列的消息。该信源在任意时间而且不论以前发生过什么消息符号，均按p(0)=0.4，p(1)=0.6的概率发出符号。
(1) 试问这个信源是否是平稳的？
(2) 试计算limN→∞HN(X)。
(3) 试计算H(X4)并写出X4信源中可能发出的所有符号。
314有一个马尔可夫信源，已知转移概率为p(S1|S1)=23，p(S2|S1)=13，p(S1|S2)=1，p(S2|S2)=0。试画出状态转移图，并求出信源熵。
315一阶马尔可夫信源的状态转移图如题图31所示，信源X的符号集为{0, 1, 2}，并定义p-=1－p。
(1) 求信源平稳后的概率分布p(0)、p(1)和p(2)； 
(2) 求此信源的熵； 
(3) 近似认为此信源为无记忆时，符号的概率分布等于平稳分布。求近似信源的熵H(X)并与H∞进行比较； 
(4) 对一阶马尔科夫信源,p取何值时H∞取最大值，又当p=0或p=1时结果如何？
316一阶马尔可夫信源的状态转移图如题图32所示，信源X的符号集为{0, 1, 2}。
(1) 求平稳后的信源的概率分布； 
(2) 求信源熵H∞； 
(3) 求p=0或p=1时信源的熵，并说明其理由。


题图31题3.15状态转移图




题图32题3.16状态转移图



317设信源发出两个消息x1和x2，它们的概率分布为p(x1)=34、p(x2)=14。求该信源的熵和冗余度。
318设某马尔可夫链的一步转移概率矩阵为

012
0
1
2qp0
q0p
0qp

试求： 
(1) 该马尔可夫链的2步转移概率矩阵； 
(2) 平稳后状态“0”，“1”，“2”的概率分布。
319设有一信源，它在开始时以p(a)=0.6、p(b)=0.3、p(c)=0.1的概率发出X1，如果X1为a时，则X2为a,b,c的概率为1/3； 如果X1为b时，则X2为a,b,c的概率为1/3； 如果X1为c时，则X2为a,b的概率为1/2，为c的概率为0。而且后面发出Xi的概率只与Xi-1有关。又p(Xi| Xi-1)=p(X2 | X1)。试利用马尔可夫信源的图示法画出状态转移图，并计算信源熵H∞。
320黑白传真机的消息元只有黑色和白色两种，即X={黑，白}，一般气象图上，黑色出现的概率p(黑)=0.3，白色出现的概率p(白)=0.7，黑白消息前后有关联，其转移概率为p(白|白)=0.9143、p(黑|白)=0.0857、p(白|黑)=0.2、p(黑|黑)=0.8。求该一阶马尔可夫信源的不确定性H(X|X)，并画出该信源的状态转移图。
321用α,β,γ三个字符组字，设组成的字有以下三种情况： 
(1) 只用α一个字母的单字母字； 
(2) 用α开头或结尾的两字母字； 
(3) 把α夹在中间的三字母字。

假定由这三种字符组成一种简单语言，试计算当所有字等概出现时，语言的冗余度。
322令X为掷钱币直至其正面第一次向上所需的次数，求H(X)。
323一段代码如下：

x=0;

for i=0 to n

x=x + 1;

end


不考虑循环次数n的限制，x是越来越大的，不可能稳定下来。请从信息论的角度证明该循环过程无法达到稳定状态，即是非平稳过程。
324某地区每年城市和郊区之间的人口移动有一定规律，大概有5%的城市人口流动到郊区，3%的郊区人口流动到城市。
(1) 请给出转移矩阵，该矩阵也称为移民矩阵。
(2) 多年以后，该地区的城市人口和郊区人口会不会各自达到一个固定的规模？即城市人口和郊区人口的数量基本稳定，不再发生大的变化。
(3) 如果能达到一个固定的规模，并假设该地区共1000万人口，那么城市人口和郊区人口的固定规模各是多少？
325某出租车公司大约有2000辆小汽车，客户可以在同一个营业点取还，也可以异地
取还，假设取还模型为

飞机场市中心汽车站
飞机场
市中心
汽车站0.900.010.09
0.010.900.09
0.090.010.90

请问市中心应该准备多少辆车？