本記事は情報理論の徹底解説シリーズに含まれます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
証明する定理
以下の3つの定理を証明します。
- 定常情報源の
エントロピーレートに関する定理 -
\begin{align}
\lim_{t\rightarrow \infty}\frac{H(X_1, \cdots, H_t)}{t} &= \lim_{t\rightarrow \infty}H(X_t| X_1, \cdots, X_{t-1})
\end{align} - 無記憶かつ定常な情報源の
エントロピーレート -
\begin{align}
\lim_{t\rightarrow \infty}\frac{H(X_1, \cdots, H_t)}{t} &= H(X_1)
\end{align} - 単純マルコフ定常情報源の
エントロピーレート -
\begin{align}
\lim_{t\rightarrow \infty}\frac{H(X_1, \cdots, H_t)}{t} &= H(X_2|X_1)
\end{align}
以下でそれぞれ証明していきます。
証明
定常情報源のエントロピーレートに関する定理
定常性とは，時間経過にかかわらずシンボル間の遷移確率が一定であるような情報源のことを指します。最初に，右辺の条件付きエントロピーが収束することを示します。エントロピーは，条件が多くなると小さくなっていく性質があるため，以下の不等式が成り立ちます。（Shannonの不等式）
H(X_{t}|H(X_1, \cdots, X_{t-1})) &= H(X_{t+1}|H(X_2, \cdots, X_{t})) \quad (\because \text{分布の定常性より})\\
&\geq H(X_{t+1}|H(X_1, \cdots, X_{t})) \quad (\because \text{条件付きエントロピーの性質より})
\end{align}
したがって，$H(X_{t}|X_1, \cdots, X_{t-1})$は収束します。続いて，エントロピーのチェインルールから同時エントロピーを条件付きエントロピーの和で表します。
H(X_1, \cdots, H_t) &= H(X_1) + H(X_2|X_1) + H(X_3|X_1, X_2) + \cdots +H(X_{t}|X_1,\cdots, X_{t-1})\\
&= \sum_{i=1}^t H(X_i|X_1, \cdots, X_{i-1})
\label{chain_entropy}
\end{align}
ここで，チェザロ平均という関係を利用します。
- チェザロ平均
-
\begin{align}
b_t &= \frac{\sum_{i=1}^t a_t}{t}
\end{align}
に対して，以下の極限\begin{align}
\lim_{t\rightarrow\infty}a_t&= a
\end{align}
が存在するとき，以下の関係が成り立つ。\begin{align}
\lim_{t\rightarrow\infty}&= a
\end{align}
先ほど，$H(X_{t}|X_1, \cdots, X_{t-1})$が収束することを示しましたので，$a_t=H(X_{t}|X_1, \cdots, X_{t-1})$とセットしてもOKです。すると，チェザロ平均の関係より$b_t = \frac{\sum_{i=1}^tH(X_{t}|X_1, \cdots, X_{t-1})}{t}$も極限$a$が存在します。したがって，式(\ref{chain_entropy})より，以下の関係が成立します。
a &= \lim_{t\rightarrow \infty}H(X_{t}|X_1, \cdots, X_{t-1})\\
&= \lim_{t\rightarrow \infty}\frac{\sum_{i=1}^tH(X_{t}|X_1, \cdots, X_{t-1})}{t}\\
&= \lim_{t\rightarrow \infty}\frac{H(X_1, \cdots, X_{t})}{t}\quad (\because \text{式(\ref{chain_entropy})より})
\end{align}
したがって，示したい等式が得られます。
\lim_{t\rightarrow \infty}\frac{H(X_1, \cdots, H_t)}{t} &= \lim_{t\rightarrow \infty}H(X_t| X_1, \cdots, X_{t-1})
\end{align}
無記憶かつ定常な情報源のエントロピーレート
続いて，無記憶性かつ定常性をもつ情報源のエントロピーレートの公式を導出します。そこまで難しくありません。基本的に，「定常情報源のエントロピーレートに関する定理」の右辺をいじっていきます。
\lim_{t\rightarrow \infty}H(X_t| X_1, \cdots, X_{t-1})
&= H(X_t)&&(\because \text{無記憶性より})\\
&= H(X_1)&&(\because \text{定常性より})\\
\end{align}
これにて証明終了です。
単純マルコフ定常情報源のエントロピーレート
最後に，単純マルコフ性をもつ定常性情報源のエントロピーレートの公式を導出します。単純マルコフ性とは，1つ前のシンボルに依存して次のシンボルの生起確率が定まるような情報源の性質のことを指しています。こちらも，そこまで難しくありません。先ほど同様に，「定常情報源のエントロピーレートに関する定理」の右辺をいじっていきます。
\lim_{t\rightarrow \infty}H(X_t| X_1, \cdots, X_{t-1})
&= H(X_t|X_{t-1})&&(\because \text{単純マルコフ性より})\\
&= H(X_2|X_1)&&(\because \text{定常性より})\\
\end{align}
これにて証明終了です。
コメント