9.3 二値情報源

9.2 節は $𝑅 (\cdot)$ のグラフの両端を決めた．左の端では，情報源アルファベットが再現アルファベットに含まれ，しかも歪み尺度が「 $0$ になるのは一致するときだけ」を満たすとき，値は情報源のエントロピーである（命題 9.2.4）．右の端では， $𝐷 m a x$ 以上の歪みを許すと値が $0$ になる（命題 9.2.5）．残っているのは両端のあいだの形で，本節はいちばん小さい情報源についてそれを決める．情報源も再現も $0$ と $1$ の二文字にとり，歪みは当たったか外れたかだけを見る Hamming 歪み（例 9.1.3）にとる．答えは，歪みを許しすぎない範囲では，情報源のエントロピーから，許した歪みのぶんのエントロピーを引いた形になる．

本節のアルファベットは有限だから，定義 9.1.5 と 9.2 節の主張はそのまま当てられる．本節は $P r [𝑋 = 1]$ を $𝜋$ と書く．補題 9.2.2 の証明が同時分布を $𝜋 𝑗 (𝑥, ˆ 𝑥)$ と書いていて字が重なるが，あちらはつねに二つの引数をとるので，引数のない $𝜋$ はつねに二値情報源のパラメータである．9.2 節が両端を確かめたときに使った $𝜋$ と同じものである．

二値エントロピー関数の形

答えを書き下すには，二値エントロピー関数 $𝐻 𝑏$ （例 1.1.2）について三つのことが要る．左右対称であること，凹であること，そして左半分で増えることである． $𝐻 𝑏$ が $𝑝 = 1 / 2$ で最大になるのだから三つめもそうなっているはずで，実際に前の二つから出る．出発点は補題 1.1.8 が示した $𝜑 (𝑡) = - 𝑡 l o g 𝑡$ の凹性ひとつである．

補題 9.3.1（二値エントロピー関数の対称性・凹性・単調性）. $𝐻 𝑏$ を例 1.1.2 の二値エントロピー関数とする．次の三つが成り立つ．

どの $𝑝 \in [0, 1]$ についても $𝐻 𝑏 (1 - 𝑝) = 𝐻 𝑏 (𝑝)$ である．
$𝑎, 𝑏 \in [0, 1]$ と $𝜆 \in [0, 1]$ について $𝐻 𝑏 (𝜆 𝑎 + (1 - 𝜆) 𝑏) \geq 𝜆 𝐻 𝑏 (𝑎) + (1 - 𝜆) 𝐻 𝑏 (𝑏)$ である．すなわち $𝐻 𝑏$ は $[0, 1]$ の上で凹である．
$0 \leq 𝑠 \leq 𝑡 \leq 1 / 2$ を満たす実数 $𝑠$ ， $𝑡$ について $𝐻 𝑏 (𝑠) \leq 𝐻 𝑏 (𝑡)$ である．

証明.

例 1.1.2 の定め方から $𝐻 𝑏 (𝑝) = 𝜑 (𝑝) + 𝜑 (1 - 𝑝)$ である（ $𝜑 (𝑡) = - 𝑡 l o g 𝑡$ は 1.1 節の記号である）．右辺は $𝑝$ と $1 - 𝑝$ を入れ替えても変わらない．
$𝑐 : = 𝜆 𝑎 + (1 - 𝜆) 𝑏$ とおく．補題 1.1.8 が示した $𝜑$ の凹性を $2$ 点の形で $𝑎$ ， $𝑏$ に当てると $𝜑 (𝑐) \geq 𝜆 𝜑 (𝑎) + (1 - 𝜆) 𝜑 (𝑏)$ である．同じ凹性を $1 - 𝑎$ ， $1 - 𝑏$ に当てると， $𝜆 (1 - 𝑎) + (1 - 𝜆) (1 - 𝑏) = 1 - 𝑐$ だから $𝜑 (1 - 𝑐) \geq 𝜆 𝜑 (1 - 𝑎) + (1 - 𝜆) 𝜑 (1 - 𝑏)$ である．二つを足すと第 $1$ の等式で使った形から $𝐻 𝑏 (𝑐) \geq 𝜆 𝐻 𝑏 (𝑎) + (1 - 𝜆) 𝐻 𝑏 (𝑏)$ を得る．
$𝑠 = 1 / 2$ ならば $𝑡 = 1 / 2$ で両辺が等しいから， $𝑠 < 1 / 2$ としてよい． $𝑡$ を $𝑠$ と $1 - 𝑠$ の凸結合として書けるように重みを選びたい．そうできれば，第 $2$ の主張の凹性より $𝐻 𝑏 (𝑡)$ は $𝐻 𝑏 (𝑠)$ と $𝐻 𝑏 (1 - 𝑠)$ の重み付き平均以上であり，第 $1$ の主張より後者は $𝐻 𝑏 (𝑠)$ に等しいから， $𝐻 𝑏 (𝑡) \geq 𝐻 𝑏 (𝑠)$ が出る． $𝜆 𝑠 + (1 - 𝜆) (1 - 𝑠) = 𝑡$ を $𝜆$ について解くと
$𝜆 : = 1 - 𝑠 - 𝑡 1 - 2 𝑠$
とおく． $𝑠 < 1 / 2$ より分母は正である． $𝑠 < 1 / 2$ と $𝑡 \leq 1 / 2$ より $𝑠 + 𝑡 < 1$ だから分子も正であり， $𝑠 \leq 𝑡$ より $1 - 𝑠 - 𝑡 \leq 1 - 2 𝑠$ だから $𝜆 \in (0, 1]$ である．また
$𝜆 𝑠 + (1 - 𝜆) (1 - 𝑠) = (1 - 𝑠) - 𝜆 (1 - 2 𝑠) = (1 - 𝑠) - (1 - 𝑠 - 𝑡) = 𝑡$
である． $𝑠$ と $1 - 𝑠$ はどちらも $[0, 1]$ に入るから，第 $2$ の主張を $𝑎 : = 𝑠$ ， $𝑏 : = 1 - 𝑠$ ととって当てると $𝐻 𝑏 (𝑡) \geq 𝜆 𝐻 𝑏 (𝑠) + (1 - 𝜆) 𝐻 𝑏 (1 - 𝑠)$ であり，第 $1$ の主張より $𝐻 𝑏 (1 - 𝑠) = 𝐻 𝑏 (𝑠)$ だから，右辺は $𝐻 𝑏 (𝑠)$ に等しい．

$◻$

形式化上の注記

補題 9.3.1 にあたる宣言は本書の形式化には無い．ただし本書が述べないだけで，三つの主張はどれも二値エントロピー関数についての Mathlib の無条件の機械検証済みの補題として存在する．対称性が Real.binEntropy_one_sub，凹性はさらに強い狭義凹性の形で Real.strictConcave_binEntropy，区間 $[0, 1 / 2]$ での単調性もさらに強い狭義単調増加の形で Real.binEntropy_strictMonoOn である．どれも対数の底の取り方によらない性質である．

下界

定義 9.1.5 が最小にするのは $𝐼 (𝑝; 𝑞)$ である．定理 1.3.4 でこれを $𝐻 (𝑋) - 𝐻 (𝑋 ∣ ˆ 𝑋)$ と読むと，第 $1$ 項は $𝑞$ を含まない定数だから，問いは「 $𝑋$ と $ˆ 𝑋$ の結びつきをいちばん弱くする」から「再現を見たあとに残る $𝑋$ の不確かさをいちばん大きくする」に移る．そして歪みの制約が言っているのは，二つの文字が食い違う確率が $𝐷$ 以下だ，ということだけである．食い違ったかどうかを表す二値の確率変数を一つ置けば，そこに二値エントロピー関数が出てくる．

命題 9.3.2（相互情報量の下界）. $𝜋 \in [0, 1]$ ， $0 \leq 𝐷 \leq 1 / 2$ とする． $X = ˆ X = {0, 1}$ とし， $𝑝$ を $𝑝 (1) = 𝜋$ ， $𝑝 (0) = 1 - 𝜋$ で定まる $X$ 上の分布， $𝑑 𝐻$ を例 9.1.3 の Hamming 歪みとし， $Q (\cdot)$ と $𝐼 (𝑝; \cdot)$ を定義 9.1.5 のとおりとする．このとき，どの $𝑞 \in Q (𝐷)$ についても

𝐼 (𝑝; 𝑞) \geq 𝐻 𝑏 (𝜋) - 𝐻 𝑏 (𝐷)

である（ $𝐻 𝑏$ は例 1.1.2 の二値エントロピー関数）．

証明. $𝑞 \in Q (𝐷)$ をとり， $(𝑋, ˆ 𝑋)$ を定義 9.1.5 のとおり同時分布 $𝑝 (𝑥) 𝑞 (ˆ 𝑥 ∣ 𝑥)$ をもつ対とする．定義 9.1.5 より $𝐼 (𝑝; 𝑞) = 𝐼 (𝑋; ˆ 𝑋)$ であり，定理 1.3.4 より $𝐼 (𝑋; ˆ 𝑋) = 𝐻 (𝑋) - 𝐻 (𝑋 ∣ ˆ 𝑋)$ である． $𝑋$ は確率 $𝜋$ で $1$ ，確率 $1 - 𝜋$ で $0$ をとるから，例 1.1.2 より $𝐻 (𝑋) = 𝐻 𝑏 (𝜋)$ である．

食い違いを表す確率変数を置く． $𝑋 \neq ˆ 𝑋$ のとき $1$ ， $𝑋 = ˆ 𝑋$ のとき $0$ をとる確率変数を $𝐸$ とする．例 9.1.3 を $𝑛 = 1$ に当てると， $𝑞$ の期待歪みは $𝔼 [𝑑 𝐻 (𝑋, ˆ 𝑋)] = P r [ˆ 𝑋 \neq 𝑋] = P r [𝐸 = 1]$ であり， $𝑞 \in Q (𝐷)$ より $P r [𝐸 = 1] \leq 𝐷$ である．

$𝐻 (𝑋 ∣ ˆ 𝑋) = 𝐻 (𝐸 ∣ ˆ 𝑋)$ を見る． $P r [ˆ 𝑋 = ˆ 𝑥] > 0$ となる $ˆ 𝑥 \in {0, 1}$ を固定し， $𝑒 ˆ 𝑥 : = P r [𝑋 \neq ˆ 𝑥 ∣ ˆ 𝑋 = ˆ 𝑥]$ とおく（ $P r [ˆ 𝑋 = ˆ 𝑥] = 0$ の項は，定義 1.2.2 のとおりどちらの量にも寄与しない）． $𝑋$ は ${0, 1}$ に値をとるから， $ˆ 𝑋 = ˆ 𝑥$ のもとでの $𝑋$ の条件付き分布は， $ˆ 𝑥$ でないほうの文字に $𝑒 ˆ 𝑥$ ， $ˆ 𝑥$ に $1 - 𝑒 ˆ 𝑥$ を置いたものである．定義 1.2.2 の $𝐻 (𝑋 ∣ ˆ 𝑋 = ˆ 𝑥)$ はこの分布に定義 1.1.1 を当てたもので，項は二つだけだから $- 𝑒 ˆ 𝑥 l o g 𝑒 ˆ 𝑥 - (1 - 𝑒 ˆ 𝑥) l o g (1 - 𝑒 ˆ 𝑥)$ に等しく，例 1.1.2 よりこれは $𝐻 𝑏 (𝑒 ˆ 𝑥)$ である．一方 $ˆ 𝑋 = ˆ 𝑥$ のもとで $𝐸 = 1$ となるのは $𝑋 \neq ˆ 𝑥$ のときだから， $ˆ 𝑋 = ˆ 𝑥$ のもとでの $𝐸$ の条件付き分布は $1$ に $𝑒 ˆ 𝑥$ ， $0$ に $1 - 𝑒 ˆ 𝑥$ を置いたもので，同じ理由で $𝐻 (𝐸 ∣ ˆ 𝑋 = ˆ 𝑥) = 𝐻 𝑏 (𝑒 ˆ 𝑥)$ である．定義 1.2.2 はこれらを $P r [ˆ 𝑋 = ˆ 𝑥]$ で平均したものだから，二つの条件付きエントロピーは等しい．

条件を落として抑える．定理 1.2.4 の基本形（条件の一方を自明な定数にとった形）より $𝐻 (𝐸 ∣ ˆ 𝑋) \leq 𝐻 (𝐸)$ である． $𝐸$ は確率 $P r [𝐸 = 1]$ で $1$ ，確率 $1 - P r [𝐸 = 1]$ で $0$ をとるから，例 1.1.2 より $𝐻 (𝐸) = 𝐻 𝑏 (P r [𝐸 = 1])$ である． $P r [𝐸 = 1] \leq 𝐷 \leq 1 / 2$ だから補題 9.3.1 の第 $3$ の主張より $𝐻 𝑏 (P r [𝐸 = 1]) \leq 𝐻 𝑏 (𝐷)$ である．

以上を合わせると $𝐻 (𝑋 ∣ ˆ 𝑋) \leq 𝐻 𝑏 (𝐷)$ であり， $𝐼 (𝑝; 𝑞) = 𝐻 𝑏 (𝜋) - 𝐻 (𝑋 ∣ ˆ 𝑋) \geq 𝐻 𝑏 (𝜋) - 𝐻 𝑏 (𝐷)$ を得る． $◼$

形式化上の注記

命題 9.3.2 にあたる宣言は無い．形式化には歪み尺度を具体的にとった実例が一つも置かれていないので，Hamming 歪みのもとで相互情報量を下から抑える宣言も無い（結論の形で探しても見つからない）．

逆向きに作る

命題 9.3.2 の証明で不等号が入ったのは二か所である．定理 1.2.4 で条件 $ˆ 𝑋$ を落としたところと，補題 9.3.1 の第 $3$ の主張で $P r [𝐸 = 1]$ を $𝐷$ に置き換えたところである．下界を達成する条件付き分布を作る筋は，抑えたこの二つを抑えた値ちょうどにすることである．食い違いの確率をちょうど $𝐷$ にし，しかも再現 $ˆ 𝑋$ を知っても食い違いについて何も分からないようにする，ということである．

後者が逆向きの構成の理由になる．素直に思いつくのは，情報源 $𝑋$ を先に置いて，そこに確率 $𝐷$ の反転を独立に加えて再現 $ˆ 𝑋$ を作る向きである．この作り方では，食い違いは作った時点で $𝑋$ と独立になる．欲しいのはそちらではなく， $ˆ 𝑋$ と独立な食い違いのほうである．順序を入れ替えて，再現 $ˆ 𝑋$ を先に置き，そこに確率 $𝐷$ の反転を独立に加えて情報源 $𝑋$ を作れば，食い違いは作った時点で $ˆ 𝑋$ と独立である．反転確率 $𝐷$ の二元対称通信路（例 6.1.8）を，情報源から再現へではなく，再現から情報源へ向けて使う，と言ってもよい．残るのは，こうして作った同時分布の第 $1$ 周辺が情報源の分布 $𝑝$ に一致するように， $ˆ 𝑋$ の側のパラメータを選ぶことだけである．

命題 9.3.3（下界を達成する条件付き分布）. $𝜋$ を実数， $𝐷$ を実数とし， $0 \leq 𝐷 < m i n (𝜋, 1 - 𝜋)$ とする． $X = ˆ X = {0, 1}$ とし， $𝑝$ を $𝑝 (1) = 𝜋$ ， $𝑝 (0) = 1 - 𝜋$ で定まる $X$ 上の分布， $𝑑 𝐻$ を例 9.1.3 の Hamming 歪みとし， $Q (\cdot)$ と $𝐼 (𝑝; \cdot)$ を定義 9.1.5 のとおりとする．このとき，期待歪みがちょうど $𝐷$ に等しい条件付き分布 $𝑞 * \in Q (𝐷)$ であって

𝐼 (𝑝; 𝑞 *) = 𝐻 𝑏 (𝜋) - 𝐻 𝑏 (𝐷)

を満たすものが存在する（ $𝐻 𝑏$ は例 1.1.2 の二値エントロピー関数）．

証明. 仮定から $m i n (𝜋, 1 - 𝜋) > 0$ ，すなわち $0 < 𝜋 < 1$ である．また $m i n (𝜋, 1 - 𝜋) \leq 1 / 2$ だから $𝐷 < 1 / 2$ で， $1 - 2 𝐷 > 0$ である． $ˆ 𝑋$ が確率 $𝑟$ で $1$ をとるとして，第 $1$ 周辺が $𝜋$ になるという条件 $𝑟 (1 - 𝐷) + (1 - 𝑟) 𝐷 = 𝜋$ を $𝑟$ について解くと

𝑟 : = 𝜋 - 𝐷 1 - 2 𝐷

とおく．分母は正であり， $𝐷 < 𝜋$ より分子も正だから $𝑟 > 0$ である． $𝐷 < 1 - 𝜋$ より $𝜋 - 𝐷 < 1 - 2 𝐷$ だから $𝑟 < 1$ である．

同時分布を書き下す． $X \times ˆ X$ 上の数の組 $𝐽$ を

𝐽 (1, 1) : = 𝑟 (1 - 𝐷), 𝐽 (0, 1) : = 𝑟 𝐷, 𝐽 (1, 0) : = (1 - 𝑟) 𝐷, 𝐽 (0, 0) : = (1 - 𝑟) (1 - 𝐷)

で定める．どれも非負であり，総和は $𝑟 + (1 - 𝑟) = 1$ である．これは「 $ˆ 𝑋$ を確率 $𝑟$ で $1$ にとり，そこに確率 $𝐷$ の反転を独立に加えて $𝑋$ を作る」という手順が与える同時分布にほかならない．

第 $1$ 周辺が $𝑝$ であることを見る． $𝐽 (1, 1) + 𝐽 (1, 0) = 𝑟 (1 - 𝐷) + (1 - 𝑟) 𝐷 = 𝐷 + 𝑟 (1 - 2 𝐷) = 𝐷 + (𝜋 - 𝐷) = 𝜋$ であり， $𝐽 (0, 1) + 𝐽 (0, 0) = 𝑟 𝐷 + (1 - 𝑟) (1 - 𝐷) = (1 - 𝐷) - 𝑟 (1 - 2 𝐷) = (1 - 𝐷) - (𝜋 - 𝐷) = 1 - 𝜋$ である．すなわち $𝑥$ について足すと $𝑝 (𝑥)$ になる．

条件付き分布を取り出す． $𝑝 (1) = 𝜋 > 0$ ， $𝑝 (0) = 1 - 𝜋 > 0$ だから $𝑞 * (ˆ 𝑥 ∣ 𝑥) : = 𝐽 (𝑥, ˆ 𝑥) / 𝑝 (𝑥)$ と定めることができ，値は非負で，各 $𝑥$ について $\sum ˆ 𝑥 𝑞 * (ˆ 𝑥 ∣ 𝑥) = 𝑝 (𝑥) / 𝑝 (𝑥) = 1$ である．よって $𝑞 *$ は定義 9.1.5 の条件付き分布であり， $𝑝 (𝑥) 𝑞 * (ˆ 𝑥 ∣ 𝑥) = 𝐽 (𝑥, ˆ 𝑥)$ だから， $𝑞 *$ に対応する対 $(𝑋, ˆ 𝑋)$ の同時分布は $𝐽$ である．

期待歪みを求める． $𝑑 𝐻$ は $𝑥 \neq ˆ 𝑥$ の対でだけ値 $1$ をとるから，定義 9.1.5 の期待歪みは $𝐽 (0, 1) + 𝐽 (1, 0) = 𝑟 𝐷 + (1 - 𝑟) 𝐷 = 𝐷$ である．よって $𝑞 * \in Q (𝐷)$ であり，期待歪みはちょうど $𝐷$ である．

相互情報量を求める．定理 1.3.4 より $𝐼 (𝑝; 𝑞 *) = 𝐻 (𝑋) - 𝐻 (𝑋 ∣ ˆ 𝑋)$ である．第 $1$ 周辺が $𝑝$ だから例 1.1.2 より $𝐻 (𝑋) = 𝐻 𝑏 (𝜋)$ である．第 $2$ 周辺は $P r [ˆ 𝑋 = 1] = 𝐽 (1, 1) + 𝐽 (0, 1) = 𝑟 (1 - 𝐷) + 𝑟 𝐷 = 𝑟$ ， $P r [ˆ 𝑋 = 0] = 1 - 𝑟$ で， $0 < 𝑟 < 1$ よりどちらも正である． $P r [𝑋 \neq 1 ∣ ˆ 𝑋 = 1] = 𝐽 (0, 1) / 𝑟 = 𝐷$ であり， $P r [𝑋 \neq 0 ∣ ˆ 𝑋 = 0] = 𝐽 (1, 0) / (1 - 𝑟) = 𝐷$ である．したがって，どちらの $ˆ 𝑥$ についても， $ˆ 𝑋 = ˆ 𝑥$ のもとでの $𝑋$ の条件付き分布は $ˆ 𝑥$ でないほうの文字に $𝐷$ ， $ˆ 𝑥$ に $1 - 𝐷$ を置いたものであり，定義 1.2.2 と定義 1.1.1 により $𝐻 (𝑋 ∣ ˆ 𝑋 = ˆ 𝑥)$ は二項の和 $- 𝐷 l o g 𝐷 - (1 - 𝐷) l o g (1 - 𝐷)$ ，すなわち例 1.1.2 の $𝐻 𝑏 (𝐷)$ に等しい．定義 1.2.2 はこれを $P r [ˆ 𝑋 = ˆ 𝑥]$ で平均したものだから $𝐻 (𝑋 ∣ ˆ 𝑋) = 𝐻 𝑏 (𝐷)$ であり， $𝐼 (𝑝; 𝑞 *) = 𝐻 𝑏 (𝜋) - 𝐻 𝑏 (𝐷)$ を得る． $◼$

形式化上の注記

命題 9.3.3 にあたる宣言は無い．Hamming 歪みを定めた宣言が形式化に無いので，その下界を達成する条件付き分布を作る宣言も無い（結論の形で探しても見つからない）．

レート歪み関数

定理 9.3.4（二値情報源のレート歪み関数）. $𝜋 \in [0, 1]$ とする． $X = ˆ X = {0, 1}$ とし， $𝑝$ を $𝑝 (1) = 𝜋$ ， $𝑝 (0) = 1 - 𝜋$ で定まる $X$ 上の分布， $𝑑 𝐻$ を例 9.1.3 の Hamming 歪みとし， $Q (\cdot)$ と $𝑅 (\cdot)$ を定義 9.1.5 のとおりとする．実数 $𝐷$ について次が成り立つ（ $𝐻 𝑏$ は例 1.1.2 の二値エントロピー関数）．

$0 \leq 𝐷 < m i n (𝜋, 1 - 𝜋)$ ならば $Q (𝐷)$ は空でなく， $𝑅 (𝐷) = 𝐻 𝑏 (𝜋) - 𝐻 𝑏 (𝐷)$ である．
$𝐷 \geq m i n (𝜋, 1 - 𝜋)$ ならば $Q (𝐷)$ は空でなく， $𝑅 (𝐷) = 0$ である．

証明.

命題 9.3.3 より， $𝐼 (𝑝; 𝑞 *) = 𝐻 𝑏 (𝜋) - 𝐻 𝑏 (𝐷)$ を満たす $𝑞 * \in Q (𝐷)$ が存在する．とくに $Q (𝐷)$ は空でなく， $𝑅 (𝐷)$ は値の集合 ${𝐼 (𝑝; 𝑞) : 𝑞 \in Q (𝐷)}$ の下限だから $𝑅 (𝐷) \leq 𝐻 𝑏 (𝜋) - 𝐻 𝑏 (𝐷)$ である．逆向きを見る． $m i n (𝜋, 1 - 𝜋) \leq 1 / 2$ だから $0 \leq 𝐷 \leq 1 / 2$ であり，命題 9.3.2 よりこの値の集合のどの元も $𝐻 𝑏 (𝜋) - 𝐻 𝑏 (𝐷)$ 以上である．下限は下界のうち最大のものだから $𝑅 (𝐷) \geq 𝐻 𝑏 (𝜋) - 𝐻 𝑏 (𝐷)$ である．二つを合わせて等号を得る．
まず命題 9.2.5 の $𝐷 m a x$ を計算する． $ˆ 𝑥 = 0$ に対しては $\sum 𝑥 𝑝 (𝑥) 𝑑 𝐻 (𝑥, 0) = 𝑝 (1) = 𝜋$ ， $ˆ 𝑥 = 1$ に対しては $\sum 𝑥 𝑝 (𝑥) 𝑑 𝐻 (𝑥, 1) = 𝑝 (0) = 1 - 𝜋$ だから， $𝐷 m a x = m i n (𝜋, 1 - 𝜋)$ である．命題 9.2.5 より $Q (𝐷 m a x)$ は空でないから， $𝐷 m a x \leq 𝐷$ に命題 9.2.1 を当てると $Q (𝐷)$ も空でない．そのうえで命題 9.2.5 の後半を $𝐷$ に当てると， $𝐷 \geq 𝐷 m a x$ だから $𝑅 (𝐷) = 0$ である．

$◼$

形式化上の注記

定理 9.3.4 にあたる宣言は無い．形式化には歪み尺度を具体的にとった実例が一つも置かれていないので，Hamming 歪みを定めた宣言も，二値情報源のレート歪み関数の値を述べた宣言も無い（結論の形で探しても見つからない）．

両端で確かめる. 左の端は $𝐷 = 0$ で，定理 9.3.4 の第 $1$ の場合の値は $𝐻 𝑏 (𝜋) - 𝐻 𝑏 (0) = 𝐻 𝑏 (𝜋)$ である． $X = ˆ X$ であり， $𝑑 𝐻 (𝑥, ˆ 𝑥) = 0$ が $ˆ 𝑥 = 𝑥$ と同値だから，命題 9.2.4 の仮定が満たされていて，これはその $𝑅 (0) = 𝐻 (𝑋)$ と一致している．右の端は $𝐷 m a x = m i n (𝜋, 1 - 𝜋)$ で，第 $1$ の場合の式にこの値を入れると， $𝜋 \leq 1 / 2$ なら $𝐻 𝑏 (𝜋) - 𝐻 𝑏 (𝜋) = 0$ ， $𝜋 > 1 / 2$ なら $𝐻 𝑏 (𝜋) - 𝐻 𝑏 (1 - 𝜋) = 0$ である（後者は補題 9.3.1 の第 $1$ の主張による）．すなわち第 $1$ の場合の式と第 $2$ の場合の値は，境目で段差なくつながっている．

通信路容量と同じ式になる. 公平なコイン（ $𝜋 = 1 / 2$ ）では $𝐷 m a x = 1 / 2$ で， $0 \leq 𝐷 < 1 / 2$ のとき $𝑅 (𝐷) = 1 - 𝐻 𝑏 (𝐷)$ ビットである．第6章例 6.1.8 の二元対称通信路の容量と同じ式が，ここでは最小にした相互情報量として現れている．偶然ではない．命題 9.3.3 の作り方は反転確率 $𝐷$ の二元対称通信路を再現から情報源へ向けて使うもので， $𝜋 = 1 / 2$ のときは再現の側が一様分布になる（命題 9.3.3 の証明の $𝑟$ が $1 / 2$ になる）．その通信路の容量を達成する入力がまさに一様入力なので，下界を達成する対の相互情報量が，例 6.1.8 の容量の値そのものになる．

得られた式が 9.2 節の一般論と食い違わないことも見ておく． $𝐷$ について非増加であることは，補題 9.3.1 の第 $3$ の主張が $[0, 1 / 2]$ の上で $𝐻 𝑏$ が増えると言っているので， $- 𝐻 𝑏 (𝐷)$ が増えないことから読める（命題 9.2.1）．凸であることは，補題 9.3.1 の第 $2$ の主張により $𝐻 𝑏$ が凹だから， $- 𝐻 𝑏$ が凸であることから読める（命題 9.2.3）．一般論が形だけを言っていたところに，二値の情報源では閉じた式が入る．

数で見る

例 9.3.5（ $𝜋 = 1 / 4$ の二値情報源）. $X = ˆ X = {0, 1}$ とし， $𝑝 (1) = 1 / 4$ ， $𝑝 (0) = 3 / 4$ ， $𝑑 = 𝑑 𝐻$ （例 9.1.3）として $𝑅 (\cdot)$ を定義 9.1.5 のとおりとする．このとき $𝑅 (0)$ は約 $0.8113$ ビット， $𝑅 (0.05)$ は約 $0.5249$ ビット， $𝑅 (0.1)$ は約 $0.3423$ ビットであり， $𝐷 \geq 1 / 4$ では $𝑅 (𝐷) = 0$ である（図 9.3.1）．

証明. $m i n (1 / 4, 3 / 4) = 1 / 4$ だから，定理 9.3.4 より $0 \leq 𝐷 < 1 / 4$ では $𝑅 (𝐷) = 𝐻 𝑏 (1 / 4) - 𝐻 𝑏 (𝐷)$ であり， $𝐷 \geq 1 / 4$ では $𝑅 (𝐷) = 0$ である．

$𝐻 𝑏 (1 / 4)$ を求める． $l o g 2 3 = 1.5849 \dots$ だから

𝐻 𝑏 (1 / 4) = 14 l o g 2 4 + 34 l o g 2 43 = 12 + 34 (2 - l o g 2 3) = 0.5 + 0.75 \times 0.4150 \dots = 0.8112 \dots

である． $𝐷 = 0$ では $𝐻 𝑏 (0) = 0$ だから $𝑅 (0) = 𝐻 𝑏 (1 / 4)$ で，約 $0.8113$ ビットである．

$𝐷 = 0.05$ では $l o g 2 0.05 = - 4.3219 \dots$ ， $l o g 2 0.95 = - 0.0740 \dots$ だから $𝐻 𝑏 (0.05) = 0.05 \times 4.3219 \dots + 0.95 \times 0.0740 \dots = 0.2160 \dots + 0.0703 \dots = 0.2863 \dots$ であり， $𝑅 (0.05) = 0.8112 \dots - 0.2863 \dots = 0.5248 \dots$ で約 $0.5249$ ビットである．

$𝐷 = 0.1$ では $l o g 2 0.1 = - 3.3219 \dots$ ， $l o g 2 0.9 = - 0.1520 \dots$ だから $𝐻 𝑏 (0.1) = 0.1 \times 3.3219 \dots + 0.9 \times 0.1520 \dots = 0.3321 \dots + 0.1368 \dots = 0.4689 \dots$ であり， $𝑅 (0.1) = 0.8112 \dots - 0.4689 \dots = 0.3422 \dots$ で約 $0.3423$ ビットである． $◼$

図 9.3.1. 例 9.3.5 の二値情報源（ $𝜋 = 1 / 4$ ，Hamming 歪み）のレート歪み関数． $𝐷 < 1 / 4$ では $𝐻 𝑏 (1 / 4) - 𝐻 𝑏 (𝐷)$ で， $𝐷 = 1 / 4$ で $0$ に達する．点は例 9.3.5 で求めた $𝐷 = 0, 0.05, 0.1$ の値である．

形式化上の注記

例 9.3.5 に対応する宣言は形式化されていない．

規模感. 例 9.3.5 の情報源では，歪みをいっさい許さないときの値が約 $0.8113$ ビットである．文字の $5$ パーセントの食い違いを許すだけで約 $0.5249$ ビットまで下がり，減り方はおよそ $35$ パーセントである． $10$ パーセントの食い違いまで許すと約 $0.3423$ ビットで，およそ $58$ パーセント減る．最初のうちは，わずかな歪みを許すだけで値が大きく落ちる． $1 / 4$ まで許すと $0$ になる．情報源を見ずにいつも $0$ を出す再現でも，食い違うのは文字の $1 / 4$ だけだからである（命題 9.2.5 の $𝐷 m a x$ の読み方）．

ここまでの主張は，どれも最適化問題の値についてのものである．9.5 節と 9.6 節へ進む前に，9.4 節でもう一つの具体例，すなわち実数値をとる情報源を扱う．

情報理論入門（Lean による形式証明つき）・GitHub