信息论学习笔记（三）

发表于 2025-05-04 分类于计算机

前段时间查文献的时候，偶然看到了一些算法里涉及到了信息论的相关知识。信息论我在几年前通过看书自学过，时间太久有些忘了，正好趁此机会重新复习一下。

参考书籍：机械工业《信息论基础（原书第二版）》（ELEMENTS OF INFORMATION THEORY SECOND EDITION），作者Thomas M. Cover, Joy A. Thomas

渐近均分性

渐近均分性的概念与大数定理类似。对符合独立同分布(i.i.d.)的一组随机变量 $x_1, x_2, … x_n$ ，记 $p(x_1, x_2, … x_n)$ 为观察序列 $x_1, x_2, … x_n$ 出现的概率，则：

$\frac{1}{n}log \frac{1}{p(x_1, x_2, … x_n)} \approx H$

当 n 很大时，一个观察序列出现的概率 $p(x_1, x_2, … x_n)$ ~ $2^{-nH}$

如上图，全体序列的集合可以分成两个子集：典型集和非典型集

典型集: 样本熵近似于真实熵。我们主要关注这个，因为任何基于典型序列的性质都以高概率成立，并决定大样本的平均行为
非典型集：包含其他的序列

随机变量的收敛

给定一个随机变量序列 $x_1, x_2, … x_n$ ，该序列收敛于随机变量 X 有三种情况：

概率收敛：对 $\forall \epsilon > 0, Pr{|X_n - X| > \epsilon} \rightarrow 0$
均方收敛： $E[(X_n - X)^2] \rightarrow 0$
以概率1收敛(几乎处处收敛): $Pr{lim_{n \rightarrow \infty} x_n = x } = 1$

渐近均分性定理（AEP）及其证明

“渐近均分”→ “几乎一切事件都会人同等的意外”

定理1：若 $x_1, x_2, … x_n$ 为 i.i.d ~ $p(x)$, 则 $-\frac{1}{n}log p(x_1, x_2, … x_n) \rightarrow H$ （依概率），其中 $H = -\sum_i p(x) log p(x)$

定义：关于 p(x) 的典型集 $A_{\epsilon}^{(n)}$ (typical set) 是序列 ($x_1, x_2, … x_n$) $\in X^n$ 的集合, 且满足：
$2^{-n(H(x) + \epsilon)} \leq p(x_1, x_2, … x_n) \leq 2^{-n(H(x) - \epsilon)}$

$A_{\epsilon}^{(n)}$ 具如下性质：

定理2（关于典型集的一些性质）：典型集的概率近似为1，典型集中所有元素几乎是等可能的，典型集元素个数近似等于 $2^{nH}$ 。更详细的数学说明如下：

如果 ($x_1, x_2, … x_n$) $\in A_{\epsilon}^{(n)}$, 则 $H(X) - \epsilon \leq -\frac{1}{n} log p(x_1, x_2, … x_n) \leq H(x) + \epsilon$
当 n 充分大， $Pr{A_{\epsilon}^{(n)}} \geq 1 - \epsilon$
$|A_{\epsilon}^{(n)}| \leq 2^{n(H(x) + \epsilon)}$ (|A|为A中元素个数)
当 n 充分大, $|A_{\epsilon}^{(n)}| \geq (1 - \epsilon)2^{n(H(x) - \epsilon)}$

基于典型集的上述性质，我们可以提出一种数据编码方式（如下图）：

非典型集 → 编码 $\leq n log |x| + 1 bit$ → 并在序列编码的前面加1 → 用 $n log |x| + 2 bit$ 编码
典型集（$A_{\epsilon}^{(n)}: 2^{n(H + \epsilon)}$ 个元素） → 描述 $n(H + \epsilon) + 1 bit$ → 并在序列编码的前面加0 → 用 $n(H + \epsilon) + 2 bit$ 编码

AEP 的推论：数据压缩

对于序列 $x_1, x_2, … x_n$ ~ $p(x)$, i.i.d ，以 $x^n$ 表示这一序列。记 $l(x^n)$为 $x^n$ 的码字长度。

若 n 充分大，使得 $Pr{A_{\epsilon}^{(n)}} \geq 1 - \epsilon$

则码字长度的数学期望为：

$$
\begin{aligned}
E(l(x^n)) &= \sum_{x^n} p(x^n) l(x^n) \\
&= \sum_{x^n \in A_\varepsilon^{(n)}} p(x^n) l(x^n) + \sum_{x^n \notin A_\varepsilon^{(n)}} p(x^n) l(x^n) \\
&\leq \sum_{x^n \in A_\varepsilon^{(n)}} p(x^n) [n(H + \varepsilon) + 2] + \sum_{x^n \notin A_\varepsilon^{(n)}} p(x^n) [n(\log |X| + \varepsilon) + 2] \\
&= Pr\left\{A_\varepsilon^{(n)}\right\} [n(H + \varepsilon) + 2] + Pr\left\{A_\varepsilon^{(n)^c}\right\} [n(\log |X| + \varepsilon) + 2] \\
&\leq n(H + \varepsilon) + \varepsilon n(\log |X| ) + 2 \\
&= n(H + \varepsilon’)\\
\end{aligned}
$$

其中 $\varepsilon’=\varepsilon+\varepsilon \text{log}|X|+\frac{2}{n}$ ，适当取 $\varepsilon$ 和 $n$ ，可以使 $\varepsilon’$ 任意小。

定理：设 $X^n$ 为服从 $p(x)$ 的 i.i.d 序列, $\epsilon > 0$, ヨ一个编码将长度为 n 的序列 $x^n$ 映射为比特串, 映射是1-1的(可逆)，对于充分大的 n, 有 $E[\frac{1}{n}l(x^n)] \leq H(X) + \epsilon$ 。从平均意义上，用 nH(X) bit 可表示序列 $X^n$ 。

最小概率集：设 $x_1, x_2, … x_n$ ~ $p(x)$, i.i.d, 对 $0 < \delta < \frac{1}{2}$, 设 $B_{\delta}^{(n)}\subset X^n$ 为使 $Pr{B_{\delta}^{(n)}} \geq 1 - \delta$ 成立的最小集合，则 $|B_{\delta}^{(n)}| \dot{=} 2^{nH}$ ，其中 $\dot{=}$ 代表 $|B_{\delta}^{(n)}|$ 和 $2^{nH}$ 在一阶指数意义下相等。