当前位置:首页 >> 数学 >> Ch2例题与证明一

Ch2例题与证明一


? 推导求条件熵为什么要用联合概率? 先取一个 y j ,在已知 y j 条件下,X 的条件熵
H ( X / y j ) 为:
H ( X / y j ) ? ? p( xi / y j )I ( xi / y j ) ? ?? p( xi / y j ) log2 p( xi / y j )
i ?1 i ?1 n n

上式为仅知某一个 y j 时 X 的条件熵,它随着 y j 的变 化而变化,仍然是一个随机变量。已知所有的 y j 时 X 仍然存在的不确定度,应该是进一步把 H ( X / y j ) 在 Y 集合上取数学期望,

H ( X / Y ) ? ? p( y j ) H ( X / y j )
j ?1

m

? ??? p( y j ) p( xi / y j ) log2 p( xi / y j )
j ?1 i ?1 m n

m

n

? ? ?? p( xi y j ) log2 p( xi / y j )
j ?1 i ?1

?

条件熵是一个确定值,表示信宿在收到 Y 后, 信源 X 仍然存在的不确定度。这是由于传输失 真造成的;

? ?

H ( X / Y ) 称为信道疑义度,也称损失熵;
条件熵 H (Y / X ) 为噪声熵。

[例 2.1.4 条件熵] 已知 X,Y ? {0,1} ,XY 构成的联合 概率为:p(00)=p(11)=1/8,p(01)=p(10)=3/8,计算条 件熵 H(X/Y)。 解: 根据条件熵公式:

H ( X / Y ) ? ??? p( xi y j ) log2 p( xi / y j )
j ?1 i ?1

m

n

p ( xi / y j ) ?

p ( xi y j ) p( y j )
2

首先求 p( y j ) ? ? p( xi y j ) ,有
i ?1

3 1 p(0) ? p( y1 ? 0) ? p( x1 y1 ? 00) ? p( x2 y1 ? 10) ? ? ? c 8 8 1 同理可求得 p(1) ? p( y2 ? 1) ? 2 从而有: p(0 / 0) ? p( x1 ? 0 / y1 ? 0) ? p(00) p( x1 y1 ? 00) 1 / 8 1 ? ? ? ? p(1 / 1) p(0) p( y1 ? 0) 1 / 2 4

3 p(1 / 0) ? p(0 / 1) ? , 4 H ( X / Y ) ? ? p(00) log2 p(0 / 0) ? ? p(01) log2 p(0 / 1) ? p(10) log2 p(1 / 0) ? p(11) log2 p(1 / 1) 1 3 3? ? 1 ? ? ? log2 ? log2 ? ? 2 ? 0.406 4 8 4? ? 8 ( bit / sym bol )

? 最大离散熵定理 用图形表示为:
y

H ( X ) ? log2 n

证明:先证明一个常用不等式:ln x ? x-1 (x>0)

y=x-1 y=ln x

1 0 x

-1

' 令 f(x)=ln x –(x-1) ,则 f ( x) ? x ? 1 , 可见当 x=1 时,

1

'' f(x)=0,它是 f(x)的极值。 且 f ( x) ?

?1 ? 0, 故此极值 x2

为极大值。 所以有: f(x) ? f(1)=0 , 当且仅当 x=1 时取等号。 这时 证法一:
n 1 H ( X ) ? log2 n ? ? p( xi ) log2 ? ? p( xi ) log2 n p ( x ) i ?1 i ?1 i n

f(x)=ln x-(x-1)

?0

=>

ln x≤(x-1)

? ? p( xi ) log2
i ?1

n

1 np( xi )

令 x ? np( x ) , 利用 ln x ? x ? 1, x ? 0, 且 log2 x ? ln x log2 e i

1

1 H ( x) ? log2 n ? ? p ( xi )[ ? 1] log2 e np( xi ) i ?1 1 ? ? [ ? p ( xi )]log2 e i ?1 n ?0 H ( X ) ? log2 n
qi pi (
n

n

?

证法二:现令 x ?
log 2 (

p i 、 q i 为两个概率),则有
, 两边取统计平均值

qi q ) ? ( i ? 1) log 2 e pi pi

qi qi p log ? p ( ? 1) ? ? qi ? 1 ? 0 ? i 求得: ? i p p i i i i i

?

? ? pi log pi ? ?? pi log qi
i i

当qi ?

? log n

1 n

结论:等概率分布时熵最大,不确定性最大。故这一 定理又被称为离散信源最大熵定理。

? 可加性的证明
H ( XY ) ? ??? p ( xi y j ) log2 p ( xi y j )
i j

? ? ?? p( xi y j ) log2 [ p ( xi ) p ( y j / xi )]
i j

? ? ?? p( xi ) p( y j / xi ) log2 p ( xi ) ? ?? p ( xi y j ) log2 p ( y j / xi )
i j i j

? ? ? ?? p ( xi ) log2 p ( xi ) ?? p( y j / xi )? ? H (Y / X ) i ? j ? ? H ( X ) ? H (Y / X ) 利用 : p ( xi y j ) ? p ( xi ) p ( y j / xi )

? p( y
j

j

/ xi ) ? 1

? 条件熵不大于信源熵(无条件熵 )的证明 证明:
H ( X / Y ) ? ??? p( xi y j ) log2 p ( xi / y j )
i j

? ? ? ?? p ( y j ) ?? p ( xi / y j ) log2 p( xi / y j )? j ? i ? ? ? ? ? ? p ( y j ) ?? p ( xi / y j ) log2 p ( xi )? j ? i ? ? ? ? ?? ?? p ( y j ) p ( xi / y j )? log2 p( xi ) i ? j ? ? ? ? p ( xi ) log2 p( xi )
i

? H (X ) 其中, ? p( y j ) p( xi / y j ) ?? p ( xi y j ) ? p ( xi )
j j

? 上凸性的证明 熵函数 H(U)为 pi ? p(ui ) 的上凸函数。 证明一:在证明本定理以前先介绍凸函数的概念。 (1)先介绍凸集合: 若集合 C ? R (n 维欧氏空间) , 有 p ? C, q ? C ,
n

且对任意实数 ? :0 ? ? ? 1,有 ? p ? (1 ? ? )q ? C ,则称为 C 为凸集合。其涵义为:凸集合中任意两元素的线性 组合仍属于原凸集合。 显然,n 维线性空间 R 为一凸集合。概率矢量
n

p ? ( p1 ? pn ) 亦为一凸集 ? p
n i ?1

i

?1 。

任意凸集合的交( ? )和并 (? ) 仍为凸集,但是其 补 (c) 并非凸集。
A?B

A? B

A

B

A

B

AC

A

(2)凸函数:又称下凸

(? ) 函数,

设 f(p)是在某个凸集 C( C ? R )上定义的实函
n

数,若对任意实数 ? (0 ? ? ? 1) 和任意矢量 p, q ? C ,满 足下列不等式:
?f ( p) ? (1 ? ?) f (q) ? f [? p ? (1 ? ?)q]

则称 f (?) 为下凸函数或凹函数 (? ) 。其含义为:凸集 合中函数的线性组合不小于凸集合中线性组合的函 数。若不等号相反,即
?f ( p) ? (1 ? ?) f (q) ? f [? p ? (1 ? ?)q]

则称 f (?) 为上凸( ? ) 。 若将上述“ ? ”﹑“ ? ”改为“>”﹑“<”则 分别称为严格凸和严格凹。 上述凹凸函数可以用下列形象直观图形来表示:

?f ( p ) ? (1 ? ? ) f (q )
? f [?p ? (1 ? ? )q ]

a

p

?p ? (1 ? ? )q

q

b

p

在[a,b]上定义的下凸 (? ) 函数

f [?p ? (1 ? ? )q ] ? ?f ( p ) ? (1 ? ? ) f (q )

a

p

?p ? (1 ? ? )q

q

b

p

在[a,b]上定义的上凸 (? ) 函数 (3) 由上述凸函数性质, 我们只需证明熵函数满足下 列不等式。即熵函数为上凸函数。
H [ pi? ? ? pi' ? (1 ? ? ) pi" ] ? ? H ( pi' ) ? (1 ? ? ) H ( pi" )

(对照上凸函数性质,即 f ? H , ? ? ? )
? ' " 其中 0 ? ? ? 1 ,而 pi ? ?pi ? (1 ? ? ) pi 因此只需证:

H[?pi' ? (1 ? ? ) pi" ] ? ?H ( pi' ) ? (1 ? ? ) H ( pi" )
? ??[?pi' ? (1 ? ? ) pi" ] log pi? ? ? ? pi' log pi' ?(1 ? ? )? pi" log pi"
i i i

pi? pi? " ? ?? ? p log ' ? (1 ? ? )? pi log " pi pi i i
' i

? ?? log ? pi'
i

? pi? " pi ? (1 ? ? ) log p ? i pi' pi" i

(Jensen 不等式 P.25)

? ?? log ? pi? ? (1 ? ? ) log ? pi?
i i

? ?? log1 ? (1 ? ? ) log1
?0

证明中, 我们引用了著名的 Jensen 不等式。 其含 义为:若 f(x)是随机变量 X( x ? X )的凸函数,则有:
E[ f ( x)] ? f [ E ( x)] —— f(x)下凸时 E[ f ( x)] ? f [ E ( x)] —— f(x)上凸时

上式证明中要注意:log x 为上凸函数。
设有一个多元函数或矢 量函数f ( x1 , x2 ,?, xn ) ? f ( X ), 对任一小于 1的正数?(0 ? ? ? 1 )及f的定义域中任意 两个矢量X,Y,若f [?X ? (1 ? ? )Y ] ? ?f ( X ) ? (1 ? ? ) f (Y ) 则称f为严格上凸函数。

证明二:设 P,Q 为两组归一的概率矢量

P ? [ p ( x1 ), p ( x2 ), 且0 ? p ( xi ) ? 1,
n n i ?1 i i ?1 i

, p ( xn )], Q ? [ p ( y1 ), p ( y2 ), 0 ? p ( yi ) ? 1

, p ( yn )]

? p( x ) ?? p( y ) ?1
则H (? P ? (1 ? ? )Q) ? ?? [? p ( xi ) ? (1 ? ? ) p ( yi )]log 2 [? p( xi ) ? (1 ? ? ) p( yi )]
i ?1 n

可以证明 0 ? ?p ( xi ) ? (1 ? ? ) p ( yi ) ? 1 ?? ? 0,1 ? ? ? 0, p ( xi ) ? 0, p ( yi ) ? 0 ??p ( xi ) ? (1 ? ? ) p ( yi ) ? 0 如果?p ( xi ) ? (1 ? ? ) p ( yi ) ? 1 1 ? ?p ( xi ) ? 1, p ( xi ) ? 1, 不可能 1?? 1 ? ?p ( xi ) 而当p ( yi ) ? 1?? ?p( xi ) ? (1 ? ? ) p( yi ) ? 1 则p ( yi ) ? 故有0 ? ?p ( xi ) ? (1 ? ? ) p ( yi ) ? 1
n n n

? [? p( x ) ? (1 ? ? ) p( y )] ? ? ? p( x ) ? (1 ? ? )? p( y )
i ?1 i i i ?1 i i ?1 i

? ? ?1?? ? 1 ? ? p ( xi ) ? (1 ? ? ) p ( yi )可以看成一种新的概率分布 由熵的极值性( t ext book P. 24) ?? ? p ( xi ) log 2 [? p ( xi ) ? (1 ? ? ) p ( yi )] ? ? H ( P )
i ?1 n

各p ( xi ), p ( yi )不完全相等,有 ?? ? p ( xi ) log 2 [? p ( xi ) ? (1 ? ? ) p ( yi )] ? ? H ( P )
i ?1 n

同理 : ?(1 ? ? )? p( yi ) log2 [?p( xi ) ? (1 ? ? ) p( yi )] ? (1 ? ? ) H (Q)
i ?1

n

两式相加整理

H [?P ? (1 ? ? )Q] ? ?H ( P) ? (1 ? ? ) H (Q)

*严格上凸函数在定义域内的极大值必为最大值,用 上凸性求最大熵时,只需求导并取极值即可。 给定信源 [ X , p( xi )],求 H ( X )在? p( xi ) ? 1 限制下的条
i ?1 n

件极值。令:

? ? ? n ?? ? H ( X ) ? ? ?? p( xi ) ? 1? ? ? 0 ?p( xi ) ? ? i ?1 ?? 得 ? [1 ? log2 p ( xi )] ? ? ? 0

? 为待定常数,若取对数的底为自然数 e,
p( xi ) ? e ? ?1 ? const
而 ? p( xi ) ? 1
i ?1 n

故 p ( x ) ? n ? H max ( X ) ? ln n

1


更多相关文档:

Ch2例题与证明三

Ch2例题与证明三_数学_高中教育_教育专区。信息论与编码典型例题?...p( xiN ) ? 1 i1 ?1 i2 ?1 i N ?1 则 H ( X N ) ? ?? p...

Ch2例题与证明三

扩 展信源的每个元素是信源 X 的输出长度为 2 的消息序 列。由于扩展信源是无记忆的,故 p(ai ) ? p( xi1 ) p( xi2 ) X 2 信源 (i1 , i2 ...

Ch2例题与证明二

C​h​2​例​题​与​证​明​ 暂无评价|0人阅读|0次下载|举报文档? 平均互信息的物理意义 (1)Y 对 X 的平均互信息 I ( X ; Y ) ...

Ch2例题与证明五

Ch2例题与证明五_计算机软件及应用_IT/计算机_专业资料。? 定长编码定理 由 L 个符号组成的, 每个符号的熵为 H(X) 的平稳无记忆符号序列 X 1 X 2 ? X...

Ch2例题与证明四

C​h​2​例​题​与​证​明​四 暂无评价|0人阅读|0次下载...H c ( X 1 ) ?H c ( X 2 ) ? ? ? H c ( X N ) i ?1 N ...

...& Coding信息论与编码(英文版)Ch2例题与证明三

扩 展信源的每个元素是信源 X 的输出长度为 2 的消息序 列。由于扩展信源是无记忆的,故 p(ai ) ? p( xi1 ) p( xi2 ) X 2 信源的元素 (i1 ,...

2017有机高考模拟试题2

有机高考模拟试题 1.CPAE 是蜂胶的主要活性成分,...欲证明 CH2=CHCHO 中含有碳碳双键 欲确定磷、砷...“银氨溶液或新制氢氧化铜”其他均正确本题得 2 ...

近世代数ch2(1-6节)习题参考答案

近世代数ch2(1-6节)习题参考答案_理学_高等教育_教育专区。第二章前 6 节...证(仿照群第二定义的证明) ?1 ?1 先证 aaR ? aR a ? eR 。 ?1 ?1...

2011届高考化学第一轮复习综合练习题2

OH OCH3 CH2CH CH2 丁香酚有关上述两种化合物的说法正确的是 A.常温下,1..... 最简单的装置接口连接顺序是 ;实验后用 F 中的固体进行验 证的方法是__...

有机思考题答案(1-2学期完整版)

有机思考题答案(1-2学期完整版)_理学_高等教育_教育专区。咖啡因 1、用升华...如: O OH CH 3 C =CHCOOEt CH 3 C CH 2COOEt 实验证明方法: (1)用...
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com