本記事は情報理論の徹底解説シリーズに含まれます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
目次
エントロピーレートに関する公式
- 定常情報源のエントロピーレートに関する定理
-
\begin{align}
\lim_{t\to\infty}\frac{H(X_{1}, \cdots, H_{t})}{t} = \lim_{t\to\infty}H(X_{t}|X_{1},\cdots, X_{t-1})\label{main1}
\end{align} - 無記憶かつ定常な情報源のエントロピーレート
-
\begin{align}
\lim_{t\to\infty}\frac{H(X_{1},\cdots,H_{t})}{t} = H(X_{1})\label{main2}
\end{align} - 単純マルコフ定常情報源のエントロピーレート
-
\begin{align}
\lim_{t\to\infty}\frac{H(X_{1},\cdots,H_{t})}{t} = H(X_{2}|X_{1})\label{main3}
\end{align}
証明
定常情報源のエントロピーレートに関する定理
次のチェザロ平均を用いて証明します。
チェザロ平均
$\displaystyle b_{t}=\frac{\sum_{i=1}^{t}a_{i}}{t}$に対して極限$\displaystyle\lim_{t\to\infty}\sum_{i=1}^{t}a_{i}=\alpha$が存在するとき，$\displaystyle\lim_{t\to\infty}b_{t}=\alpha$が成り立つ。
これを式($\ref{main1}$)に適用するためには，$H(X_1, \cdots, H_t)$を$\sum_{i=1}^{t}a_{i}$のような形で表す必要があります。エントロピーのチェインルールを利用すると，
\begin{align}
H(X_{1}, \cdots, H_{t})
&= H(X_{1}) + H(X_{2}|X_{1}) + \cdots +H(X_{t}|X_{1},\cdots, X_{t-1})\\[0.7em]
&= \sum_{i=1}^{t} H(X_{i}|X_{1}, \cdots, X_{i-1})
\end{align}
H(X_{1}, \cdots, H_{t})
&= H(X_{1}) + H(X_{2}|X_{1}) + \cdots +H(X_{t}|X_{1},\cdots, X_{t-1})\\[0.7em]
&= \sum_{i=1}^{t} H(X_{i}|X_{1}, \cdots, X_{i-1})
\end{align}
と表されます。一方，定常情報源では時間経過によらずシンボル間の遷移確率が一定となるため，
\begin{align}
H(X_{i}|X_{1}, \cdots, X_{i-1}) &= H(X_{i+1}|X_{2}, \cdots, X_{i})
\end{align}
H(X_{i}|X_{1}, \cdots, X_{i-1}) &= H(X_{i+1}|X_{2}, \cdots, X_{i})
\end{align}
が成り立ちます。また，エントロピーは条件が多くなると小さくなっていく性質があるため，
\begin{align}
H(X_{i+1}|X_{2}, \cdots, X_{i})
&\geq H(X_{i+1}|X_{1}, \cdots, X_{i})
\end{align}
H(X_{i+1}|X_{2}, \cdots, X_{i})
&\geq H(X_{i+1}|X_{1}, \cdots, X_{i})
\end{align}
となります。これらより
\begin{align}
H(X_{i}|X_{1}, \cdots, X_{t-1})
&\geq H(X_{i+1}|X_{1}, \cdots, X_{i})
\end{align}
H(X_{i}|X_{1}, \cdots, X_{t-1})
&\geq H(X_{i+1}|X_{1}, \cdots, X_{i})
\end{align}
が成り立つため，
\begin{align}
\lim_{t\to\infty}\sum_{i=1}^{t}H(X_{i}|X_{1}, \cdots, X_{i-1}) = \lim_{t\to\infty}(X_{t}|X_{1}, \cdots, X_{t-1})
\end{align}
\lim_{t\to\infty}\sum_{i=1}^{t}H(X_{i}|X_{1}, \cdots, X_{i-1}) = \lim_{t\to\infty}(X_{t}|X_{1}, \cdots, X_{t-1})
\end{align}
が得られます。したがって，チェザロ平均の関係より式($\ref{main1}$)が成り立つことが示されました。
無記憶かつ定常な情報源のエントロピーレート
式($\ref{main2}$)の右辺は，無記憶性と定常性により
\begin{align}
\lim_{t\to\infty}H(X_{t}|X_{1}, \cdots, X_{t-1})
= H(X_t)
= H(X_1)
\end{align}
\lim_{t\to\infty}H(X_{t}|X_{1}, \cdots, X_{t-1})
= H(X_t)
= H(X_1)
\end{align}
となります。
単純マルコフ定常情報源のエントロピーレート
単純マルコフ情報源では$1$つ前のシンボルだけに依存して次のシンボルの生起確率が定まるため，定常性に注意して式($\ref{main3}$)の右辺を変形すると
\begin{align}
\lim_{t\to\infty}H(X_{t}|X_{1},\cdots,X_{t-1})
= H(X_{t}|X_{t-1})
= H(X_{2}|X_{1})
\end{align}
\lim_{t\to\infty}H(X_{t}|X_{1},\cdots,X_{t-1})
= H(X_{t}|X_{t-1})
= H(X_{2}|X_{1})
\end{align}
となります。
コメント
コメント一覧 （3件）
お世話になっております。
式(4),(5)の条件部がエントロピーになっているのですが、これは誤植でしょうか...?
式(6),(14)でHの中身にH_tとある点、
また、式(8)でaの添え字がtになっている点、式(10)でlimの後におそらくb_t？が抜けている点も気になりました。
ご確認よろしくお願いいたします。
すみません…この記事ボロボロすぎました。
学生の頃に書き殴ったメモをそのまま貼り付けていたようです。
大変失礼しました。記事を全面的に書き直したのでご確認ください。
修正していただきありがとうございます！
ご対応感謝いたします。