§E13.11確率的手法

証明.(1)を示す。$A=\emptyset$のときは§E11.1 命題 2.1の 1 より両辺が$0$である。$A\ne\emptyset$とし、$A$の相異なる元を$\omega_1,\dots,\omega_r$と並べる。$1\le i\le r$に対し$A_i=\{\omega_i\}$、$i>r$に対し$A_i=\emptyset$と置くと、$(A_i)_{i\ge1}$は二つずつ交わらない事象の列であり、その合併は$A$である。§E9.2 定義 1.1の可算加法性を適用すると$\mathbb P(A)=\sum_{i\ge1}\mathbb P(A_i)$であり、§E11.1 命題 2.1の 1 より$i>r$の項は$0$であるから、右辺は$\sum_{i=1}^{r}\mathbb P(\{\omega_i\})=\sum_{\omega\in A}\mathbb P(\{\omega\})$に等しい。

(2)を示す。 Borel 集合$B\subseteq\mathbb R$に対し、$X^{-1}(B)$は$\Omega$の部分集合であるから$X^{-1}(B)\in2^{\Omega}$である。ゆえに$X$は可測である。▨

証明.$X^{+}=\max(X,0)$と$X^{-}=\max(-X,0)$と置く。$\Omega$は有限であるから$X^{+}$は有限個の値しか取らず、各値の逆像は$2^{\Omega}$に属する。ゆえに$X^{+}$は非負単関数であり、その積分は§E9.6 定義 1.1によって定まる。$\Omega$の一点集合の族$(\{\omega\})_{\omega\in\Omega}$は$\Omega$の互いに交わらない有限分割であり、$X^{+}=\sum_{\omega\in\Omega}X^{+}(\omega)\mathbf 1_{\{\omega\}}$と書くことができるから、§E9.6 命題 1.2を分割$(\{\omega\})_{\omega\in\Omega}$と係数$(X^{+}(\omega))_{\omega\in\Omega}$へ適用して$\int_{\Omega}X^{+}\,d\mathbb P=\sum_{\omega\in\Omega}X^{+}(\omega)\,\mathbb P(\{\omega\})$を得る。この右辺は有限個の実数の和であるから有限である。$X^{-}$についても同じ議論を行うと$\int_{\Omega}X^{-}\,d\mathbb P$が有限であることが分かる。$\lvert X\rvert=X^{+}+X^{-}$であるから$\mathbb E[\lvert X\rvert]<\infty$であり、§E11.4 定義 1.1の意味で$X$は可積分である。さらに同じ定義により$\mathbb E[X]=\mathbb E[X^{+}]-\mathbb E[X^{-}]=\sum_{\omega\in\Omega}\bigl(X^{+}(\omega)-X^{-}(\omega)\bigr)\mathbb P(\{\omega\})=\sum_{\omega\in\Omega}X(\omega)\,\mathbb P(\{\omega\})$である。$X^{2}$は確率変数であるから、いま示したことを$X^{2}$へ適用すると$X^{2}$も可積分である。

指示変数については$\mathbf 1_A(\omega)$が$\omega\in A$で$1$、そうでないとき$0$であるから$\mathbb E[\mathbf 1_A]=\sum_{\omega\in\Omega}\mathbf 1_A(\omega)\mathbb P(\{\omega\})=\sum_{\omega\in A}\mathbb P(\{\omega\})=\mathbb P(A)$である。▨

証明.(1)を示す。命題 1.3より$\mathbb E[Y]-\mathbb E[X]=\sum_{\omega\in\Omega}\bigl(Y(\omega)-X(\omega)\bigr)\mathbb P(\{\omega\})$である。右辺の各項は、$Y(\omega)-X(\omega)\ge0$と$\mathbb P(\{\omega\})\ge0$の積であるから非負である。有限個の非負の実数の和は非負であるから$\mathbb E[Y]-\mathbb E[X]\ge0$である。

(2)を示す。 項数$n$についての数学的帰納法（§D2.1 命題 1.2）による。$n=1$のときは§E11.4 命題 1.2を$X=X_1$、$Y=0$、$a=a_1$、$b=0$に対して適用すればよい。$n-1$で主張が成り立つとする。命題 1.3よりすべての確率変数が可積分であるから、§E11.4 命題 1.2を$X=\sum_{i=1}^{n-1}a_iX_i$、$Y=X_n$、$a=1$、$b=a_n$に対して適用することができ$\mathbb E\!\left[\sum_{i=1}^{n}a_iX_i\right]=\mathbb E\!\left[\sum_{i=1}^{n-1}a_iX_i\right]+a_n\mathbb E[X_n]$を得る。帰納法の仮定を第一項へ適用すると主張の等式を得る。▨

証明.$\lvert K\rvert$についての数学的帰納法（§D2.1 命題 1.2）による。

$\lvert K\rvert=0$のとき、$\prod_{i\in\emptyset}S_i$は空写像だけからなる一点集合であり、空積の規約により左辺の被加数は$1$である。したがって左辺は$1$であり、右辺も空積として$1$である。

$\lvert K\rvert=k\ge1$とし、$k-1$の場合に主張が成り立つとする。$j\in K$を一つ取り、$K'=K\setminus\{j\}$と置く。写像$\prod_{i\in K}S_i\longrightarrow\Bigl(\prod_{i\in K'}S_i\Bigr)\times S_j,\qquad \tau\longmapsto(\tau|_{K'},\tau_j)$は全単射である。この全単射で和を書き換え、各項の積を$j$の因子と残りの因子へ分けると$\sum_{\tau\in\prod_{i\in K}S_i}\prod_{i\in K}f_i(\tau_i) =\sum_{s\in S_j}\ \sum_{\sigma\in\prod_{i\in K'}S_i}f_j(s)\prod_{i\in K'}f_i(\sigma_i) =\sum_{s\in S_j}f_j(s)\left(\sum_{\sigma\in\prod_{i\in K'}S_i}\prod_{i\in K'}f_i(\sigma_i)\right)$となる。ここで有限和の入れ替えと分配法則だけを用いた。内側の和へ帰納法の仮定を適用すると、この式は$\left(\sum_{s\in S_j}f_j(s)\right)\prod_{i\in K'}\left(\sum_{s\in S_i}f_i(s)\right)=\prod_{i\in K}\left(\sum_{s\in S_i}f_i(s)\right)$に等しい。▨

証明. (2)を先に示す。$J\subseteq I$と$\sigma\in\{0,1\}^{J}$を取る。$\omega\in C_{\sigma}$であることと、$\omega$が$J$上で$\sigma$に一致し$I\setminus J$上で任意の値を取ることは同値である。したがって写像$\omega\mapsto\omega|_{I\setminus J}$は$C_{\sigma}$から$\{0,1\}^{I\setminus J}$への全単射である。この全単射で和を書き換え、各項の積を$J$の因子と$I\setminus J$の因子へ分けると$\mathbb P_{I,p}(C_{\sigma})=\sum_{\tau\in\{0,1\}^{I\setminus J}}\ \prod_{i\in J}q(\sigma_i)\cdot\prod_{i\in I\setminus J}q(\tau_i) =\left(\prod_{i\in J}q(\sigma_i)\right)\sum_{\tau\in\{0,1\}^{I\setminus J}}\ \prod_{i\in I\setminus J}q(\tau_i)$となる。最後の和へ補題 2.1を$K=I\setminus J$、$S_i=\{0,1\}$、$f_i=q$に対して適用すると、その値は$\prod_{i\in I\setminus J}(q(0)+q(1))=\prod_{i\in I\setminus J}1=1$である。ゆえに$\mathbb P_{I,p}(C_{\sigma})=\prod_{i\in J}q(\sigma_i)$である。$\sigma$がすべて$1$のときこの値は$p^{\lvert J\rvert}$、すべて$0$のときは$(1-p)^{\lvert J\rvert}$である。

(1)を示す。 各$\mathbb P_{I,p}(\{\omega\})$は$[0,1]$の元の有限積であるから非負である。$J=\emptyset$として(2)を適用すると$C_{\sigma}=\Omega_{I,p}$であり、その確率は空積として$1$である。すなわち$\sum_{\omega\in\Omega_{I,p}}\mathbb P_{I,p}(\{\omega\})=1$である。一点集合の確率が非負で総和が$1$であり、事象の確率をその元の一点集合の確率の和で定めたので、$\mathbb P_{I,p}$は有限加法的であり、全体の確率が$1$である。$\Omega_{I,p}$は有限であるから可算加法性は有限加法性に帰着し、$\mathbb P_{I,p}$は確率測度である。

(3)を示す。$k\ge1$とし、相異なる添字$i_1,\dots,i_k\in I$と Borel 集合$B_1,\dots,B_k\subseteq\mathbb R$を取る。座標は$\{0,1\}$の値だけを取るから、事象$\{\omega_{i_r}\in B_r\}$は、$\beta_r=B_r\cap\{0,1\}$と置くと$\{\omega_{i_r}\in\beta_r\}$に等しい。$\beta_r$が空集合である$r$が存在すれば、両辺はいずれも$0$である。$\beta_r=\{0,1\}$である$r$については、その添字に対する条件は制約を課さない。したがって、$\beta_r$が一元集合である添字だけを集めて$J$と置き、$\sigma_{i_r}$をその一元集合の元と定めると$\mathbb P_{I,p}\!\left(\bigcap_{r=1}^{k}\{\omega_{i_r}\in\beta_r\}\right)=\mathbb P_{I,p}(C_{\sigma})=\prod_{i\in J}q(\sigma_i)$である。他方、各$r$について(2)を$J=\{i_r\}$に対して適用すると、$\beta_r$が一元集合のとき$\mathbb P_{I,p}(\omega_{i_r}\in\beta_r)=q(\sigma_{i_r})$、$\beta_r=\{0,1\}$のとき$\mathbb P_{I,p}(\omega_{i_r}\in\beta_r)=1$である。ゆえに$\prod_{r=1}^{k}\mathbb P_{I,p}(\omega_{i_r}\in\beta_r)=\prod_{i\in J}q(\sigma_i)$であり、両者は一致する。§E11.7 命題 1.2より、座標の族は相互独立である。▨

証明. 各$\omega\in\Omega$について$\mathbf 1_{\bigcup_{i=1}^{n}A_i}(\omega)\le\sum_{i=1}^{n}\mathbf 1_{A_i}(\omega)$が成り立つ。実際、左辺は$0$または$1$である。左辺が$1$であるのは$\omega$がいずれかの$A_i$に属する場合であり、そのとき右辺の対応する項が$1$であって他の項は非負であるから、右辺は$1$以上である。左辺が$0$の場合は、右辺が非負であるから不等式が成り立つ。

命題 1.4 (1)を両辺の確率変数へ適用し、続いて命題 1.4 (2)を右辺へ適用すると$\mathbb E\!\left[\mathbf 1_{\bigcup_{i=1}^{n}A_i}\right]\le\sum_{i=1}^{n}\mathbb E[\mathbf 1_{A_i}]$を得る。命題 1.3により両辺の指示変数の期待値を確率へ置き換えると、主張の不等式を得る。

後半を示す。$\sum_{i=1}^{n}\mathbb P(A_i)<1$と仮定すると、いま示した不等式より$\mathbb P(\bigcup_{i=1}^{n}A_i)<1$である。$\mathbb P$は確率測度であるから$\mathbb P\!\left(\bigcap_{i=1}^{n}(\Omega\setminus A_i)\right)=1-\mathbb P\!\left(\bigcup_{i=1}^{n}A_i\right)>0$である。確率が正である事象は空でない。実際、空事象の確率は$0$だからである。ゆえに$\bigcap_{i=1}^{n}(\Omega\setminus A_i)\ne\emptyset$である。▨

証明. すべての$\omega\in\Omega$について$\mathbf 1_{\{X\ge1\}}(\omega)\le X(\omega)$が成り立つ。実際、$X(\omega)\ge1$のときは左辺が$1$で右辺が$1$以上であり、$X(\omega)<1$のときは左辺が$0$で右辺が非負である。この各点の不等式は$X$が非負であることだけから従い、整数値であることを用いていない。

命題 1.4 (1)と命題 1.3より$\mathbb P(X\ge1)=\mathbb E\!\left[\mathbf 1_{\{X\ge1\}}\right]\le\mathbb E[X]<1$である。

ここで$X$が非負整数値であることを用いる。$X(\omega)<1$を満たす$\omega$は$X(\omega)=0$を満たすから、事象$\{X=0\}$は$\{X\ge1\}$の補事象である。ゆえに$\mathbb P(X=0)=1-\mathbb P(X\ge1)>0$である。確率が正である事象は空でないから、$X(\omega)=0$を満たす$\omega\in\Omega$が存在する。整数値であることを用いたのは、この補事象の同定の一か所だけである。▨

証明. 後半の不等式を示す。$\mu=\mathbb E[X]$と置き、背理法による。$\mathbb P(X\ge\mu)=0$と仮定する。$\Omega_{+}=\{\omega\in\Omega:\ \mathbb P(\{\omega\})>0\}$と置く。$\sum_{\omega\in\Omega}\mathbb P(\{\omega\})=1$であるから$\Omega_{+}\ne\emptyset$である。仮定より、$\omega\in\Omega_{+}$ならば$X(\omega)<\mu$である。実際、$X(\omega)\ge\mu$を満たす$\omega\in\Omega_{+}$が存在すれば$\mathbb P(X\ge\mu)\ge\mathbb P(\{\omega\})>0$となって仮定に反する。

命題 1.3より、$\mathbb P(\{\omega\})=0$である項は和へ寄与しないから$\mu=\mathbb E[X]=\sum_{\omega\in\Omega_{+}}X(\omega)\mathbb P(\{\omega\})<\sum_{\omega\in\Omega_{+}}\mu\,\mathbb P(\{\omega\})=\mu\sum_{\omega\in\Omega_{+}}\mathbb P(\{\omega\})=\mu$となる。ここで、$\Omega_{+}$が空でなく各項の重み$\mathbb P(\{\omega\})$が正であるから、狭義の不等号が保たれる。また$\sum_{\omega\in\Omega_{+}}\mathbb P(\{\omega\})=1$を最後の等号で用いた。$\mu<\mu$は矛盾である。ゆえに$\mathbb P(X\ge\mu)>0$であり、確率が正である事象は空でないから$X(\omega_{+})\ge\mu$を満たす$\omega_{+}$が存在する。

前半の不等式は、いま示したことを確率変数$-X$へ適用して得られる。実際命題 1.4 (2)より$\mathbb E[-X]=-\mathbb E[X]=-\mu$であり、$-X\ge-\mu$と$X\le\mu$は同じ事象を定めるから$\mathbb P(X\le\mu)=\mathbb P(-X\ge-\mu)>0$である。▨

証明.$V$を添字集合、$p=1/2$として定義 2.2の確率空間$(\Omega_{V,1/2},2^{\Omega_{V,1/2}},\mathbb P)$を取る。$\omega\in\Omega_{V,1/2}$に対し$A(\omega)=\{v\in V:\ \omega_v=1\},\qquad B(\omega)=\{v\in V:\ \omega_v=0\}$と定めると、$V=A(\omega)\sqcup B(\omega)$は$V$の分割である。辺$e=\{u,v\}\in E$に対し、$e$が横断辺であること、すなわち$\omega_u\ne\omega_v$であることの指示変数を$X_e$と書く。

$\mathbb P(X_e=1)$を計算する。命題 2.3 (2)を$J=\{u,v\}$に対して適用すると、$(\omega_u,\omega_v)$が取る四つの値のそれぞれの確率は$q(\cdot)q(\cdot)=1/4$である。$\omega_u\ne\omega_v$となる値は$(1,0)$と$(0,1)$の二つであり、これらは互いに交わらない事象を定めるから$\mathbb P(X_e=1)=\frac14+\frac14=\frac12$である。命題 1.3より$\mathbb E[X_e]=1/2$である。

横断辺の本数は$X=\sum_{e\in E}X_e$である。命題 1.4 (2)より$\mathbb E[X]=\sum_{e\in E}\mathbb E[X_e]=\frac m2$である。ここで各$X_e$は互いに確率的に独立ではないが、有限項の線形性はいかなる独立性も仮定しない。命題 5.1より$X(\omega_{+})\ge\mathbb E[X]=m/2$を満たす$\omega_{+}$が存在する。この$\omega_{+}$が定める分割$V=A(\omega_{+})\sqcup B(\omega_{+})$の横断辺の本数は$m/2$以上である。▨

証明.命題 1.3により、有限確率空間上の確率変数はすべて二次可積分であるから、§E11.4 定義 2.1の分散と共分散、および§E11.4 命題 2.3の公式を、以下に現れるすべての確率変数へ適用することができる。

(1)を示す。$Z=\sum_{i=1}^{n}a_iX_i$と置く。§E11.4 命題 2.3より$\operatorname{Cov}(Z,Y)=\mathbb E[ZY]-\mathbb E[Z]\mathbb E[Y]$である。$ZY=\sum_{i=1}^{n}a_i(X_iY)$であるから、命題 1.4 (2)を$ZY$と$Z$の双方へ適用すると$\operatorname{Cov}(Z,Y)=\sum_{i=1}^{n}a_i\mathbb E[X_iY]-\left(\sum_{i=1}^{n}a_i\mathbb E[X_i]\right)\mathbb E[Y] =\sum_{i=1}^{n}a_i\bigl(\mathbb E[X_iY]-\mathbb E[X_i]\mathbb E[Y]\bigr)$となる。再び§E11.4 命題 2.3により、括弧の中は$\operatorname{Cov}(X_i,Y)$である。対称性$\operatorname{Cov}(X,Y)=\operatorname{Cov}(Y,X)$は、同じ公式の右辺$\mathbb E[XY]-\mathbb E[X]\mathbb E[Y]$が$X$と$Y$の入れ替えで変わらないことから従う。

(2)を示す。§E11.4 定義 2.1の定義を見比べると、任意の確率変数$Z$について$\operatorname{Var}(Z)=\operatorname{Cov}(Z,Z)$である。$Z=\sum_{i=1}^{n}X_i$に対して(1)を第一変数へ、続いて第二変数へ適用すると$\operatorname{Var}(Z)=\operatorname{Cov}\!\left(\sum_{i=1}^{n}X_i,\ \sum_{j=1}^{n}X_j\right)=\sum_{i=1}^{n}\sum_{j=1}^{n}\operatorname{Cov}(X_i,X_j)$を得る。この二重和を$i=j$の項と$i\ne j$の項へ分ける。$i=j$の項の和は$\sum_{i=1}^{n}\operatorname{Var}(X_i)$である。$i\ne j$の項は、対$\{i,j\}$ごとに$\operatorname{Cov}(X_i,X_j)$と$\operatorname{Cov}(X_j,X_i)$の二つが現れ、対称性よりこの二つは等しい。ゆえに$i\ne j$の項の和は$2\sum_{i<j}\operatorname{Cov}(X_i,X_j)$である。▨

証明.$\mu=\mathbb E[X]>0$と置く。命題 1.3より$X$は二次可積分であるから、§E11.4 系 3.2を確率変数$X$と閾値$t=\mu>0$に対して適用することができ$\mathbb P\bigl(\lvert X-\mu\rvert\ge\mu\bigr)\le\frac{\operatorname{Var}(X)}{\mu^{2}}$を得る。

事象の包含$\{X=0\}\subseteq\{\lvert X-\mu\rvert\ge\mu\}$を確かめる。$X(\omega)=0$ならば$\lvert X(\omega)-\mu\rvert=\lvert-\mu\rvert=\mu$であり、$\mu\ge\mu$が成り立つからである。確率測度は包含について単調であるから$\mathbb P(X=0)\le\mathbb P\bigl(\lvert X-\mu\rvert\ge\mu\bigr)\le\frac{\operatorname{Var}(X)}{\mu^{2}}$である。

この議論は、$X$が整数値であることも非負であることも用いていない。事象の包含に用いたのは、$X(\omega)=0$から$\lvert X(\omega)-\mu\rvert=\mu$が従うことだけであり、この含意は$X$が任意の実数値を取る場合にも成り立つからである。したがって同じ不等式は、$\mathbb E[X]>0$を満たす確率変数$X:\Omega\to\mathbb R$についても成り立つ。有限確率空間上の確率変数はすべて二次可積分であるから（命題 1.3）、§E11.4 系 3.2の適用条件もこの場合に満たされている。▨

証明. 前半。$n$を主張の条件を満たす正の整数とする。$V=\{1,\dots,n\}$を$K_n$の頂点集合、$I$をその辺集合、すなわち$V$の二元部分集合の全体とする。$\lvert I\rvert=\binom n2$である。$p=1/2$として定義 2.2の有限確率空間$(\Omega_{I,1/2},2^{\Omega_{I,1/2}},\mathbb P)$を取る。$\omega\in\Omega_{I,1/2}$は$K_n$の辺集合の塗り分けを表すものとし、$\omega_e=1$を「辺$e$が赤である」、$\omega_e=0$を「辺$e$が青である」と読む。$\Omega_{I,1/2}$の元と$K_n$の辺集合の赤と青への塗り分けは一対一に対応する。