估计仍有不确定性
即使译码器收到一些信息,仍可能出错。错误概率如何限制原符号剩余的不确定性?我们证明有限字母表的一个界,并说明理解它所需的假设。
令 取值于大小为 的集合 , 为有限值观察。确定性估计器 取值于 。若 ,令 ,否则 ;设 。对数以二为底,,端点值由连续延拓定义。
定理 12.1.1
(Fano 不等式:有限情况)
对任何这样的联合分布与估计器,
证明
(先分出错误标记,再取平均)
固定概率为正的观察值 。由于 由 和 确定,条件熵链式法则给出
对每个条件概率为正的分支:当 ,已知 ,故其熵为零;当 , 限于至多 个其他符号,熵至多为 。零概率分支的加权贡献为零。令 ,包括端点情况,得到
对 取平均。由 的凹性及 Jensen 不等式,。熵最大值界给出 。不可能观察值的项没有贡献。
证明透视
错误标记、估计器的取值范围与凹性在哪里起作用
证明靠三个事实。第一, 是 的函数,所以加入它不增加熵:,这使链式法则的拆分成为恒等式而非不等式。第二,估计器取值于 :在错误分支上 避开 ,这正是 而非 的来源。第三,取平均一步用到 的凹性,所以当各条件错误率 不相同时,此步会失去精确性。等号成立当且仅当每个 都等于 ,而且在每个概率为正的错误分支上, 在 以外的 个符号上均匀分布。
达到等号的四符号例子
例题 12.1.2
(对称错误可达到此界)
令 在 上均匀。给定 时, 的概率为 ,其他三个值各以概率 出现。取 。则 。由对称性, 均匀;对每个观察值 , 的条件分布在 上的概率为 ,在其他符号上各为 。因此
此处第一个不等式取等号,第二个较松的界为 比特。
若错误分布不均匀,第一个不等式便是严格的。
例题 12.1.3
(集中的错误留下差距)
令 在 上均匀, 的概率为 , 的概率为 ,并取 。则 ;由对称性 均匀,而给定 时, 的概率为 , 的概率为 。因此
差距恰为 比特:在错误分支上 已被确定,所以允许剩下 个符号的那一项完全没有用上。
正确理解不等式方向
若 ,定理给出 :估计器几乎必然恢复 。在此有限情况下,逆命题对某个估计器也成立:条件熵为零时,每个正概率观察值都确定一个 值。但它不必对每个估计器成立,因为估计器可以故意忽略或反转观察。
反例模式
零不确定性不代表每个译码器正确
令 为公平比特,,刻意选错误估计器 。则 ,但 。Fano 界仍成立: 时右边为 。不能仅由低条件熵推断某个译码器的错误率低,也不能不检查估计器及相关范围就反解此界。
此界没有声称估计器最优、没有证明编码定理,也没有给出未指定信道的精确错误率。它适用于所述有限联合分布和所选估计器。反过来,若已知条件熵大于某错误率代入右边的值,该错误率便被排除。
例题 12.1.4
(不含任何信息的观察)
令 在 上均匀, 与 独立,于是 比特。令 。其导数 在 时为正,所以 在 上递增,而
因此 Fano 界 迫使每个估计器都有 ;例如 排除了错误率 。固定猜一个符号的错误率正是 ,所以在这个退化情形下此界取等号。
常见错误
(丢掉二元熵一项)
看似自然的简化 是错的。在四符号例子中 比特,而 。是否出错本身也不确定, 正是为这个标记付出的代价。
常见错误
(带有删除输出的估计器)
证明需要 。若译码器可输出符号 ,则出错时 个值都仍有可能。取公平比特 、与之独立的 ,以及总是输出 的译码器,则 、,但 。允许删除输出时,应把 换成 。
习题
快速检查
(对 ,化简第一个 Fano 界。 时它说明什么?)
计算 。
解答 · 答案
因 ,有 。零错误时右边为零。
快速检查
(在四符号例子中,计算 并判断第一个界是否取等号。)
把每个条件错误分布与等号条件比较。
解答 · 答案
,第一个界取等号,因为每个条件错误分布在其他三个符号上均匀,且所有 都是 。
快速检查
(若 是公平比特,而估计器总输出 ,求 和 。)
解答 · 答案
决定 ,所以 ;而估计器总是出错,所以 。此界成为 。
快速检查
(当 时,为什么可用 限制 ?)
数一数该分支上 的可能取值。
解答
给定 且出错时, 只能是与 不同的 个值之一;支撑于至多这么多符号的分布,其熵至多为其数目的对数。若事件概率为零,其加权贡献为零。
延伸阅读
MIT 开放课程信息论第二讲 讨论 Fano 引理。