Information Theory

信息论要点笔记📒

催更｜辅导｜私塾兼职｜联系偷偷：LifeGoesOn_Rio

1. 信息论基础

1.1 信息量

在信息论中，“信息量”用来衡量一个事件发生时，我们获得了多少新的信息。
核心直觉是：

• 事件越罕见，发生时带来的信息越大。
• 事件越常见，发生时带来的信息越少。
• 事件必然发生（概率 = 1）时，它带来的信息是 0（因为没学到新东西）。

举个例子：

• 你早上看到太阳升起，这事发生概率几乎 1 → 信息量很小（甚至是 0）。
• 你在北京的冬天突然看到有人穿短袖，这事概率很低 → 信息量很大。

---

信息论的创始人 Shannon（香农） 给信息量下的定义是：

$$
I(x) = -\log_b P(x)
$$

其中：

• $P(x)$：事件 $x$ 发生的概率
• $b$：对数的底（常用 2 表示以“比特”为单位，也可以用自然对数表示“纳特”）

---

香农选择对数有几个原因：

1. 可加性
   如果两个事件是独立的：

   $$
   I(x,y) = I(x) + I(y)
   $$

   用概率乘法定律：

   $$
   P(x,y) = P(x)P(y)
   $$

   取对数就变成加法，数学上很优雅。

2. 方便量纲统一
   用 $\log_2$ 时，单位是 bit（比特），方便和二进制系统关联。

---

单位

• 比特（bit）：底为 2 的对数
• 纳特（nat）：底为 $e$ 的对数
• 哈特莱（hartley）：底为 10 的对数

举例：
如果一个事件的概率是 $\frac12$，它的信息量是：

$$
I = -\log_2 \frac12 = 1 \ \text{bit}
$$

意思是：得知该事件发生，等价于获得 1 个二进制是/否问题的答案。

---

信息量的特点

1. 非负性：$I(x) \ge 0$
2. 概率越小 → 信息量越大
3. 确定性事件（$P = 1$）的信息量为 0
4. 对稀有事件（如 $P = 0.0001$），信息量很大。

---

一个生活类比

把“信息量”想象成惊讶程度：

• 天气预报说今天 100% 下雨 → 你出门看到雨，不惊讶 → 信息量 = 0
• 天气预报说今天只有 10% 下雨 → 结果你出门被淋了 → 信息量很大（学到了“天气预报错了”）。

1.2 平均信息量（Average Information Content）

在信息论中，平均信息量也叫熵（Entropy），是衡量一个随机变量（Random Variable）平均能带来多少信息的指标。它反映了系统的不确定性（Uncertainty）。

公式：

$$
H(X) = - \sum_{i=1}^n P(x_i) \log_b P(x_i)
$$

其中：

• $X$：离散型随机变量（Discrete Random Variable）
• $P(x_i)$：事件 $x_i$ 发生的概率（Probability）
• $b$：对数底（Logarithm Base），常用 $b = 2$（单位 bit）

---

直观理解

• 如果所有事件概率相等（Uniform Distribution），熵最大（最不确定）。
• 如果某个事件概率接近 1，熵很小（系统几乎已知）。

---

假设抛一个公平硬币（Fair Coin）：

$$
P(\text{正}) = 0.5, \quad P(\text{反}) = 0.5
$$

$$
H = -[0.5 \log_2 0.5 + 0.5 \log_2 0.5] = 1 \ \text{bit}
$$

意思是：每次抛币平均获得 1 比特的信息。

1.3 二元信息熵（Binary Entropy）

二元信息熵（Binary Entropy）是指一个二元信源（Binary Source）的平均信息量（Average Information Content）。
这种信源只有两种可能输出：

$$
X \in {0, 1}
$$

它的熵由单个参数 $p = P(X = 1)$ 决定。

---

对于概率 $p$（Probability）和 $1-p$ 的二元随机变量（Binary Random Variable）：

$$
H(p) = - p \log_2 p - (1-p) \log_2 (1-p)
$$

其中：

• $H(p)$：二元熵（Binary Entropy）
• $p$：取值为 1 的概率（Success Probability）
• $1-p$：取值为 0 的概率（Failure Probability）
• $\log_2$：以 2 为底的对数（Logarithm Base 2）

---

性质

1. 对称性（Symmetry）：

   $$
   H(p) = H(1-p)
   $$

   因为交换 0 和 1 不影响不确定性。

2. 最大值（Maximum）：
   当 $p = 0.5$ 时：

   $$
   H(0.5) = -0.5 \log_2 0.5 - 0.5 \log_2 0.5 = 1 \ \text{bit}
   $$

   这是不确定性最大的情况（完全随机的二元信源）。

3. 最小值（Minimum）：
   当 $p = 0$ 或 $p = 1$ 时，

   $$
   H = 0
   $$

   因为输出是确定的，没有信息量。

---

直观理解

• 当一枚硬币（Coin）是公平的（$p = 0.5$），每次抛掷带来的信息量最大：1 bit
• 当一枚硬币几乎总是正面朝上（$p$ 接近 1），信息量很小，因为结果几乎可预测。

1.4 归一化熵（Normalized Entropy）

$$
h(s) = \frac{H(s)}{\log_2 M}
$$

是归一化熵（Normalized Entropy）的形式，有时候也叫相对熵（Relative Entropy，另一种用法）。

这个公式的意思是：

• $H(s)$：信源（Source）的熵（Entropy），表示平均每个符号的信息量。
• $M$：信源字母表（Alphabet）的符号总数（可能取值的数量）。
• $\log_2 M$：当信源概率完全均匀（Uniform Distribution）时的最大熵（Maximum Entropy）。
• $h(s)$：归一化熵（Normalized Entropy），即实际熵占最大熵的比例。

---

熵的最大值出现在概率均匀时：

$$
H_{\max} = \log_2 M
$$

所以，为了得到一个 0 到 1 之间 的量，人们用：

$$
h(s) = \frac{H(s)}{\log_2 M}
$$

• 如果 $h(s) = 1$：信源是完全均匀的（最不可预测）。
• 如果 $h(s) = 0$：信源是完全确定的（可预测，没有信息量）。
• 介于 0 和 1 之间：有一定规律性，但不是完全可预测。

---

假设信源字母表 $M = 4$，符号概率：

$$
P = {0.5, 0.25, 0.25, 0}
$$

计算：

$$
H(s) = -[0.5\log_2 0.5 + 0.25\log_2 0.25 + 0.25\log_2 0.25]
$$

$$
H(s) = 1.5\ \text{bits}
$$

最大熵：

$$
\log_2 4 = 2\ \text{bits}
$$

归一化熵：

$$
h(s) = \frac{1.5}{2} = 0.75
$$

意思是：这个信源的随机性相当于最随机信源的 75%。

---

1.5 冗余度（Redundancy）

冗余度（Redundancy）表示一个信源（Source）在编码或符号序列中，不携带新信息的部分所占的比例。
它描述了信源中“可预测性”（Predictability）的大小。

换句话说，冗余度 = 1 − 随机性程度。
在很多情况下，信源的符号分布并不是均匀的，因此它的熵低于最大可能的熵，差值就是冗余造成的。

---

假设信源字母表（Alphabet）大小为 $M$，

• 实际熵：$H(s)$（Entropy）
• 最大熵：$H_{\max} = \log_2 M$（Maximum Entropy）

归一化形式的冗余度（Normalized Redundancy）：

$$
R = 1 - \frac{H(s)}{\log_2 M}
$$

其中：

• $R$：冗余度（Redundancy）
• $\frac{H(s)}{\log_2 M}$：归一化熵（Normalized Entropy），也叫相对熵（Relative Entropy，在另一种定义下）

---

性质

1. 范围：

   $$
   0 \le R \le 1
   $$

   • $R = 0$：完全随机，无冗余
   • $R = 1$：完全确定，全是冗余

2. 解释：

   • 高冗余度意味着数据中有较多的可预测性，容易压缩（Compressibility）
   • 低冗余度意味着数据更随机，压缩率低

---

例子：假设字母表大小 $M = 4$：
最大熵：

$$
H_{\max} = \log_2 4 = 2\ \text{bits}
$$

某信源熵：

$$
H(s) = 1.5\ \text{bits}
$$

冗余度：

$$
R = 1 - \frac{1.5}{2} = 0.25
$$

这意味着信源中有 25% 的信息是冗余的，可被预测或压缩掉。

---

应用

• 自然语言（Natural Language）：英语的冗余度大约 50%，这使得我们即使漏掉一些字母，也能推断出完整单词。
• 通信系统（Communication Systems）：适当增加冗余（如校验码 Error-Detecting Codes）可以提高抗噪能力。
• 数据压缩（Data Compression）：压缩的过程本质上是消除冗余。

2. 熵的计算

2.1 联合自信息量（Joint Self-Information）

联合自信息量（Joint Self-Information）是衡量两个随机变量同时取到特定值这一事件所包含的信息量。
它是单个事件自信息量的推广，定义在联合事件（Joint Event）上。

如果我们有两个随机变量 $X$ 和 $Y$，某一次观测的结果是 $(x, y)$，则其联合自信息量为：

$$
I(x, y) = -\log_b p(x, y)
$$

其中：

• $p(x, y)$：联合概率（Joint Probability）
• $b$：对数底（Logarithm Base），常用 $b = 2$（单位 bit）或 $b = e$（单位 nat）

---

解释

• 概率越小的联合事件，信息量越大（更“惊喜”）。

• 如果 $X$ 和 $Y$ 独立：

  $$
  p(x, y) = p(x) \cdot p(y) \quad\Rightarrow\quad I(x, y) = I(x) + I(y)
  $$

  这表明独立事件的联合自信息量等于它们单独信息量的和。

---

与联合熵的关系

联合熵（Joint Entropy）其实是联合自信息量的期望值：

$$
H(X, Y) = \mathbb{E}[I(X, Y)] = -\sum_{x}\sum_{y} p(x, y) \log p(x, y)
$$

所以：

• 联合自信息量 → 单次事件的“惊讶度”
• 联合熵 → 平均“惊讶度”

---

假设：

• $X$ 取值 ${0, 1}$
• $Y$ 取值 ${a, b}$
  联合概率表（Joint Probability Table）为：

	$a$	$b$
0	0.5	0.25
1	0.125	0.125

例子：事件 $(1, b)$ 的联合自信息量：

$$
I(1, b) = -\log_2 (0.125) = -\log_2 \left(\frac{1}{8}\right) = 3 \ \text{bits}
$$

说明这个事件发生时，我们获得了 3 比特的新信息。

---

2.2 条件自信息量（Conditional Self-Information）

条件自信息量（Conditional Self-Information）描述了在已知一个事件发生的前提下，另一个事件发生所带来的信息量。

如果随机变量 $X$ 取到值 $x$，并且我们已知 $Y = y$ 已经发生，那么条件自信息量定义为：

$$
I(x \mid y) = -\log_b p(x \mid y)
$$

其中：

• $p(x \mid y)$：条件概率（Conditional Probability）
• $b$：对数底（Logarithm Base），通常取 2（单位 bit）或 $e$（单位 nat）

---

• 条件自信息量表示在额外信息（已知 $Y=y$）下，我们需要多少信息来确定 $X=x$。

• 如果 $X$ 和 $Y$ 独立（Independent），则：

  $$
  p(x \mid y) = p(x) \quad\Rightarrow\quad I(x \mid y) = I(x)
  $$

  已知 $Y$ 不会减少对 $X$ 的不确定性。

• 如果 $Y$ 能确定 $X$，则 $p(x \mid y) = 1$，此时：

  $$
  I(x \mid y) = 0
  $$

  说明已知 $Y$ 后不需要额外信息来确定 $X$。

---

条件熵（Conditional Entropy）是条件自信息量的期望值：

$$
H(X\mid Y) = -\sum_{y}\sum_{x} p(x,y)\log p(x\mid y).
$$

---

举例假设：

• $X \in {A, B}$
• $Y \in {1, 2}$
  并且已知：

$$
p(X=A \mid Y=1) = 0.25
$$

则：

$$
I(A \mid 1) = -\log_2 (0.25) = 2 \ \text{bits}
$$

意思是：在已知 $Y=1$ 的情况下，确定 $X=A$ 仍然需要 2 比特的信息。

---

2.3 联合熵（Joint Entropy）

联合熵（Joint Entropy）描述了两个随机变量（Random Variables）$X$ 和 $Y$ 同时取值时的平均信息量（Average Information Content）。

它是对联合概率分布（Joint Probability Distribution）上联合自信息量（Joint Self-Information）的期望：

$$
H(X, Y) = - \sum_{x} \sum_{y} p(x, y) \log_b p(x, y)
$$

其中：

• $p(x, y)$：联合概率（Joint Probability）
• $b$：对数底（Logarithm Base），$b=2$ 时单位是 bit，$b=e$ 时单位是 nat。

---

• 联合熵度量的是观察到整个事件对 $(X, Y)$ 所需的平均信息量。

• 如果 $X$ 和 $Y$ 独立（Independent），则：

  $$
  H(X, Y) = H(X) + H(Y)
  $$

• 如果 $X$ 完全由 $Y$ 决定（Deterministic Relationship），那么：

  $$
  H(X, Y) = H(Y) = H(X)
  $$

  因为知道一个变量就完全知道另一个变量，不会增加不确定性。

---

性质

1. 非负性（Non-Negativity）

   $$
   H(X, Y) \ge 0
   $$

2. 上界（Upper Bound）

   $$
   H(X, Y) \le H(X) + H(Y)
   $$

   等号在独立时成立。

3. 链式法则（Chain Rule）

   $$
   H(X, Y) = H(X) + H(Y \mid X)
   $$

   或：

   $$
   H(X, Y) = H(Y) + H(X \mid Y)
   $$

   表示联合熵可以分解为单个熵 + 条件熵。

---

举例

假设：

X/Y	y₁	y₂
x₁	0.25	0.25
x₂	0.25	0.25

则：

$$
H(X, Y) = -\sum_{x,y} 0.25 \log_2 0.25 = -4 \times 0.25 \times (-2) = 2 \ \text{bits}
$$

说明每次观察到 $(X, Y)$ 对需要 2 比特的信息。

---

2.4 条件熵（Conditional Entropy）

条件熵是用来衡量在已知一个随机变量 $Y$ 的情况下，另一个随机变量 $X$ 的不确定性。

设 $X, Y$ 是两个离散型随机变量，联合分布为 $p(x,y)$，则 条件熵 定义为：

$$
H(X \mid Y) = - \sum_{y} p(y) \sum_{x} p(x \mid y) \log p(x \mid y)
$$

也可以写作期望形式：

$$
H(X \mid Y) = \sum_{y} p(y) H(X \mid Y=y)
$$

其中：

• $H(X \mid Y=y)$ 表示在 $Y=y$ 的条件下，$X$ 的熵。
• $H(X \mid Y)$ 表示整体上 $X$ 在已知 $Y$ 的情况下的不确定性。

---

含义（Intuition）

• $H(X)$ 表示 $X$ 的原始不确定性。
• $H(X \mid Y)$ 表示在知道 $Y$ 的情况下，$X$ 还剩下多少不确定性。

👉 所以 条件熵就是已知 $Y$ 后，$X$ 还包含多少信息的不确定性。

例如：

• 如果 $X$ 和 $Y$ 完全独立，则 $H(X \mid Y) = H(X)$。
• 如果 $X$ 由 $Y$ 唯一确定，则 $H(X \mid Y) = 0$。

---

常用公式（Formulas）

1. 与联合熵的关系

   $$
   H(X,Y) = H(Y) + H(X \mid Y) = H(X) + H(Y \mid X)
   $$

   这说明：联合熵可以分解成一个变量的熵加上另一个变量的条件熵。

2. 与互信息的关系

   $$
   I(X;Y) = H(X) - H(X \mid Y) = H(Y) - H(Y \mid X)
   $$

   互信息（Mutual Information）就是熵的减少量，即知道 $Y$ 以后 $X$ 的不确定性减少了多少。

---

假设有一个二元变量：

• $X$ 表示天气是否下雨：$X={0=\text{不下雨}, 1=\text{下雨}}$
• $Y$ 表示是否打伞：$Y={0=\text{不打伞}, 1=\text{打伞}}$

设分布为：

• $p(X=1)=0.3, ; p(X=0)=0.7$
• $p(Y=1 \mid X=1)=0.9, ; p(Y=0 \mid X=1)=0.1$
• $p(Y=1 \mid X=0)=0.2, ; p(Y=0 \mid X=0)=0.8$

我们要计算 $H(X \mid Y)$。

步骤：

1. 先求边际分布 $p(Y)$：

   $$
   p(Y=1) = p(X=1)p(Y=1 \mid X=1) + p(X=0)p(Y=1 \mid X=0)
   $$

   $$
   = 0.3 \times 0.9 + 0.7 \times 0.2 = 0.27 + 0.14 = 0.41
   $$

   同理：

   $$
   p(Y=0) = 0.59
   $$

2. 再求条件分布 $p(X \mid Y)$：
   例如

   $$
   p(X=1 \mid Y=1) = \frac{p(X=1,Y=1)}{p(Y=1)} = \frac{0.27}{0.41} \approx 0.6585
   $$

   $$
   p(X=0 \mid Y=1) = 1 - 0.6585 = 0.3415
   $$

   同理可求 $p(X \mid Y=0)$。

3. 计算条件熵：

   $$
   H(X \mid Y) = \sum_y p(y) H(X \mid Y=y)
   $$

   代入数值可得结果。

👉 这表示：当我们知道一个人是否打伞（$Y$）时，对天气是否下雨（$X$）的不确定性减少了。

---

性质（Properties）

1. 非负性：

   $$
   H(X \mid Y) \geq 0
   $$

2. 小于等于原熵：

   $$
   H(X \mid Y) \leq H(X)
   $$

   （已知信息只会减少不确定性，不会增加）

3. 独立时等号成立：

   $$
   H(X \mid Y) = H(X), \quad \text{若 $X$ 与 $Y$ 独立}
   $$

---

✨总结：

• 条件熵 $H(X \mid Y)$ = 已知 $Y$ 后，$X$ 还剩下的不确定性。
• 它是联合熵和互信息的重要桥梁。
• 在通信、机器学习、统计建模里，用来度量“一个变量对另一个变量的不确定性削减”。

---

2.5 链式法则证明

2.5.1 二元情形的证明

命题：对离散随机变量 $X,Y$，有

$$
H(X,Y)=H(Y)+H(X\mid Y).
$$

证明（从定义出发）：

$$
\begin{aligned}
H(X,Y)
&= -\sum_{x,y} p(x,y),\log p(x,y) \
&= -\sum_{x,y} p(x,y),\log\big(p(y),p(x\mid y)\big) \qquad (\text{乘法法则 } p(x,y)=p(y)p(x|y))\
&= -\sum_{x,y} p(x,y),\log p(y);-;\sum_{x,y} p(x,y),\log p(x\mid y) \
&= -\sum_{y}!\Big(\sum_{x}p(x,y)\Big)\log p(y);-;\sum_{y}!\sum_{x} p(y),p(x\mid y),\log p(x\mid y) \
&= -\sum_{y} p(y),\log p(y);-;\sum_{y} p(y)\Big(\sum_{x} p(x\mid y),\log p(x\mid y)\Big) \
&= H(Y);+;\sum_{y} p(y),H(X\mid Y=y) \
&= H(Y)+H(X\mid Y).
\end{aligned}
$$

证毕。

同样也可写成期望形式：
$H(X,Y)=\mathbb{E}[-\log p(X,Y)] = \mathbb{E}[-\log p(Y)] + \mathbb{E}[-\log p(X\mid Y)] = H(Y)+H(X\mid Y)$。

---

2.5.2 推广到 $n$ 个变量

命题：对离散随机变量 $X_1,\dots,X_n$，

$$
H(X_1,\dots,X_n)=\sum_{i=1}^{n} H\big(X_i \mid X_1,\dots,X_{i-1}\big).
$$

证明思路：数学归纳法或反复应用二元链式法则。

• 当 $n=2$ 时即上一节已证。
• 假设对 $n-1$ 个变量成立，则

$$
\begin{aligned}
H(X_1,\dots,X_n)
&= H(X_1,\dots,X_{n-1}) + H\big(X_n \mid X_1,\dots,X_{n-1}\big) \
&= \sum_{i=1}^{n-1} H\big(X_i \mid X_1,\dots,X_{i-1}\big) + H\big(X_n \mid X_1,\dots,X_{n-1}\big).
\end{aligned}
$$

归纳完成。

---

2.5.3 带条件的链式法则

对任意随机变量（或变量组）$Z$：

$$
H(X,Y\mid Z)=H(Y\mid Z)+H(X\mid Y,Z),
$$

以及

$$
H(X_1,\dots,X_n\mid Z)=\sum_{i=1}^{n} H\big(X_i \mid X_1,\dots,X_{i-1},Z\big).
$$

证明：把所有概率替换为条件于 $Z$ 的条件概率（如 $p(x,y\mid z)$），逐点固定 $Z=z$ 后对上一节的证明按 $z$ 加权求期望即可。

---

2.5.4 几个常用等价式与推论

1. 互信息展开

   $$
   I(X;Y)=H(X)-H(X\mid Y)=H(Y)-H(Y\mid X).
   $$

   由链式法则和 $H(X,Y)=H(X)+H(Y)-I(X;Y)$ 互相推出。

2. 三者互信息的链式展开

   $$
   I(X;Y,Z)=I(X;Y)+I(X;Z\mid Y).
   $$

3. 独立与确定性的极端

   • 若 $X\perp Y$，则 $H(X\mid Y)=H(X)$，链式法则退化为 $H(X,Y)=H(X)+H(Y)$。
   • 若 $X$ 由 $Y$ 确定，则 $H(X\mid Y)=0$，于是 $H(X,Y)=H(Y)$。

---

2.5.5 连续情形（差分熵）提示

对连续随机变量，差分熵 $h(\cdot)$ 也满足形式相同的链式法则：

$$
h(X,Y)=h(Y)+h(X\mid Y),
$$

证明同样基于密度的乘法法则 $f_{X,Y}(x,y)=f_Y(y)f_{X\mid Y}(x\mid y)$ 与积分版的推导。需要注意差分熵可以为负，但链式关系依然成立。

---

小结：链式法则本质是把联合分布分解为连乘的条件分布（乘法法则），再把 $-\log$ 作用到连乘上变为求和，最后用“先求条件熵、再按条件加权平均”的结构完成。

---

2.6 互信息量（Mutual Information）

设 $X, Y$ 是两个随机变量，联合分布为 $p(x,y)$，边际分布为 $p(x), p(y)$。
互信息量定义为：

$$
I(X;Y) = \sum_{x}\sum_{y} p(x,y)\log \frac{p(x,y)}{p(x)p(y)}.
$$

等价写法：

• 由熵定义：

$$
I(X;Y) = H(X) - H(X\mid Y).
$$

• 对称性：

$$
I(X;Y) = H(Y) - H(Y\mid X).
$$

• 与联合熵关系：

$$
I(X;Y) = H(X)+H(Y)-H(X,Y).
$$

---

含义（Intuition）

• 熵 $H(X)$ 表示 $X$ 的不确定性。
• 条件熵 $H(X\mid Y)$ 表示已知 $Y$ 后 $X$ 还剩下的不确定性。
• 互信息 $I(X;Y)$ = 不确定性的减少量 = $Y$ 对 $X$ 提供的信息量。

👉 换句话说：
互信息衡量的是 $X$ 与 $Y$ 之间的相关性，即知道 $Y$ 能减少多少关于 $X$ 的不确定性。

---

性质（Properties）

1. 非负性

   $$
   I(X;Y) \geq 0
   $$

   且当且仅当 $X, Y$ 独立时，$I(X;Y)=0$。
   （证明基于相对熵： $I(X;Y)=D_{\text{KL}}(p(x,y)\parallel p(x)p(y))$）。

2. 对称性

   $$
   I(X;Y) = I(Y;X).
   $$

3. 上界

   $$
   I(X;Y) \leq \min{H(X), H(Y)}.
   $$

   （你最多只能学到对方熵那么多信息。）

4. 链式法则（多变量）

   $$
   I(X;Y,Z) = I(X;Y) + I(X;Z\mid Y).
   $$

5. 条件互信息

   $$
   I(X;Y\mid Z) = H(X\mid Z) - H(X\mid Y,Z).
   $$

---

假设还是上次的“天气（下雨与否）– 打伞与否”的例子：

• $X=$ 天气是否下雨（1=下雨, 0=不下雨）。
• $Y=$ 是否打伞（1=打伞, 0=不打伞）。

我们之前算过：

• $H(X) \approx 0.881$ bits
• $H(X\mid Y)\approx 0.551$ bits

所以：

$$
I(X;Y)=H(X)-H(X\mid Y)\approx 0.881-0.551=0.330\ \text{bits}.
$$

这意味着：知道“是否打伞”能减少约 0.33 bit 的“下雨不确定性”。

---

互信息可以看成两个熵的交集：

H(X)      H(Y)
  ●---------●
   \       /
    \ I(X;Y)

• 圈的大小代表不确定性（熵）。
• 重叠部分就是互信息。
• 整个区域的并集就是联合熵 $H(X,Y)$。

---

1. 特征选择：在机器学习中，用互信息衡量一个特征对目标变量的信息贡献。
2. 通信系统：互信息衡量信道输入和输出的相关程度，最大化互信息得到信道容量。
3. 独立性检验：如果 $I(X;Y)=0$，就可以判定 $X,Y$ 独立。

---

✅ 总结：

• 互信息 $I(X;Y)$ = 已知 $Y$ 后，$X$ 的不确定性减少量。
• 本质上是相对熵 $D_{\text{KL}}(p(x,y),|,p(x)p(y))$。
• 它量化了“两个变量共享的信息量”。

2.7 互信息量与熵的证明

下面给出几种等价而常用的严格推导，把互信息与熵的公式互相“推”出来。默认对数为 $\log_2$。

---

2.6.1 从互信息的“比值定义”推到熵恒等式

定义（离散型）：

$$
I(X;Y)=\sum_{x,y}p(x,y),\log\frac{p(x,y)}{p(x),p(y)}.
$$

把对数拆成和于是得到

$$
\boxed{I(X;Y)=H(X)+H(Y)-H(X,Y)}.
$$

再配合联合熵链式法则 $H(X,Y)=H(Y)+H(X\mid Y)$，立刻推出另外两条等价式：

$$
\boxed{I(X;Y)=H(X)-H(X\mid Y)}
\qquad\text{以及}\qquad
\boxed{I(X;Y)=H(Y)-H(Y\mid X)}.
$$

---

2.6.2 从“相对熵视角”一行证明

把互信息写成相对熵（KL 散度）：

$$
I(X;Y)=D_{\mathrm{KL}}\bigl(p_{X,Y},|,p_X p_Y\bigr)
=\sum_{x,y}p(x,y)\log\frac{p(x,y)}{p(x)p(y)}.
$$

按上式同样展开即可得到
$I(X;Y)=H(X)+H(Y)-H(X,Y)$
以及前述两条差分式
$I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)$。

顺便可见 非负性 与 独立当且仅当互信息为 0：

$$
I(X;Y)=D_{\mathrm{KL}}(p_{X,Y},|,p_Xp_Y)\ge 0,
\quad
=0 \iff p_{X,Y}=p_Xp_Y.
$$

---

2.6.3 “从互信息生成熵”：$H(X)=I(X;X)$

把 $Y$ 取成 $X$ 本身（“自互信息”）：

$$
\begin{aligned}
I(X;X)
&=\sum_x p(x,x)\log\frac{p(x,x)}{p(x),p(x)}
=\sum_x p(x)\log\frac{p(x)}{p(x)^2}
=\sum_x p(x)\log\frac{1}{p(x)}\
&=-\sum_x p(x)\log p(x)
=\boxed{H(X)}.
\end{aligned}
$$

这给出一个优雅结论：熵就是变量与自身的互信息。

---

2.6.4 从链式法则侧推（等价回路）

由链式法则

$$
H(X,Y)=H(Y)+H(X|Y),
$$

代回第 1) 式 $I(X;Y)=H(X)+H(Y)-H(X,Y)$ 得

$$
I(X;Y)=H(X)-H(X|Y),
$$

同理交换 $X,Y$ 得另一式。三者互为等价环。

---

2.6.5 连续型（差分熵）提示

对连续变量（密度 $f$），定义

$$
I(X;Y)=\int f_{X,Y}(x,y)\log\frac{f_{X,Y}(x,y)}{f_X(x)f_Y(y)},\mathrm{d}x,\mathrm{d}y,
$$

同样可得

$$
I(X;Y)=h(X)+h(Y)-h(X,Y)=h(X)-h(X|Y)=h(Y)-h(Y|X),
$$

注意差分熵 $h(\cdot)$ 可为负，但上述恒等式依旧成立。

---

• 由定义 $I=\sum p\log\frac{p}{pp}$ 直接代数展开，就得到

  $$
  I(X;Y)=H(X)+H(Y)-H(X,Y)=H(X)-H(X|Y)=H(Y)-H(Y|X).
  $$

• 由 $I(X;X)$ 能反推出熵的标准公式 $H(X)=-\sum p\log p$。

• 由 KL 视角立即得到非负性与独立性判据。

---

2.8 离散无记忆信源及其扩展

在信息论中，研究的对象之一就是 信源（source）。信源就是信息产生的来源，比如文字、语音、视频信号等等。为了分析和建模，我们通常对信源进行数学抽象。

2.8.1 离散信源（Discrete Source）

• 定义：
  一个信源在每个离散时刻 $t=1,2,3,\dots$ 输出一个符号 $X_t$，这些符号取自一个有限或可数的字母表（alphabet） $\mathcal{X} = {x_1, x_2, \dots, x_m}$。

  信源输出的序列为：

  $$
  X_1, X_2, X_3, \dots
  $$

• 信源的统计特性：
  信源可以用 符号的概率分布 来描述：

  $$
  P(X = x_i) = p_i, \quad i=1,2,\dots,m, \quad \sum_{i=1}^m p_i = 1
  $$

---

2.8.2 无记忆信源（Memoryless Source）

• 定义：
  如果一个信源在每个时刻输出的符号 相互独立，并且都服从同一个概率分布 $P(X)$，则称为 无记忆信源。

  也就是说：

  $$
  P(X_1 = x_{i_1}, X_2 = x_{i_2}, \dots, X_n = x_{i_n}) = \prod_{k=1}^n P(X_k = x_{i_k})
  $$

• 含义：

  • “无记忆”表示：信源在某个时刻输出的符号，不依赖于过去输出的符号。
  • 常见的例子：抛硬币、掷骰子、文本中独立的字母序列（不考虑语言结构）。

---

2.8.3 信源扩展（Source Extension）

• 动机：
  为了更好地分析信源信息量，我们不仅可以看单个符号，还可以看“符号块”（block）。

• 定义：
  将无记忆信源的输出分组，每 $n$ 个符号作为一个“超级符号（super-symbol）”，组成一个新的扩展信源，称为 $n$ 阶扩展信源（$n$-th extension source）。

  例如：原始信源符号为 $X$，其字母表为 $\mathcal{X}={x_1, \dots, x_m}$，那么：

  • $n$ 阶扩展信源的字母表为：

    $$
    \mathcal{X}^n = { (x_{i_1}, x_{i_2}, \dots, x_{i_n}) \mid x_{i_k} \in \mathcal{X} }
    $$

    共 $m^n$ 个符号。

  • 扩展信源的概率分布为：

    $$
    P(x_{i_1}, x_{i_2}, \dots, x_{i_n}) = \prod_{k=1}^n P(x_{i_k})
    $$

• 熵的关系：
  单符号信源的熵为：

  $$
  H(X) = -\sum_{i=1}^m p_i \log p_i
  $$

  $n$ 阶扩展信源的熵为：

  $$
  H(X^n) = - \sum_{(x_{i_1}, \dots, x_{i_n})} P(x_{i_1}, \dots, x_{i_n}) \log P(x_{i_1}, \dots, x_{i_n})
  $$

  对于无记忆信源：

  $$
  H(X^n) = n H(X)
  $$

  每个符号的平均信息量（熵率）保持不变：

  $$
  \frac{H(X^n)}{n} = H(X)
  $$

---

2.8.4 示例

假设一个无记忆二元信源（binary source）：

$$
\mathcal{X} = {0,1}, \quad P(0) = 0.25, \quad P(1)=0.75
$$

1. 单符号信源熵：

   $$
   H(X) = -0.25\log_2 0.25 - 0.75 \log_2 0.75 \approx 0.811 \ \text{bits/symbol}
   $$

2. 二阶扩展信源字母表：

   $$
   {00, 01, 10, 11}
   $$

   概率分别为：
   $P(00)=0.25^2=0.0625$
   $P(01)=0.25 \times 0.75=0.1875$
   $P(10)=0.75 \times 0.25=0.1875$
   $P(11)=0.75^2=0.5625$

   熵：

   $$
   H(X^2) = -\sum P(x_i) \log_2 P(x_i) \approx 1.622 \ \text{bits/2 symbols}
   $$

   每符号熵率：

   $$
   H(X^2)/2 = 0.811 \ \text{bits/symbol}
   $$

   与单符号信源熵相同。

---

✅ 总结：

1. 离散无记忆信源：每次独立、相同分布地输出符号。
2. 信源扩展：将多个符号打包成新的“超级符号”，便于编码和分析。
3. 熵的性质：无记忆信源的熵是可加的，扩展不会改变熵率。

---

3. 马尔可夫信源

在现实世界中，大多数信源并不是完全 无记忆 (memoryless) 的。比如自然语言文本中，某个字母的出现往往和前一个字母相关；视频序列中，某一帧和上一帧之间存在强烈的相关性。为了建模这类“有记忆”的信源，就引入了 马尔可夫信源 (Markov Source)。

---

3.1 马尔可夫链 (Markov Chain) 基础

• 定义 (Definition)：
  若随机过程 $X_1, X_2, X_3, \dots$ 满足条件

  $$
  P(X_{n+1} = x \mid X_n, X_{n-1}, \dots, X_1) = P(X_{n+1} = x \mid X_n)
  $$

  则称其为马尔可夫链 (Markov Chain)。

  👉 含义：下一个符号的概率只依赖于当前状态 (current state)，而与更早的状态无关。

• 转移概率 (Transition Probability)：
  记作：

  $$
  p_{ij} = P(X_{n+1} = x_j \mid X_n = x_i)
  $$

  满足：

  $$
  p_{ij} \ge 0, \quad \sum_j p_{ij} = 1
  $$

• 状态转移矩阵 (Transition Matrix)：

  $$
  P = \begin{bmatrix}
  p_{11} & p_{12} & \cdots & p_{1m} \\
  p_{21} & p_{22} & \cdots & p_{2m} \\
  \vdots & \vdots & \ddots & \vdots \\
  p_{m1} & p_{m2} & \cdots & p_{mm}
  \end{bmatrix}
  $$

  其中 $m$ 是信源字母表大小。

---

3.2 马尔可夫信源 (Markov Source)

• 定义 (Definition)：
  如果一个信源可以用马尔可夫链建模，即每个符号的产生概率依赖于前一个符号，则称其为 一阶马尔可夫信源 (First-order Markov Source)。

  更一般地，若符号的产生依赖于前 $k$ 个符号，则称为 $k$ 阶马尔可夫信源 ($k$-th Order Markov Source)。

---

3.3 平稳分布 (Stationary Distribution)

• 定义 (Definition)：
  如果存在一个概率分布 $pi = (\pi_1, \pi_2, \dots, \pi_m)$，使得：

  $$
  \pi = \pi P, \quad \sum_i \pi_i = 1
  $$

  则称 $\pi$ 为 平稳分布 (stationary distribution)。

• 意义：
  长时间运行后，马尔可夫信源的状态分布会收敛于 $\pi$，与初始状态无关。

---

3.4 马尔可夫信源的熵率 (Entropy Rate)

• 符号信息熵 (Entropy per symbol)：
  对于一般信源，熵率定义为：

  $$
  H = \lim_{n \to \infty} \frac{1}{n} H(X_1, X_2, \dots, X_n)
  $$

• 一阶马尔可夫信源的熵率 (Entropy Rate of First-order Markov Source)：
  若平稳分布为 $\pi_i$，转移概率为 $p_{ij}$，则：

  $$
  H = - \sum_{i=1}^m \pi_i \sum_{j=1}^m p_{ij} \log p_{ij}
  $$

  👉 含义：熵率是“加权平均条件熵 (conditional entropy)”：

  $$
  H = H(X_{n+1} \mid X_n)
  $$

• 特殊情况：

  • 如果 $p_{ij}$ 与 $i$ 无关（即各状态转移概率相同），则马尔可夫信源退化为无记忆信源 (memoryless source)。
  • 若马尔可夫信源高度相关（如总是保持状态不变），则熵率趋近于 $0$。

---

3.5 二阶及高阶马尔可夫信源 (Higher-order Markov Sources)

• 定义：
  若符号依赖于前 $k$ 个符号，则称为 $k$ 阶马尔可夫信源。

  $$
  P(X_{n+1} \mid X_n, X_{n-1}, \dots, X_{1}) = P(X_{n+1} \mid X_n, \dots, X_{n-k+1})
  $$

• 化简技巧：
  可以把 $k$ 阶马尔可夫信源 转换为 一阶马尔可夫信源，方法是把“长度为 $k$ 的符号块”当作一个超级状态 (super-state)。

---

3.6 马尔可夫信源的编码意义 (Coding Implications)

1. 压缩效率 (Compression Efficiency)：

   • 无记忆信源的编码只利用单个符号的概率分布。
   • 马尔可夫信源的符号间有相关性，若编码时考虑符号相关性，可以提高压缩率。

2. 预测编码 (Predictive Coding)：

   • 马尔可夫信源可用于预测下一个符号。
   • 在自然语言处理中，$n$ 元模型 (n-gram model) 就是 $n-1$ 阶马尔可夫模型。

3. 熵率作为极限 (Entropy Rate as Limit)：

   • 在最佳编码 (optimal coding) 下，平均码长 (average code length) 接近熵率 $H$。

---

3.7 示例 (Example)

考虑一个二元马尔可夫信源：$\mathcal{X} = {0,1}$
转移概率矩阵：

$$
P = \begin{bmatrix}
0.9 & 0.1 \\
0.5 & 0.5
\end{bmatrix}
$$

• 求平稳分布：
  解方程 $\pi = \pi P$：

  $$
  \pi = (0.8333, \ 0.1667)
  $$

• 熵率：

  $$
  H = - \sum_{i=1}^2 \pi_i \sum_{j=1}^2 p_{ij} \log_2 p_{ij}
  $$

  计算：

  $$
  H \approx -0.8333(0.9 \log_2 0.9 + 0.1 \log_2 0.1)
  -0.1667(0.5 \log_2 0.5 + 0.5 \log_2 0.5)
  $$

  $$
  \approx 0.503 \ \text{bits/symbol}
  $$

👉 比无记忆二元信源的最大熵 $1$ bits/symbol 要低，说明存在相关性 (correlation)。

---

4. 信源编码 (Source Coding)

信源编码 (source coding) 是信息论的核心任务之一，目标是将信源符号序列表示为二进制序列，尽可能减少冗余，使得传输和存储更加高效。

在信源编码的研究中，首先需要定义“码 (code)”的性质。根据符号和码字 (codeword) 之间的对应关系，可以区分 奇异码 (singular code) 与 非奇异码 (non-singular code)。

---

4.1 奇异码 (Singular Code)

如果某个编码方案中，至少有两个不同的信源符号 (different source symbols) 被映射到相同的码字 (same codeword)，则称这个编码方案为奇异码 (singular code)。

形式化表达：
设信源字母表为 $\mathcal{X} = {x_1, x_2, \dots, x_m}$，码字集合为 $\mathcal{C} = {c_1, c_2, \dots, c_m}$。
如果 $\exists i \ne j$，使得 $c_i = c_j$，则该码是奇异码。

---

特点 (Properties)

1. 不可区分性 (indistinguishability)：两个不同符号编码成同一个码字，解码时无法区分，信息丢失。
2. 不可逆性 (irreversibility)：奇异码不是一一映射，不存在解码的唯一性。
3. 无实际应用价值 (no practical use)：因为无法保证信息还原。

---

示例 (Example)

• 信源字母表：$\mathcal{X} = {A, B, C}$

• 编码方案：

  $$
  A \to 0, \quad B \to 0, \quad C \to 1
  $$

在这个例子中，$A$ 和 $B$ 都被编码为 0，所以该码是 奇异码。
当接收到码字 “0” 时，解码器无法区分它对应的是 $A$ 还是 $B$。

---

4.2 非奇异码 (Non-Singular Code)

如果编码方案保证 不同的信源符号 (different source symbols) 一定映射为 不同的码字 (different codewords)，则称其为 非奇异码 (non-singular code)。

形式化表达：
若 $\forall i \ne j$，有 $c_i \ne c_j$，则该码是 非奇异码。

---

特点 (Properties)

1. 一一对应 (one-to-one mapping)：不同符号对应不同码字。
2. 可逆性 (reversibility)：至少在 符号级别 (symbol level) 可以解码。
3. 必要条件 (necessary condition)：非奇异性是信源编码的基本要求，否则无法保证信息还原。

---

示例 (Example)

• 信源字母表：$\mathcal{X} = {A, B, C}$

• 编码方案：

  $$
  A \to 0, \quad B \to 10, \quad C \to 11
  $$

在这个编码中，不同的符号被映射为不同的码字，因此它是 非奇异码。

当接收到 “0” 时一定是 $A$，接收到 “10” 时一定是 $B$，接收到 “11” 时一定是 $C$。

---

4.3 非奇异码的局限性 (Limitations)

• 非奇异码只能保证 单个符号与码字一一对应，但并不能保证符号序列的唯一解码性。
  例如：

  $$
  A \to 0, \quad B \to 01, \quad C \to 011
  $$

  虽然这是非奇异码，但当接收到 “011” 时，可能被解读为：

  • $C$，或
  • $A$ + $B$，或
  • $A$ + $A$ + $C$ 的部分前缀。
    这说明仅有非奇异性不足以保证正确解码，还需要更严格的约束（→ 前缀码 prefix code，在 4.3 里会继续讨论）。

---

✅ 总结

1. 奇异码 (Singular Code)：

   • 不同信源符号可能映射到同一码字。
   • 不能唯一解码，信息丢失。
   • 没有实际应用价值。

2. 非奇异码 (Non-Singular Code)：

   • 不同信源符号对应不同码字。
   • 符号级别可逆。
   • 是信源编码的必要条件，但并不足够，还需要 唯一可译码 (uniquely decodable code) 与 前缀码 (prefix code) 来进一步保证解码的唯一性和效率。

---

4.4 唯一可译码 (Uniquely Decodable Code)

若一个编码方案不仅保证 单个符号的唯一性，而且保证 任意有限长的码字串 (concatenation of codewords) 都能被唯一地分解为信源符号序列，则称该码为 唯一可译码 (uniquely decodable code)。

👉 换句话说：

• 接收方在得到一串比特后，能唯一地确定它由哪些码字组成。
• 不会出现多种可能的解码方式。

---

与非奇异码的关系

• 非奇异码：保证 单个符号 ↔ 单个码字 是一一对应的。
• 唯一可译码：进一步保证 任意码字串 也能唯一分解。
• 所有唯一可译码一定是非奇异码，但反之不成立。

---

示例 (Example 1)

信源字母表：${A, B, C}$
编码方案：

$$
A \to 0, \quad B \to 10, \quad C \to 11
$$

这是一个非奇异码。

• 序列 “01110” 的解码唯一：

  • $0 \to A$
  • $11 \to C$
  • $10 \to B$
    即 “ACB”。

该码也是 唯一可译码。

---

示例 (Example 2 - 非唯一可译)

信源字母表：${A, B, C}$
编码方案：

$$
A \to 0, \quad B \to 01, \quad C \to 011
$$

这是非奇异码（不同符号对应不同码字）。
但考虑码字串 “011”：

• 可能是 $C$
• 也可能是 $A + B$
  所以这是 非唯一可译码。

---

判定工具：Kraft–McMillan 不等式 (Kraft–McMillan Inequality)

• 定理：一个 $D$ 元（$D=2$ 表示二进制）的码是唯一可译码的 充要条件 是：
  存在一组码长 ${l_1, l_2, \dots, l_m}$ 满足：

  $$
  \sum_{i=1}^m D^{-l_i} \leq 1
  $$

• 这个条件保证码字在无限二叉树中不会产生歧义。

---

4.5 前缀码 (Prefix Code)

若一个码满足：没有任何码字是另一个码字的前缀 (prefix)，则称该码为 前缀码 (prefix code)。

👉 含义：接收方在读取比特时，只要遇到一个完整的码字，就能立即解码，不必等待后续比特。

---

特点 (Properties)

1. 即时解码 (instantaneous decoding)：不需要等待更多输入，比特流可以逐位解码。
2. 唯一可译 (uniquely decodable)：所有前缀码都是唯一可译码。
3. 构造方法 (construction)：常见的 Huffman 编码 (Huffman coding) 就是前缀码。

---

示例 (Example 1 - 前缀码)

信源字母表：${A, B, C, D}$
编码方案：

$$
A \to 0, \quad B \to 10, \quad C \to 110, \quad D \to 111
$$

• 没有任何码字是另一个码字的前缀。
• 因此这是一个 前缀码。

码字串 “0110110” 解码过程：

• 0 → A
• 110 → C
• 110 → C
  解码唯一且即时完成：结果 “ACC”。

---

示例 (Example 2 - 非前缀码)

信源字母表：${A, B}$
编码方案：

$$
A \to 0, \quad B \to 01
$$

• “0” 是 “01” 的前缀。
• 因此这是 非前缀码。

解码时若接收到 “01”，可能是 “A + …” 或直接 “B”，需要等待更多比特，无法即时解码。

---

前缀码与 Kraft–McMillan 不等式

• 前缀码一定满足 Kraft–McMillan 不等式。

• Kraft–McMillan 定理：如果 ${l_i}$ 满足

  $$
  \sum_{i=1}^m 2^{-l_i} \le 1
  $$

  那么一定存在一个二进制前缀码，其码长恰好为 ${l_i}$。

---

✅ 总结

1. 奇异码 (Singular code)：不同符号可能映射到同一码字 → 无法解码 → 无用。
2. 非奇异码 (Non-singular code)：不同符号有不同码字 → 单符号可逆，但序列可能歧义。
3. 唯一可译码 (Uniquely decodable code)：任意码字串都能唯一分解 → 可保证正确信息还原。
4. 前缀码 (Prefix code)：没有码字是另一码字的前缀 → 即时解码 → 是最常用的唯一可译码。

👉 在实际通信和压缩中，前缀码 是最重要的编码形式，例如 Huffman 编码 (Huffman coding) 就是经典的前缀码。

---

4.6 Huffman 编码 (Huffman Coding)

在信源编码 (source coding) 中，我们的目标是：

• 用尽可能少的比特来表示信源符号；
• 符合 无失真 (lossless) 的要求，即可以唯一解码。

Huffman 编码是 David A. Huffman 在 1952 年提出的最优前缀码 (optimal prefix code) 构造算法。
它的特点是：

• 输入：信源符号及其概率分布 $P(x)$；
• 输出：一组满足前缀码性质的二进制码字；
• 目标：使平均码长 (average codeword length) 最小，且接近于香农熵 $H(X)$。

Huffman 编码的核心思想是：
👉 高概率的符号用短码字表示，低概率的符号用长码字表示。

这样可以降低整体平均码长。

---

Huffman 编码算法 (Algorithm)

假设信源字母表为 $\mathcal{X} = {x_1, x_2, \dots, x_m}$，对应概率为 $p_1, p_2, \dots, p_m$。
算法步骤如下：

1. 排序 (Sort)
   将所有符号按概率从大到小排序。

2. 合并 (Merge)
   取出概率最小的两个符号，合并为一个新的“复合符号”，其概率等于两者之和。

3. 重复 (Iterate)
   将新符号加入集合，重新排序，再次合并两个最小概率的符号，直到只剩一个根节点。

4. 分配码字 (Assign Codes)
   在合并树 (Huffman tree) 中，约定：

   • 左分支 → 0
   • 右分支 → 1
     最后从根到叶子路径即为该符号的码字。

---

示例 (Example)

信源字母表：${A, B, C, D}$
概率：

$$
P(A) = 0.4, \quad P(B) = 0.3, \quad P(C) = 0.2, \quad P(D) = 0.1
$$

Step 1: 排序

$A(0.4), B(0.3), C(0.2), D(0.1)$

Step 2: 合并最小的两个符号

$C(0.2) + D(0.1) \to CD(0.3)$

现在：$A(0.4), B(0.3), CD(0.3)$

Step 3: 再合并

$B(0.3) + CD(0.3) \to BCD(0.6)$

现在：$A(0.4), BCD(0.6)$

Step 4: 合并

$A(0.4) + BCD(0.6) \to 根(1.0)$

Step 5: 分配码字

• $A$: 0
• $B$: 10
• $C$: 110
• $D$: 111

得到 Huffman 编码：

$$
A \to 0, \quad B \to 10, \quad C \to 110, \quad D \to 111
$$

---

平均码长 (Average Codeword Length)

定义：

$$
L = \sum_{i=1}^m p_i \cdot l_i
$$

其中 $l_i$ 是符号 $x_i$ 的码字长度。

在上例中：

• $A$: 长度 1
• $B$: 长度 2
• $C$: 长度 3
• $D$: 长度 3

$$
L = 0.4 \cdot 1 + 0.3 \cdot 2 + 0.2 \cdot 3 + 0.1 \cdot 3 = 1.9 \ \text{比特/符号}
$$

信源熵：

$$
H(X) = -\sum p_i \log_2 p_i \approx 1.846 \ \text{比特/符号}
$$

结论：

$$
H(X) \le L < H(X) + 1
$$

这是Huffman 编码最优性的定理。

---

Huffman 编码的性质 (Properties)

1. 最优前缀码 (Optimal Prefix Code)

   • 对于给定符号概率分布，Huffman 编码得到的平均码长 $L$ 是最小的。

2. 接近熵 (Close to Entropy)

   • $H(X) \le L < H(X) + 1$。

3. 唯一性 (Uniqueness)

   • 当所有概率均为 $2^{-n}$ 形式时，Huffman 编码唯一。
   • 否则可能有多个等价的 Huffman 树（不同结构但平均码长相同）。

---

Huffman 编码的局限性 (Limitations)

1. 依赖精确概率：需要事先知道信源概率分布。
2. 非整数熵问题：如果 $H(X)$ 不是整数，Huffman 编码无法完全达到熵的下界。
3. 动态信源问题：信源概率随时间变化时，Huffman 编码需频繁更新。
4. 符号独立性假设：假设符号独立，而实际信源可能有记忆性。

---

应用 (Applications)

• 数据压缩：ZIP 文件、GZIP、PNG 图像格式、MP3 等都使用 Huffman 编码作为核心算法。
• 通信系统：在信道编码前先做 Huffman 编码以减少冗余。

---

✅ 总结

• Huffman 编码是 最优前缀码 构造算法。
• 步骤：合并最小概率符号 → 构造 Huffman 树 → 分配码字。
• 性质：平均码长最小，满足 $H(X) \le L < H(X)+1$。
• 局限性：需已知概率分布，且对动态信源效果不佳。