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

難易度 4大学院入試の標準レベル証明問題大学数学情報理論・符号理論

実数 $p, ρ$ は $0 < p < \frac{1}{2}$ , $0 < ρ \leq 1$ を満たすとする。入力 $X$ ・出力 $Y$ がともに ${0, 1}$ に値をとる 2 元対称通信路で、
$P (Y = x ∣ X = x) = 1 - p, P (Y = 1 - x ∣ X = x) = p (x = 0, 1)$
であるものを考える。ただし、記号 $1$ を送るには費用がかかるため、入力分布は $P (X = 1) \leq ρ$ を満たすものだけが使えるとする。

エントロピーの対数の底は $2$ とし、 $0 lo g_{2} 0 = 0$ と約束する。2 値エントロピー関数を $h (s) = - s lo g_{2} s - (1 - s) lo g_{2} (1 - s)$ $(0 \leq s \leq 1)$ 、相互情報量を $I (X; Y) = H (Y) - H (Y ∣ X)$ （ただし $H (Y ∣ X) = \sum_{x} P (X = x) H (Y ∣ X = x)$ ）で定め、 $m = min {ρ, \frac{1}{2}}$ とおく。

このとき、 $P (X = 1) \leq ρ$ を満たす入力分布の中で $I (X; Y)$ を最大にするものは $P (X = 1) = m$ である分布ただ 1 つであり、その最大値は
$h (m (1 - p) + (1 - m) p) - h (p)$
であることを証明せよ。

この問題で使うもの

エントロピー（説明と入口の問題）
2 元対称通信路の通信路容量（説明と入口の問題）
離散無記憶通信路の通信路容量（説明と入口の問題）
増減表と極値（説明と入口の問題）
指数関数・対数関数の導関数（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

入力分布は $π = P (X = 1)$ だけで決まります。 $I (X; Y) = H (Y) - H (Y ∣ X)$ の 2 項を $π$ で表し、どちらが $π$ によるかを調べましょう。

ヒント 2

$H (Y ∣ X) = h (p)$ は $π$ によらず、 $P (Y = 1) = p + (1 - 2 p) π$ です。 $h^{'} (s) = lo g_{2} \frac{1 - s}{s}$ から、 $h$ が $[0, \frac{1}{2}]$ で狭義単調増加であることを示しておくと役に立ちます。

ヒント 3

$I (X; Y) = h (p + (1 - 2 p) π) - h (p)$ と書けます。 $ρ \leq \frac{1}{2}$ なら $p + (1 - 2 p) π$ は $π \in [0, ρ]$ で $\frac{1}{2}$ を超えないこと、 $ρ > \frac{1}{2}$ なら $π = \frac{1}{2}$ で $h$ の値が $1$ になることに注目して、場合分けしましょう。

採点の観点と模範解答

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

採点の観点を見る

$π = P (X = 1)$ とおき、 $H (Y ∣ X = 0) = H (Y ∣ X = 1) = h (p)$ から $H (Y ∣ X) = h (p)$ が $π$ によらないことを示している（2 点）
全確率の公式で $P (Y = 1) = p + (1 - 2 p) π$ を求め、 $I (X; Y) = h (p + (1 - 2 p) π) - h (p)$ と表している（2 点）
導関数 $h^{'} (s) = lo g_{2} \frac{1 - s}{s}$ と平均値の定理などにより、 $h$ が $[0, \frac{1}{2}]$ で狭義単調増加であること（および $s \neq = \frac{1}{2}$ で $h (s) < 1$ であること）を根拠をつけて示している（2 点）
$ρ \leq \frac{1}{2}$ の場合に $p + (1 - 2 p) π \leq \frac{1}{2}$ を確かめ、狭義単調性から $π = ρ$ でのみ最大になることを示している（2 点）
$ρ > \frac{1}{2}$ の場合に $π = \frac{1}{2}$ で $P (Y = 1) = \frac{1}{2}$ となり、それ以外の $π$ では $I (X; Y)$ が真に小さいことを示し、最大値の式を結論している（2 点）

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

模範解答を読む

方針. 入力分布は $π = P (X = 1)$ で決まり、制約は $0 \leq π \leq ρ$ である。 $I (X; Y)$ を $π$ の関数として表し、 $h$ の単調性を使ってその最大点を調べる。

補題（ $h$ の性質）. (i) $h (s) = h (1 - s)$ $(0 \leq s \leq 1)$ 。(ii) $h$ は $[0, \frac{1}{2}]$ で狭義単調増加である。(iii) $s \neq = \frac{1}{2}$ なら $h (s) < h (\frac{1}{2}) = 1$ 。

（証明）(i) は定義式で $s$ と $1 - s$ を入れ替えると同じ式になることから従う。
(ii) $lim_{s \to + 0} s lo g_{2} s = 0$ と約束 $0 lo g_{2} 0 = 0$ より $h$ は $[0, 1]$ で連続である。 $0 < s < 1$ では微分可能で
$h^{'} (s) = - lo g_{2} s - \frac{1}{ln 2} + lo g_{2} (1 - s) + \frac{1}{ln 2} = lo g_{2} \frac{1 - s}{s}$
であり、 $0 < s < \frac{1}{2}$ では $\frac{1 - s}{s} > 1$ なので $h^{'} (s) > 0$ 。 $0 \leq s_{1} < s_{2} \leq \frac{1}{2}$ とすると、 $h$ は $[s_{1}, s_{2}]$ で連続、 $(s_{1}, s_{2})$ で微分可能なので、平均値の定理より $h (s_{2}) - h (s_{1}) = h^{'} (ξ) (s_{2} - s_{1})$ となる $ξ \in (s_{1}, s_{2}) \subset (0, \frac{1}{2})$ がある。 $h^{'} (ξ) > 0$ より $h (s_{2}) > h (s_{1})$ 。
(iii) $h (\frac{1}{2}) = - lo g_{2} \frac{1}{2} = 1$ 。 $s < \frac{1}{2}$ なら (ii) より $h (s) < h (\frac{1}{2})$ 。 $s > \frac{1}{2}$ なら $1 - s < \frac{1}{2}$ なので (i), (ii) より $h (s) = h (1 - s) < h (\frac{1}{2})$ 。

ステップ 1（ $H (Y ∣ X)$ ）. $X = 0$ のとき $Y$ の分布は $(P (Y = 0), P (Y = 1)) = (1 - p, p)$ なので $H (Y ∣ X = 0) = h (p)$ 。 $X = 1$ のときは $(p, 1 - p)$ なので補題 (i) より $H (Y ∣ X = 1) = h (1 - p) = h (p)$ 。よって
$H (Y ∣ X) = (1 - π) h (p) + π h (p) = h (p)$
であり、これは $π$ によらない。

ステップ 2（ $H (Y)$ ）. 全確率の公式より
$P (Y = 1) = (1 - π) p + π (1 - p) = p + (1 - 2 p) π .$
これを $u (π)$ とおくと $H (Y) = h (u (π))$ である。したがって
$I (X; Y) = h (u (π)) - h (p) (0 \leq π \leq ρ) .$
$0 < p < \frac{1}{2}$ より $1 - 2 p > 0$ なので、 $u$ は狭義単調増加で、 $u (0) = p$ , $u (\frac{1}{2}) = p + \frac{1 - 2 p}{2} = \frac{1}{2}$ である。

ステップ 3（ $ρ \leq \frac{1}{2}$ の場合, $m = ρ$ ）. $0 \leq π \leq ρ \leq \frac{1}{2}$ のとき $p \leq u (π) \leq u (ρ) \leq u (\frac{1}{2}) = \frac{1}{2}$ で、 $u (π)$ は $[0, \frac{1}{2}]$ に入る。 $0 \leq π < ρ$ なら $u (π) < u (ρ)$ なので、補題 (ii) より $h (u (π)) < h (u (ρ))$ 。よって $I (X; Y)$ は $π = ρ$ でのみ最大となり、最大値は $h (u (ρ)) - h (p)$ である。

ステップ 4（ $ρ > \frac{1}{2}$ の場合, $m = \frac{1}{2}$ ）. $π = \frac{1}{2}$ は $0 \leq π \leq ρ$ を満たし、 $u (\frac{1}{2}) = \frac{1}{2}$ より $h (u (\frac{1}{2})) = 1$ 。 $π \neq = \frac{1}{2}$ なら $u$ が狭義単調増加なので $u (π) \neq = \frac{1}{2}$ であり、補題 (iii) より $h (u (π)) < 1$ 。よって $I (X; Y)$ は $π = \frac{1}{2}$ でのみ最大となり、最大値は $h (u (\frac{1}{2})) - h (p)$ である。

結論. どちらの場合も、 $I (X; Y)$ を最大にする入力分布は $P (X = 1) = m$ のものただ 1 つで、最大値は
$h (u (m)) - h (p) = h (m (1 - p) + (1 - m) p) - h (p)$
である（ $u (m) = p + (1 - 2 p) m = m (1 - p) + (1 - m) p$ ）。 $■$

（注: $ρ \geq \frac{1}{2}$ では制約がないときの容量 $1 - h (p)$ に一致し、 $ρ < \frac{1}{2}$ では費用制約のため容量が真に小さくなる。）

この問題の確認

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

別の AI が模範解答を見ずに 3 回証明を試み、3 回証明できました
2 つの AI が独立に、模範解答の証明を 1 ステップずつ確かめました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

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