16.3 Shearer の不等式

定理 16.2.1 が使った覆いは特別なものだった．番号を $1$ 個ずつ抜いた $𝑛$ 個の集合という決まった族で，どの番号もちょうど $𝑛 - 1$ 回覆われる．証明を読み返すと，この形はほとんど効いていない．効いたのは，各集合について定理 16.1.4 を書き下し，条件をどれも $𝑖$ より小さい番号の全体にそろえて物差しを合わせ，最後に「どの番号が何回覆われたか」を数えたことだけである．そこで族のほうを一般にとり，覆う回数だけを仮定に残す．

定理 16.3.1（Shearer の不等式）. 定義 16.1.1 の設定で， $𝑟 \geq 1$ ， $𝑆 1, \dots, 𝑆 𝑟 \subseteq {1, \dots, 𝑛}$ とし， $𝑘$ を非負整数とする．どの $𝑖 \in {1, \dots, 𝑛}$ についても $𝑖$ を含む $𝑆 𝑗$ が $𝑘$ 個以上あるならば

𝑘 𝐻 (𝑋 {1, \dots, 𝑛}) \leq 𝑟 \sum 𝑗 = 1 𝐻 (𝑋 𝑆 𝑗)

である．

証明. 各 $𝑗$ について定理 16.1.4 を $𝑆 𝑗$ に当てると

𝐻 (𝑋 𝑆 𝑗) = \sum 𝑖 \in 𝑆 𝑗 𝐻 (𝑋 𝑖 ∣ 𝑋 𝑆 𝑗 \cap {1, \dots, 𝑖 - 1})

である． ${1, \dots, 𝑖 - 1}$ を， $𝑆 𝑗$ に属する番号と属さない番号に分けると，前者は $𝑆 𝑗 \cap {1, \dots, 𝑖 - 1}$ であり，二つは交わらず和が ${1, \dots, 𝑖 - 1}$ である． $𝑋 {1, \dots, 𝑖 - 1}$ をこの二つの組の対とみて（補題 16.1.2），定理 1.2.4 を当てると，右辺の各項は $𝐻 (𝑋 𝑖 ∣ 𝑋 {1, \dots, 𝑖 - 1})$ 以上である．よって

𝑟 \sum 𝑗 = 1 𝐻 (𝑋 𝑆 𝑗) \geq 𝑟 \sum 𝑗 = 1 \sum 𝑖 \in 𝑆 𝑗 𝐻 (𝑋 𝑖 ∣ 𝑋 {1, \dots, 𝑖 - 1})

である．右辺の二重の和を $𝑖$ ごとにまとめ直すと， $𝐻 (𝑋 𝑖 ∣ 𝑋 {1, \dots, 𝑖 - 1})$ が現れる回数は $𝑖$ を含む $𝑆 𝑗$ の個数であり，仮定よりそれは $𝑘$ 以上である．定義 1.2.2 の中辺の各項に命題 1.1.4 を当てるとこの量は非負だから，回数を $𝑘$ に減らしても和は小さくなるだけで

𝑟 \sum 𝑗 = 1 𝐻 (𝑋 𝑆 𝑗) \geq 𝑘 𝑛 \sum 𝑖 = 1 𝐻 (𝑋 𝑖 ∣ 𝑋 {1, \dots, 𝑖 - 1})

である．最後に定理 16.1.4 を $𝑆 = {1, \dots, 𝑛}$ に当てると，右辺の和は $𝐻 (𝑋 {1, \dots, 𝑛})$ に等しい． $◼$

形式化: shearer_inequality (ソース)

形式化上の注記. 宣言は族の添字を任意の有限型でとる．本文が族を $𝑆 1, \dots, 𝑆 𝑟$ と番号で並べているのは，その添字を ${1, \dots, 𝑟}$ にとった場合にあたる．

族を「番号 $𝑖$ だけを抜いた $𝑛$ 個の集合」ととると，どの番号も $𝑛 - 1$ 個の集合に含まれるので $𝑘 = 𝑛 - 1$ ととれて，定理 16.3.1 は定理 16.2.1 そのものになる．Han の不等式は Shearer の不等式の特別な場合である．

物差しをそろえると読む. 定理 16.3.1 の証明で二つの不等号が入った場所は，性質が違う．第 $1$ の不等号（定理 1.2.4）は，集合ごとにばらばらだった条件を ${1, \dots, 𝑖 - 1}$ の全体まで増やして，どの集合についても同じ量で下から押さえる段である．条件を増やせば残る不確かさは増えないので，もとの各項はその同じ量以上になる．ここを通すと，族の形は「どの番号が何回現れたか」という数だけに畳まれる．第 $2$ の不等号は，その回数を仮定の $𝑘$ まで減らす段で，減らしてよいのは各項が非負だからである．

系 16.3.2（劣加法性）. 定義 16.1.1 の設定で

𝐻 (𝑋 {1, \dots, 𝑛}) \leq 𝑛 \sum 𝑖 = 1 𝐻 (𝑋 𝑖)

である（ $𝐻 (𝑋 𝑖)$ は定義 1.1.1 の $1$ 変数のエントロピーである）．

証明. 族を $𝑛$ 個の $1$ 点集合 ${1}, \dots, {𝑛}$ ととると，どの番号もちょうど一つの集合に含まれるので， $𝑘 = 1$ として定理 16.3.1 が使えて

𝐻 (𝑋 {1, \dots, 𝑛}) \leq 𝑛 \sum 𝑖 = 1 𝐻 (𝑋 {𝑖})

である． $𝑋 {𝑖}$ は ${𝑖}$ から $X$ への関数に値をとる．その値に $𝑖$ での値を対応させる写像は単射で，この写像で $𝑋 {𝑖}$ を移したものが $𝑋 𝑖$ だから， $𝐻 (𝑋 {𝑖}) = 𝐻 (𝑋 𝑖)$ である（補題 16.1.2）． $◼$

形式化: entropy_pi_le_sum_entropy (ソース)

形式化上の注記. 宣言の右辺も $1$ 変数のエントロピーの和で， $1$ 点集合についての部分集合のエントロピーの和ではない．二つが等しいことを述べる単独の宣言はない．また，形式化は本文と別の道をとり，Shearer の不等式を経由せずに， $𝑆$ が全体の場合のチェイン則の各項を条件のない $1$ 変数のエントロピーで直に押さえて証明している．結論の定理は同一である．

系 16.3.2 は， $𝑛$ 個をまとめて見たときの不確かさが， $1$ 個ずつ見たときの不確かさの合計を超えないと言っている．変数どうしに重なりがあれば，まとめて見るほうが得をする． $2$ 変数のときに，独立なら両辺が等しくなることは第1章 1.2 節で見た．結合密度をもち値が定まるかぎり，微分エントロピーについても同じ形の不等式が成り立つ（定理 7.4.3）．

例 16.3.3. 例 16.1.3 の 1 の族について， ${1, 2}$ ， ${2, 3}$ ， ${1, 3}$ を族にとるとどの番号もちょうど二つの集合に含まれ， $𝑘 = 2$ として定理 16.3.1 の両辺は $4$ と $5$ である． ${1}$ ， ${2}$ ， ${3}$ を族にとると $𝑘 = 1$ として両辺は $2$ と $3$ である．

証明. 例 16.1.3 の 1 より $𝐻 (𝑋 {1, 2, 3}) = 2$ だから， $𝑘 = 2$ の族では左辺が $2 \cdot 2 = 4$ ，右辺が $𝐻 (𝑋 {1, 2}) + 𝐻 (𝑋 {2, 3}) + 𝐻 (𝑋 {1, 3}) = 1 + 2 + 2 = 5$ である． $𝑘 = 1$ の族では左辺が $1 \cdot 2 = 2$ ，右辺が $1 + 1 + 1 = 3$ である． $◼$

例 16.3.3 の二つの族は，どちらも定理 16.3.1 の仮定を満たしながら， $𝐻 (𝑋 {1, 2, 3})$ に与える上界が違う． $𝑘 = 2$ の族は $5 / 2$ で押さえ， $𝑘 = 1$ の族は $3$ で押さえる（実際の値は $2$ である）．

16.1 節の終わりに置いた問い，すなわち $𝐻 (𝑋 𝑆)$ について示すことのどこまでが値の出どころに依らないのか，にここで答えておく．定理 16.3.1 の証明でエントロピーの中身が効いているのは，定理 16.1.4 のチェイン則と，条件付きエントロピーの非負性と，定理 1.2.4 の三つだけである．この三つは，定義 16.1.7 の三条件をそれぞれ書き換えたものである．チェイン則は第 $1$ の条件から増分を足し上げて出る等式であり，定理 1.2.4 を当てた段は，16.1 節で見たとおり第 $3$ の劣モジュラ性の言い換えであり，条件付きエントロピーの非負性は第 $2$ の単調性にあたる．この対応をたどって定理 16.3.1 を階数関数一般に書き直すと，次を得る．

系 16.3.4（Shearer の不等式の階数関数への一般化）. $𝑛 \geq 1$ とし， $r k$ を ${1, \dots, 𝑛}$ 上のポリマトロイドの階数関数（定義 16.1.7）とする． $𝑟 \geq 1$ ， $𝑆 1, \dots, 𝑆 𝑟 \subseteq {1, \dots, 𝑛}$ とし， $𝑘$ を非負整数とする．どの $𝑖 \in {1, \dots, 𝑛}$ についても $𝑖$ を含む $𝑆 𝑗$ が $𝑘$ 個以上あるならば

𝑘 r k ({1, \dots, 𝑛}) \leq 𝑟 \sum 𝑗 = 1 r k (𝑆 𝑗)

である．とくに $𝑟 = 𝑛$ ， $𝑆 𝑖 : = {1, \dots, 𝑛} ∖ {𝑖}$ （ $1 \leq 𝑖 \leq 𝑛$ ）， $𝑘 = 𝑛 - 1$ ととると

(𝑛 - 1) r k ({1, \dots, 𝑛}) \leq 𝑛 \sum 𝑖 = 1 r k ({1, \dots, 𝑛} ∖ {𝑖})

である．

証明. 定理 16.3.1 の証明が使った三つを，定義 16.1.7 の条件から順に作り直す（そこで補題 16.1.2 を挟んだのは，条件を二つの組の対とみるための読み替えで，集合の関数を相手にするならその段は要らない）．以下，集合 $𝐵$ に $𝐵$ の外の番号 $𝑖$ を足したときの $r k (𝐵 \cup {𝑖}) - r k (𝐵)$ を， $𝐵$ に $𝑖$ を足したときの増分と呼ぶ．

第一に，定理 16.1.4 にあたる等式である． $𝑇 \subseteq {1, \dots, 𝑛}$ をとり， $𝑖 \in 𝑇$ ごとに $𝐵 𝑖 : = 𝑇 \cap {1, \dots, 𝑖 - 1}$ とおくと $𝑇 \cap {1, \dots, 𝑖} = 𝐵 𝑖 \cup {𝑖}$ である． $𝑖$ を $𝑇$ の小さい順に動かすと $𝑇 \cap {1, \dots, 𝑖}$ の形の集合が順に大きくなるから，増分の和は隣どうしが打ち消し合って $r k (𝑇)$ と $r k (\emptyset)$ の差だけが残る．第 $1$ の条件により

r k (𝑇) = \sum 𝑖 \in 𝑇 (r k (𝐵 𝑖 \cup {𝑖}) - r k (𝐵 𝑖))

である．

第二に，定理 1.2.4 にあたる不等式である． $𝐵 \subseteq 𝐶 \subseteq {1, \dots, 𝑛}$ と $𝑖 \notin 𝐶$ をとり，第 $3$ の条件を二つの集合 $𝐵 \cup {𝑖}$ と $𝐶$ に当てる．二つの和集合は $𝐶 \cup {𝑖}$ ，共通部分は $𝐵$ だから

r k (𝐶 \cup {𝑖}) - r k (𝐶) \leq r k (𝐵 \cup {𝑖}) - r k (𝐵)

であり，すでに知っている集合が大きいほど増分は小さい．

第三に，増分が非負であることは第 $2$ の条件そのものである．

あとは定理 16.3.1 の証明のとおりである．各 $𝑗$ について第一の等式を $𝑇 = 𝑆 𝑗$ に当て，その $𝑖$ 番目の項に第二の不等式を $𝐵 = 𝑆 𝑗 \cap {1, \dots, 𝑖 - 1}$ ， $𝐶 = {1, \dots, 𝑖 - 1}$ ととって当てると，各項は ${1, \dots, 𝑖 - 1}$ に $𝑖$ を足したときの増分以上である． $𝑗$ について足して $𝑖$ ごとにまとめ直すと， $𝑖$ の増分が現れる回数は $𝑖$ を含む $𝑆 𝑗$ の個数で，仮定よりそれは $𝑘$ 以上である．第三により増分は非負だから，回数を $𝑘$ に減らしても和は小さくなるだけで

𝑟 \sum 𝑗 = 1 r k (𝑆 𝑗) \geq 𝑘 𝑛 \sum 𝑖 = 1 (r k ({1, \dots, 𝑖}) - r k ({1, \dots, 𝑖 - 1}))

である．第一の等式を $𝑇 = {1, \dots, 𝑛}$ に当てると，右辺の和は $r k ({1, \dots, 𝑛})$ に等しい．後半は，番号 $𝑖$ を抜いた $𝑛$ 個の集合ではどの番号もちょうど $𝑛 - 1$ 個の集合に含まれることによる． $◼$

形式化上の注記. 階数関数一般についてこの不等式を述べる宣言はない．ポリマトロイドの構造 Polymatroid (InformationTheory/Polymatroid/Basic.lean) を仮定にとる宣言を結論の形で探しても，部分集合のエントロピーからその構造を組み立てる entropyPolymatroid (InformationTheory/Shannon/Polymatroid.lean) のほかには見つからない．機械検証が及ぶのは定理 16.3.1 の形までである．

系 16.1.8 より $𝐻 (𝑋 𝑆)$ はポリマトロイドの階数関数だから，系 16.3.4 は定理 16.3.1 を含み，したがって定理 16.2.1 も含む．問いへの答えは，Han の不等式も Shearer の不等式も，値がエントロピーであることを使っていない，ということである．定義 16.1.7 の三条件を満たす集合の関数でありさえすれば，同じ不等式が成り立つ．

覆いを一般にとれるようになったことの値打ちは，族を目的に合わせて選べるところにある．次節は，有限集合の上の一様分布に従う確率変数を定義 16.1.1 の族に置く．そうすると例 1.1.3 によって左辺が集合の要素数の対数になり，右辺の各項は定理 1.1.5 によって，座標の一部だけに切り詰めた像の要素数の対数で上から押さえられる．こうして定理 16.3.1 は，集合の要素数とその像の要素数とを結ぶ数え上げの不等式になる．

InformationTheory — 形式化検証つき情報理論教科書（レビュー版）．数式は MathJax + AMS Euler で事前レンダリング．