資訊理論抄書筆記 - 馬爾可夫鏈與熵的結合

04-12

針對隨機變數 $X$ ，其熵 $H(X)=-sum_x p(x)log_2 p(x)$ 可以衡量 $X$ 的不確定度。

複雜一點，聯合分布 $(X,Y)$ ，熵為 $H(X,Y)=-sum_xsum_yp(x,y)log_2p(x,y)$ 。

而當這裡的隨機變數 $X$ 變成一個隨機過程 ${X_i}$ 時，就有必要重新思考如何度量不確定度了。單個的定義 $H(X_i)$ 不是很好，於是我們乾脆定義一個比較平均一點的熵-熵率。

Definition 1：熵率（entropy rate）：
若極限 $H(chi)=lim_{n ightarrow infty}frac{{H(X_1,X_2,...,X_n)}}{n}$ 存在，則 $H(chi)$ 稱為 ${X_i}$ 的熵率

另一個量也與熵率有不可描述的聯繫： $qquad quad H(chi)=lim_{n ightarrowinfty}H(X_n|X_{n-1},X_{n-2},...,X_1)$

這兩個量也不過是反映一個隨機過程的entropy怎麼變化的。

而以此定義的同時，會得到一個比較漂亮的結果，如下：

Theorem 1：
一個平穩隨機過程 ${X_i}$ （即 $P(X_1=x_1,X_2=x_2,....,X_n=x_n) = P(X_{1+l},X_{2+l},...,X_{n+l})$ ，任意連續n個狀態之間的聯繫和時間無關），它的 $H(chi)=H(chi)$

這個證明其實比較容易，淑芬中有一道經典的習題 $qquad 已知lim_ { n ightarrow infty}a_n=a,那麼lim_{n ightarrow infty}frac{sum_{i=0}^na_i}{n} = a$

這道題在這裡有了運用。

$H(X_n|X_{n-1},...,X_1)=H(X_{n+1}|X_n,...,X_2) \ geq H(X_{n+1}|X_n,...,X_2,X_1)$

第一個等式是平穩性得到，後面相當於說明了 $a_n$ 是遞減恆正，則 $a_n$ 自然有極限，

結合 $frac{H(X_1,..,X_n)}{n}=frac{1}{n}sum_{i=1}^nH(X_i|X_{i-1},...,X_1)\$

兩邊取極限，可以很容易得證

而這個漂亮的性質，應用在我們的馬爾科夫過程中，就有更加亦可賽艇的結論！

先上馬爾可夫過程（又稱為馬爾可夫鏈）定義

Definition 2：馬爾可夫鏈(Markov chain or Markov process)

離散隨機過程 ${X_i}$ 滿足 $P(X_n=x_n|X_{n-1}=x_{n-1},...,X_1=x_1) = P(X_n=x_n|X_{n-1}=x_{n-1})$
則稱其為馬爾可夫鏈

對於這個定義，其實有一個比較有趣的概括

Knowing the present state, the future of the system is independent of the past.

某種程度上相當於：對於現在的你來說，未來永遠與過去無關 （這句話...或許能拿來煲一碗雞湯）

那麼這樣來的話，對於平穩的Markov chain，初始為平穩分布，它的熵率 $H(chi) = lim_{n ightarrow infty}H(X_n|X_{n-1}) = H(X_2|X_1) \ =-sum_{x_1,x_2}p(x_1)p(x_2|x_1)log_2 p(x_2|x_1)$

所以對於Markov chain求熵率其實很簡單，然而我們眉頭微微一皺，會發現事情並不簡單。經常會有隨機過程不是Markov chain，而是Markov chain的函數

比如離散的隨機過程 ${Y_i}$ 和平穩的Markov chain ${X_i}$ 滿足 $Y_i=f(X_i)$ 。

其實問題並不複雜.....

重新思考下可以發現：

顯然這個隨機過程是平穩的，因此也可以用 $H(Y_n|Y_{n-1},...,Y_1) ightarrow H(Upsilon)$ 來求熵率，但除此之外我們有一些奇妙的結論，比如關於 ${Y_i}$ 的夾逼不等式。

Theorem 2： $H(Y_n|Y_{n-1},...,Y_1,X_1)leq H(Upsilon) leq H(Y_n|Y_{n-1},...,Y_1)$
且
$lim_{n ightarrowinfty}H(Y_n|Y_{n-1},...,Y_1,X_1)= H(Upsilon) = lim_{n ightarrowinfty}H(Y_n|Y_{n-1},...,Y_1)$

定理的證明有點巧，但也自然，兩個式子的右式的證明，在前面說明 $qquad H(Y_n|Y_{n-1},...,Y_1)quad$ 關於n遞減,取極限時給過了。問題主要是左邊的式子的證明。

對於第一個不等式來說，我們想辦法把Markov chain的性質和平穩的性質用上去。 $egin{align} H(Y_n|Y_{n-1},...,Y_1,X_1) &leq H(Y_n|Y_{n-1},...,Y_1,X_1,_...,X_{-k})qquad Markov quad chain性質 \ &=H(Y_n|Y_{n-1},...,Y_1,X_1,_...,X_{-k},Y_{-k},..Y_{1}) quad 因為Y_i是X_i的函數\ &= H(Y_{n+k}|Y_{n+k-1},.....,Y_1,X_k,...,X_1)quad平穩性質\ &leq H(Y_{n+k}|Y_{n+k-1},...,Y_{1}) end{align}$

再令 $k ightarrow infty$ 得證

第二個等式來說仿照上面的證法，利用 $H(Y_n|Y_{n-1},...,Y_1,X_1)-H(Y_n|Y_{n-1},...,Y_1)=I(X_1;Y_n|Y_{n-1},...,Y_1)\$ 和 $sum_{n=1}^{infty}I(X_1;Y_n|Y_{n-1},...,Y_1)=lim_{n{ ightarrow}infty}I(X_1;Y_1,...,Y_n)$ 就能得證

於是乎，這篇文章講了什麼呢？

emmm......主要講了怎麼定義隨機過程的「熵」以及怎麼求這個「熵」，尤其是Markov chain的熵率，大概就是這樣。