信息论讲义

目录

• 第 1 周 概率论基础
• 第 2 周 随机变量、独立性与一阶/二阶矩不等式
• 第 3 周 Chernoff 界、大数定律与熵的引入
• 第 4 周 熵的性质、Shannon 唯一性定理、联合熵与条件熵
• 第 5 周 条件熵的性质与链式法则
• 第 6 周 互信息、KL 散度与信息不等式

---

第 1 周 概率论基础

信息论中最基本的研究对象——熵——是建立在随机变量及其分布之上的,因此首先严格回顾概率论的核心定义。

1.1 概率空间

定义 1.1(概率测度)

概率是一个映射 $P:\mathcal{F}\to [0,1]$,其中 $\mathcal{F}$ 是样本空间 $\Omega$ 上的事件域(σ-代数)。$P$ 满足:

1. 非负性:$P(A)\ge 0$;
2. 归一性:$P(\Omega )=1$;
3. 可加性:对两两不相交的事件 $A_1,A_2,\dots$,有 $P\left({\bigcup }_i{A}_i\right)={\sum }_{i}P(A_i)$。

• 事件 (Event):样本空间 $\Omega$ 中样本点的集合,通常视为 $\Omega$ 的子集。
• 独立事件 (Independent Events):若 $P(A\cap B)=P(A)P(B)$,则称事件 $A,B$ 独立。

1.2 条件概率与三大公式

定义 1.2(条件概率)

设 $P(B)>0$,在 $B$ 发生条件下 $A$ 的概率为 $P(A\mid B)=\frac{P(A\cap B)}{P(B)}.$

全概率公式 (Law of Total Probability)

若 $\{B_i{\}}_{i=1}^n$ 是 $\Omega$ 的一个划分,且 $P(B_i)>0$,则对任意事件 $A$, $P(A)={\sum }_{i=1}^{n}P(A\mid B_i)P(B_i).$

贝叶斯公式 (Bayes' Law)

对任意事件 $A,B$,$P(B)>0$: $P(A\mid B)=\frac{P(B\mid A)P(A)}{P(B)}.$

直观理解:贝叶斯公式把”先验” $P(A)$ 通过观察到 $B$ 后更新成”后验” $P(A\mid B)$,$P(B\mid A)/P(B)$ 是似然带来的更新因子。

---

第 2 周 随机变量、独立性与一阶/二阶矩不等式

2.1 随机变量与分布

定义 2.1(随机变量)

随机变量 (r.v.) 是一个函数 $X:\Omega \to D_X$,其中 $D_X$ 称为 $X$ 的值域 (domain/range)。

定义 2.2(概率质量函数 PMF)

离散随机变量 $X$ 的 PMF 为 $p_X:D_X\to [0,1],p_X(x)=\mathrm{Pr}[X=x].$ 其支撑集 (support) 为 $\mathrm{Supp}(X)=\{x\in D_X:p_X(x)>0\}.$

定义 2.3(联合/边缘/条件分布)

设 $X,Y$ 为随机变量。

• 联合分布:$p_{X,Y}(x,y)=\mathrm{Pr}[X=x\wedge Y=y]$。
• 边缘分布:$p_X(x)={\sum }_{y\in D_Y}{p}_{X,Y}(x,y)$。
• 条件分布:对 $p_Y(y)>0$, $p_{X\mid Y}(x\mid y)=\frac{p_{X,Y}(x,y)}{p_Y(y)}=\mathrm{Pr}[X=x\mid Y=y].$

2.2 期望与方差

定义 2.4(期望与方差)

$\mu =E[X]={\sum }_{x\in D_X}x\cdot p_X(x),$ $\mathrm{Var}(X)=E\left[(X-\mu {)}^2\right]=E[X^2]-(E[X]{)}^2.$

定义 2.5(条件期望)

对事件 $B$,$P(B)>0$: $E[X\mid B]={\sum }_{x\in D_X}x\mathrm{Pr}[X=x\mid B].$

期望的线性性 (Linearity of Expectation)

对任意两个随机变量 $X,Y$(无论是否独立), $E[X+Y]=E[X]+E[Y].$

证明

利用联合分布展开并交换求和顺序:

$$\begin{array}{rl}E[X+Y]& =\sum _{x,y}(x+y)p_{X,Y}(x,y)\\ & =\sum _{x}x\sum _y{p}_{X,Y}(x,y)+\sum _{y}y\sum _x{p}_{X,Y}(x,y)\\ & =\sum _{x}x{p}_X(x)+\sum _{y}y{p}_Y(y)\\ & =E[X]+E[Y].■\end{array}$$

2.3 独立性

定义 2.6(独立性)

随机变量 $X$ 与 $Y$ 独立,记作 $X\perp \perp Y$,当且仅当对所有 $x\in D_X,y\in D_Y$, $p_{X,Y}(x,y)=p_X(x)p_Y(y).$

定义 2.7(相互独立 / 两两独立 / 条件独立)

设 $n\ge 3$,$X_1,\dots ,X_n$ 为随机变量。

• 相互独立 (mutually independent):对所有 $(x_1,\dots ,x_n)$, $p_{X_1,\dots ,X_n}(x_1,\dots ,x_n)={\prod }_{i=1}^n{p}_{X_i}(x_i).$
• 两两独立 (pairwise independent):对所有 $1\le i<j\le n$,$X_i\perp \perp X_j$。
• 条件独立:给定 $Z$,称 $X\perp \perp Y\mid Z$,若对所有满足 $p_Z(z)>0$ 的 $z$, $p_{X,Y\mid Z}(x,y\mid z)=p_{X\mid Z}(x\mid z)p_{Y\mid Z}(y\mid z).$

两两独立 ≠ 相互独立

相互独立严格强于两两独立。例如三个 0/1 变量 $X_1,X_2,X_3=X_1\oplus X_2$ 两两独立但不相互独立。

命题 2.8(独立随机变量的性质)

设 $X_1,\dots ,X_n$ 相互独立,则

1. $E\left[\prod _{i=1}^n{X}_i\right]=\prod _{i=1}^{n}E[X_i]$;
2. $\mathrm{Var}\left(\sum _{i=1}^n{X}_i\right)=\sum _{i=1}^n\mathrm{Var}(X_i)$;
3. 对任意函数 $f_1,\dots ,f_n$,$f_1(X_1),\dots ,f_n(X_n)$ 仍相互独立。

定义 2.9(马尔可夫链)

称随机变量 $X_1\to X_2\to \cdots \to X_n$ 构成马尔可夫链 (Markov chain),若对每个 $i=2,\dots ,n$, $p_{X_i\mid X_1,\dots ,X_{i-1}}(x_i\mid x_1,\dots ,x_{i-1})=p_{X_i\mid X_{i-1}}(x_i\mid x_{i-1}).$ 直观:给定”现在”,则”未来”与”过去”无关。

2.4 集中不等式 I:Markov 与 Chebyshev

定理 2.10(Markov 不等式 / 一阶矩方法)

设 $X\ge 0$ 的随机变量,$a>0$,则 $\mathrm{Pr}[X\ge a]\le \frac{E[X]}{a}.$

证明

$$\begin{array}{rl}E[X]& =\sum _{x\ge 0}x\mathrm{Pr}[X=x]\\ & \ge \sum _{x\ge a}x\mathrm{Pr}[X=x]\\ & \ge a\sum _{x\ge a}\mathrm{Pr}[X=x]=a\mathrm{Pr}[X\ge a].■\end{array}$$

例 2.11

若 $E[X]=500$,则 $\mathrm{Pr}[X\ge 700]\le \frac{500}{700}\approx 0.71$。Markov 给出的界比较松。

定理 2.12(Chebyshev 不等式 / 二阶矩方法)

设 $X$ 有均值 $\mu =E[X]$、方差 ${\sigma }^2=\mathrm{Var}(X)$。对任意 $k>0$: $\mathrm{Pr}\left[|X-\mu |\ge k\right]\le \frac{{\sigma }^2}{k^2}.$

证明

令 $Y=(X-\mu {)}^2\ge 0$,则 $E[Y]={\sigma }^2$。由 Markov, $\mathrm{Pr}[Y\ge k^2]\le \frac{{\sigma }^2}{k^2}.$ 而 $\{|X-\mu |\ge k\}=\{Y\ge k^2\}$,故结论成立。$■$

例 2.13(1000 次硬币实验)

设 $X={\sum }_{i=1}^{1000}{X}_i$,$X_i\sim \mathrm{Bern}(1/2)$ 独立。则 $\mu =500$,$\mathrm{Var}(X)=250$。

估计 $\mathrm{Pr}[|X-500|\ge 200]$: $\mathrm{Pr}[|X-500|\ge 200]\le \frac{250}{200^2}=\frac{250}{40000}=\mathrm{0.00625.}$ 比 Markov 给出的界精细得多。

---

第 3 周 Chernoff 界、大数定律与熵的引入

3.1 Chernoff 界(一般形式)

定理 3.1(Chernoff Bound, General Form)

设 $X_1,\dots ,X_n\in [0,1]$ 相互独立,$X={\sum }_{i=1}^n{X}_i$,$\mu =E[X]={\sum }_{i=1}^{n}E[X_i]$。

• 上尾 (upper tail):对任意 $\delta >0$, $\mathrm{Pr}[X\ge (1+\delta )\mu ]\le {\left(\frac{e^{\delta }}{(1+\delta {)}^{1+\delta }}\right)}^{\mu }.$
• 下尾 (lower tail):对任意 $0<\delta <1$, $\mathrm{Pr}[X\le (1-\delta )\mu ]\le {\left(\frac{e^{-\delta }}{(1-\delta {)}^{1-\delta }}\right)}^{\mu }.$

证明(上尾)

思路:借助矩生成函数 (MGF) 把 $X$ 转化成指数形式,再调参数 $t$ 优化。

对任意 $t>0$,由于 $e^{tx}$ 在 $x\ge 0$ 单调递增, $\mathrm{Pr}[X\ge (1+\delta )\mu ]=\mathrm{Pr}[e^{tX}\ge e^{t(1+\delta )\mu }]\le \frac{E[e^{tX}]}{e^{t(1+\delta )\mu }}(\text{Markov}).$

由独立性,$E[e^{tX}]={\prod }_{i}E[e^{t{X}_i}]$。再利用关键凸性不等式: $\boxed{e^{tx}\le 1+(e^t-1)x\text{对 }x\in [0,1]}$ (这是因为 $e^{tx}$ 在 $[0,1]$ 上是凸函数,而右边正是连接 $(0,1)$ 与 $(1,e^t)$ 的弦。原笔记此处遗漏了 $x\in [0,1]$ 的前提,在此补充。)

所以 $E[e^{t{X}_i}]\le 1+(e^t-1){\mu }_i\le e^{(e^t-1){\mu }_i}(\text{用 }1+x\le e^x).$ 累乘得 $E[e^{tX}]\le e^{(e^t-1)\mu }$,故 $\mathrm{Pr}[X\ge (1+\delta )\mu ]\le \frac{e^{(e^t-1)\mu }}{e^{t(1+\delta )\mu }}.$ 对右端关于 $t$ 求最优,令 $t=\ln (1+\delta )>0$,代入即得 $\mathrm{Pr}[X\ge (1+\delta )\mu ]\le {\left(\frac{e^{\delta }}{(1+\delta {)}^{1+\delta }}\right)}^{\mu }.■$

注:Chernoff 界的紧度

对 Bernoulli 随机变量,Chernoff 界在 $\delta =\Omega ({\mu }^{-1/2})$ 直至 $\delta =O(1)$ 范围内是紧的(tight)。

3.2 Chernoff 界(常用简化形式)

实际使用时,以下指数形式更便于估计。

定理 3.2(乘性 Chernoff 界,简化形式)

在定理 3.1 的条件下:

• 上尾:对任意 $\delta >0$, $\mathrm{Pr}[X\ge (1+\delta )\mu ]\le \{\begin{array}{ll}\exp \left(-\frac{\mu {\delta }^2}{3}\right),& 0<\delta <1,\\ \exp \left(-\frac{\mu \delta }{3}\right),& \delta \ge 1.\end{array}$
• 下尾:对 $0<\delta <1$, $\mathrm{Pr}[X\le (1-\delta )\mu ]\le \exp \left(-\frac{\mu {\delta }^2}{2}\right).$

直观对比

不等式	适用条件	衰减速度
Markov	$X\ge 0$	$1/a$
Chebyshev	有限方差	$1/k^2$
Chernoff	独立有界和	$\exp (-\mu {\delta }^2)$(指数)

Chernoff 是目前最强、最紧的尾部界,广泛用于随机化算法、密码学、机器学习、信息论。

3.3 大数定律

定理 3.3(弱大数定律, Weak Law of Large Numbers)

设 $X_1,\dots ,X_n$ 独立同分布(i.i.d.),$\mu =E[X_i]$,方差有限 ${\sigma }^2=\mathrm{Var}(X_i)$。令 ${\bar{X}}_n=\frac{1}{n}{\sum }_{i=1}^n{X}_i.$ 则对任意 $\epsilon >0$, ${\lim }_{n\to \infty }\mathrm{Pr}\left[|{\bar{X}}_n-\mu |\ge \epsilon \right]=0.$

证明(由 Chebyshev 推出)

$E[{\bar{X}}_n]=\mu$,$\mathrm{Var}({\bar{X}}_n)={\sigma }^2/n$。由 Chebyshev, $\mathrm{Pr}[|{\bar{X}}_n-\mu |\ge \epsilon ]\le \frac{\mathrm{Var}({\bar{X}}_n)}{{\epsilon }^2}=\frac{{\sigma }^2}{n{\epsilon }^2}\stackrel{n\to \infty }{\to }0.■$

---

3.4 熵 (Entropy):刻画随机变量的不确定性

定义 3.4(熵)

设 $X$ 是离散随机变量,PMF 为 $p_X$,熵定义为 $H(X)=-{\sum }_{x\in \mathrm{Supp}(X)}{p}_X(x)\log p_X(x).$ (默认底数为 2,单位 bit。)

熵是对$X$不确定性的度量:$H(X)$ 越大,$X$ 越”不可预测”。

命题 3.5(非负性)

对任意随机变量 $X$,$H(X)\ge 0$,等号成立 $⟺$ $X$ 几乎处处取确定值。

证明草图:每一项 $-p\log p\ge 0$(对 $p\in (0,1]$),且仅当某个 $p_i=1$、其余 $=0$ 时整个和为 0。

典型例子

例 3.6(常见分布的熵)

• 均匀分布:$X$ 在 $\{1,\dots ,n\}$ 均匀分布,$\mathrm{Pr}[X=i]=1/n$, $H(X)={\sum }_{i=1}^n\frac{1}{n}\log n=\log n.$
• 二元(Bernoulli)熵:$X\in \{0,1\}$,$\mathrm{Pr}[X=1]=p$, $H_2(p)=-p\log p-(1-p)\log (1-p),$ 在 $p=1/2$ 时取最大值 1,函数对称且关于 $p=1/2$ 凹。

3.5 凸函数与 Jensen 不等式

定义 3.7(凸函数)

$f:\mathbb{R}\to \mathbb{R}$ 凸,若对所有 $x_1,x_2\in \mathbb{R}$ 与 $\lambda \in [0,1]$, $f(\lambda x_1+(1-\lambda )x_2)\le \lambda f(x_1)+(1-\lambda )f(x_2).$ 若 $x_1\ne x_2$ 时严格小于,则称 $f$ 严格凸。

定理 3.8(Jensen 不等式)

设 $f$ 凸,$x_1,\dots ,x_n\in \mathbb{R}$,$p_1,\dots ,p_n\in [0,1]$ 且 $\sum p_i=1$,则 $f\left({\sum }_{i=1}^n{p}_i{x}_i\right)\le {\sum }_{i=1}^n{p}_{i}f(x_i).$ 若 $f$ 严格凸,则等号成立 $⟺$ 在所有 $p_i>0$ 的位置上 $x_i$ 全相等。

对凹函数(如 $\log$),不等号反向。

证明(对 $n$ 归纳)

基础:$n=2$ 即凸函数定义。

归纳:假设对 $n-1$ 成立,设 $q=1-p_1={\sum }_{i=2}^n{p}_i$, $f\left({\sum }_{i=1}^n{p}_i{x}_i\right)=f\left(p_1{x}_1+q{\sum }_{i=2}^n\frac{p_i}{q}{x}_i\right)\le p_{1}f(x_1)+qf\left({\sum }_{i=2}^n\frac{p_i}{q}{x}_i\right)$ $\le p_{1}f(x_1)+q{\sum }_{i=2}^n\frac{p_i}{q}f(x_i)={\sum }_{i=1}^n{p}_{i}f(x_i).■$

3.6 熵的上界

定理 3.9(熵的最大值)

设 $X$ 取值数为 $n$,则 $H(X)\le \log n$ ； 等号成立 $⟺$ $X$ 在其支撑集上均匀分布。

证明

不妨设 $X\in \{1,\dots ,n\}$,$\mathrm{Pr}[X=i]=p_i$。由 $\log$ 的凹性与 Jensen 不等式, $H(X)={\sum }_{i=1}^n{p}_i\log \frac{1}{p_i}\le \log \left({\sum }_{i=1}^n{p}_i\cdot \frac{1}{p_i}\right)=\log n.$ 严格凹性给出等号成立的等价条件:所有 $p_i$ 相等,即 $X$ 均匀。$■$

---

第 4 周 熵的性质、Shannon 唯一性定理、联合熵与条件熵

4.1 Stirling 公式与多项式系数

Stirling 公式

$n!\sim {\left(\frac{n}{e}\right)}^n\sqrt{2\pi n}=\Theta \left(\sqrt{n}\cdot {\left(\frac{n}{e}\right)}^n\right).$

由此可估计二项系数:对 $p\in (0,1)$, $\left(\genfrac{}{}{0ex}{}{n}{pn}\right)=\frac{n!}{(pn)!((1-p)n)!}={\Theta }_p\left(\frac{1}{\sqrt{n}}\right)\cdot 2^{n{H}_2(p)}=2^{n{H}_2(p)-{\Theta }_p(\log n)}=2^{n(H_2(p)-o(1))}.$

更一般地,多项式系数:对概率向量 $(p_1,\dots ,p_n)$ 与 $N\to \infty$, $\left(\genfrac{}{}{0ex}{}{N}{p_{1}N,p_{2}N,\dots ,p_{n}N}\right)=\frac{N!}{{\prod }_i(p_{i}N)!}=2^{N(H(p_1,\dots ,p_n)-o(1))}.$

直观理解

熵刻画了典型序列的数量级:在长度 $N$、字符分布为 $(p_1,\dots ,p_n)$ 的序列中,典型序列约有 $2^{NH(p_1,\dots ,p_n)}$ 条。这是熵作为”信息量”度量的组合学根据。

4.2 熵在确定性函数下的不增

定理 4.1

设 $X$ 是随机变量,$Y=f(X)$,其中 $f$ 是确定性函数。则 $H(Y)\le H(X),$ 等号成立 $⟺$ $f$ 在 $\mathrm{Supp}(X)$ 上是单射。

直观:确定性函数不会增加随机性——可能把不同 $x$ 合并成同一个 $y$,从而损失信息。

4.3 Shannon 唯一性定理 (Shannon 1948)

定理 4.2(Shannon 1948,熵的唯一性)

设 $H(p_1,\dots ,p_n)$ 是非负函数,满足以下三条公理:

1. 连续性 (Continuity):$H$ 关于每个 $p_i$ 连续;
2. 对称性 (Symmetry):$H$ 在 $p_i$ 的任意置换下不变;
3. 可加性 / 分组律 (Additivity / Grouping):若一个选择被分解为多步, $H(p_1,\dots ,p_n)=H(w_1,w_2)+w_{1}H\left(\frac{p_1}{w_1},\dots ,\frac{p_k}{w_1}\right)+w_{2}H\left(\frac{p_{k+1}}{w_2},\dots ,\frac{p_n}{w_2}\right),$ 其中 $w_1={\sum }_{i=1}^k{p}_i,w_2={\sum }_{i=k+1}^n{p}_i$。

则存在常数 $K>0$ 使得 $H(p_1,\dots ,p_n)=-K{\sum }_{i=1}^n{p}_i\log p_i.$

证明思路(三步法)

Step 1. 令 $A(n)=H(1/n,\dots ,1/n)$。把均匀分布在 $mn$ 个等概率事件上的不确定性,等价分解成”先选 $m$ 组之一,再在组内选 $n$ 个之一”,由可加性得 $A(mn)=A(m)+A(n)\forall m,n\in \mathbb{N}.$ 由连续性可推出存在常数 $K$ 使 $A(n)=K\log n$。

Step 2(有理概率):设 $p_i=k_i/m$,$k_i,m\in \mathbb{N}$,$\sum k_i=m$。把”在 $m$ 个等概率事件中均匀地选一个”分两步:先按 $(p_1,\dots ,p_n)$ 选哪一组(组 $i$ 含 $k_i$ 个事件),再在组内均匀选,可加性给出 $A(m)=H(p_1,\dots ,p_n)+{\sum }_{i=1}^n\frac{k_i}{m}A(k_i).$ 代入 $A(\cdot )=K\log (\cdot )$: $H(p_1,\dots ,p_n)=K\log m-K{\sum }_i\frac{k_i}{m}\log k_i=-K{\sum }_i\frac{k_i}{m}\log \frac{k_i}{m}=-K{\sum }_i{p}_i\log p_i.$

Step 3. 利用连续性,把有理概率推广到所有实概率。$■$

4.4 联合熵 (Joint Entropy)

定义 4.3(联合熵)

设 $X,Y$ 联合 PMF 为 $p_{X,Y}$。联合熵为 $H(X,Y)=-{\sum }_{(x,y)\in D_X\times D_Y}{p}_{X,Y}(x,y)\log p_{X,Y}(x,y)=-E\left[\log p_{X,Y}(X,Y)\right].$

例 4.4(独立时联合熵相加)

若 $X,Y$ 独立,则 $p_{X,Y}(x,y)=p_X(x)p_Y(y)$, $H(X,Y)=-E[\log p_X(X)+\log p_Y(Y)]=H(X)+H(Y).$

定理 4.5(联合熵的次可加性, Subadditivity)

对任意随机变量 $X,Y$, $H(X,Y)\le H(X)+H(Y),$ 等号成立 $⟺$ $X,Y$ 独立。

证明(两种写法)

写法 1:要证 ${\sum }_{x,y}{p}_{X,Y}(x,y)\log \frac{1}{p_{X,Y}(x,y)}\le {\sum }_{x,y}{p}_{X,Y}(x,y)\log \frac{1}{p_X(x)}+{\sum }_{x,y}{p}_{X,Y}(x,y)\log \frac{1}{p_Y(y)},$ 等价于 $(\ast )={\sum }_{x,y}{p}_{X,Y}(x,y)\log \frac{p_X(x)p_Y(y)}{p_{X,Y}(x,y)}\le 0.$ 由 Jensen(对 $\log$ 凹), $(\ast )\le \log \left({\sum }_{x,y}{p}_{X,Y}(x,y)\cdot \frac{p_X(x)p_Y(y)}{p_{X,Y}(x,y)}\right)=\log \left({\sum }_x{p}_X(x){\sum }_y{p}_Y(y)\right)=\log 1=0.$

写法 2(更简洁): $H(X)+H(Y)-H(X,Y)=E\left[\log \frac{p_{X,Y}(X,Y)}{p_X(X)p_Y(Y)}\right].$ 由 Jensen(此处 $\log$ 凹用反向):上式 $\ge 0$ 等价于 $E[\log Z]\le \log E[Z]$,而 $E\left[\frac{p_X(X)p_Y(Y)}{p_{X,Y}(X,Y)}\right]={\sum }_{x,y}{p}_X(x)p_Y(y)=1,$ 故 $H(X)+H(Y)-H(X,Y)\ge 0$。$■$

等号条件由 Jensen 严格凹性给出:几乎处处 $p_{X,Y}(x,y)=p_X(x)p_Y(y)$,即 $X,Y$ 独立。

应用 1:二项系数和的熵界

例 4.6(二项系数和的上界)

对 $m\le n/2$, ${\sum }_{i=0}^m\left(\genfrac{}{}{0ex}{}{n}{i}\right)\le 2^{n{H}_2(m/n)}.$

证明:取 $X\sim \mathrm{Uniform}\{Z\subseteq [n]:|Z|\le m\}$,则 $H(X)=\log \left({\sum }_{i=0}^m\left(\genfrac{}{}{0ex}{}{n}{i}\right)\right).$ 设 $X_i=1_{i\in X}\in \{0,1\}$。$(X_1,\dots ,X_n)$ 与 $X$ 一一对应,故 $H(X)=H(X_1,\dots ,X_n)$。

由次可加性:$H(X_1,\dots ,X_n)\le {\sum }_{i=1}^{n}H(X_i)=nH(X_1)$(对称性)。

又 $\mathrm{Pr}[X_1=1]=\mathrm{Pr}[1\in X]\le m/n$,且 $H_2(\cdot )$ 在 $[0,1/2]$ 单调递增,故 $H(X_1)\le H_2(m/n).$ 综合得 $\log {\sum }_{i=0}^m\left(\genfrac{}{}{0ex}{}{n}{i}\right)\le n{H}_2(m/n)$,即结论。$■$

应用 2:二元对称信道初探

例 4.7(BSC 信道的联合熵)

设 $X\sim \mathrm{Bern}(1/2)$,噪声 $N\sim \mathrm{Bern}(\epsilon )$ 与 $X$ 独立,$Y=X\oplus N\in \{0,1\}$。

计算:

• $H(X)=H_2(1/2)=1$。

• $\mathrm{Pr}[Y=0]=\mathrm{Pr}[X=0,N=0]+\mathrm{Pr}[X=1,N=1]=\frac{1}{2}(1-\epsilon )+\frac{1}{2}\epsilon =\frac{1}{2}$。所以 $H(Y)=1$。

• 联合分布: $\mathrm{Pr}[(X,Y)=(0,0)]=\frac{1}{2}(1-\epsilon ),\mathrm{Pr}[(X,Y)=(0,1)]=\frac{1}{2}\epsilon ,$ $(1,1)$ 与 $(0,0)$ 同概率,$(1,0)$ 与 $(0,1)$ 同概率。

  因此 $H(X,Y)=H\left(\frac{1-\epsilon }{2},\frac{\epsilon }{2},\frac{\epsilon }{2},\frac{1-\epsilon }{2}\right)=1+H_2(\epsilon ).$

验证次可加性:$H(X,Y)=1+H_2(\epsilon )\le 1+1=H(X)+H(Y)$,等号当且仅当 $\epsilon =1/2$(此时 $X,Y$ 独立)。

     X            Y
 0 ──────1-ε─────► 0
    ╲   ε    ╱
     ╲      ╱
      ╲    ╱
     ε ╲  ╱
 1 ──────1-ε─────► 1

BSC(ε):比特以概率 ε 翻转。

4.5 条件熵 (Conditional Entropy)

定义 4.8(条件熵)

设 $X,Y$ 联合 PMF 为 $p_{X,Y}$。给定 $Y$ 时 $X$ 的条件熵为 $H(X\mid Y)=-{\sum }_{(x,y)\in D_X\times D_Y}{p}_{X,Y}(x,y)\log p_{X\mid Y}(x\mid y)=-E\left[\log p_{X\mid Y}(X\mid Y)\right].$

等价表达

先固定 $Y=y$ 计算”片段熵”,再按 $Y$ 的分布加权平均: $H(X\mid Y=y)=-{\sum }_{x\in D_X}{p}_{X\mid Y}(x\mid y)\log p_{X\mid Y}(x\mid y),$ $H(X\mid Y)={\sum }_{y\in D_Y}{p}_Y(y)H(X\mid Y=y)=E_Y\left[H(X\mid Y=y)\right].$

链式法则 (Chain Rule)

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

证明:由 $p_{X,Y}=p_Y\cdot p_{X\mid Y}$,两边取 $-\log$ 再求期望即可。

几个直接推论

• 由次可加性 $H(X,Y)\le H(X)+H(Y)$ 与链式法则,得 条件不增: $H(X\mid Y)\le H(X),$ 等号 $⟺$ $X\perp \perp Y$。即”知道更多,信息量(不确定性)不增”。
• $H(X\mid Y)\ge 0$,等号 $⟺$ $X$ 是 $Y$ 的确定函数。

第 5 周 条件熵的性质与链式法则

回顾:条件熵的定义(第 4 周末) $H(X\mid Y)=-{\sum }_{x,y}{p}_{X,Y}(x,y)\log p_{X\mid Y}(x\mid y)=-E!\left[\log p_{X\mid Y}(X\mid Y)\right].$ 等价地,$H(X\mid Y)={\sum }_y{p}_Y(y),H(X\mid Y=y)$。

5.1 条件熵的边界情况(两个典型例子)

例 5.1

• 若 $X=f(Y)$($X$ 是 $Y$ 的确定函数):$H(X\mid Y)=0$。 知道 $Y$ 后,$X$ 完全确定,不确定性为零。
• 若 $X\perp Y$($X$ 与 $Y$ 独立):$H(X\mid Y)=H(X)$。 $Y$ 的信息对 $X$ 毫无帮助。

例 5.2(BSC(ε) 的条件熵) 设 $X\sim 0,1$ 均匀,$N\sim \mathrm{Bern}(\epsilon )$ 与 $X$ 独立,$Y=X\oplus N$。

联合分布(行为 $Y$,列为 $X$):

$Y\backslash X$	0	1
0	$\frac{1}{2}(1-\epsilon )$	$\frac{1}{2}\epsilon$
1	$\frac{1}{2}\epsilon$	$\frac{1}{2}(1-\epsilon )$

计算: $H(X\mid Y)={\sum }_{x,y}P(x,y)\log \frac{1}{P(x\mid y)}=(1-\epsilon )\log \frac{1}{1-\epsilon }+\epsilon \log \frac{1}{\epsilon }=H_2(\epsilon ).$

直观解读:

• $\epsilon \to 0$:信道几乎无噪声,$H(X\mid Y)\to 0$(接收到 $Y$ 就能还原 $X$);
• $\epsilon \to \frac{1}{2}$:信道完全随机,$H(X\mid Y)\to 1$(知道 $Y$ 也没有帮助)。

5.2 条件使熵减小(Conditioning Reduces Entropy)

定理 5.3(Thm 3.13) 对任意随机变量 $X,Y$, $H(X\mid Y)\le H(X),$ 等号成立 $⟺$ $X\perp !!!\perp Y$。

证明 $H(X\mid Y)-H(X)=E!\left[\log \frac{1}{P(X\mid Y)}\right]-E!\left[\log \frac{1}{P(X)}\right]=E!\left[\log \frac{P(X)}{P(X\mid Y)}\right]=E!\left[\log \frac{P(X)P(Y)}{P(X,Y)}\right].$

令 $Z=\frac{P(X)P(Y)}{P(X,Y)}$,由 Jensen 不等式(对凹函数 $\log$): $E[\log Z]\le \log E[Z]=\log {\sum }_{x,y}\frac{P(x,y)\cdot P(x)P(y)}{P(x,y)}=\log !\left({\sum }_{x}P(x){\sum }_{y}P(y)\right)=\log 1=0.$

故 $H(X\mid Y)-H(X)\le 0$。等号成立当且仅当 $Z$ 几乎处处为常数 1,即 $P(X,Y)=P(X)P(Y)$,即 $X\perp !!!\perp Y$。$■$

注意:"条件使熵减小"是 平均意义下的! 对特定的 $Y=y$,条件熵 $H(X\mid Y=y)$ 可以大于 $H(X)$;但加权平均后一定不超过 $H(X)$。

5.3 熵的链式法则

定理 5.4(两变量链式法则,Thm 3.14) $H(X,Y)=H(X)+H(Y\mid X).$

证明 $H(X)+H(Y\mid X)=-E[\log P(X)]-E[\log P(Y\mid X)]=-E!\left[\log \frac{P(X,Y)}{P(X)}\cdot P(X)\right]=-E[\log P(X,Y)]=H(X,Y).■$

定理 5.5(一般链式法则,Thm 3.15) 对任意随机变量 $X_1,\dots ,X_n$, $H(X_1,\dots ,X_n)={\sum }_{i=1}^{n}H(X_i\mid X_1,\dots ,X_{i-1})\le {\sum }_{i=1}^{n}H(X_i).$ (不等号由定理 5.3 逐项给出,即次可加性。)

证明(归纳法) 基础($n=2$):即定理 5.4。

归纳步骤:设对 $n-1$ 成立,则 $H(X_1,\dots ,X_n)=H(X_1,\dots ,X_{n-1})+H(X_n\mid X_1,\dots ,X_{n-1})$ $={\sum }_{i=1}^{n-1}H(X_i\mid X_1,\dots ,X_{i-1})+H(X_n\mid X_1,\dots ,X_{n-1})={\sum }_{i=1}^{n}H(X_i\mid X_1,\dots ,X_{i-1}).■$

定理 5.6(条件熵的链式法则,Thm 3.16 & 3.17) $H(X_1,X_2\mid Y)=H(X_1\mid Y)+H(X_2\mid X_1,Y).$ 一般地, $H(X_1,\dots ,X_n\mid Y)={\sum }_{i=1}^{n}H(X_i\mid X_1,\dots ,X_{i-1},Y).$

证明(以两变量为例) 对 $H(X_1,X_2,Y)$ 用两种方式展开: $H(X_1,X_2,Y)=H(Y)+H(X_1,X_2\mid Y)=H(Y)+H(X_1\mid Y)+H(X_2\mid X_1,Y).$ 同时 $H(X_1,X_2,Y)=H(X_1,X_2)+H(Y\mid X_1,X_2)$,两式相减整理即得。$■$

5.4 Kolmogorov 复杂度(补充)

定义 5.7(Kolmogorov 复杂度) 对二进制串 $X\in {0,1}^{\ast }$,定义其 Kolmogorov 复杂度 $K(X)$ 为能在通用图灵机(UTM,如 Python 解释器)上输出 $X$ 的最短程序的长度(以比特计)。

直观:$K(X)$ 衡量 $X$ 的”内在随机性”——若 $X$ 有规律可循(如 $00\cdots 0$),则存在短程序输出它;若 $X$ 完全随机,则没有比 $X$ 本身更短的描述。$K(X)$ 与熵的关系是信息论的深层主题,此处暂不展开。

---

第 6 周 互信息、KL 散度与信息不等式

6.1 互信息(Mutual Information)

定义 6.1(互信息,Def 3.18) 随机变量 $X$ 与 $Y$ 之间的互信息定义为 $I(X;Y)=H(X)-H(X\mid Y).$ 直观:知道 $Y$ 之后,$X$ 的不确定性减少了多少。

等价表达式

以下四种形式完全等价,各有用武之地:

$\boxed{\begin{array}{rlrlr}I(X;Y)& =H(X)-H(X\mid Y)& =H(Y)-H(Y\mid X)& =H(X)+H(Y)-H(X,Y)& =D_{\mathrm{KL}}(P_{XY},|,P_X{P}_Y)=\sum _{x,y}P(x,y)\log \frac{P(x,y)}{P(x)P(y)}\end{array}}$

推导(从定义出发) $I(X;Y)=H(X)-H(X\mid Y)=H(X)-H(X,Y)+H(Y)=H(X)+H(Y)-H(X,Y).$ 又 $I(X;Y)={\sum }_{x,y}P(x,y)\log \frac{1}{P(x\mid y)}-{\sum }_{x,y}P(x,y)\log \frac{1}{P(x)}={\sum }_{x,y}P(x,y)\log \frac{P(x,y)}{P(x)P(y)}=D_{\mathrm{KL}}(P_{XY}|P_X{P}_Y).$

逐点互信息(Pointwise MI)

定义 6.2 对特定取值 $(X,Y=y)$,逐点互信息为 $I(X;Y=y)=H(X)-H(X\mid Y=y).$

注意:$I(X;Y=y)$ 可以为负(例如观测到一个低概率事件反而增大了对 $X$ 的不确定性);但对 $Y$ 取期望后一定非负: $I(X;Y)=E_Y[I(X;Y=y)]\ge 0.$

6.2 互信息的基本性质

命题 6.3(对称性,Prop 3.19) $I(X;Y)=I(Y;X).$ 从 $H(X)+H(Y)-H(X,Y)$ 的形式立即可见。

定理 6.4(非负性,Thm 3.20) $I(X;Y)\ge 0,$ 等号成立 $⟺$ $X\perp !!!\perp Y$。

证明 $I(X;Y)=D_{\mathrm{KL}}(P_{XY}|P_X{P}_Y)\ge 0,$ 由 Gibbs 不等式(见定理 6.8)直接得到。等号条件:$P_{XY}=P_X{P}_Y$,即独立。$■$

命题 6.5(上界) $I(X;Y)\le \min H(X),H(Y).$

证明:$I(X;Y)=H(X)-H(X\mid Y)\le H(X)$;由对称性也 $\le H(Y)$。

特殊情形

• 若 $X\perp !!!\perp Y$:$I(X;Y)=0$;
• 若 $Y=f(X)$(确定函数):$I(X;Y)=H(Y)-H(Y\mid X)=H(Y)$;
• BSC($\epsilon$):$I(X;Y)=H(Y)-H(Y\mid X)=1-H_2(\epsilon )$,在 $X\sim \mathrm{Bern}(1/2)$ 时取最大值。

6.3 条件互信息(Conditional Mutual Information)

定义 6.6(条件互信息,Def 3.25) 对随机变量 $X,Y,Z$,条件互信息为 $I(X;Y\mid Z)=H(X\mid Z)-H(X\mid Y,Z).$ 直观:在已知 $Z$ 的前提下,$Y$ 带来的关于 $X$ 的额外信息量。

等价表达式(Prop 1.3) $I(X;Y\mid Z)=H(Y\mid Z)-H(Y\mid X,Z)=H(Y,Z)-H(Z)-H(X,Y,Z)+H(X,Z).$

例 6.7 若 $X=f(Y,Z)$(确定函数),则 $H(X\mid Y,Z)=0$,故 $I(X;Y\mid Z)=H(X\mid Z).$ 这说明:在已知 $Z$ 后,$Y$ 的加入使 $X$ 的不确定性完全消除。

定理 6.8(条件互信息非负) $I(X;Y\mid Z)\ge 0,$ 等号成立 $⟺$ $X\perp !!!\perp Y\mid Z$。

证明:$I(X;Y\mid Z)=H(X\mid Z)-H(X\mid Y,Z)\ge 0$,因为条件使熵减小(定理 5.3 的条件版)。$■$

两个推论:

• $I(X;Y)=I(X;Y\mid \varnothing )\ge 0$(互信息非负);
• $H(X\mid Y)=I(X;X\mid Y)\ge 0$(条件熵非负)。

6.4 互信息的链式法则

定理 6.9(互信息链式法则) $I(X;Y,Z)=I(X;Y)+I(X;Z\mid Y).$

证明 $\mathrm{LHS}=H(X)+H(Y,Z)-H(X,Y,Z).$ $\mathrm{RHS}=[H(X)+H(Y)-H(X,Y)]+[H(X\mid Y)-H(X\mid Y,Z)].$ 其中 $H(X\mid Y)=H(X,Y)-H(Y)$,$H(X\mid Y,Z)=H(X,Y,Z)-H(Y,Z)$,代入整理: $\mathrm{RHS}=H(X)+H(Y,Z)-H(X,Y,Z)=\mathrm{LHS}.■$

推论 6.10(一般链式法则) $I(X;Y_1,\dots ,Y_n)={\sum }_{i=1}^{n}I(X;Y_i\mid Y_1,\dots ,Y_{i-1}).$ 带条件的版本: $I(X;Y_1,\dots ,Y_n\mid Z)={\sum }_{i=1}^{n}I(X;Y_i\mid Y_1,\dots ,Y_{i-1},Z).$

证明(归纳法) 基础($n=2$):即定理 6.9。

归纳步骤:设对 $n-1$ 成立, $I(X;Y_1,\dots ,Y_n)=I(X;Y_1,\dots ,Y_{n-1})+I(X;Y_n\mid Y_1,\dots ,Y_{n-1})$ $={\sum }_{i=1}^{n-1}I(X;Y_i\mid Y_1,\dots ,Y_{i-1})+I(X;Y_n\mid Y_1,\dots ,Y_{n-1})={\sum }_{i=1}^{n}I(X;Y_i\mid Y_1,\dots ,Y_{i-1}).■$

---

6.5 距离与散度

定义 6.11(全变差距离与 KL 散度) 设 $P,Q$ 是有限集 $\Omega$ 上的概率分布。

• 全变差距离 (Total Variation Distance): $|P-Q{|}_{\mathrm{TV}}=\frac{1}{2}{\sum }_{\omega \in \Omega }|P(\omega )-Q(\omega )|.$
• KL 散度 (KL Divergence): $D_{\mathrm{KL}}(P|Q)={\sum }_{\omega \in \Omega }P(\omega )\log \frac{P(\omega )}{Q(\omega )}=E_{X\sim P}!\left[\log \frac{P(X)}{Q(X)}\right].$

KL 散度不是距离!

• 不对称:$D_{\mathrm{KL}}(P|Q)\ne D_{\mathrm{KL}}(Q|P)$;
• 不满足三角不等式。

但 KL 散度始终非负(Gibbs 不等式),且等于零 $⟺$ $P=Q$。

定理 6.12(Gibbs 不等式 / Thm 3.22) 对任意两个分布 $P,Q$: $D_{\mathrm{KL}}(P|Q)\ge 0,$ 等号成立 $⟺$ $P(x)=Q(x)$ 对所有 $x$ 成立。

证明(Jensen 不等式) $D_{\mathrm{KL}}(P|Q)=-E_{X\sim P}!\left[\log \frac{Q(X)}{P(X)}\right]\ge -\log E_{X\sim P}!\left[\frac{Q(X)}{P(X)}\right]=-\log {\sum }_{x}P(x)\cdot \frac{Q(x)}{P(x)}=-\log 1=0.$ 第一个不等号由 $-\log$ 的凸性与 Jensen 不等式给出。等号条件:$Q(X)/P(X)$ 几乎处处为常数,结合 $\sum P=\sum Q=1$ 即得 $P=Q$。$■$

---

6.6 信息不等式

6.6.1 数据处理不等式(互信息版)

定理 6.13(Data Processing Inequality for MI) 若 $X\to Y\to Z$ 构成马尔可夫链(即 $X\perp !!!\perp Z\mid Y$),则 $I(X;Z)\le I(X;Y).$ 等号成立 $⟺$ $X\to Z\to Y$ 也构成马尔可夫链(即 $X\perp !!!\perp Y\mid Z$)。

证明 由马尔可夫条件 $X\perp !!!\perp Z\mid Y$,有 $I(X;Z\mid Y)=0$。

用链式法则对 $I(X;Y,Z)$ 做两种展开: $I(X;Y,Z)=I(X;Y)+\underset{=0}{\underbrace{I(X;Z\mid Y)}}=I(X;Y).$ $I(X;Y,Z)=I(X;Z)+I(X;Y\mid Z)\ge I(X;Z).$

因此 $I(X;Y)\ge I(X;Z)$。等号成立当且仅当 $I(X;Y\mid Z)=0$,即 $X\perp !!!\perp Y\mid Z$。$■$

直观理解 数据处理只会 损失信息,不会增加信息。$Z$ 是 $Y$ 的"下游",而 $Y$ 是 $X$ 的"下游";从 $X$ 的角度看,$Z$ 携带的信息不可能超过 $Y$。

6.6.2 对数和不等式(Log-Sum Inequality)

引理 6.14(Log-Sum Inequality / Lemma 2.2) 对非负实数 $a_1,\dots ,a_n$ 和 $b_1,\dots ,b_n$(其中 $\sum a_i>0$,$\sum b_i>0$), ${\sum }_{i=1}^n{a}_i\log \frac{a_i}{b_i}\ge !\left({\sum }_{i=1}^n{a}_i\right)\log \frac{{\sum }_i{a}_i}{{\sum }_i{b}_i}.$ 等号成立 $⟺$ $a_i/b_i$ 对所有 $b_i>0$ 的 $i$ 为常数。

证明 令 $A=\sum a_i$,$B=\sum b_i$,定义分布 $p_i=a_i/A$,$q_i=b_i/B$。

由 Gibbs 不等式 $D_{\mathrm{KL}}(p|q)\ge 0$: ${\sum }_i{p}_i\log \frac{p_i}{q_i}\ge 0⟹\frac{1}{A}{\sum }_i{a}_i\log \frac{a_i/A}{b_i/B}\ge 0.$ 展开 $\log$: $\frac{1}{A}{\sum }_i{a}_i!\left(\log \frac{a_i}{b_i}-\log \frac{A}{B}\right)\ge 0⟹{\sum }_i{a}_i\log \frac{a_i}{b_i}\ge A\log \frac{A}{B}.■$

6.6.3 数据处理不等式(KL 散度版)

定理 6.15(Data Processing Inequality for KL Divergence) 设 $P,Q$ 是 $\mathcal{X}$ 上的概率分布,$T:\mathcal{X}\to \mathcal{Y}$ 是任意函数。令 $P_{T(X)},Q_{T(X)}$ 分别为 $P,Q$ 在 $T$ 下的推前分布 (pushforward): $P_{T(X)}(y)={\sum }_{x:T(x)=y}P(x),Q_{T(X)}(y)={\sum }_{x:T(x)=y}Q(x).$ 则 $D_{\mathrm{KL}}(P_X|Q_X)\ge D_{\mathrm{KL}}(P_{T(X)}|Q_{T(X)}).$

证明 $D_{\mathrm{KL}}(P_X|Q_X)={\sum }_{x}P(x)\log \frac{P(x)}{Q(x)}={\sum }_y{\sum }_{x:T(x)=y}P(x)\log \frac{P(x)}{Q(x)}.$

对每个 $y$,令 $a_x=P(x)$,$b_x=Q(x)$(对所有 $x\in T^{-1}(y)$),由对数和不等式: ${\sum }_{x:T(x)=y}P(x)\log \frac{P(x)}{Q(x)}\ge !\left({\sum }_{x:T(x)=y}P(x)\right)\log \frac{{\sum }_{x:T(x)=y}P(x)}{{\sum }_{x:T(x)=y}Q(x)}=P_{T(X)}(y)\log \frac{P_{T(X)}(y)}{Q_{T(X)}(y)}.$

对 $y$ 求和即得 $D_{\mathrm{KL}}(P_X|Q_X)\ge D_{\mathrm{KL}}(P_{T(X)}|Q_{T(X)})$。$■$

直观 对数据做任何处理(映射/压缩/随机化),两个分布之间的 KL 散度只会减小,不会增大。这与互信息版本的数据处理不等式在本质上是同一件事(因为 $I(X;Y)=D_{\mathrm{KL}}(P_{XY}|P_X{P}_Y)$)。

6.6.4 Fano 不等式

背景:在信息论与统计中,我们常常想知道:如果从 $Y$ 中恢复 $X$,错误概率至少有多大?Fano 不等式给出了这个下界。

定理 6.16(Fano's Inequality) 设 $X\in {\mathcal{D}}_X$,$Y$ 为随机变量,$\hat{X}=f(Y)$ 是基于 $Y$ 对 $X$ 的估计器。令 $P_e=\mathrm{Pr}[\hat{X}\ne X].$ 则 $H(X\mid Y)\le H_2(P_e)+P_e\log (|{\mathcal{D}}_X|-1).$ 从而(由 $H_2(P_e)\le 1$)得到简化下界: $P_e\ge \frac{H(X\mid Y)-1}{\log |{\mathcal{D}}_X|}.$

证明(平均参数法 + 双向展开) 不妨设 $\hat{X}$ 是 $Y$ 的确定函数(若为随机函数,对随机化参数取期望后结论不变)。令 $E=1[\hat{X}\ne X]\in 0,1\text{(错误指示变量)}.$

对 $H(E,X\mid Y)$ 做两种展开:

展开一(先展开 $X$): $H(E,X\mid Y)=H(X\mid Y)+H(E\mid X,Y).$ 因为 $E$ 由 $X$ 和 $Y$(以及 $\hat{X}=f(Y)$)完全确定,所以 $H(E\mid X,Y)=0$。故 H(E,X\mid Y)=H(X\mid Y).\tag{1}

展开二(先展开 $E$): H(E,X\mid Y)=H(E\mid Y)+H(X\mid E,Y)\le H(E)+H(X\mid E,Y).\tag{2} 上式不等号由”条件使熵减小”给出。

估计 $H(X\mid E,Y)$: $H(X\mid E,Y)=\underset{1-P_e}{\underbrace{\mathrm{Pr}[E=0]}}\cdot H(X\mid E=0,Y)+\underset{P_e}{\underbrace{\mathrm{Pr}[E=1]}}\cdot H(X\mid E=1,Y).$

• $E=0$ 意味着 $\hat{X}=X$,故 $X$ 由 $Y$ 完全确定,$H(X\mid E=0,Y)=0$;
• $E=1$ 意味着 $X\ne \hat{X}(Y)$,此时 $X$ 落在 ${\mathcal{D}}_X\setminus \hat{X}(Y)$ 中,共 $|{\mathcal{D}}_X|-1$ 个值,故 $H(X\mid E=1,Y)\le \log (|{\mathcal{D}}_X|-1)$。

因此 $H(X\mid E,Y)\le P_e\log (|{\mathcal{D}}_X|-1)$。

合并:由 $(1)=(2)$ 及 $H(E)=H_2(P_e)$: $H(X\mid Y)\le H_2(P_e)+P_e\log (|{\mathcal{D}}_X|-1).■$

Fano 不等式的应用 若要证明 任何基于 $Y$ 的估计器都有较大错误概率,只需证明 $H(X\mid Y)$ 很大。这是信息论证明下界的标准框架,在编码定理逆向证明、统计学习理论等场合大量使用。

---

6.7 信道容量初探

定义 6.17(信道容量,Shannon 1948) 信道 $\Pi$ 的容量定义为对所有合法输入分布取最大化的互信息: $C(\Pi )={\max }_{X\sim \chi }I(X;Y),Y\sim \Pi (\cdot \mid X).$

Shannon 信道编码定理(非正式) 任何速率 $R<C(\Pi )$ 的可靠通信都是可实现的:存在编码方案使错误概率趋于零。反之,任何 $R>C(\Pi )$ 的可靠通信都是不可能的。

可实现速率上限:$R=C(\Pi )-o(1)$。

例 6.18(BSC(ε) 的容量) $C(\mathrm{BSC}(\epsilon ))={\max }_{X}I(X;Y)=1-H_2(\epsilon ),$ 在 $X\sim \mathrm{Bern}(1/2)$ 时取到(此时 $H(Y)=1$ 取最大)。

当 $\epsilon =0$(无噪声)时 $C=1$;当 $\epsilon =1/2$(完全随机)时 $C=0$。

---

附录:第 5—6 周公式速查

公式	含义
$H(X\mid Y)\le H(X)$	条件使熵减小(等号 $⟺$ 独立)
$H(X,Y)=H(X)+H(Y\mid X)$	链式法则(熵)
$I(X;Y)=H(X)-H(X\mid Y)$	互信息定义
$I(X;Y)=D_{\mathrm{KL}}(P_{XY}\Vert P_X{P}_Y)$	互信息与 KL 散度
$I(X;Y,Z)=I(X;Y)+I(X;Z\mid Y)$	链式法则(互信息)
$I(X;Z)\le I(X;Y)$,若 $X\to Y\to Z$	数据处理不等式
$D_{\mathrm{KL}}(P_X\Vert Q_X)\ge D_{\mathrm{KL}}(P_{T(X)}\Vert Q_{T(X)})$	KL 散度的数据处理
$H(X\mid Y)\le H_2(P_e)+P_e\log (\Vert {\mathcal{D}}_X\Vert -1)$	Fano 不等式
$C(\Pi )={\max }_{X}I(X;Y)$	信道容量

符号	含义
$\Omega$	样本空间
$D_X,\mathrm{Supp}(X)$	$X$ 的值域、支撑集
$p_X(x)$	$X$ 的 PMF
$p_{X,Y},p_{X\mid Y}$	联合/条件 PMF
$E[X],\mathrm{Var}(X)$	期望、方差
$X\perp \perp Y$	$X,Y$ 独立
$X\perp \perp Y\mid Z$	给定 $Z$ 条件独立
$H(X),H_2(p)$	熵、二元熵
$H(X,Y),H(X\mid Y)$	联合熵、条件熵
$\log$	默认以 2 为底

---

一句话总结

概率三大不等式(Markov / Chebyshev / Chernoff)给我们尾部估计的工具;熵则把这些”概率”凝练成对”信息量”的度量,联合熵与条件熵进一步刻画多个随机变量间的信息关系。