信息论学习笔记（四）

发表于 2025-05-18 分类于计算机

前段时间查文献的时候，偶然看到了一些算法里涉及到了信息论的相关知识。信息论我在几年前通过看书自学过，时间太久有些忘了，正好趁此机会重新复习一下。

参考书籍：机械工业《信息论基础（原书第二版）》（ELEMENTS OF INFORMATION THEORY SECOND EDITION），作者Thomas M. Cover, Joy A. Thomas

随机过程的熵率

随机过程 ${X_t}$ 是一个带下标的随机变量序列，（对于马尔科夫链来说，序列里的各位置的值之间不相互独立）。要刻画这个随机过程，需要知道所有有限的联合概率密度函数：

$$
P{(X_1, X_2, \ldots, X_n)=(x_1,x_2,\ldots,x_n)} = p(x_1, x_2, \ldots, x_n)
$$

若对于一个随机过程的每个 n 与位移 $l$ ，$\forall x_1, x_2, \ldots, x_n \in X$，均满足

$$
P(X_1 = x_1, X_2 = x_2, \ldots, X_n = x_n) = P(X_{1+l} = x_1, X_{2+l} = x_2, \ldots, X_{n+l} = x_n)
$$

则称该过程平稳。

对 $n = 1, 2, \ldots$ 及所有 $x_1, x_2, \ldots, x_n \in X$，有

$$
P(X_{n+1} = x_{n+1} | X_n = x_n, X_{n-1} = x_{n-1}, \ldots, X_1 = x_1) = P(X_{n+1} = x_{n+1} | X_n = x_n)
$$

则离散随机过程 $X_1, X_2, \ldots$ 为马尔可夫过程。【即，第 $n+1$ 时刻的状态仅依赖于第 $n$ 时刻，而与更早的状态无关】

若条件概率 $P(X_{n+1} | X_n)$ 不依赖于 n，即对于 $n = 1, 2, \ldots$，有

$$
P(X_{n+1} = b | X_n = a) = P(X_2 = b | X_1 = a), (\forall a, b \in X)
$$

则称马尔可夫链是时间不变的。【无特别声明，总是假定马尔可夫链时间不变】

对于马尔可夫链 ${X_t}$，$X_n$ 为 n 时刻的状态。

一个时间不变的马尔可夫链完全由初始状态与概率转移矩阵 $P = [P_{ij}]$ 所表征。

$$
P_{ij} = P(X_{n+1} = j | X_n = i), (i, j \in {1, 2, \ldots, m})
$$

对于一个马尔可夫链：

若在时刻 n，随机变量的概率密度函数为 $p(x_n)$，那么在 n+1 时刻，概率密度函数为

$$
p(x_{n+1}) = \sum_{x_n} p(x_n) P_{x_n x_{n+1}}
$$

若在n+1时刻，状态空间上的分布与n时刻的分布相同，则称此分布为平稳分布。

若马尔可夫链的初始状态服从平稳分布，那么其为平稳过程。

当下列极限存在时，随机过程 ${X_i}$ 的熵率定义为

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

其反映了n个随机变量的每字符熵。

$$
H(X) = \lim_{n \to \infty} \frac{1}{n} H(X_1, X_2, \ldots, X_n)= \lim_{n \to \infty} \frac{1}{n} \log m^n = \log m \text{ (bit/字符)}
$$

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

当下列极限存在时，定义一个与熵率有关的量【已知前n-1随机变量的情况下，最后一个随机变量的条件熵】：

$$
H’(X) = \lim_{n \to \infty} H(X_n | X_{n-1}, X_{n-2}, \ldots, X_1)
$$

对于平稳过程，$H(X)$，$H’(X)$ 均存在，且相等。

对于平稳的马尔可夫链【平稳分布为 $\mu$ ，转移矩阵为 $P$ ，则 $H(X)=-\sum_{ij}\mu_iP_{ij}logP_{ij}$ 】， $H(X) = H(X_1 | X)$ ，其中的条件熵可根据给出的平稳分布计算得到：平稳分布 $\mu$ 为下列方程组的解：

$$
\mu_j = \sum_i \mu_i P_{ij} \text{ (对 } \forall j \text{ 的解)}
$$

$X_1, X_2, \ldots, X_n$ 构成平稳的马尔可夫链，$Y_i = f(X_i)$，则：
- ①$H(Y_n | Y_{n-1}, Y_{n-2}, \ldots, Y_1, X_n) \leq H(\mathcal{Y}) \leq H(Y_n | Y_{n-1}, \ldots, Y_1)$ ， $\mathcal{Y}$ 为包含所有 $Y_i$ 的集合
- ② $\lim_{n \to \infty} H(Y_n | Y_{n-1}, \ldots, Y_1, X_n) = H(\mathcal{Y}) = \lim_{n \to \infty} H(Y_n | Y_{n-1}, \ldots, Y_1)$

也可考虑 $X_i$ 的随机函数 $Y_i$（非确定性过程）
- 给定马尔可夫链 $X_1, X_2, \ldots, X_n$，则得到 $Y_1, Y_2, \ldots, Y_n$，且每个 $Y_i$ 服从 $p(Y_i | X_i)$ 在条件独立于其它所有 $X_j, j \neq i$。
  - 即 $p(x^n, y^n) = p(x^n) \prod_{i=1}^n p(x_{i+1} | x_i) \prod_{i=1}^n p(y_i | x_i)$ ，是为隐马尔可夫模型 (HMM)