第一次信息论作业参考答案_492908107.pdf

2009 年信息论第一次作业参考答案 2009 年信息论第一次作业参考答案 1 在 NBA 季后赛中 两个队要进行七战四胜制的系列赛 当任意一个队获得四场胜利 时 这一轮系列赛结束 不妨用 A B 来表示这两个队 用 X 表示这场系列赛中每 场比赛的结果 X 可能的取值有 AAAA BABABAA BBBAAAA 等 用 Y 来表示总共进行 的比赛场次 Y 的取值范围为 4 至 7 假设每场比赛独立 且两队实力相当 即每 个队在每场比赛中获胜的概率均为 50 求 H X H Y H Y X 和 H X Y 解 确定 Y k 时 X 可能的取值个数为 3 1 2 k C 因为如果 A 队赢得整个系列赛 则最 后一场必然是 A 赢 而前面 k 1 场中 A 赢了 3 场的可能情况有 3 1k C 种 于是 X 的可能 取值为 3 1 2 k C 其中每一个取值对应的概率为2 k Y 4 时 X 可能取值个数有 2 个 每个的概率为 1 16 11 4 2 168 P Y Y 5 时 X 可能取值个数有 3 4 2 8C 个 每个的概率为 1 32 11 5 8 324 P Y Y 6 时 X 可能取值个数有 3 5 2 20C 个 每个的概率为 1 64 15 6 20 6416 P Y Y 7 时 X 可能取值个数有 3 6 2 40C 个 每个的概率为 1 128 15 7 40 12816 P Y 于是有 log 1155 log16log32log64log64 841616 5 8125 H Xp xp x log 11516516 log8log4loglog 84165165 1 924 H Yp yp y 0H Y X 因为确定 X Y 就完全确定了 3 889 H X YH XH Y XH Y 2 和的熵 设X Y为两个随机变量 取值分别为 12 r x xx 和 12 s y yy 令 ZXY 1 证明 H Z XH Y X 如果X Y独立 则 H YH Z 且 H XH Z 即独立随机变量的和随机性增加 2 试给出一个例子 即不独立的情况 满足 H XH Z 和 H YH Z 3 在什么条件下 H ZH XH Y 成立 解 1 ZXY 则 p Zz Xxp Yzx Xx 有 log xz H Z Xp xp Zz Xxp Zz Xx log xz p xp Yzx Xxp Yzx Xx log xy p xp Yy Xxp Yy Xx H Y X 如果X Y独立 则 H Y XH Y 由于条件减少熵 故 H ZH Z XH Y XH Y 同理有 H ZH X 2 考虑如下联合分布 1 1 2 0 1 2 XY 概率为 概率为 容易算得 1H YH X 而0ZXY 概率为 1 故 0H Z 3 我们有 H ZH X YH XH Y 第一个不等式是由于 Z是 X Y 的函数 注 第二个不等式由下面得到 H X YH XH Y XH XH Y 等式成立的条件为 X Y 是 Z的函数且 H Y XH Y 即 X Y独立 注 令 X 为一离散随机变量 Y g X 是 X 的函数 我们有 H X g XH XH g XXH X H X g XH g XH X g XH g X 于是 H g XH X 3 条件可以减少熵 但是条件是否能减少互信息呢 对于随机变量 X Y Z 是否一 定有 I X Y ZI X Y 如果你认为该不等式成立 请给出证明 不成立 请 举出反例 解 条件不一定能减少互信息 反例如下 X Y 是独立的 均为二元等概分布的随机变量 Z X Y 由于 X Y 独立 I X Y 0 而 0 5 I X Y ZH X ZI X Y 4 Monty Hall 你在参加一个电视游戏节目 这个节目提供的奖品是一部汽车 节目主持人先给你 看三扇门 说其中一扇门里面是一部汽车 另外两扇门里面是山羊 他要你挑选一 扇门 但暂时不打开 选完后 知道门后面有什么的主持人打开你未挑选的两扇门 中的一扇 并确保里面是一头山羊 现在你有一次机会可以改变主意 以便赢得一 部汽车 这时他问你要不要改变主意换另外一扇没有打开的门 请问你是否应该改 变选择 主持人提供了多少关于汽车位置的信息量 解 应该改变选择 理由如下 用 A B C 表示三扇门 用A B C 表示大奖在 A B C 门后面 不妨假设一开 始你选择的是 A 门 用 B主持人给你看的是 B 门后是山羊这一事件 现在需要计算 P C B 1 3 1 1 3 1 2 1 3 0 1 3 1 2 3 P C B P C B P B P C P BC P A P BAP B P BBP C P BC 而 1 3 P A B 因此需要改变选择 这里的关键在于主持人知道大奖在哪扇门后面 如果大奖在 C 后面则主持人只能打开 B 门 一开始大奖在三个门后等概分布 熵为 log3 1 585bit 主持人打开 B 门后 大奖在两 扇门后分别以 1 3 2 3 的概率分布 熵为 H 1 3 0 918bit 主持人提供的信息量为 1 585 0 918 0 667bit 5 不等式 令X Y Z是联合随机变量 证明下面不等式 并给出等号成立满足的条件 1 H X Y ZH X Z 2 I X Y ZI X Z 3 H X Y ZH X YH X ZH X 4 I X Z YI Z Y XI Z YI X Z 解 1 证明 H X Y ZH Y X ZH X ZH X Z 等号成立条件 0H Y X Z 2 证明 I X Y ZI X ZI Y Z XI X Z 等式成立条件 0I Y Z X 3 证明 H X Y ZH X YH Z X Y H X ZH XH Z XH Z X YI Y Z X H X Y ZH X Y 等号成立条件 0I Y Z X 4 证明 I X ZI Y ZI Y Z X I X Z YI X Y ZI Y Z XI Y Z I X Z YI Y ZI Y Z I X Z Y 等号恒成立 6 如果函数 x y 对任意的 x y 满足如下四个性质 则称 x y 满足距离的定义 0 x y x yy x 0 x y 当且仅当 x y x yy zx z 定义 X YH X YH Y X 如果存在一个 X 到 Y 的一一映射 则称 X Y 试证明 X Y 是一个距离 解 由于条件熵总是非负的 所以 0 x y 有 x y 定义的对称性有 x yy x 先证 如果 H Y X 0 则 Y 是 X 的一个函数 说 Y 是 X 的一个函数 即对于任取 p x 0 只存在唯一的 y 使得 p x y 0 现在反设存在 0 x 1 y 2 y使得 10 0p yx 20 0p yx 于是 010102020 x log log log 0 xy H Y Xp xp yp y x p xp yxp yxp yxp yx 因为当 0 1 t 时 log0tt 等号只在 t 等于 0 或 1 的时候成立 于是有前面的反设推出矛盾 因此当 H Y X 0 时 Y 是 X 的一个函数 于是当 X Y 0 时 H Y X H X Y 0 X 也是 Y 的函数 此时 X Y 之间存在一 一映射 反过来 如果 X Y 之间映射 则有 H Y X H X Y 0 于是 X Y 0 证法一 H X YH Y ZH X Y ZH Y Z H X Y Z H X ZH Y X Z H X Z 同理有 H Y XH Z YH Z X 于是有 x yy zx z 证法二 2 X YH X YH Y X H X YH YH X YH X H X YH YH X 同理 2 2 Y ZH Y ZH YH Z X ZH X ZH XH Z 则 2 2 2 2 0 X YY ZX Z H X YH Y ZH X ZH Y H X YH YH X Y ZH Y ZH X Y ZH X Z H X YH X Y ZH Y X Z I X Z YH Y X Z 7 鉴别信息 设 22 1 22 11 exp 22 xyxy xy p x y 22 2 222 2 11 exp2 2 1 21 xxyy xy xxyy px y 试求 12 D pp 21 D pp 解 1 121 2 log p x y D ppp x ydxdy px y 2 1 log 1 p x ydxdy 2222 1 22222 11 log 2 22 1 xyxxyy xyxxyy e p x ydxdy 111 22 22 222 2 1log2 log 2 1 1 ppp xyxy e EXEYEXY 2 2 2 1 log log 1 1 e 2 212 1 log px y D pppx ydxdy p x y 2 2 1 log 1 px ydxdy 2222 2 22222 11 log 2 2 1 2 xxyyxy xxyyxy e p x ydxdy 222 22 22 222 2 1log2 log 2 1 1 ppp xyxy e EXEYEXY 2 1 log 1 8 X Y 为二维联合高斯分布 其概率密度函数满足 22 2 22 X N0 Y 试求 当1 0 1 时的互信息I X Y 解 依题意可知 X Y均满足高斯分布 log log 2 nat 同理 log 2 nat 依题意有 1 2 1 exp 1 2 1 2 故 log log 2 log 2 1 2 log 2 1 2 2 log 2 1 nat log 2 log 2 log 2 1 log 1 1 0 bit 0 另解 当 0时 X与Y不相关 由于二者为高斯分布 从而独立 所以此时 0 当 1时 2 0 即X依概率 1 与Y处处相等 由于X Y为连续随机变量 故 同理 当 1时 X依概率 1 与 Y处处相等 9 Fano 不等式 令Pr 1 2 i Xip im 且 12 m ppp 则对X的最小差错概率的 预测为 1X 相应的差错概率为 1 1 e Pp 通过在给定差错 1 1 e pP 条件下 最大化 H p 12 m H p pp 找到 e P的下界 用 H p表示 解 在给定 e P的情况下 1 p也给定 通过最大化 X 的熵 来得到它关于 e P的上界 11 2 loglog m ii i H ppppp 11 2 logloglog m ii eee i ee pp ppPPP PP 32 m ee eee ppp H PPH PPP log 1 ee H PPm 当 23 m ppp相等时取等号 于是可以以差错概率 e P预测的 X 满足 log 1 ee H XH PPm 即无条件形式的 Fano 不等式 可以由此得到 e P的下界 1 log 1 log 1 e e H XH PH X P mm 10 考虑一个离散随机变量 X 取值空间为 12 n x xx 定义 的一个置换操作 S S 对应一个 1 n 的排列 1 n mm i im S xx 即由 操作 S 定义一个新的 随机变量 S X 操作把 X 的具体取值 i x变换成 i m x 于是概率分布满足 i im P S XxP Xx 这样的置换操作一共有 n 种 按照任意一种确定的 顺序记为 1 S 2 S n S 1 证明 任取操作 i S 有 X i H SH X 2 取前两个置换操作 1 S 2 S 考虑一个与 X 独立的随机变量 Z Z 为一个二 元随机变量 以 0 5 的概率取 0 0 5 的概率取 1 如下定义 2 SX 1 2 2 0 1 S XZ SX SXZ 当时 当时 试证 2 H SXH X 3 同样的方法定义 k SX 取前 k 个置换操作 1 k SS 考虑随机变量 Z Z 与 X 独立 同时 Z 为一个 k 元的随机变量 在 0 k 1 中等概分布 1 0 1 k k S XZ SX SXZk 当时 当时 试证 1 kk H SXH SX 4 n S在所有可能的置换操作中等概选取 计算 n SX的概率分布 以及 n H SX 解 1 置换操作没有改变分布 因此有 X i H SH X 2 解法一 设 1 X S的的分布为 1 n pp p 2 X S的分布为 1 n qq q 则 2 SX的分布为 2 rpq 于是由熵函数的上凸特性 2 2 HH H SXHH X pq r 解法二 2 2 2 2 12 0 0 1 1 11 22 H SXH SXZ p zH SXzp zH SXz H S XH SX H