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

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

入力アルファベットが ${0, 1}$ 、出力アルファベットが ${0, e, 1}$ の通信路を考える（ $e$ は「消失」を表す記号である）。入力 $X$ と出力 $Y$ の条件付き確率は、 $x = 0, 1$ に対して
$P (Y = x ∣ X = x) = \frac{2}{3}, P (Y = e ∣ X = x) = \frac{1}{3}$
であり、それ以外の出力が現れる確率は $0$ である（すなわち、入力が反転して出力されることはない）。入力の分布を
$P (X = 0) = \frac{3}{4}, P (X = 1) = \frac{1}{4}$
とするとき、相互情報量 $I (X; Y)$ を求めよ。ただし、エントロピーの対数の底は $2$ とする（単位はビット）。

この問題で使うもの

相互情報量（説明と入口の問題）
エントロピー（説明と入口の問題）
同時エントロピーと条件付きエントロピー（説明と入口の問題）
確率の定義と和事象・余事象（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

$I (X; Y) = H (Y) - H (Y ∣ X)$ を使い、まず出力 $Y$ の分布を求めましょう。

ヒント 2

$P (Y = y) = \sum_{x} P (X = x) P (Y = y ∣ X = x)$ で $Y$ の分布を求めます。 $H (Y ∣ X)$ は、どちらの入力でも出力が確率 $\frac{2}{3}, \frac{1}{3}$ に分かれることに注目します。

ヒント 3

$P (Y = 0) = \frac{1}{2}, P (Y = 1) = \frac{1}{6}, P (Y = e) = \frac{1}{3}$ より $H (Y) = \frac{2}{3} + \frac{1}{2} lo g_{2} 3$ 、また $H (Y ∣ X) = lo g_{2} 3 - \frac{2}{3}$ です。

答えと解説

答えを見る

\frac{4}{3} - \frac{1}{2} lo g_{2} 3

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

解説を読む

$I (X; Y) = H (Y) - H (Y ∣ X)$ を用いて計算する。

$Y$ の分布 全確率の公式より
$P (Y = 0) = \frac{3}{4} \cdot \frac{2}{3} = \frac{1}{2}, P (Y = 1) = \frac{1}{4} \cdot \frac{2}{3} = \frac{1}{6}, P (Y = e) = \frac{3}{4} \cdot \frac{1}{3} + \frac{1}{4} \cdot \frac{1}{3} = \frac{1}{3} .$

$H (Y)$
$H (Y) = \frac{1}{2} lo g_{2} 2 + \frac{1}{6} lo g_{2} 6 + \frac{1}{3} lo g_{2} 3 = \frac{1}{2} + \frac{1}{6} (1 + lo g_{2} 3) + \frac{1}{3} lo g_{2} 3 = \frac{2}{3} + \frac{1}{2} lo g_{2} 3.$

$H (Y ∣ X)$ $X = 0$ のとき $Y$ は確率 $\frac{2}{3}, \frac{1}{3}$ で $0, e$ をとり、 $X = 1$ のときも確率 $\frac{2}{3}, \frac{1}{3}$ で $1, e$ をとる。どちらの場合も条件付きエントロピーは
$\frac{2}{3} lo g_{2} \frac{3}{2} + \frac{1}{3} lo g_{2} 3 = lo g_{2} 3 - \frac{2}{3}$
であるから、 $H (Y ∣ X) = lo g_{2} 3 - \frac{2}{3}$ 。

相互情報量
$I (X; Y) = (\frac{2}{3} + \frac{1}{2} lo g_{2} 3) - (lo g_{2} 3 - \frac{2}{3}) = \frac{4}{3} - \frac{1}{2} lo g_{2} 3 (\approx 0.541) .$

（検算） $H (X ∣ Y)$ を考えると、 $Y = 0$ または $Y = 1$ なら $X$ は確定し、 $Y = e$ なら $X$ の条件付き分布は事前分布 $(\frac{3}{4}, \frac{1}{4})$ と同じなので $H (X ∣ Y) = \frac{1}{3} H (X)$ 。よって $I (X; Y) = \frac{2}{3} H (X) = \frac{2}{3} (2 - \frac{3}{4} lo g_{2} 3) = \frac{4}{3} - \frac{1}{2} lo g_{2} 3$ となり一致する。

別解

これは消失確率 $ε = 1/3$ の二元消失通信路である。

$I (X; Y) = H (X) - H (X ∣ Y)$ を使う。

出力 $Y = e$ のとき、入力は $Y$ から何もわからないので $H (X ∣ Y = e) = H (X)$ 。
$Y = 0$ または $Y = 1$ のとき、入力は一意に決まるので $H (X ∣ Y = y) = 0$ 。

したがって $H (X ∣ Y) = P (Y = e) H (X) = \frac{1}{3} H (X)$ となり、
$I (X; Y) = (1 - \frac{1}{3}) H (X) = \frac{2}{3} H (X) .$

$H (X) = - \frac{3}{4} lo g_{2} \frac{3}{4} - \frac{1}{4} lo g_{2} \frac{1}{4}$
$= \frac{3}{4} (2 - lo g_{2} 3) + \frac{1}{4} \cdot 2$
$= \frac{3}{2} - \frac{3}{4} lo g_{2} 3 + \frac{1}{2}$
$= 2 - \frac{3}{4} lo g_{2} 3$ .

よって
$I (X; Y) = \frac{2}{3} (2 - \frac{3}{4} lo g_{2} 3) = \frac{4}{3} - \frac{1}{2} lo g_{2} 3.$

検算： $lo g_{2} 3 \approx 1.58496$ なので、 $H (X) \approx 2 - 1.18872 = 0.81128$ 。 $\frac{2}{3} \cdot 0.81128 \approx 0.54085$ 。一方 $\frac{4}{3} - 0.79248 = 0.54085$ で一致する。

別の方法による確認： $Y$ の分布は $P (Y = 0) = \frac{3}{4} \cdot \frac{2}{3} = \frac{1}{2}$ 、 $P (Y = 1) = \frac{1}{4} \cdot \frac{2}{3} = \frac{1}{6}$ 、 $P (Y = e) = \frac{1}{3}$ 。
$H (Y) = \frac{1}{2} \cdot 1 + \frac{1}{6} lo g_{2} 6 + \frac{1}{3} lo g_{2} 3$
$= \frac{1}{2} + \frac{1}{6} (1 + lo g_{2} 3) + \frac{1}{3} lo g_{2} 3$
$= \frac{2}{3} + \frac{1}{2} lo g_{2} 3$ .
$H (Y ∣ X) = H (1/3) = lo g_{2} 3 - \frac{2}{3}$ .
$I = H (Y) - H (Y ∣ X) = \frac{2}{3} + \frac{1}{2} lo g_{2} 3 - lo g_{2} 3 + \frac{2}{3} = \frac{4}{3} - \frac{1}{2} lo g_{2} 3$ 。一致する。

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が答えを見ずに 3 回解き、3 回とも同じ答えになりました
プログラムで答えを計算し直し、一致を確認しました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる