随机过程的熵率

前面几章默认的信源模型大多是 i.i.d.（独立同分布）。这很方便，但也很理想化。现实里很多序列都有记忆：

• 自然语言中，字母 q 后面通常接 u
• 天气预报中，今天晴天会影响明天晴天的概率
• 用户点击序列中，当前页面会影响下一步行为

这时单个变量的熵 $H(X)$ 已不足以描述整个信源。因为相邻符号有相关性，知道过去会降低未来的不确定性。于是信息论引入熵率：长期看来，信源每产生一个符号，平均到底新增多少信息。

为什么需要平稳性

若一个过程的统计规律随着时间漂移，那么"长期平均每步信息量"可能根本没有稳定意义。平稳性就是为了排除这种不稳定。

随机过程是什么

随机过程 $\{X_i\}_{i\ge 1}$ 是一列带时间下标的随机变量。对任意 $n$，其联合分布写成

与前面章节不同，这里不再默认各个时刻独立。联合分布可能包含很强的时间相关性。

平稳过程是什么

若对任意整数 $n,k\ge 1$，都有

即任意长度为 $n$ 的块的联合分布在时间平移后不变，则称该过程是平稳的。

直觉上，平稳表示"统计规律不随时间改变"——序列样子会变，但生成机制不变。这正是熵率定义有意义的前提。

为什么需要这个定义

对长度为 $n$ 的序列，总熵是 $H(X_1,\dots,X_n)$。如果我们想问"平均每个符号对应多少信息"，自然要除以 $n$。再让 $n\to\infty$，就得到长期平均值。

它是什么

若极限存在，随机过程 $\mathcal X=\{X_i\}$ 的熵率定义为

对平稳过程，这个极限存在。

两种等价表达

由链式法则，

因此

对平稳过程，可证明条件熵序列 $H(X_n|X_1^{n-1})$ 随 $n$ 单调不增且极限存在，并满足

两种表达是完全等价的：

与 i.i.d. 的关系

若 $X_1,X_2,\dots$ i.i.d.，则

因此

熵率退化为单符号熵，说明熵率是熵在"有记忆信源"上的推广。

为什么条件熵会递减

因为条件越多，不确定性越小。一般有

所以把更长的历史作为条件，不会增加对下一个符号的不确定性。

为什么需要马尔可夫假设

完整随机过程的历史依赖太复杂——$X_{n+1}$ 可能依赖所有过去。马尔可夫链提供了一个足够简单、又能表达相关性的模型：未来只依赖当前状态。

它是什么

若对任意 $n$，都有

则称 $\{X_n\}$ 为一阶马尔可夫链。

若转移规律不随时间变，即

与 $n$ 无关，则称为时间不变马尔可夫链（也叫平稳马尔可夫链）。这类链完全由初始分布 $p(X_1)$ 和转移矩阵 $P=[P_{ij}]$ 共同刻画。

怎么推联合分布

由链式法则和马尔可夫性质：

这就是马尔可夫链比一般过程更易处理的根本原因。

马尔可夫链状态转移图

以二状态链为例，转移矩阵

对应的状态转移图如下：

stateDiagram-v2
  direction LR
  [*] --> 状态0
  [*] --> 状态1

  状态0 --> 状态0 : P00=0.9
  状态0 --> 状态1 : P01=0.1
  状态1 --> 状态0 : P10=0.2
  状态1 --> 状态1 : P11=0.8
  

为什么需要平稳分布

若初始状态 $X_1$ 就服从平稳分布 $\mu$，那么以后每个时刻的边缘分布都一样，整个链就是平稳过程，此时熵率表达式会大幅简化。

它是什么

若分布 $\mu=(\mu_1,\dots,\mu_m)$ 满足

或向量形式

则称 $\mu$ 为该马尔可夫链的平稳分布。

含义：一步转移后，分布不变。

怎么求平稳分布：解方程组

对二状态链，设 $\mu=(\mu_0,\mu_1)$，则

展开第一行：$\mu_0 = 0.9\mu_0 + 0.2\mu_1$，化简得 $\mu_0=2\mu_1$。

结合 $\mu_0+\mu_1=1$，解得

存在唯一性条件

若有限状态马尔可夫链满足：

• 不可约：任意状态都能经有限步到达任意其他状态
• 非周期：返回某状态的可能步数没有公共周期结构

则平稳分布唯一，且从任意初始分布出发，状态分布最终都会收敛到它。

它是什么

若 $\{X_n\}$ 是平稳马尔可夫链，平稳分布为 $\mu$，转移矩阵为 $P$，则熵率为

进一步展开为

怎么推出来

第一步，由马尔可夫性质，给定完整历史与只给定上一步完全等价：

第二步，由平稳性，这个条件熵与时刻无关，所以所有 $n\ge 2$ 都等于 $H(X_2|X_1)$。结合熵率的条件熵形式：

第三步，按条件熵定义展开：

平稳下 $\Pr(X_1=i)=\mu_i$，而

代入即得

怎么理解

它就是"每个状态的下一步随机性"按该状态长期出现频率（即平稳分布 $\mu_i$）做加权平均。

两种形式的关系图

graph LR
    A["H_n = (1/n)H(X_1,...,X_n)"] --> B["链式法则"]
    B --> C["条件熵形式 H(X_n|X_1^{n-1})"]
    C --> D["马尔可夫简化 H(X_n|X_{n-1})"]
    D --> E["平稳下 = H(X_2|X_1)"]
    E --> F["—求和—> H = -Σμ_i ΣP_ij log P_ij"]
    style F fill:#dbeafe
  

对于打字机，没有记忆，熵率就是单符号熵；对于有记忆信源，熵率取决于平稳分布和转移矩阵。

下面用一个对称二状态马尔可夫链来演示 $P_{11}$（自留概率）从 $0.5$ 到 $0.99$ 时熵率的变化。当 $P_{11}$ 接近 $1$ 时，系统强烈倾向于保持当前状态，下一步的条件熵变小，熵率下降。

图中蓝线为熵率 $H(P_{11})$，橙色滑块控制 $P_{11}$，橙色点显示当前值。当 $P_{11}=0.5$（无记忆）时 $H=1$ bit；当 $P_{11}\to 1$ 时 $H\to 0$，系统趋于确定。

加权图上的随机游走

课件给出了一种把马尔可夫链推广到加权图的方式：节点 $i$ 到节点 $j$ 的转移概率与边权重 $W_{ij}$ 成正比。

平稳分布：$\mu_j=\frac{d_j}{\sum_k d_k}$，其中 $d_j=\sum_i W_{ij}$ 是节点 $j$ 的度。

热力学第二定律的类比

把孤立系统看作马尔可夫链，可以证明：

• 相对熵 $D(u_n\|u)$ 随 $n$ 递减，系统趋向平衡分布
• 若平稳分布是均匀分布，则熵增加
• 对于平稳马尔可夫过程，条件熵 $H(X_n|X_1)$ 随 $n$ 递增

这些结论与热力学第二定律的形式完全对应，说明熵率概念不只属于通信理论，它本质上描述的是"一个随机动力系统长期每步产生多少新不确定性"。

平稳过程与时不变马尔可夫链的关系

graph TB
    A["随机过程 {X_n}"] --> B{满足马尔可夫性？}
    B -->|是| C["时间不变马尔可夫链"]
    B -->|否| D["一般平稳过程"]
    C --> E{初始分布 = 平稳分布？}
    E -->|是| F["平稳马尔可夫链
可直接套公式计算熵率"]
    E -->|否| G["统计量收敛到平稳分布
需计算极限"]
    D --> H["用熵率定义式
H = lim (1/n)H(X1,...,Xn)"]
    F --> I["H = -Σμ_i ΣP_ij log P_ij"]
    G --> J["迭代求μ = μP极限"]
    J --> I
    H --> K["或用条件熵形式
H = lim H(X_n|X_1^{n-1})"]
  

总结：若链是时间不变的且从平稳分布出发，则熵率可直接套公式；若初始分布不是平稳分布，则需先求平稳分布 $\mu=\mu P$。

模型描述

棋子只能在棋盘格子上做随机移动。不同棋子有不同的合法走法，产生不同的转移矩阵和熵率。

象的例子特别有意思——由于只能走同色格子，整个图被分割成两个不相通的子图，没有唯一的平稳分布。这提醒我们：马尔可夫链的不可约性（任意状态可互通）不是理所当然的。