早稲田大学 創造理工学研究科 経営システム工学専攻 2016年7月実施 情報数理応用 問題1

标签：

• Waseda-University
• Entropy
• Conditional-Entropy
• Mutual-Information
• Typical-Sequence

Author

祭音Myyura

Description

シンボル が確率 で独立に生起する定常無記憶情報源 と、シンボル が確率 で独立に生起する定常無記憶情報源 を考える。また を条件付き確率とする。

1. エントロピー の式を示せ。
2. エントロピーの意味と実務上の意義を説明せよ。
3. 条件付きエントロピー の定義と意味を説明せよ。
4. 相互情報量 の定義と意味を説明せよ。
5. 標準系列とエントロピーの関係、その概念と意味を説明せよ。

Kai

以下では対数の底を とし、単位を bit とする。

[小問 1]

である。 の項は と約束する。

[小問 2]

事象 の自己情報量は であり、エントロピーはその期待値である。したがって、情報源の不確実性、または1シンボルを観測したときに得られる平均情報量を表す。

実務上は、無損失圧縮に必要な平均符号長の理論的下限を与える。定常無記憶情報源を十分長いブロックで符号化すれば、平均符号長を1シンボル当たり bit に近づけられるが、それより小さくすることは一般にできない。

[小問 3]

である。これは を知った後にも残る の平均的な不確実性であり、

を満たす。

[小問 4]

同時確率を とすると、

である。また

であるから、 を知ることによって減少する の不確実性を表す。常に であり、独立なら である。

[小問 5]

個の出力列 に対し、-標準系列集合を

と定義する。漸近等分割性より

標準系列では

すなわち、長い系列のほとんどは、ほぼ等確率な約 個の系列へ集中する。これが典型集合だけを符号化して平均符号長を bit に近づけられる理由である。