Shearerの補題(Shearer's lemma)とは、有限集合に値をとる確率変数の組 $X=(X_1,\dots,X_n)$ と座標の部分集合 $A_1,\dots,A_s$ について、各座標が少なくとも $k$ 個の $A_j$ に含まれるなら $k\,H(X)\le\sum_jH(X_{A_j})$ が成り立つ、というエントロピーの不等式である。各 $X_{A_j}$ のエントロピーを連鎖律で分け、条件を増やすとエントロピーが増えないことを使って証明される。一様分布に当てはめると、集合の大きさをその射影の大きさで抑える Loomis–Whitney 型の不等式になる。応用に、$m$ 本の辺をもつグラフの三角形の個数が $\frac{\sqrt2}3m^{3/2}$ 以下であることや、$d$-正則二部グラフの独立集合の個数についての Kahn の定理がある。
前提知識: Shannonエントロピー, 確率変数
Shearerの補題(Shearer's lemma)は、確率変数の組 $X=(X_1,\dots,X_n)$ のエントロピーを、座標の部分集合 $A_1,\dots,A_s$ に制限した組 $X_{A_j}$ のエントロピーで上から抑える不等式である。各座標が少なくとも $k$ 個の $A_j$ に含まれるなら
$$
k\,H(X_1,\dots,X_n)\le\sum_{j=1}^sH(X_{A_j})
$$
が成り立つ。$A_j$ を 1 点集合 $\{1\},\dots,\{n\}$ にとると劣加法性 $H(X)\le\sum_iH(X_i)$ になり、$n=3$ で 2 点集合を 3 つとると $2H(X,Y,Z)\le H(X,Y)+H(Y,Z)+H(X,Z)$ になる。
一様分布のエントロピーは台の大きさの対数なので、この不等式は「集合の大きさを、その射影の大きさで抑える」数え上げの不等式に読み替えられる。こうして、グラフの中の三角形の個数を辺の本数で抑える評価、立体をその影で抑える Loomis–Whitney 型の不等式、正則二部グラフの独立集合の個数についての Kahn の定理が得られる。一般形は F. R. K. Chung、R. L. Graham、P. Frankl、J. B. Shearer の 1986 年の論文による(Zha23 p. 199)。
確率変数はすべて有限集合に値をとるものとし、$\log$ は自然対数とする。エントロピー $H(\cdot)$、同時エントロピー、条件付きエントロピー $H(Y\mid X)$ は Shannonエントロピー の定義「エントロピー」「同時・条件付きエントロピーと相互情報量」のものである。$[n]:=\{1,\dots,n\}$ とし、$A\subseteq[n]$ について $X_A:=(X_i)_{i\in A}$(添字の小さい順に並べた組)、$X_{< i}:=X_{[i-1]}$ と書く。$X_\emptyset$ は定数とみなし $H(X_\emptyset)=0$ とする。
Shannonエントロピー の定理「連鎖律と劣加法性」の 1 を繰り返し使うと、$n$ 個の変数の 連鎖律
$$
H(X_1,\dots,X_n)=\sum_{i=1}^nH(X_i\mid X_{< i})
$$
が得られる($H(X_{[i]})=H(X_{< i})+H(X_i\mid X_{< i})$ を $i=1,\dots,n$ について足せばよい)。もう 1 つ、条件を増やすとエントロピーが増えないことを使う。
$Y,Z,W$ を有限集合に値をとる確率変数とすると、$H(Y\mid Z,W)\le H(Y\mid Z)$ である。
$P(Z=z)>0$ となる $z$ を固定し、事象 $Z=z$ のもとでの条件付き確率 $P_z:=P(\,\cdot\mid Z=z)$ を考える。条件付きエントロピーの定義から
$$
H(Y\mid Z,W)=\sum_{z,w}P(Z=z,W=w)\,H(Y\mid Z=z,W=w)=\sum_zP(Z=z)\sum_wP_z(W=w)\,H(Y\mid Z=z,W=w)
$$
である(和は確率が正の項にわたる)。右辺の内側の和は、確率 $P_z$ のもとでの $W$ を条件とする $Y$ の条件付きエントロピーである。Shannonエントロピー の定理「連鎖律と劣加法性」の 3 を確率 $P_z$ のもとで使うと、それは $P_z$ のもとでの $Y$ のエントロピー $H(Y\mid Z=z)$ 以下である。$z$ について重み $P(Z=z)$ で足すと $H(Y\mid Z)$ になる。$\square$
とくに $B\subseteq C\subseteq[n]$ なら $H(X_i\mid X_C)\le H(X_i\mid X_B)$ である。
$X=(X_1,\dots,X_n)$ を有限集合に値をとる確率変数の組とする。$[n]$ の部分集合の有限族 $\mathcal A$ と重み $w\colon\mathcal A\to[0,\infty)$ が、ある $k\ge0$ について
$$
\sum_{A\in\mathcal A,\ A\ni i}w(A)\ge k\qquad(i=1,\dots,n)
$$
を満たすとする。このとき
$$
k\,H(X)\le\sum_{A\in\mathcal A}w(A)\,H(X_A)
$$
である。とくに、$[n]$ の部分集合の列 $A_1,\dots,A_s$(重複を許す)で各 $i\in[n]$ が少なくとも $k$ 個の $A_j$ に含まれるなら、$k\,H(X)\le\sum_{j=1}^sH(X_{A_j})$ である。
$A=\{a_1< a_2< \cdots< a_r\}\subseteq[n]$ とする。$X_A$ に上の連鎖律を使うと
$$
H(X_A)=\sum_{t=1}^rH\bigl(X_{a_t}\mid X_{a_1},\dots,X_{a_{t-1}}\bigr)
$$
である。$\{a_1,\dots,a_{t-1}\}\subseteq[a_t-1]$ なので、lem-sh-conditioning により各項は $H(X_{a_t}\mid X_{< a_t})$ 以上である。よって
$$
H(X_A)\ge\sum_{i\in A}H(X_i\mid X_{< i})
$$
である。これに $w(A)\ge0$ を掛けて $A\in\mathcal A$ について足し、和の順序を入れ替えると
$$
\sum_{A\in\mathcal A}w(A)H(X_A)\ge\sum_{i=1}^n\Bigl(\sum_{A\ni i}w(A)\Bigr)H(X_i\mid X_{< i})\ge k\sum_{i=1}^nH(X_i\mid X_{< i})=k\,H(X)
$$
となる。2 つ目の不等号は $H(X_i\mid X_{< i})\ge0$(条件付き分布ごとのエントロピーが $0$ 以上)と仮定から、最後の等号は上の連鎖律による。列 $A_1,\dots,A_s$ の場合は、$w(A)$ を $A$ が列に現れる回数とすればよい。$\square$
証明の要点は、各 $X_{A}$ のエントロピーを連鎖律で 1 変数ずつに分け、条件を「$A$ の中の前の変数」から「全体の前の変数」に増やして揃えることにある。揃えた後は各項 $H(X_i\mid X_{< i})$ が少なくとも $k$ 回現れ、連鎖律でまとめると $k\,H(X)$ になる。
$X_1,\dots,X_n$ が独立で、各 $i$ がちょうど $k$ 個の $A_j$ に含まれるなら、$H(X_A)=\sum_{i\in A}H(X_i)$ なので等号が成り立つ。
$S$ を $[n]$ の部分集合に値をとる確率変数で $X$ と独立なものとし、$\mu:=\min_iP(i\in S)$ とおく。このとき $\mu\,H(X)\le H(X_S\mid S)$ である。
$S$ と $X$ が独立なので、$P(S=A)>0$ のとき $S=A$ のもとでの $X_S$ の分布は $X_A$ の分布であり、$H(X_S\mid S)=\sum_AP(S=A)H(X_A)$ である。$w(A):=P(S=A)$ とおくと $\sum_{A\ni i}w(A)=P(i\in S)\ge\mu$ なので、thm-sh-main から従う。$\square$
この形は PW25 の Theorem 1.8(pp. 18–19)で、同書は族を交わりと合併で置き換えて鎖にする別の証明を与えている。$S$ を $k$ 元部分集合の上の一様分布にとると、$P(i\in S)=k/n$ なので
$$
\frac1nH(X)\le\frac1k\cdot\frac1{\binom nk}\sum_{|A|=k}H(X_A)
$$
となる。これが Han の不等式(PW25 Theorem 1.7 と Remark 1.2、pp. 17–18)の一部である。
$X$ が有限集合 $T$ の上の一様分布に従えば $H(X)=\log|T|$ で、$X_A$ は $T$ の射影の中に値をとるので $H(X_A)$ はその大きさの対数以下である(Shannonエントロピー の定理「エントロピーの範囲」)。こうして thm-sh-main から次が出る。
$\Omega_1,\dots,\Omega_n$ を有限集合、$T\subseteq\Omega_1\times\cdots\times\Omega_n$ とし、$A\subseteq[n]$ について $\pi_A\colon T\to\prod_{i\in A}\Omega_i$ を座標 $A$ への射影とする。$[n]$ の部分集合の列 $A_1,\dots,A_s$ で、各 $i$ が少なくとも $k$ 個の $A_j$ に含まれるなら
$$
|T|^k\le\prod_{j=1}^s|\pi_{A_j}(T)|
$$
である。とくに $A_j:=[n]\setminus\{j\}$(各 $i$ は $n-1$ 個に含まれる)とすると $|T|^{n-1}\le\prod_{j=1}^n|\pi_{[n]\setminus\{j\}}(T)|$ であり、$n=3$ では $|T|^2\le|\pi_{xy}(T)|\,|\pi_{yz}(T)|\,|\pi_{xz}(T)|$ である。
$T=\emptyset$ なら自明である。そうでなければ $X$ を $T$ の上の一様分布に従う確率変数とすると、$k\log|T|=k\,H(X)\le\sum_jH(X_{A_j})\le\sum_j\log|\pi_{A_j}(T)|$ である。両辺の指数をとればよい。$\square$
$\Omega_i=\{0,1\}$ のとき $T$ は $[n]$ の部分集合の族 $\mathcal F$ とみなせ、$\pi_A(T)$ は $\{F\cap A:F\in\mathcal F\}$ にあたる。直方体 $T=B_1\times B_2\times B_3$ では $n=3$ の不等式の両辺がともに $(|B_1||B_2||B_3|)^2$ で等号が成り立ち、原点と 3 つの単位ベクトルの 4 点からなる $T$ では $16\le3\cdot3\cdot3=27$ である。
$\mathbb R^n$ のコンパクト集合の体積とその座標超平面への射影の体積についての同じ形の不等式 $|K|^{n-1}\le\prod_j|\pi_{[n]\setminus\{j\}}(K)|$ を Loomis–Whitney の不等式 という。L. H. Loomis と H. Whitney(1949 年)による(Zha23 Remark 5.3.6 と (5.4)、pp. 181–182)。PW25 は微分エントロピーを使って Bollobás–Thomason の箱定理からこれを導いている(Theorem 8.6・Corollary 8.7、pp. 164–165)。関数の形の不等式は、Brascamp–Liebの不等式 の例として、また Sobolevの埋め込み定理 の証明の補題として現れる。
$m$ 本の辺をもつグラフに含まれる三角形の個数は $\frac16(2m)^{3/2}=\frac{\sqrt2}3m^{3/2}$ 以下である。
三角形の個数を $N$ とし、$N\ge1$ とする。三角形の頂点に順序を付けた組 $(x_1,x_2,x_3)$ は $6N$ 個あり、その上の一様分布に従う $X=(X_1,X_2,X_3)$ を考える。$H(X)=\log(6N)$ である。各 $(X_a,X_b)$($a\ne b$)は向きの付いた辺、すなわち $2m$ 通りの値の 1 つをとるので $H(X_a,X_b)\le\log(2m)$ である。$\{1,2\},\{2,3\},\{1,3\}$ の各点は 2 回ずつ現れるので、thm-sh-main により $2\log(6N)\le3\log(2m)$、すなわち $6N\le(2m)^{3/2}$ である。$\square$
完全グラフ $K_n$ では $m=\binom n2$、$N=\binom n3$ で、上界との比は $\dfrac{n-2}{\sqrt{n(n-1)}}$ であり、$n\to\infty$ で $1$ に近づく。よって定数 $\frac{\sqrt2}3$ は改善できない。この評価と、隣接行列の固有値を使う別証明は PW25 §8.2 の (8.2) と Remark 8.1(p. 160)にある。
グラフ $F$ の独立集合(独立集合。空集合を含む)の個数を $i(F)$ と書く。
二部分割を $(A,B)$ とする。辺の本数を 2 通りに数えると $d|A|=d|B|$ なので $|A|=|B|=n/2$ である。$F$ の独立集合を一様に選んだものを $I$ とし、$v\in V(F)$ について $X_v:=1$($v\in I$)、$0$($v\notin I$)とする。$I$ と $(X_v)_v$ は 1 対 1 に対応するので $\log i(F)=H(X)$ である。連鎖律から
$$
H(X)=H(X_A)+H(X_B\mid X_A)
$$
である。
$B$ の部分。 $B=\{b_1,\dots,b_r\}$ とし、$H(X_B\mid X_A)$ を連鎖律で $\sum_tH(X_{b_t}\mid X_A,X_{b_1},\dots,X_{b_{t-1}})$ と書いて lem-sh-conditioning を使い、さらに $b$ の近傍 $N(b)\subseteq A$ への条件に減らすと(これも同じ補題)
$$
H(X_B\mid X_A)\le\sum_{b\in B}H(X_b\mid X_{N(b)})
$$
である。
$A$ の部分。 族 $\{N(b):b\in B\}$ では、各 $a\in A$ がちょうど $\deg(a)=d$ 個の $N(b)$ に含まれる。thm-sh-main により $H(X_A)\le\frac1d\sum_{b\in B}H(X_{N(b)})$ である。よって
$$
\log i(F)\le\sum_{b\in B}\Bigl(\frac1dH(X_{N(b)})+H(X_b\mid X_{N(b)})\Bigr)
$$
である。
各項の評価。 $b\in B$ を固定し、$Y:=X_{N(b)}\in\{0,1\}^d$、$Z:=X_b$、$p:=P(Y=0)$($0$ はすべての成分が $0$ の値)とおく。$Y\ne0$ なら $b$ の近傍の頂点が $I$ に入っているので $Z=0$ で、そのときの条件付きエントロピーは $0$ である。$Y=0$ のときは $Z$ は 2 値なので $H(Z\mid Y=0)\le\log2$ である。よって $H(Z\mid Y)\le p\log2$ である。また $E:=[Y=0]$($Y=0$ なら $1$、そうでなければ $0$)は $Y$ の関数なので $H(Y)=H(Y,E)$ であり(組 $(Y,E)$ の値は $Y$ の値で決まる)、連鎖律から $H(Y,E)=H(E)+H(Y\mid E)$ である。$H(E)=h(p)$、$H(Y\mid E=1)=0$、$H(Y\mid E=0)\le\log(2^d-1)$ だから
$$
H(Y)\le h(p)+(1-p)\log(2^d-1),\qquad h(p):=-p\log p-(1-p)\log(1-p)
$$
である。$a:=2^d-1$、$c:=2^d$ とおくと $d\cdot p\log2=p\log c$ なので
$$
\frac1dH(Y)+H(Z\mid Y)\le\frac1d\bigl(h(p)+(1-p)\log a+p\log c\bigr)
$$
である。$0< p< 1$ なら、右辺の括弧の中は $(1-p)\log\frac a{1-p}+p\log\frac cp$ と書け、$\log$ の凹性(Jensenの不等式)により $\log\bigl((1-p)\frac a{1-p}+p\frac cp\bigr)=\log(a+c)$ 以下である。$p\in\{0,1\}$ なら括弧の中は $\log a$ か $\log c$ で、やはり $\log(a+c)$ 以下である。$a+c=2^{d+1}-1$ なので、各項は $\frac1d\log(2^{d+1}-1)$ 以下である。
$|B|=n/2$ 個の項を足すと $\log i(F)\le\frac n{2d}\log(2^{d+1}-1)$ である。
等号。 $K_{d,d}$ の独立集合は、一方の部の部分集合か他方の部の部分集合で、両方に共通なのは空集合だけなので、$i(K_{d,d})=2^d+2^d-1=2^{d+1}-1$ である。非交和の独立集合は各成分の独立集合の組なので、個数は積になる。$\square$
たとえば $d=2$ の閉路 $C_6$ では $i(C_6)=18\le7^{3/2}\approx18.52$、$C_8$ では $i(C_8)=47\le7^2=49$ である。この定理は J. Kahn(2001 年、Kah01)が Shearer の補題を使って示した(Zha23 Theorem 5.3.14 と Remark 5.3.18、pp. 184–185)。二部グラフの仮定は Y. Zhao(2010 年)が外し、すべての $d$-正則グラフで同じ上界が成り立つ(同 Theorem 5.3.14)。Zha23 Theorem 5.5.20(pp. 200–201)は、同じ方法で独立集合をグラフ準同型の個数に置き換えた形(D. Galvin と P. Tetali による)を証明している。
| 外した仮定 | 例 | 成り立たなくなる結論 |
|---|---|---|
| 各座標が $k$ 個以上の集合に含まれること(thm-sh-main) | $n=2$、$A_1=A_2=\{1\}$、$k=2$、$X_1$ は定数、$X_2$ は 2 値の一様分布 | $2H(X)=2\log2>0=H(X_{A_1})+H(X_{A_2})$ |
| $S$ と $X$ が独立であること(cor-sh-random) | $n=1$、$X_1$ は 2 値の一様分布、$X_1=0$ のとき $S=\{1\}$、$X_1=1$ のとき $S=\emptyset$ | $\mu=\frac12$ だが $H(X_S\mid S)=0<\frac12\log2=\mu H(X)$ |
| $F$ が正則であること(thm-sh-kahn。最大次数 $d$ の二部グラフに緩める) | 道 $P_3$($=K_{1,2}$、$d=2$、$n=3$) | $i(P_3)=5>7^{3/4}\approx4.30$ |
1 行目:座標 $2$ はどの $A_j$ にも含まれない。$H(X)=H(X_2)=\log2$、$H(X_1)=0$ である。2 行目:$S=\{1\}$ のとき $X_S=X_1=0$ に決まり、$S=\emptyset$ のとき $X_S$ は定数なので、$H(X_S\mid S)=0$ である。$P(1\in S)=P(X_1=0)=\frac12$ である。3 行目:$P_3$ の頂点を $u,v,w$($v$ が中央)とすると、独立集合は $\emptyset,\{u\},\{v\},\{w\},\{u,w\}$ の 5 個である。$7^{3/4}<5$ は $7^3=343<5^4=625$ と同値である。
$n=3$ の形 $2H(X,Y,Z)\le H(X,Y)+H(X,Z)+H(Y,Z)$ とその証明は Zha23 Theorem 5.5.16(p. 199)、一般形は同 Theorem 5.5.17(p. 199)で、同書はこれを Chung–Graham–Frankl–Shearer(1986 年、CGFS86)に帰している。完全マッチングの個数についての Bregmanの定理 のエントロピーによる証明は、連鎖律を変数の順序を無作為にして平均する方法で、Shearer の補題とは別の工夫である(PW25 §8.3)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する