信息论第二章(叶中行)

1、第2章 随机过程的信息度量和渐近等分性 2.1 2.2 2.3 2.4 2.5 2.1 信源和随机过程的基本概念信源的模型表示成一个在信源字母集中取值的随机序列或随机过程信源分类u信源可以按信号取值集合和信号取值时刻的连续性和离散性分类u也可以按对应数学模型随机过程的统计特征来分类信源分类信号取值集合信号取值时间集合信源名称离散离散离散信源(或数字信源)连续离散连续信源连续连续波形信源(或模拟信源)离散连续u无记忆信源u有记忆信源u平稳或遍历信源u马氏信源u高斯信源信源分类随机过程(0)( ).( )0.0( ),0t ttX t X ttttX t t当固定时，电话交换站在 0, 时间内收到

2、的呼叫次数是随机变量，记为服从参数为 的泊松分布，其中 是单位时间内平均收到的呼叫次数，且如果 从 变到+ ， 时刻前收到的呼叫次数需用一族随机变量，来表示，则该随机现象就是一例：个随机过程121,2,nnXnXXXn ， 医院不断地登记新生儿的性别。以0表示男，以1表示女，表示第 次登记的数字，得到一列，记为，例称为随机过程1,2,nnnXnXXn 生物群体的增长问题。设有一生物群体，由于繁殖每一代会产生下一代，令表示第 代生物体个数，是可取非负整数值的随机变量，称，例为随机过程随机过程数学定义( , )( , ),( , )( , )( , )( ),F PTTXttT XtF PXttT

3、X t tT设是一个概率空间， 是一个实的参数集，定义在 和 上的二元函数，如果对于任意固定的是上的随机变量，则称，为该概率空间上的随机过程，简记定义：( ),( )( ),( )()X t tTtX tX t tTtX tttTS设是随机过程，则当 固定时，是一个随机变量，称之为在 时刻的状态.随机变量固定,所有可能的取值构成的集合，称为随机过程的状态空定:间，记为义( ),( )( ),X t tTX tTx t设是随机过程,则当固定时，是定义在 上不具有随机性的普通函数，记为称为随机过程的一个样本函数。其图像称为随机过程的一条定义:样本曲线随机过程分类u离散参数、离散状态的随机过程u离散

4、参数、连续状态的随机过程u连续参数、离散状态的随机过程u连续参数、连续状态的随机过程严平稳过程1212121212121212( ),1,( ),( ),( )(),(),()(;) (;) nnnnnnnnX t tTntttTtttnX tX tX tX tX tX tF t ttx xxF tttx xx设是一随机过程，如果对于任意的和任意的 ， ， ，以及定使的任意实数 ， 维随机变量（）和（）有相同的联合分布函数，即, , , , , ,义： ,1,2,( ),itTR inX t tT称是严(强，狭义)平稳过程121212122112( ; )( ) (;)(;) = (0;)F

5、t xF xtF t tx xF ttx xFtt x x严平稳过程的有限维分布不随时间的推移而发生改变严平稳过程的所有一维分布函数与 无关；二维分布函数仅是时间间隔的函数，而与两个时刻本身无关，即,宽平稳过程( ),( )(),( , )(), ,( ,)( ),( ),()XXXXXXX t tTtT mtms tT Rs tRtsR t tT Rt tRX t tT 设是二阶矩过程，如果：(1)常数(2)或则称为宽 弱，广义 平稳过程，简定义：称平稳过程XXmtE X ttE Xt2随机过程的均值函数( )=( ) 称为随机过程的一阶矩均方值函数( )=( ) 称为随机过程的二阶矩121

6、2 ()2.1.1(,) (,) nrnnnXXXXPXXXx xxp x xx1212一个离散信源的输出为一个取值于有限字母集 的随机过程，记为 =, , ，其中 称为状态集，一个离散随机过程是一列随机变量，它是由一族联合分布, ,所定义唯一决定的()( ),nriXXXP Xxp x xi12(1)当, 为相互独立的随机变量序列，且服从相同的分布对任意 成立，称它为无记忆信源1122111122120,rmmmmmmrmmmmmmm km kmkP XxXxXxXxP XxXxXxXxmkx xx(2)称一个随机过程为阶马尔可夫过程，如果= |=,=, ,= |=,=, ,=对任意和所有的

7、 ,成立1122111111()rmmmmmmrmmmmmmkP XxXxXxXxP XxXxp xx当时称为马尔可夫过程（简称马氏过程），此时= |=,=,= |=|1111(01( )( ),1,2,(0|0)0.25,(1|0)0.75(0|1)0.6,(1|1)0.4ri+iri+iri+iri+iXXXp xxiP XXP XXP XXP XX12(一阶平稳马氏信源)设=,)是取值于，的一个平稳马氏信源，其平稳分布为=一步转移概率为（对）例2.1.1n求信源状态转移概率矩阵和状态转移图以及 长序列的联合分布 解：21122121(,)01400 0110112.1.2(|, (|,)

8、iiiriiiiiiXXXPXxXx XxP xx x设为取值于，的二阶平稳马氏信源，其状态可用两个二进制数字表示，共有 种，信源的统计特性则由以下的转例二阶平稳马氏信源移概率简记为(0|00)0.8, (1|11)0.8, (1|00)(0|11)0.2(0|01)(0|10)(1|01)(1|10)0.5PPPPPPPP求信源状态转移概率矩阵和状态转移图以及有限维分布 解：11121212121212, , , (,)(,) = (,)(,),1,2,kkmmkttththrtttmrthththmmmkt tthXXXXPXXXx xxPXXXx xxx xxmk(3)称离散随机过程为平

9、稳的，若对任意的正整数及任意的正整数与有相同的联合分布，即,对 ( ,)和任意 成立11221111211,()0 ( ( | )rmmmmmmrmmmmmmx yP XxXxXxXxP XxXxP XxXxmMp y x如果一个马氏过程是平稳的，则= |=,=, ,= |=|对任意的成立，即转移概率不依赖于时间，称为马氏过程的公共一步转移概率矩阵12,1, (,)rjrM j=1若存在 上的一个概率分布 ，满足称为马氏过程的平稳分布为稳态分布矢量，122312( ,)(,), (,)01rxx xTTxx xATxAxAAPx xA(4)设为一实数列，用 表示移位算子，称实数列的集合 为平移

10、不变集，如果当且仅当称一个平稳过程为遍历的，如果对任何平移不变集 有,或其中P(1|00)=0, P(0|11)=0121010(,)1,0,1 2.1.1()lim =1 iiniinrniXXXEXaX anPXan设为相互独立的随机变量序列，并服从相同的分布，且有有限数学期望则以概率收敛到即对任意的定理有弱大数定律121010(,)1,0,1 lim2. 1.2()1 = iinniinrniXXXXEXaX anPXan设为相互独立的随机变量序列，并服从相同的分布，且有有限数学期望则以概率1收敛到即对任意的有定理强大数定律kX一个信源序列如果使强大数定理成立，称它为平均遍历的。rrkk

11、P ZP ZXXZk 设Z为取值于 0,1 上有均匀分布( ( =0)= ( =1)=1例2./2)的随机变量，信源序列满足对所有 成立，判断信源是否1.4是遍历的。解 ( )()( )( )11l2im.2.1( )inf( )nnf nf mnf mf nf nf nnn设是满足的半可加数列则 引理2.2 随机过程的信息度量12def11(,)1 () lim(,)1 ()inf(2.2.2,) ,nnnnXXXHXH XXnHXH XXn定设是平稳信源，则存在，且理12def121(,)1()lim(|,2.2,)().3 ()nnnXXXHXH XXXXnHXHX设是平稳信源，则(1)

12、 存在(2)理 定 ,1,2,lim,1li2m.2.4nnnnknka naaaan=1设实数列有极限则 理 =引121 (1)(,) (.5)(2.)2XXXHXH X设为无记忆信源，则熵率系211()(|)kHXH XX当时，即对平稳马氏信源 1211(2)(,) ()(|,)kkXXXkHXH XXX设为阶平稳马氏信源 log()() =1log() lo2 2g. .1HXHXHX冗余度 = 相对冗余度信息含量效率 =定义12312 , ()1/2, ()1/3.Xx xxp xp x设信源求信息含量效率和相例对冗余度例2.1.1 一阶平稳马氏信源设 是取值于 的一个一阶平稳马氏信源

13、，其平稳分布为一步转移概率为12,(,)XXX0,111( ),(0)(0)0.5,(1)(1)0.5rrxPXPX1111(0|0)0.25,(1|0)0.75(0|1)0.6,(1|1)0.4riiriiriiriiP XXP XXP XXP XX则用转移概率矩阵表示为也可用状态转移图表示为0.250.750.60.4p010.250.750.60.4| ()log ( = ( , ) =loglog ()()xyxxyp xp y|xp yp xH Y Xp x H Y XxEp Y|Xyp y|x|x-（）=（ ） （） -=）1111(0|0)0.25,(1|0)0.75(0|1)0

14、.6,(1|1)0.4riiriiriiriiP XXP XXP XXP XX注意到此处注意到此处211H X | XH X对例2.1.1中的马氏信源例2.2.2，计算熵率()和( )0.250.750.60.4pH X计算例2.1.2二阶马氏信源的熵率例2.2. (3)(0|00) 0.8, (1|11) 0.8, (1|00)(0|11) 0.2(0|01)(0|10)(1|01)(1|10) 0.5PPPPPPPP2.3 渐近等分性质 ,11log()(2).3.1knXkp XnH X对无记忆信源有 -以概率收敛到定理()2.3.1 nW我们称集合中的序列为弱典型序列，或称-定义典型序

15、列( )()()( )( )()( )() 0, (1)()(2):1(32) .3.2nnn H Xnn H Xrnnnnrrn H Xnn H XXWP XnP WP XXWnW - ()- ()对任给的有如，则22成立当 充分大时， 成立当 充分大时， (1- )22定理2. 4信源编码定理12,(2.4.1.() XXp x设为无记忆信源，服从公共分定理信源编码定布理1(1)log()0.eRMH XRnnP 当码率时，存在码率为 的编码，使得当时，误差概率1(2)log()01.eRMH XnnRnP 当码率时,其中且不随而变化，则对任何以码率为 的编码，当时，。：WXWMM，I，WX：Xnnnnnnn1|,.,21 ,:|)()()(编号为码字集为称每个编号为一个码字每个给予一个编号分成两部分个序列2.5 Shannon-McMillan-Breiman定理定理12121 ,( ),1 2. log (,5.1,) 1()( )rnXXp xPXXXnH XH P设, 为独立同分布随机过程，其公共分布为则-以概率 收敛到单个随机变量的为理公共熵定121 ,1 lim(2.5.(2)nnniXXTff T XEf Xn设,是遍历的平稳序引理列， 为一位算子， 为可积函数，则移121221 ,1 limlog (,2.5,)=(|) 1.3 rnnXX