熵

基本概念

熵：$H(X)=-\sum_{x} p(x)\log p(x)$
条件熵：$H(X|Y)=H(X,Y)-H(Y)=\sum_y p(y)H(X|Y=y)=-\mathbb{E}[\log p(X|Y)]$
互信息：$I(X;Y)=\sum_{x\in\mathcal{X}}\sum_{y\in\mathcal{Y}}p(x,y)\log\frac{p(x,y)}{p(x)p(y)}=H(X)+H(Y)-H(XY)=H(X)-H(X|Y)$
相对熵（$KL$ 散度）：$D(p|q)=\sum_x p(x)\log \frac{p(x)}{q(x)}$

链式法则

  • $H(X_1,X_2,\cdots,X_n)=\sum_{i}H(X_1|X_1,X_2,\cdots,X_i)$
  • $I(X_1,X_2,…,X_n;Y)=I(X_1;Y)+I(X_2;Y|X_1)+I(X_3;Y|X_1,X_2)+…+I(X_n;Y|X_1,…,X_{n-1})$
  • $D(p(x,y)|q(x,y))=D(p(x)|q(x))+D(p(y|x)|q(y|x))$

不等式

  • $0\leq H(X)\leq \log|\mathcal{X}|$；当 $X$ 确定时取 $0$，当 $X$ 为均匀分布时取 $\log|\mathcal{X}|$
  • $0\leq H(X|Y)\leq H(X)$；当 $\forall y$ 使得 $p(y)>0$ 时，$X$ 取值确定时取 $0$，当 $X,Y$ 独立时取 $\log |\mathcal{X}|$
  • $0\leq I(X;Y)\leq \min(H(X),H(Y))$；当 $X,Y$ 独立时取 $0$，当 $X$ 是 $Y$ 的函数时取 $H(Y)$
  • 需要注意 $D(p|q)\neq D(q|p)$；$0\leq D(p|q)$，当 $p=q$ 时取 $0$
  • 熵的凹性：$H(\lambda X+(1-\lambda)Y)\geq \lambda H(X)+(1-\lambda)H(Y)$；考虑 $X,Y$ 的混合
  • 相对熵的凸性：$D(\lambda p_1+(1-\lambda)p_2|\lambda q_1+(1-\lambda)q_2)\leq \lambda D(p_1|q_1)+(1-\lambda)D(p_2|q_2)$
  • 数据处理不等式：对于马尔可夫链 $X\leftrightarrow Y\leftrightarrow Z$，有：$I(X;Z)\leq I(X;Y)$
  • 费诺不等式：对于马尔可夫链：$X\leftrightarrow Y\leftrightarrow \hat X$，设错误率 $P_e=Pr[X\neq \hat X]$，则有 $H(P_e)+P_e\log |\mathcal{X}|\geq H(X|\hat X)\geq H(X|Y)$；属于数据处理不等式的推广

等式

  • $H(X)=\log |\mathcal{X}|-D(X|u_\mathcal{X})$：熵越大，和均匀分布越相似
  • $I(X;Y)=D(p_{XY}|p_Xp_Y)=\min_{q_X,q_Y} D(p_{XY}|q_Xq_Y)$
  • 组合法则：$H(p_1,p_2,p_3,\cdots,p_n)=H(p_3,\cdots,p_n)+(p_1+p_2)H(\frac{p_1}{p_1+p_2},\frac{p_1}{p_1+p_2})$

渐进均分性

令 $X_1,X_2,\cdots, X_n\quad \text{i.i.d.}$，则 $A_\epsilon^{(n)}={(x_1,x_2,…,x_n)|2^{-n(H(X)+\epsilon)}<p(x_1,x_2,…,x_n)<2^{-n(H(X)-\epsilon)}}$ 为其典型集。（特别地，当其为均匀分布时，$|A^{(n)}_\epsilon|\rightarrow 2^{-n\log |\mathcal{X}|}=|\mathcal{X}|^n$）

  • 当 $n$ 充分大时，采样 $n$ 个元素得到的序列属于典型集的概率大于 $1-\epsilon$
  • 典型集大小的下界是 $(1-\epsilon)2^{n(H(X)-\epsilon)}$（当 $n$ 充分大时），上界是 $2^{n(H(X)+\epsilon)}$
  • 典型集的大小与具体的概率分布无关，而只与其熵有关

当我们使用典型集编码时，考虑一个长度为 $n$ 的码：若其在典型集中则编码，否则失败。于是失败概率为 $1-\epsilon$，平均码长为 $H(X)$。

随机过程

熵率

随机过程两种熵率的定义为：
$$H(\mathcal{X})=\lim_{n\rightarrow\infty}\frac1nH(X_1,X_2,\cdots,X_n)$$

$$H’(\mathcal{X})=\lim_{n\rightarrow\infty}H(X_n|X_1,X_2,\cdots,X_{n-1})$$
对于平稳随机过程，有 $H(\mathcal{X})=H’(\mathcal{X})$。

非周期不可约平稳马尔可夫过程的熵率

$$H(\mathcal{X})=H’(\mathcal{X})=\lim_{n\rightarrow\infty}H(X_n|X_{n-1})=H(X_2|X_1)$$
因此计算过程分为三步：

  • 解 $\mu=\mu P$ 得到平稳分布 $\mu$
  • 令 $X_1\sim \mu$，计算 $(X_1,X_2)$ 的分布
  • $H(\mathcal{X})=H(X_2|X_1)=H(X_1X_2)-H(X_1)$

马尔可夫链的函数

设 $X_1,X_2,…,X_n$ 为马尔可夫链，再设 $Y_i=\Phi(X_i)$，其中 $\Phi$ 为一随机过程，有：
$$H(Y_n|X_1,Y_1,Y_2,\cdots,Y_{n-1})\leq H(\mathcal{Y})\leq H(Y_n|Y_1,Y_2,\cdots,Y_{n-1})$$
$$\lim_{n\rightarrow\infty} H(Y_n|X_1,Y_1,Y_2,\cdots,Y_{n-1})= H(\mathcal{Y})=\lim_{n\rightarrow\infty} H(Y_n|Y_1,Y_2,\cdots,Y_{n-1})$$

数据压缩

Kraft不等式

  • 对于即时码，$\sum_{x\in \mathcal{X}}D^{-l(x)}<1$ 是即时码存在的充分必要条件
  • 对于唯一可译码，条件不变

香农码

  • 考虑修正累积分布函数，对每个样本取该函数值小数点后 $l_i$ 位作为编码
  • 其中 $l_i=\lceil \log_D\frac{1}{p_i}\rceil$
  • 对于香农码，有 $H_D(X)\leq L<H_D(X)+1$
  • 竞争最优性：考虑另一个唯一可译码的长度 $l’(x)$，有：$$Pr[l’(x)\leq l(x)-c]\leq\frac{1}{2^{c-1}}$$证明通过拆分后应用 Kraft 不等式得到。

信道容量

定义

  • 信道容量定义为：$\max_{p(x)}I(X;Y)$
  • 对于二元对称信道，有 $C=1-H(p)$
  • 对于二元擦除信道，有 $C=1-a$
  • 对于一般对称信道，有 $C=\log|\mathcal{Y}|-H(\text{转移分布})$
  • $(M,n)$ 码的码率为 $R=\frac{\log M}{n}$

联合典型性

定义服从 $p(x,y)$ 的联合典型序列集合 $A^{(n)}_\epsilon$ 为：
$$A^{(n)}_\epsilon={(x^n,y^n)\in\mathcal{X}^n\times\mathcal{Y}^n:|-\frac1n\log p(x^n)-H(X)|<\epsilon,|-\frac1n\log p(y^n)-H(Y)|<\epsilon,|-\frac1n\log p(x^n,y^n)-H(X,Y)|<\epsilon }$$

具有以下性质：

  • $Pr[(X^n,Y^n)\in A^{(n)}_\epsilon]\rightarrow 1$
  • $|A^{(n)}_\epsilon|\leq 2^{n(H(X,Y)+\epsilon)}$
  • 若 $(X_1^n,Y_1^n)\sim p(X^n)p(Y^n)$，即 $X_1$ 与 $Y_1$ 是独立的且与 $(X,Y)$ 具有相同的边际分布，则有 $Pr[(X_1^n,Y_1^n)\in A^{(n)}_\epsilon]\leq 2^{-nI(X;Y)-3\epsilon}$

其余结论

  • 并联信道的信道容量：$2^C=2^{C_1}+2^{C_2}$

微分熵

概念

  • $h(X)=-\int p(x)\log p(x)\text{d}x$，$h(X)$ 可以是负数
  • $h(X,Y)=-\int\int p(x,y)\log p(x,y)\text{d}x\text{d}y$
  • $h(X|Y)=h(XY)-h(Y)$
  • $D(f|g)=\int f(x)\log \frac{f(x)}{g(x)}\text{d}x$；$D(f|g)\geq 0$，当 $f$ 与 $g$ 在至多一个零测集上不相等时取等
  • $I(X;Y)=h(X)+h(Y)-h(XY)$；$I(X;Y)\geq 0$，当 $X,Y$ 独立时取等

推论

  • $h(aX)=h(X)+\log|a|$
  • $h(\mathcal{N}(\mu,K))=\frac12\log(2\pi e)^n\text{det}(K)$，在给定方差时，这是令微分熵最大的分布

高斯信道

定义

在一个功率为 $P$、噪声方差为 $N$ 的高斯信道中，我们做出如下定义：

  • 下标集：${1,2,\cdots,M}$
  • 编码函数：$f:[1,M]^n\rightarrow \mathbb{R}^n$
  • 译码函数：$g:\mathbb{R}^n\rightarrow [1,M]^n$
  • 算术平均误差：$P^{(n)}e=\frac1M \sum{i=1}^M \lambda_i$，其中 $\lambda_i$ 为 $P[g(y^n_i)\neq i|\text{输入}x^n_i]$

高斯信道假定信道的噪声来源是一个标准正态分布 $Z=\mathcal{N}(0,N)$。因此在随机变量的意义上有：$Y=X+Z$。

高斯信道编码定理

通过数学形式的定义，我们已经定义出一个功率限制为 $P$、噪声方差为 $N$ 的高斯信道的信道容量为：
$$C=\max_{f(x):\mathbb{E}[X^2]\leq P}I(X;Y)=\frac12\log(1+\frac PN)$$

率失真理论

率失真函数

  • 定义：$R(D)=\min_{\sum_{(x,\bar x)}p(x)p(\bar x|x)d(\bar x,x)\leq D}I(X;\bar X)$
  • 率失真定理：对于 $R> R(D)$，存在码字集大小为 $M=2^{nR}$ 的码序列 $X^n$ 使得 $\mathbb{E}[X^n,{\bar X}^n]\leq D$

率失真计算

  • 伯努利信源+汉明距离：$R(D)=H(X)-H(X|\hat X)=H(p)-H(D)$
  • 高斯信源+均方距离：$R(D)=h(X)-h(X|\hat X)\geq h(X)-h(\mathcal{N}(0,(X-\hat X)^2))=\frac12\log\frac{\sigma^2}{D}$

信源信道分离性

  • 率失真为 $R(D)$ 的信源能够在信道容量为 $C$ 的信道中传输当且仅当 $R(D)<C$

型方法

概念

  • 型 $T$ 是一个 $n$ 维单纯型上的一点，定义出 $n$ 个维度的频数比例
  • 令 $\mathcal{P}$ 为所有 $n$ 维型的集合，则有 $|\mathcal{P}_n|\leq (n+1)^{|\mathcal{X}|}$
  • 令 $P\in\mathcal{P}$ ，则所有长度为 $n$ 且型为 $P$ 的所有序列的集合为 $T(P)$

基本定理

  • $|\mathcal{P}_n|\leq (n+1)^{|\mathcal{X}|}$
  • $\frac{1}{(n+1)^{|\mathcal{X}|}}2^{nH(P)}\leq|T(P)|\leq 2^{nH(P)}$
  • $\frac{1}{(n+1)^{|\mathcal{X}|}}2^{-nD(P_x|Q)}\leq Q^n(T(P))\leq 2^{-nD(P_x|Q)}$
  • $Q^n(x)=2^{-n(D(P_x|Q)+H(P_x))}$

通用信源编码

  • 思想：采样足够多次，通过频率估计概率进行编码。
  • 表达：存在一列通用信源编码 $(2^{nR},n)$，使得对满足 $H(Q)<R$ 的任何信源 $Q$ 都有 $P^{(n)}_e\rightarrow 0$
  • 考虑 $R_n=R-|\mathcal{X}|\frac{\log(n+1)}{n}$ 作为传输速率

Sanov定理

  • 令 $X_1,X_2,\cdots,X_n\sim Q(x)\text{i.i.d}$，令 $E\subseteq\mathcal{P}$ 为一个概率分布，则有：$$Q^n(E)=Q^n(E\cap \mathcal{P}n)\leq(n+1)^{|\mathcal{X}|}2^{-nD(P^|Q)}$$
    其中 $P^    =\arg \min    {P\in E}D(P|Q)$ 是在相对熵意义下最接近 $Q$ 的 $P\in E$

  • 假定需要计算 $Pr[\frac1n\sum_{i=1}^ng_j(X_i)\geq a_j,j=1,2,\cdots,k]$，则定义集合 $E={P:\sum_aP(a)g_j(a)\geq a_j,j=1,2,\cdots,k}$；可计算出 $P^*$ 为：$$P^*=\frac{Q(x)e^{\sum_i \lambda_ig_i(x)}}{\sum_{a\in \mathcal{X}}Q(a)e^{\sum_i \lambda_ig_i(a)}}$$

  • 例子：计算骰子投掷 $n$ 次后点数平均值大于等于 $4$ 的概率。令 $E={P:\sum_{i=1}^6 iP(i)\geq 4}$，代入得 $P^*=\frac{2^{\lambda x}}{\sum_{i=1}^6 2^{\lambda i}}$

假设检验

  • 设 $X_1,X_2,\cdots,X_n\sim Q\quad \text{i.i.d.}$
  • 设 $H_1:Q=P_1,\quad H_2:Q=P_2$，令 $\alpha,\beta$ 为双边的错误率
  • 有当 $\alpha\rightarrow 0$ 时，$\beta\rightarrow 2^{-nD(P_1|P_2)}$

Fisher信息与Cramer-Rao不等式

  • 进行参数估计时，令$J(\theta)=\mathbb{E}_\theta[\frac{\partial}{\partial \theta}\ln f(x;\theta)]^2$
  • 对 $\theta$ 的任意无偏估计量 $T$，有 $\text{var}(T)\geq \frac{1}{J(\theta)}$