《Elements of Information Theory》二版习题解析
5星 · 超过95%的资源 需积分: 50 50 浏览量
更新于2024-07-26
收藏 1020KB PDF 举报 "《Elements of Information Theory》第二版习题解答"
这本资源是关于信息理论的经典教材《Elements of Information Theory》第二版的习题详细解答。由Thomas M. Cover和Joy A. Thomas合著，内容涵盖从基础概念到深入理论的多个方面。解答共164页，非扫描版，因此阅读体验应该较好。
本书的核心知识点包括：
1. **引言**：这部分可能介绍了信息理论的基本概念和历史背景，为后续章节的学习铺垫。
2. **熵、相对熵和互信息**：这是信息论的基础，熵衡量信息的不确定性，相对熵（Kullback-Leibler散度）衡量两个概率分布的相似性，而互信息则描述了两个随机变量之间的关联程度。
3. **渐近等分割性质（Asymptotic Equipartition Property, AEP）**：这个概念在大数定律中起关键作用，它表明对于大多数长序列，其大部分信息可以被少数“典型”序列所代表。
4. **随机过程的熵率**：讨论了随时间变化的系统（如信源）的信息产生速率，是理解连续时间信息流的关键。
5. **数据压缩**：基于Shannon熵的编码理论，探讨如何有效地压缩数据，同时保持解压缩后的信息完整性。
6. **赌博与数据压缩**：这部分可能将信息论的概念应用到赌博策略上，通过信息熵和期望值来分析决策问题。
解答集由斯坦福大学课程的助教和教师编写，特别感谢John Gill、David Evans、Jim Roche、Laura Ekroot和Young Han Kim的贡献。对于难题，题目中提供了提示，并且在某些解决方案中包含额外有趣的内容，比如第12页的硬币称重问题。
此解答集欢迎读者提供反馈、建议和错误修正，以持续改进和完善。
这本书的习题解答对于学习信息理论的学生来说是一份宝贵的资源，不仅帮助解决具体问题，还能通过额外材料加深对概念的理解，提高应用能力。
Entropy, Relative Entropy and Mutual Information 15
• ρ(x, y) = 0 if and only if x = y
• ρ(x, y) + ρ(y, z) ≥ ρ(x, z) .
(a) Show that ρ(X, Y ) = H(X|Y ) + H(Y |X) satisfies the first, second and fourth
properties above. If we say that X = Y if there is a one-to-one function mapping
from X to Y , then the third property is also satisfied, and ρ(X, Y ) is a metric.
(b) Verify that ρ(X, Y ) can also be expressed as
ρ(X, Y ) = H(X) + H(Y ) − 2I(X; Y ) (2.11)
= H(X, Y ) − I(X; Y ) (2.12)
= 2H(X, Y ) − H(X) −H(Y ). (2.13)
Solution: A metric
(a) Let
ρ(X, Y ) = H(X|Y ) + H(Y |X). (2.14)
Then
• Since conditional entropy is always ≥ 0 , ρ(X, Y ) ≥ 0 .
• The symmetry of the definition implies that ρ(X, Y ) = ρ(Y, X) .
• By problem 2.6, it follows that H(Y |X) is 0 iff Y is a function of X and
H(X|Y ) is 0 iff X is a function of Y . Thus ρ(X, Y ) is 0 iff X and Y
are functions of each other - and therefore are equivalent up to a reversible
transformation.
• Consider three random variables X , Y and Z . Then
H(X|Y ) + H(Y |Z) ≥ H(X|Y, Z) + H(Y |Z) (2.15)
= H(X, Y |Z) (2.16)
= H(X|Z) + H(Y |X, Z) (2.17)
≥ H(X|Z), (2.18)
from which it follows that
ρ(X, Y ) + ρ(Y, Z) ≥ ρ(X, Z). (2.19)
Note that the inequality is strict unless X → Y → Z forms a Markov Chain
and Y is a function of X and Z .
(b) Since H(X|Y ) = H(X) −I(X; Y ), the first equation follows. The second relation
follows from the first equation and the fact that H(X, Y ) = H(X) + H(Y ) −
I(X; Y ) . The third follows on substituting I(X; Y ) = H(X) + H(Y ) −H(X, Y ) .
10. Entropy of a disjoint mixture. Let X
1
and X
2
be discrete random variables drawn
according to probability mass functions p
1
(·) and p
2
(·) over the respective alphabets
X
1
= {1, 2, . . . , m} and X
2
= {m + 1, . . . , n}. Let
X =
(
X
1
, with probability α,
X
2
, with probability 1 − α.
剩余163页未读，继续阅读
1121 浏览量
2008-03-21 上传
268 浏览量
148 浏览量
2008-03-21 上传
101 浏览量
144 浏览量
2008-03-21 上传
