Week 8

回顾

Shannon-type Inequality

$I(X;Y\mid Z)\ge 0$

所有正线性组合（positive linear combinations）均满足此类不等式。

KL 散度：

$D_{KL}(P\Vert Q)={\sum }_{x}p(x)\log \frac{p(x)}{Q(x)}$

全变差距离与 KL 散度的关系：

$\Vert P-Q{\Vert }_{TV}=\sqrt{O(D_{KL}(P\Vert Q))}$

更精确的表述是 Pinsker 不等式：$\Vert P-Q{\Vert }_{TV}\le \sqrt{\frac{1}{2}{D}_{KL}(P\Vert Q)}$，上式为课堂简化记法。

信息论安全（Information Theoretic Security） vs 计算安全（Computational Security）

---

Def 3.42 Commitment Scheme

符号约定：

• $M$：消息（message）
• $C$：承诺（commitment）
• $R$：随机字符串（random string）

定义：

$C=\text{Commit}(M,R)$

$\text{Verify}(C,M,R)\to \{0,1\}$

性质

(1) Hiding（隐藏性）： Commitment 不泄露关于 $M$ 的任何信息，即：

$I(M;C)=0$

等价地：

$H(M)-H(M\mid C)=0$

即已知 $C$ 后，$M$ 的不确定性没有减少。

(2) Binding（绑定性）： 给定 $C$，$M$ 被唯一确定，即：

$H(M\mid C)=0$

注意 Hiding 和 Binding 在信息论意义下是互相矛盾的（两者不能同时完美满足），实际方案通常在计算安全意义下实现其中一个。例如 $C=\text{SHA256}(M,R)$ 在计算安全意义下满足 Binding，在信息论意义下满足 Hiding（因为 $R$ 是随机的）。

例子：石头剪刀布

Alice 和 Bob 用 Commitment Scheme 实现公平的石头剪刀布：

1. Alice 计算 $C=\text{Commit}(\text{"stone"},R)$
2. Alice 将 $C$ 发送给 Bob
3. Bob 发送 $\text{"Scissor"}$ 给 Alice
4. Alice 发送 $M=\text{"stone"}$，$R$ 给 Bob
5. Bob 验证 $\text{Verify}(C,M,R)=1$

这保证了 Alice 无法在看到 Bob 的选择后改变自己的选择（Binding），且 Bob 在步骤 3 前无法得知 Alice 的选择（Hiding）。

---

Def 3.43 Secret Sharing（秘密共享）

$(t,n)$-threshold Secret Sharing：

• 秘密：$S$
• 份额：$R_1,R_2,\dots ,R_n$

性质

1) Reconstruction（重构性）： 任意 $t$ 个份额可以恢复秘密。

$H(S\mid R_J)=0,\forall J\subseteq [n]\text{ with }|J|=t,R_J=\{R_j:j\in J\}$

2) Privacy（隐私性）： 任意 $t-1$ 个份额不泄露关于 $S$ 的任何信息。

$H(S\mid R_J)=H(S),\forall J\subseteq [n]\text{ with }|J|=t-1$

---

引入：熵、地址与通信

端到端消息传输

如何将消息从端到端传递：

信道模型：BSC($\epsilon$)（Binary Symmetric Channel，二元对称信道，翻转概率为 $\epsilon$）。

---

4 Compression（压缩）

4.1 Asymptotic Equipartition Property（渐近等分性）

Thm 4.1（AEP）

设 $X_1,\dots ,X_n$ 为 i.i.d.，分布为 $p(x)$，则：

$-\frac{1}{n}\log P(X_1,\dots ,X_n)\stackrel{P}{\to }H(X)$

即 $\forall \epsilon >0$：

${\lim }_{n\to \infty }\mathrm{Pr}\left[\left|-\frac{1}{n}\log P(X_1,\dots ,X_n)-H(X)\right|\ge \epsilon \right]=0$

证明：

$-\frac{1}{n}\log P(X_1,\dots ,X_n)=-\frac{1}{n}{\sum }_{i=1}^n\log P(X_i)$

随机变量 $-\log P(X_i)$ 是 i.i.d. 的，期望为 $H(X)$，由弱大数定律（weak law of large numbers）得证。

---

Thm 4.2（Quantitative AEP，定量渐近等分性）

设 $X_1,\dots ,X_n$ 为 i.i.d.，分布为 $p(x)$。

令 $B={\max }_x(-\log p(x))=O_p(1)$，则对任意 $\epsilon >0$ 和所有 $n$：

$\mathrm{Pr}\left[\left|\frac{1}{n}\log P(X_1,\dots ,X_n)-H(X)\right|\ge \epsilon \right]\le O_{n\to \infty ;\epsilon }(1)=2^{-{\Omega }_{\epsilon }(n)}\le 2\exp \left(-\frac{n{\epsilon }^2}{3B^2}\right)$

证明：

令 $Z_i=-\log P(X_i)$，则：

$-\frac{1}{n}\log P(X_1,\dots ,X_n)=\frac{1}{n}(Z_1+\cdots +Z_n)$

$Z_i$ 取值在 $(0,B]$ 内，对 $Z_1,\dots ,Z_n$ 应用 Chernoff 界即得。

---

典型集（Typical Set）

定义：

${\text{Typical}}_{\epsilon }(n)=\left\{x_1,\dots ,x_n\in {\mathcal{X}}^n:\left|-\frac{1}{n}\log P(X_1,\dots ,X_n)-H(X)\right|\le \epsilon \right\}$

由 AEP：

$\mathrm{Pr}\left[X_1,\dots ,X_n\notin {\text{Typical}}_{\epsilon }(n)\right]\le 2^{-{\Omega }_{p,\epsilon }(n)}$

---

Prop 4.3 典型集的大小

对任意 $\epsilon >0$ 以及充分大的 $n$（即 $n\ge N(\epsilon ,p)$）：

$(1-\epsilon )2^{n(H(X)-\epsilon )}\le \left|{\text{Typical}}_{\epsilon }(n)\right|\le 2^{n(H(X)+\epsilon )}$

证明（上界 $\le$）：

对典型集中的每个 $x$，有 $P(x)\ge 2^{-n(H(X)+\epsilon )}$，故：

$1\ge {\sum }_{x\in {\text{Typical}}_{\epsilon }(n)}P(x)\ge \left|{\text{Typical}}_{\epsilon }(n)\right|\cdot 2^{-n(H(X)+\epsilon )}$

从而 $\left|{\text{Typical}}_{\epsilon }(n)\right|\le 2^{n(H(X)+\epsilon )}$。

证明（下界 $\ge$）：

对典型集中的每个 $x$，有 $P(x)\le 2^{-n(H(X)-\epsilon )}$，故：

${\sum }_{x\in {\text{Typical}}_{\epsilon }(n)}P(x)\le \left|{\text{Typical}}_{\epsilon }(n)\right|\cdot 2^{-n(H(X)-\epsilon )}$

又由 Quantitative AEP：

${\sum }_{x\in {\text{Typical}}_{\epsilon }(n)}P(x)=1-O_{n\to \infty ;p,\epsilon }(1)\ge (1-\epsilon )$

两式合并得 $\left|{\text{Typical}}_{\epsilon }(n)\right|\ge (1-\epsilon )\cdot 2^{n(H(X)-\epsilon )}$。

---

Def 4.4（Uniquely Decodable，唯一可译码）

码 $C:\mathcal{X}\to \{0,1{\}}^{\ast }$ 是唯一可译的，若对任意两个有限序列 $(x_1,\dots ,x_n)$ 和 $(y_1,\dots ,y_m)$（元素均取自 $\mathcal{X}$），等式：

$C(x_1)\cdots C(x_n)=C(y_1)\cdots C(y_m)$

蕴含 $n=m$ 且 $x_i=y_i$，$\forall i$。

---

Def 4.5（Prefix Code，前缀码）

码 $C:\mathcal{X}\to \{0,1{\}}^{\ast }$ 称为前缀码（或无前缀码，prefix-free code），若没有任何码字是另一个码字的前缀。

前缀码一定是唯一可译码，可以用二叉树表示：每个码字对应一个叶节点，从根到叶的路径给出码字。

---

Thm 4.6（Source Coding Theorem，信源编码定理）

设 $\mathcal{X}$ 是有限集，$p(x)$ 是 $\mathcal{X}$ 上的分布。

1）可达性（存在好码）： 对任意 $\ell >H(X)$ 以及充分大的 $n$，存在唯一可译码 $C:{\mathcal{X}}^n\to \{0,1{\}}^{\ast }$，使得：

$\frac{1}{n}{\sum }_{x\in {\mathcal{X}}^n}p(x)|C(x)|\le \ell$

2）逆定理（下界）： 对任意唯一可译码 $C:{\mathcal{X}}^n\to \{0,1{\}}^{\ast }$ 和任意 $n$，平均码长满足：

$\frac{1}{n}{\sum }_{x\in {\mathcal{X}}^n}p(x)|C(x)|\ge H(X)$

证明（上界部分）

设 $\{x^{(1)},\dots ,x^{(T)}\}$ 枚举 ${\text{Typical}}_{\epsilon }(n)$，其中 $T\le 2^{n(H(X)+\epsilon )}$。

定义码 $C:{\mathcal{X}}^n\to \{0,1{\}}^{\ast }$，码长 $t=\lceil {\log }_2(T+1)\rceil =n(H(X)+\epsilon )+2$：

$C(x)=\{\begin{array}{ll}\text{Binary}(i,t)& x=x^{(i)}\in {\text{Typical}}_{\epsilon }(n)\\ 0^t\cdot \text{Enc}(x_1)\cdots \text{Enc}(x_n)& \text{otherwise}\end{array}$

其中 $\text{Enc}:\mathcal{X}\to \{0,1{\}}^{\lceil {\log }_2|\mathcal{X}|\rceil }$ 是对单个符号的定长编码。

码长分析：

若 $x$ 是典型序列： $|C(x)|=\lceil {\log }_2(T+1)\rceil \le n(H(X)+\epsilon )+2$

否则： $|C(x)|\le n(H(X)+\epsilon )+2+n\lceil {\log }_2|\mathcal{X}|\rceil$

平均码长：

$\text{average length}=n(H(X)+\epsilon )+2+\mathrm{Pr}\left[x\notin {\text{Typical}}_{\epsilon }(n)\right]\cdot n\lceil {\log }_2|\mathcal{X}|\rceil$

$\le n(H(X)+\epsilon )+2^{-{\Omega }_{\epsilon ,p}(n)}\cdot O_p(n)$

$=n(H(X)+\epsilon )+o(n)$

故对充分大的 $n$，平均每符号码长 $\le \ell =H(X)+2\epsilon$（可取任意 $\epsilon >0$）。$■$