この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

情報理論・符号理論の問題

難易度 2教科書の演習問題レベル証明問題大学数学情報理論・符号理論

$X, Y$ を空でない有限集合とし、 $X$ を $X$ に値をとる確率変数、 $f : X \to Y$ を写像として $Y = f (X)$ とおく。 $y \in Y$ に対して $f^{- 1} (y) = {x \in X ∣ f (x) = y}$ とし、
$k = y \in f (X) max f^{- 1} (y)$
（ $f$ の像の各点の逆像の元の個数の最大値）とおく。

エントロピーの対数の底は $2$ とし、 $0 lo g_{2} 0 = 0$ と約束する。条件付きエントロピーは
$H (X ∣ Y) = y : P (Y = y) > 0 \sum P (Y = y) H (X ∣ Y = y)$
（ $H (X ∣ Y = y)$ は条件付き分布 $P (X = \cdot ∣ Y = y)$ のエントロピー）で定め、 $H (Y ∣ X)$ も同様に定める。

このとき
$H (X) \leq H (f (X)) + lo g_{2} k$
が成り立つことを証明せよ。

なお、連鎖律 $H (X, Y) = H (X) + H (Y ∣ X) = H (Y) + H (X ∣ Y)$ と、 $n$ 個の元からなる有限集合上の確率分布のエントロピーは $0$ 以上 $lo g_{2} n$ 以下であること、は用いてよい。

この問題で使うもの

エントロピー（説明と入口の問題）
同時エントロピーと条件付きエントロピー（説明と入口の問題）

この問題を解けるようになるまで（63 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

$H (X)$ を $H (f (X))$ と $H (X ∣ f (X))$ に分け、 $H (X ∣ f (X)) \leq lo g_{2} k$ を示す方針で考えましょう。

ヒント 2

$f (X)$ は $X$ で決まるので $H (f (X) ∣ X) = 0$ です。連鎖律から $H (X) = H (f (X)) + H (X ∣ f (X))$ が得られます。

ヒント 3

$P (Y = y) > 0$ のとき、条件付き分布 $P (X = \cdot ∣ Y = y)$ は $f^{- 1} (y)$ の外では $0$ です。 $f^{- 1} (y)$ の元は $k$ 個以下なので、 $H (X ∣ Y = y)$ を上から評価できます。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

$X = x$ のもとで $f (X)$ の分布が 1 点に集中することから $H (f (X) ∣ X) = 0$ を示している（2 点）
連鎖律を使って $H (X) = H (f (X)) + H (X ∣ f (X))$ を導いている（2 点）
$P (Y = y) > 0$ のとき条件付き分布 $P (X = \cdot ∣ Y = y)$ が $f^{- 1} (y)$ の外で $0$ になることを、条件付き確率の計算で確かめている（2 点）
用いてよい事実と $∣ f^{- 1} (y) ∣ \leq k$ から $H (X ∣ Y = y) \leq lo g_{2} k$ を導いている（2 点）
重み $P (Y = y)$ の和が $1$ であることを使って $H (X ∣ f (X)) \leq lo g_{2} k$ を示し、求める不等式を結論している（2 点）

結果を記録する（このブラウザにだけ保存されます）:

模範解答を読む

方針. 連鎖律と $H (Y ∣ X) = 0$ から $H (X) = H (Y) + H (X ∣ Y)$ を導き、 $H (X ∣ Y) \leq lo g_{2} k$ を示す。

ステップ 1（ $H (Y ∣ X) = 0$ ）. $P (X = x) > 0$ を満たす $x$ をとる。 $X = x$ のもとでは $Y = f (X) = f (x)$ なので、
$P (Y = y ∣ X = x) = {10 (y = f (x)) (y \neq = f (x))$
である。この分布のエントロピーは $- 1 \cdot lo g_{2} 1 = 0$ （ほかの項は $0 lo g_{2} 0 = 0$ ）なので $H (Y ∣ X = x) = 0$ 。したがって
$H (Y ∣ X) = x : P (X = x) > 0 \sum P (X = x) \cdot 0 = 0.$

ステップ 2（ $H (X)$ の分解）. 連鎖律 $H (X) + H (Y ∣ X) = H (X, Y) = H (Y) + H (X ∣ Y)$ にステップ 1 を代入して
$H (X) = H (Y) + H (X ∣ Y) . (1)$

ステップ 3（ $H (X ∣ Y = y) \leq lo g_{2} k$ ）. $P (Y = y) > 0$ を満たす $y$ をとる。 $P (Y = y) = \sum_{x \in f^{- 1} (y)} P (X = x) > 0$ より $f^{- 1} (y) \neq = \emptyset$ なので $y \in f (X)$ である。また
$P (X = x ∣ Y = y) = \frac{P ( X = x , f ( X ) = y )}{P ( Y = y )} = ⎩ ⎨ ⎧ \frac{P ( X = x )}{P ( Y = y )} 0 (x \in f^{- 1} (y)) (x \in / f^{- 1} (y))$
であり、 $\sum_{x \in f^{- 1} (y)} P (X = x ∣ Y = y) = 1$ である。よって条件付き分布 $P (X = \cdot ∣ Y = y)$ は、 $f^{- 1} (y)$ の外では確率 $0$ なので、 $0 lo g_{2} 0 = 0$ の約束によりそのエントロピーは $f^{- 1} (y)$ 上の確率分布のエントロピーと等しい。 $f^{- 1} (y)$ の元の個数は $∣ f^{- 1} (y) ∣$ だから、用いてよい事実より
$H (X ∣ Y = y) \leq lo g_{2} f^{- 1} (y) \leq lo g_{2} k .$
最後の不等号は、 $y \in f (X)$ なので $k$ の定義から $∣ f^{- 1} (y) ∣ \leq k$ であり、 $lo g_{2}$ が単調増加であることによる。

ステップ 4（ $H (X ∣ Y) \leq lo g_{2} k$ ）. ステップ 3 と $P (Y = y) \geq 0$ より
$H (X ∣ Y) = y : P (Y = y) > 0 \sum P (Y = y) H (X ∣ Y = y) \leq lo g_{2} k y : P (Y = y) > 0 \sum P (Y = y) = lo g_{2} k .$

結論. $(1)$ とステップ 4 より
$H (X) = H (f (X)) + H (X ∣ f (X)) \leq H (f (X)) + lo g_{2} k$
が成り立つ。 $■$

（注: $f$ が単射なら $k = 1$ で $H (X) \leq H (f (X))$ となり、どの $y$ の逆像も $2$ 個以下なら、 $f (X)$ に変えることで失われる情報は高々 $1$ ビットである。）

情報理論・符号理論の問題

この問題で使うもの

ヒント

採点の観点と模範解答

次のおすすめ

この問題の確認

間違いを報告する

関連する問題