情報源符号化定理の証明
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/11/13 23:47 UTC 版)
「シャノンの情報源符号化定理」の記事における「情報源符号化定理の証明」の解説
X が独立同分布(iid)な情報源であるとき、その時系列 X1, ..., Xn は、離散値の場合はエントロピー H(X) 、連続値の場合は差分エントロピーで独立同分布となる。情報源符号化定理によれば、情報源のエントロピーより大きい任意のレートの任意の ε > 0 に対して、十分に大きい n と、情報源 X1:n の独立同分布な n 個の複写をとり、これを n(H(X) + ε) この二進数ビットに写像するエンコーダがあり、それは、少なくとも 1 − ε の確率で、情報源記号 X1:n が二進数ビットから復元できる。 達成可能性の証明。 いくつかの ε > 0 を修正し、 p ( x 1 , … , x n ) = Pr [ X 1 = x 1 , ⋯ , X n = x n ] . {\displaystyle p(x_{1},\ldots ,x_{n})=\Pr \left[X_{1}=x_{1},\cdots ,X_{n}=x_{n}\right].} とする。典型集合（英語版） Aεn は、以下のように定義される。 A n ε = { ( x 1 , ⋯ , x n ) : | − 1 n log p ( x 1 , ⋯ , x n ) − H n ( X ) | < ε } {\displaystyle A_{n}^{\varepsilon }=\left\{(x_{1},\cdots ,x_{n})\ :\ \left|-{\frac {1}{n}}\log p(x_{1},\cdots ,x_{n})-H_{n}(X)\right|<\varepsilon \right\}} 漸近的等分配性（英語版）(AEP)が示すところによると、十分に大きい n に対して、情報源によって生成された列が典型集合 Aεn に含まれる確率は 1 に近づく。特に、十分に大きい n に対しては、 P ( ( X 1 , X 2 , ⋯ , X n ) ∈ A n ε ) {\displaystyle P((X_{1},X_{2},\cdots ,X_{n})\in A_{n}^{\varepsilon })} は任意に 1 に近く、具体的には 1 − ε {\displaystyle 1-\varepsilon } より大きくすることができる。 典型集合の定義は、典型集合にある列が以下を満足することを意味する。 2 − n ( H ( X ) + ε ) ≤ p ( x 1 , ⋯ , x n ) ≤ 2 − n ( H ( X ) − ε ) {\displaystyle 2^{-n(H(X)+\varepsilon )}\leq p\left(x_{1},\cdots ,x_{n}\right)\leq 2^{-n(H(X)-\varepsilon )}} 注意: Aεnから導かれる列 ( X 1 , X 2 , ⋯ X n ) {\displaystyle (X_{1},X_{2},\cdots X_{n})} の確率は 1 − ε より大きい。 p ( x 1 , x 2 , ⋯ x n ) {\displaystyle p(x_{1},x_{2},\cdots x_{n})} の左側（下限）からは | A n ε | ≤ 2 n ( H ( X ) + ε ) {\displaystyle \left|A_{n}^{\varepsilon }\right|\leq 2^{n(H(X)+\varepsilon )}} となる。 p ( x 1 , x 2 , ⋯ x n ) {\displaystyle p(x_{1},x_{2},\cdots x_{n})} の右側（上限）および全体集合 Aεn の全確率に対する下限からは | A n ε | ≥ ( 1 − ε ) 2 n ( H ( X ) − ε ) {\displaystyle \left|A_{n}^{\varepsilon }\right|\geq (1-\varepsilon )2^{n(H(X)-\varepsilon )}} となる。 よって、 | A n ε | ≤ 2 n ( H ( X ) + ε ) , n . ( H ( X ) + ε ) {\displaystyle \left|A_{n}^{\varepsilon }\right|\leq 2^{n(H(X)+\varepsilon )},n.(H(X)+\varepsilon )} ビットはこの集合の任意の文字列を指すのに十分である。 エンコードアルゴリズム : エンコーダは、入力列が典型集合内にあるかどうかをチェックする。そうであれば、典型集合内の入力列のインデックスを出力する。そうでなければ、エンコーダは任意の n(H(X) + ε) 桁の数を出力する。入力列が典型集合内にある限り（少なくとも 1 − ε の確率で）、エンコーダは何の誤りも生じない。従って、エンコーダの誤りの確率の上限は ε である。 逆の証明。その逆は、Aεn より小さいサイズの集合が 1 から離れる確率の集合をカバーすることを示すことで証明できる。
※この「情報源符号化定理の証明」の解説は、「シャノンの情報源符号化定理」の解説の一部です。
「情報源符号化定理の証明」を含む「シャノンの情報源符号化定理」の記事については、「シャノンの情報源符号化定理」の概要を参照ください。
- 情報源符号化定理の証明のページへのリンク
