第五讲、平稳离散信源的熵

约 987 个字 7 张图片预计阅读时间 3 分钟

一、基本定义

随机过程： $t \sim X(t)$
我们希望：能把随机变量的熵推广到随机过程
平稳随机过程：
- 定义：对于任意的 $n$，任意的 $t_1, t_2, \cdots, t_n \in T$ 和 $h$，若 $(X(t_1), X(t_1), \cdots, X(t_n))$ 与 $(X(t_1 + h), X(t_2 + h), \cdots, X(t_n + h))$ 具有同样的分布，则称随机过程 $\{X(t)\}$ 是平稳随机过程。
- 性质：
  - $E(X(t_n)) = E(X(t_n + h)) = E(X(0)) = Const.$
  - $X(t)$ 的均值和方差对于所有 $t$ 都一样。

例：温度？不是平稳信源，因为h=5个月，一月的第一天和六月的第一天不会遵照同分布。

平稳信源：任意长度片段的联合概率分布与时间起点无关

$$ Pr(X_1X_2 \cdots X_L) = Pr(X_{1+n}X_{2+n} \cdots X_{L+n}) $$ - 简单无记忆信源：不同时间的随机变量不相关

$$ Pr(X_1X_2 \cdots X_L) = \prod_{i=1}^{L} Pr(X_i) $$ - $m$阶马尔可夫信源：（$m = 1$：马尔可夫信源）

\[ Pr(X_l \mid X_{l-1}X_{l-2} \cdots X_0) = Pr(X_l \mid X_{l-1}X_{l-2} \cdots X_{l-m}) \]

二、平稳信源的熵

如果一个平稳信源发出长度为 $N$ 的序列 $X_1, X_2, \cdots, X_n$，令 $N$ 维随机矢量 $X = (X_1, X_2, \cdots, X_n)$，则

\[ H(X) = H(X_1, X_2, \cdots, X_n) = -\sum p(x_1, x_2, \cdots, x_n) \log p(x_1, x_2, \cdots, x_n) \]

我们考虑掷骰子：掷一次，$\log_26$; 两次，$2\log_26,\dots$

$\therefore H(X)$ 随 $N$ 增长而增长，趋向无穷大

这样会导致无法比较，我们就需要定义平均每符号熵：$H_N(X) \triangleq \frac{1}{N} H(X) = \frac{1}{N} (X_1X_2 \cdots X_N)$。由此我们就可以研究出一个单位有多少即知信息量。

熵速率：$H_{\infty}(X) = \lim_{N \to \infty} H_N(X)$

平均条件熵：$H(X_N \mid X_{N-1}X_{N-2} \cdots X_1)$

三、平稳信源熵的性质

$H(X_N \mid X_{N-1}X_{N-2} \cdots X_1)$ 随 $N$ 增大而单调不增

物理意义： - 书写l，不确定度很大 - 而当书写到lo时，剩下的字母可能性就消了，不确定度减小了很多 - 到lov的时候，就没几种可能了。 - love: 0 bit

证明：

利用$H(X|Y)\leq H(X),$

$H(X_N|X_1,X_2,\cdots, X_{N-1})$ $\leq H(X_N|X_2,\cdots,X_{N-1}) = H(X_{N-1}|X_1,\cdots,X_{N-2}) \leq H(X_2|X_1) \leq H(X_1)$

(等号是由于平稳信源的性质)

$H_N(X) \geq H(X_N \mid X_{N-1}X_{N-2} \cdots X_1)$

证明：

$H_N(X)=\frac{1}{N}H(X_1,X_2,\cdots, X_{N-1},X_{N})$

$H_N(X)$ 随 $N$ 增大也单调不增

利用$H(Y)=H(XY)+H(Y|X)$

有：$H_N(X)=\frac{1}{N}\{H(X_1,X_2,\cdots,X_{N-1})+H(X_N | X_1, X_2, \cdots, X_{N-1})\}$

进行递推：

原式$\leq \frac{1}{N} \{(N-1)H_{N-1}(X)+H_N(X)\}$ （不等号：第二条性质+$H_N(X)$的定义）

显然有$H_N(X) \leq H_{N-1}(X)$

$\therefore \text{原式} \leq \frac{1}{N} \{(N-1)H_{N-1}(X)+H_{N-1}(X)\}=H_{N-1}(X)$

$\therefore H_N(X) \leq H_{N-1}(X)$

$H_{\infty}(X) = \lim_{N \to \infty} H_N(X) = \lim_{N \to \infty} H(X_N \mid X_{N-1}X_{N-2} \cdots X_1)$

四、熵速率

对无记忆离散源，若 $X$ 在取值范围 $\mathcal{X}=\set{x_1,x_2,\cdots,x_K}$ 上等概分布，则 $H(X)=\log K\triangleq H_0$。

马尔可夫信源

对于 $m$ 阶马尔科夫信源，$x_{i_{n}}$是$n$时刻信源输出符号，$s_{i_{n}}$是$n$时刻信源状态。每一个状态$s_{i}$对应一个长度为 $m$ 的符号序列。

$p_{ij}(n)$ 是 $n$ 时刻状态 $s_{i}$ 转移到 $s_{j}$ 的概率。

对于既约的马尔可夫信源，存在一个唯一的平稳分布 $Q$，使得 $Q=P^{T}Q$。

马尔可夫信源的熵率

马尔可夫信源的熵率等于信源在各状态下的条件熵对状态概率求平均。