Created: 2026-03-06 07:53:04
Updated: 2026-03-06 07:53:04

4.1 马尔可夫链

随机过程是一系列随机变量，它们可以存在任意的依赖关系。随机过程由它们的联合分布唯一确定：

Pr{(X1,X2,…,Xn)=(x1,x2,…,xn)}=p(x1,x2,…,xn),(x1,x2,…,xn)∈Hn,n=1,2,…\text{Pr}\left\{(X_{1},X_{2},\dots,X_{n})=(x_{1},x_{2},\dots,x_{n})\right\} = p(x_{1},x_{2},\dots,x_{n}),\qquad(x_{1},x_{2},\dots,x_{n})\in \mathscr{H}^n ,n=1,2,\dots

Stationary process：stationary process指的是任意一系列随机变量的联合分布不依赖于时间。

马尔可夫链:Xn+1X_{n+1}只依赖于XnX_{n}，与其他变量无关。

Pr(Xn+1=xn+1∣Xn=xn,Xn−1=n−1,…,X1=x1)=Pr(Xn+1=xn+1∣Xn=xn)\text{Pr}(X_{n+1}=x_{n+1}\mid X_{n}=x_{n},X_{n-1}=n-1,\dots,X_{1}=x_{1}) = \text{Pr}(X_{n+1}=x_{n+1}\mid X_{n}=x_{n})

除非另行说明，始终假设马尔可夫链是时不变的。此时一个马尔可夫链由状态转移矩阵和初态唯一确定。
不可约马尔可夫链：从链中的任意态，经过有限步，能以非零概率到达任意态。

如果n+1n+1时的分布和nn时的一致，那么这个分布叫做定态分布（Stationary distribution）。之所以这么叫，是因为一个马尔可夫链初态是Stationary distribution,那么它形成了stationary process.

对于非周期、不可约的有限状态马尔可夫链，它的稳态分布是唯一的。从任意初态分布，时间无限长后达到的分布都趋于这个稳态分布。

4.2 Entropy Rate

对于随时间变化的过程，一个自然的问题是：熵如何随时间增长/变化？

定义：一个随机过程{Xi}\{X_{i}\}的Entropy rate为（当极限存在时）：

H(H)=lim⁡n→∞1nH(X1,X2,…,Xn)H(\mathscr{H})=\lim_{ n \to \infty } \frac{1}{n}H(X_{1},X_{2},\dots,X_{n})

例子：

1.Typewriter （打字机）

认为mm个字符等可能出现，考虑nn次打字的过程，于是H(X1,X2,…,Xn)=log⁡mn,H(H)=log⁡mH(X_{1},X_{2},\dots,X_{n})=\log m^n,H(\mathscr{H})=\log m

2.独立同分布随机变量

X1,X2,…X_{1},X_{2},\dots 是独立同分布随机变量，那么

H(H)=lim⁡n→∞H(X1,X2,…Xn)n=lim⁡n→∞nH(X1)n=H(X1)H(\mathscr{H})=\lim_{ n \to \infty } \frac{H(X_{1},X_{2},\dots X_{n})}{n} = \lim_{ n \to \infty } \frac{nH(X_{1})}{n} = H(X_{1})

3.独立但不同分布随机变量

H(X1,X2,…,Xn)=∑i=1nH(Xi)H(X_{1},X_{2},\dots,X_{n})= \sum_{i=1}^nH(X_{i})
但各个H(Xi)不相等。我们可以挑选一系列XiX_{i}使得极限值不存在。例如，pi=P(Xi=1)p_{i}=P(X_{i}=1)，

pi={0.5if 2k<log⁡log⁡i≤2k+10if 2k+1<log⁡log⁡i≤2k+2for k =0,1,2,...p_{i} = \begin{cases} 0.5 & \text{if}\ 2k<\log \log i\leq 2k+1 \\ 0 & \text{if}\ 2k+1<\log \log i \leq 2k+2 \end{cases}\qquad \text{for k =0,1,2,...}

这样有很长的H(Xi)=1H(X_{i})=1的序列，并紧跟着长度指数增长H(Xi)=0H(X_{i})=0的序列，使得足以影响该序列之前的平均值，因此平均值的极限不存在。

定义一个与熵率相关的量：当极限存在时，

H′(H)=lim⁡n→∞H(Xn∣Xn−1,Xn−2,…,X1)H'(\mathscr{H}) = \lim_{ n \to \infty } H(X_{n}\mid X_{n-1},X_{n-2},\dots,X_{1})

前者是平均每个符号的熵，后者是已知之前的符号时后一个符号的熵。

[!theorem] Theorem 4.2.1

对于平稳随机过程，上述两个极限均存在，且有H(H)=H′(H)H(\mathscr{H})=H'(\mathscr{H})

[!Theorem] Theorem 4.2.2
对于平稳随机过程，H(Xn∣Xn−1…X1)H(X_{n}\mid X_{n-1}\dots X_{1})随n递减，且极限为H′(H)H'(\mathscr{H})

[!Proof]
H(Xn+1∣X1,X2,…,Xn)≤H(Xn+1∣Xn,…,X2)=H(Xn∣Xn−1…X1)H(X_{n+1}\mid X_{1},X_{2},\dots,X_{n})\leq H(X_{n+1}\mid X_{n},\dots,X_{2})=H(X_{n}\mid X_{n-1}\dots X_{1})
由于H(Xn∣Xn−1,…,X1)H(X_{n}|X_{n-1},\dots,X_{1})是非负递减序列，因此有极限值，按定义记为H′(H)H'(\mathscr{H})

[!Theorem] Theorem 4.2.3(Cesaro mean)
若an→a,bn=∑i=1nanna_{n}\to a,b_{n} = \frac{\sum_{i=1}^na_{n}}{n},则bn→ab_{n}\to a

下面证明Theorem 4.2.1.由链式法则

H(X1,X2,…,Xn)n=1n∑i=1nH(Xi∣Xi−1,…,X1)\frac{H(X_{1},X_{2},\dots,X_{n})}{n} = \frac{1}{n}\sum_{i=1}^n H(X_{i}\mid X_{i-1},\dots,X_{1})

Entropy rate 是conditional entropy的时间平均，加上定理4.2.2和4.2.3，即可得证。
随机过程的熵率的重要性来源于ergodic process（各态历经过程）的AEP。书中15.7将证明，对于各态历经过程，以下极限有概率1会发生： ^4a9bc6

−1nlog⁡p(X1,X2,…,Xn)→H(H)-\frac{1}{n}\log p(X_{1},X_{2},\dots,Xn) \to H(\mathscr{H})

对于马尔可夫链，熵率由如下公式给出：

H(H)=H′(H)=lim⁡n→∞H(Xn∣Xn−1,…,X1)=lim⁡n→∞H(Xn∣X1)=H(X2∣X1)H(\mathscr{H}) = H'(\mathscr{H}) = \lim_{ n \to \infty } H(X_{n}\mid X_{n-1},\dots,X_{1}) = \lim_{ n \to \infty } H(X_{n}\mid X_{1}) = H(X_{2}\mid X_{1})

其中条件熵由稳态分布给出。
或者写作：

H(H)=−∑ijμiPijlog⁡PijH(\mathscr{H}) = -\sum_{ij}\mu_{i}P_{ij}\log P_{ij}

4.3 Example：Entropy rate of a random walk on a weighted graph

Consider a weighted and undirected graph, with weight Wij≥0W_{ij}\geq 0 from node ii to node jj, Wij=WjiW_{ij}=W_{ji}. A particle randomly walks from node to node in this graph. The random walk XnX_{n} is a sequence of vertices of a graph. The probability of choosing the next vertex j given Xn=iX_{n}=i is proportional to the weight of the edge.

Pij=Wij∑kWikP_{ij} =\frac{W_{ij}}{\sum_{k}W_{ik}}

这时，定态分布有一个十分简单的形式。令Wi=∑jWijW_{i} = \sum_{j}W_{ij}, W=∑i,j:j>iWijW = \sum_{i,j: j>i} W_{ij}是对图中所有边的求和。于是∑iWi=2W\sum_{i}W_{i} = 2W

我们猜测，稳态分布是

μi=Wi∑iWi\mu_{i} = \frac{W_{i}}{\sum_{i}W_{i}}

只需证明μP=μ\mu P =\mu。于是

∑iμiPij=∑iWi2WWijWi=∑i12WWij=Wj2W=μj\begin{align} \sum_{i}\mu_{i}P_{ij} & =\sum_{i} \frac{W_{i}}{2W} \frac{W_{ij}}{W_{i}} \\ \\ & =\sum_{i} \frac{1}{2W}W_{ij} \\ & = \frac{W_{j}}{2W}=\mu_{j} \end{align}

注意，最后一行的求和用到了无向图的对称性。
我们可以计算熵率

H(H)=H(X2∣X1)=−∑iμi∑jPijlog⁡Pij=−∑iWi2W∑jWijWilog⁡WijWi=−∑i∑jWij2Wlog⁡Wij2W+∑i∑jWij2Wlog⁡Wi2W\begin{align} H(\mathscr{H}) & = H(X_{2}\mid X_{1}) \\ & =-\sum_{i}\mu_{i} \sum_{j}P_{ij} \log P_{ij} \\ & =-\sum_{i} \frac{W_{i}}{2W} \sum_{j} \frac{W_{ij}}{W_{i}} \log \frac{W_{ij}}{W_{i}} \\ & = -\sum_{i}\sum_{j} \frac{W_{ij}}{2W}\log \frac{W_{ij}}{2W} + \sum_{i}\sum_{j} \frac{W_{ij}}{2W}\log \frac{W_{i}}{2W} \end{align}

例如，考虑king在8×88\times 8格子上的运动。在中央时，king等概率向周围8个格子运动；在一边时，可以向周围5个格子运动；在一个角落时，可以向周围3个格子运动。因此，根据这些数值按正比分配概率，就得到分布{8420,5420,3420}\left\{ \frac{8}{420}, \frac{5}{420}, \frac{3}{420} \right\}，这个随机过程的熵率是0.92log⁡80.92\log 8.当n无穷大时，这个随机过程不存在边缘效应，就将得到log⁡8\log 8的熵率。

4.4 Hidden Markov Models

令X1,X2,…,XnX_{1},X_{2},\dots,X_{n}是一个stationary Markov chain，令Yi=ϕ(Xi)Y_{i} = \phi(X_{i})是一个处理，于是得到随机变量的序列Y1,Y2,…,YnY_{1},Y_{2},\dots,Y_{n}。在多数情况下，我们只有系统的一部分信息。如果YiY_{i}也构成马尔可夫链的话，会极大地简化问题，但多数情况下并不是这样。不过，既然马尔可夫链是定态的，YiY_{i}也是，因此它的熵率是良定义的。不过如果我们计算H(Y)H(\mathscr{Y})，我们有可能会算H(Yn∣Yn−1,…,Y1)H(Y_{n}\mid Y_{n-1},\dots,Y_{1})，对每个n，然后找出它的极限。既然这个收敛可能会任意慢，我们也不会知道我们得到的值有多接近极限值，也不知道该什么时候停止计算。
从计算上讲，拥有极限的上界和下界值是相当有用的。我们可以在二者差很小的时候停止计算，然后得到一个极限的很好的估计。
我们已经知道H(Yn∣Yn−1,…,Y1)H(Y_{n}\mid Y_{n-1},\dots,Y_{1})是单调递减并逼近H(Y)H(\mathscr{Y})的。对于下界，我们将使用H(Yn∣Yn−1,…,Y2,X1)H(Y_{n}\mid Y_{n-1},\dots,Y_{2},X_{1})。这是一个很清晰的trick，因为X1X_{1}与Y1,Y0,…Y_{1},Y_{0},\dots相比包含了关于YnY_{n}同样多的信息。

title: Lemma 4.4.1
$$
H(Y_{n}\mid Y_{n-1},\dots,Y_{2},Y_{1})\leq H(\mathscr{Y})
$$

```ad-note
title: Proof
collapse: open
We have, for $k = 1,2,...,$
证明左侧式子随n增加单调增加：
$$
\begin{align}
H(Y_n | Y_{n-1},\dots,Y_{2},X_{1})  &= H(Y_{n}\mid Y_{n-1} ,\dots,Y_{2},Y_{1},X_{1}) \tag{$Y_i=f(X_i)$}\\
   &= H(Y_{n}\mid Y_{n-1},\dots,Y_{1},X_{1},X_{0},X_{-1},\dots,X_{-k}) \tag{Markovity of X} \\
   &= H(Y_{n}\mid Y_{n-1},\dots,Y_{1},X_{1},X_{0},X_{-1},\dots,X_{-k},Y_{0},\dots,Y_{-k})  \tag{$Y_i=f(X_i)$}\\
   & \leq  H(Y_{n}\mid Y_{n-1},\dots,Y_{1},Y_{0} ,\dots,Y_{-k})\tag{conditioning reduces entropy} \\
  & = H(Y_{n+k+1}\mid Y_{n+k},\dots,Y_{1}) \tag{stationarity}
\end{align}
$$
```

title: Lemma 4.4.2
$$
H(Y_{n}\mid Y_{n-1},\dots,Y_{1})-H(Y_{n}\mid Y_{n-1},\dots,Y_{1},X_{1}) \to 0
$$
```ad-note
title: Proof：
collapse: open
$$
H(Y_{n}\mid Y_{n-1},\dots,Y_{1}) - H(Y_{n}\mid Y_{n-1},\dots,Y_{1},X_{1})= I(X_{1};Y_{n}\mid Y_{n-1},\dots,Y_{1})
$$
By properties of mutual information:
$$
I(X_{1};Y_{1},Y_{2},\dots,Y_{n})\leq H(X_{1})
$$
注意，这里分号后没有竖线，这意味着表示的是$X_1$和"各个$Y_{i}$联合分布"之间的共同信息。
Hence,
$$
\lim_{ n \to \infty } I(X_{1};Y_{1},\dots,Y_{n}) \leq H(X_{1})
$$
By chain rule,
$$
\begin{align}
\lim_{ n \to \infty } I(X_{1};Y_{1},\dots,Y_{n}) &  = I(X_{1};Y_{1})+I(X_{1};Y_{2}\mid Y_{1})+I(X_{1};Y_{3}\mid Y_{1},Y_{2})+\dots+I(X_{1};Y_{n}\mid Y_{1},\dots,Y_{n-1})+\dots \\
&= \sum_{i=1}^\infty I(X_{1};Y_{i}\mid Y_{i-1},\dots,Y_{1})
\end{align}
$$
左侧的极限是有界的，右侧的无穷和各个项非负，因此项的极限存在且必为0：
$$
\lim_{ n \to \infty } I(X_{1};Y_{n}\mid Y_{n-1},\dots,Y_{1})=0
$$

最后，我们总结一下得到的结论：

title: Theorem 4.4.1

If $X_{1},X_{2},\dots,X_{n}$ form a stationary Markov Chain, and $Y_{i}=\phi(X_{i})$, then
$$
H(Y_{n\mid Y_{n-1},\dots,Y_{1},X_{1}}) \leq H(\mathscr{Y}) \leq H(Y_{n}\mid Y_{n-1},\dots,Y_{1})
$$
and
$$
\lim_{ n \to \infty } H(Y_{n}\mid Y_{n-1},\dots,Y_{1},X_{1}) = H(\mathscr{Y}) =\lim_{ n \to \infty } H(Y_{n}\mid Y_{n-1},\dots,Y_{1})
$$

Leave a Comment

captcha
Fontsize