§E16.26ランダムグラフ

証明.主張 (1)を示す。定義 1.1の確率空間は§E16.11 定義 2.2のものそのものであるから、§E16.11 命題 2.3 (3)を適用すればよい。

主張 (2)を示す。$J\subseteq E(\omega)$であることと、すべての$e\in J$について$\omega_e=1$であることは、$E(\omega)=\{e:\ \omega_e=1\}$という定義から同値である。同様に、$J\cap E(\omega)=\emptyset$であることと、すべての$e\in J$について$\omega_e=0$であることは同値である。§E16.11 命題 2.3 (2)をこの$J$に対して適用すると、前者の確率は$p^{\lvert J\rvert}$、後者の確率は$(1-p)^{\lvert J\rvert}$である。▨

証明. 辺の個数。各$e\in I_n$について$Y_e=\mathbf 1_{\{\omega_e=1\}}$と置くと$X_{\mathrm e}=\sum_{e\in I_n}Y_e$である。命題 1.2 (2)を$J=\{e\}$に対して適用すると$\mathbb P_{n,p}(\omega_e=1)=p$であり、§E16.11 命題 1.3より$\mathbb E[Y_e]=p$である。§E16.11 命題 1.4 (2)より$\mathbb E[X_{\mathrm e}]=\sum_{e\in I_n}\mathbb E[Y_e]=\lvert I_n\rvert\,p=\binom n2 p$である。

三角形の個数。$V_n$の三元部分集合$S$に対し、$S$の二元部分集合の全体を$I(S)\subseteq I_n$と書く。$\lvert I(S)\rvert=\binom32=3$である。$S$が三角形をなすことと$I(S)\subseteq E(\omega)$は同値であるから、$Z_S=\mathbf 1_{\{I(S)\subseteq E(\omega)\}}$と置くと$X_{\triangle}=\sum_{S}Z_S$である。ここで和は$V_n$の三元部分集合すべてにわたる。命題 1.2 (2)を$J=I(S)$に対して適用すると$\mathbb E[Z_S]=p^{3}$である。三元部分集合は$\binom n3$個あるから、§E16.11 命題 1.4 (2)より$\mathbb E[X_{\triangle}]=\binom n3p^{3}$である。

孤立点の個数。$v\in V_n$に対し$I(v)=\{e\in I_n:\ v\in e\}$と置く。$V_n$の$v$以外の頂点は$n-1$個あり、それぞれと$v$の対が$I(v)$の元であるから$\lvert I(v)\rvert=n-1$である。$v$が$G(\omega)$の孤立点であることと$I(v)\cap E(\omega)=\emptyset$は同値であるから、$W_v=\mathbf 1_{\{I(v)\cap E(\omega)=\emptyset\}}$と置くと$X_0=\sum_{v\in V_n}W_v$である。命題 1.2を$J=I(v)$に対して適用すると$\mathbb E[W_v]=(1-p)^{n-1}$である。頂点は$n$個あるから$\mathbb E[X_0]=n(1-p)^{n-1}$である。

三つのいずれについても、指示変数どうしは頂点や辺を共有しており確率的に独立ではないが、§E16.11 命題 1.4 (2)ではいかなる独立性も仮定されない。▨

証明.§D1.24 定義 1.1により$\exp(x)=\sum_{k=0}^{\infty}x^{k}/k!$であり、§D1.24 命題 1.2によりこの級数はすべての実数$x$で絶対収束する。とくに$\exp(0)=1$である。また§D1.24 定理 2.1より$\exp(x)\exp(-x)=\exp(0)=1$であり、§D1.24 命題 3.1より$\exp$は正の値だけを取るから$\exp(-x)=\frac{1}{\exp(x)}$である。

極限における不等号の保存。以下の二箇所で用いるので、次の主張を先に示す。実数の数列$(a_m)_{m\ge1}$と実数$c$について、すべての整数$m\ge1$が$a_m\le c$を満たし、かつ$(a_m)_{m\ge1}$が実数$a$へ収束するならば$a\le c$である。実際、$a>c$と仮定し$\varepsilon=a-c>0$と置くと、§D1.5 定義 1.1により整数$M$が存在して、$m\ge M$を満たすすべての整数$m$について$\lvert a_m-a\rvert<\varepsilon$が成り立つ。この$m$については$a_m>a-\varepsilon=c$となり、すべての整数$m\ge1$が$a_m\le c$を満たすことに反する。ゆえに$a\le c$である。同じ主張は§B1.7 定理 3.3にも述べられている。ただし先行記事ではその証明が与えられていないので、本記事ではこの主張を上の議論によって自給する。

準備。$0\le u<1$に対し$\exp(u)\le\dfrac{1}{1-u}$を示す。$m\ge1$を整数とすると、$k\ge0$について$k!\ge1$かつ$u^{k}\ge0$であるから$\sum_{k=0}^{m}\frac{u^{k}}{k!}\le\sum_{k=0}^{m}u^{k}$である。右辺は初項$1$、公比$u$の有限等比和であり、$u\ne1$であるから§B1.1 公式 2.4より$\dfrac{1-u^{m+1}}{1-u}$に等しい。$0\le u<1$より$u^{m+1}\ge0$であるから、この値は$\dfrac{1}{1-u}$以下である。左辺は$m\to\infty$で$\exp(u)$へ収束し、右辺$\dfrac{1}{1-u}$は$m$によらない定数であるから、冒頭で示した極限における不等号の保存を$a_m=\sum_{k=0}^{m}u^{k}/k!$、$c=\dfrac{1}{1-u}$に対して適用して$\exp(u)\le\dfrac{1}{1-u}$を得る。

主張 (1)を示す。 三つの場合に分ける。$x\ge0$のとき、級数の各項は非負であるから、第$0$項と第$1$項だけを残して$\exp(x)\ge1+x$を得る。$x\le-1$のとき、$1+x\le0$であり$\exp(x)>0$であるから主張は成り立つ。$-1<x<0$のとき、$u=-x$と置くと$0<u<1$である。準備より$\exp(u)\le\dfrac{1}{1-u}$であり、両辺は正であるから逆数を取って不等号の向きを変えると$\exp(x)=\exp(-u)=\frac{1}{\exp(u)}\ge1-u=1+x$である。

主張 (2)を示す。$u\ge0$に対し主張 (1)を$x=-u$に適用すると$\exp(-u)\ge1-u$である。

主張 (3)を示す。$0\le u<1$とし、$t=\dfrac{u}{1-u}$と置く。$1-u>0$かつ$u\ge0$より$t\ge0$である。主張 (1)を$x=t$に適用すると$\exp(t)\ge1+t=1+\frac{u}{1-u}=\frac{1-u+u}{1-u}=\frac{1}{1-u}$である。両辺は正であるから逆数を取って$\exp(-t)\le1-u$を得る。

主張 (4)を示す。$s>0$とし$x=\log s$と置く。§D1.24 定義 3.2より$\exp(x)=s$である。主張 (1)より$s=\exp(x)\ge1+x=1+\log s$であり、移項して$\log s\le s-1$を得る。

整数$n\ge1$に対し、$\sqrt n>0$であるから§D1.24 定理 3.4を$a=b=\sqrt n$に対して適用して$\log n=\log(\sqrt n\cdot\sqrt n)=2\log\sqrt n$である。いま示したことを$s=\sqrt n$に適用すると$\log\sqrt n\le\sqrt n-1<\sqrt n$であるから$\log n<2\sqrt n$である。また、$s=n$に適用すると$\log n\le n-1<n$であり、$n>0$で割って$\log n/n<1$を得る。

主張 (5)を示す。$k\ge1$に対し$k!\ge2^{k-1}$が成り立つ。実際、$k=1$では$1\ge1$であり、$k$で成り立つとすると$(k+1)!=(k+1)k!\ge2\cdot2^{k-1}=2^{k}$である。ゆえに$m\ge1$に対し$\sum_{k=0}^{m}\frac1{k!}\le1+\sum_{k=1}^{m}\frac{1}{2^{k-1}}=1+\frac{1-2^{-m}}{1-1/2}\le1+2=3$である。ここで§B1.1 公式 2.4を初項$1$、公比$1/2$に対して用いた。左辺は$m\to\infty$で$\exp(1)$へ収束し、右辺$3$は$m$によらない定数であるから、冒頭で示した極限における不等号の保存を$a_m=\sum_{k=0}^{m}1/k!$、$c=3$に対して適用して$\exp(1)\le3$を得る。$\exp(1/2)>0$であり§D1.24 定理 2.1より$\exp(1/2)^{2}=\exp(1)\le3<4=2^{2}$であるから$\exp(1/2)<2$である。▨

証明.命題 2.1の証明の記号を用い、$X_0=\sum_{v\in V_n}W_v$とする。ここで$W_v=\mathbf 1_{A_v}$であり、$A_v=\{\omega:\ I(v)\cap E(\omega)=\emptyset\}$は「$v$が孤立点である」という事象である。$\mathbb P_{n,p}(A_v)=(1-p)^{n-1}=q$である。

各項の分散。$W_v^{2}=W_v$であるから§E11.4 命題 2.3より$\operatorname{Var}(W_v)=\mathbb E[W_v^{2}]-\mathbb E[W_v]^{2}=q-q^{2}=q(1-q)$である。

共分散。相異なる$u,v\in V_n$を取る。$W_uW_v=\mathbf 1_{A_u\cap A_v}$であり、$A_u\cap A_v$は$I(u)\cup I(v)$のすべての座標が$0$である事象である。$\lvert I(u)\rvert=\lvert I(v)\rvert=n-1$であり、$I(u)\cap I(v)=\{\{u,v\}\}$は一元集合であるから$\lvert I(u)\cup I(v)\rvert=(n-1)+(n-1)-1=2n-3$である。$n\ge2$より$2n-3\ge1$である。命題 1.2を$J=I(u)\cup I(v)$に対して適用すると$\mathbb P_{n,p}(A_u\cap A_v)=(1-p)^{2n-3}$である。ゆえに§E11.4 命題 2.3より$\operatorname{Cov}(W_u,W_v)=(1-p)^{2n-3}-q^{2}=(1-p)^{2n-3}-(1-p)^{2n-2}=(1-p)^{2n-3}\bigl(1-(1-p)\bigr)=p\,(1-p)^{2n-3}$である。

展開式を適用する。§E16.11 命題 6.1 (2)より$\operatorname{Var}(X_0)=\sum_{v\in V_n}\operatorname{Var}(W_v)+2\sum_{u<v}\operatorname{Cov}(W_u,W_v) =nq(1-q)+2\binom n2\,p\,(1-p)^{2n-3}$であり、$2\binom n2=n(n-1)$であるから主張の等式を得る。

比の評価。$p>0$とする。$1-p>0$より$q>0$であり、$\mathbb E[X_0]=nq>0$である。$\mathbb E[X_0]^{2}=n^{2}q^{2}$で割ると$\frac{\operatorname{Var}(X_0)}{\mathbb E[X_0]^{2}} =\frac{nq(1-q)}{n^{2}q^{2}}+\frac{n(n-1)p(1-p)^{2n-3}}{n^{2}q^{2}} =\frac{1-q}{nq}+\frac{(n-1)p}{n}\cdot\frac{(1-p)^{2n-3}}{(1-p)^{2n-2}}$である。ここで$q^{2}=(1-p)^{2n-2}$を用いた。最後の分数は$\dfrac{1}{1-p}$に等しい。$0<q\le1$より$1-q\le1$であり、$\dfrac{n-1}{n}\le1$であるから$\frac{\operatorname{Var}(X_0)}{\mathbb E[X_0]^{2}}\le\frac{1}{nq}+\frac{p}{1-p}$を得る。▨

証明.$N_1$を$N_1\ge16(1+\varepsilon)^{2}$かつ$N_1\ge2$を満たす整数とし、以下$n\ge N_1$とする。

まず$p_n\le1/2$を示す。補題 3.1 (4)より$\log n<2\sqrt n$であるから$(1+\varepsilon)\frac{\log n}{n}<(1+\varepsilon)\frac{2\sqrt n}{n}=\frac{2(1+\varepsilon)}{\sqrt n}$である。$n\ge16(1+\varepsilon)^{2}$より$\sqrt n\ge4(1+\varepsilon)$であるから、右辺は$\dfrac{2(1+\varepsilon)}{4(1+\varepsilon)}=\dfrac12$以下である。ゆえに$(1+\varepsilon)\log n/n<1/2<1$であり、最小値は第一項で達成されて$p_n=(1+\varepsilon)\log n/n\le1/2$である。また$n\ge2$より$\log n>0$であるから$p_n>0$である。

Markov の不等式を適用する。$X_0$は非負確率変数であるから、§E11.4 定理 3.1を$a=1$に対して適用すると$\mathbb P_{n}(X_0\ge1)\le\mathbb E[X_0]$である。命題 2.1より$\mathbb E[X_0]=n(1-p_n)^{n-1}$である。

期待値を上から抑える。補題 3.1 (2)より$0\le1-p_n\le\exp(-p_n)$である。$t\mapsto t^{n-1}$は$[0,\infty)$上で単調非減少であるから$(1-p_n)^{n-1}\le\bigl(\exp(-p_n)\bigr)^{n-1}=\exp\bigl(-(n-1)p_n\bigr)$である。最後の等号は§D1.24 定理 2.1を$n-1$回適用して得られる。ここで$(n-1)p_n=n\,p_n-p_n=(1+\varepsilon)\log n-p_n\ge(1+\varepsilon)\log n-\frac12$であるから、§D1.24 命題 3.1の単調増加性より$\exp\bigl(-(n-1)p_n\bigr)\le\exp\!\left(-(1+\varepsilon)\log n+\frac12\right)$である。§D1.24 定義 3.2より$n=\exp(\log n)$であるから、§D1.24 定理 2.1を用いて$\mathbb E[X_0]\le\exp(\log n)\exp\!\left(-(1+\varepsilon)\log n+\frac12\right)=\exp\!\left(\frac12\right)\exp\bigl(-\varepsilon\log n\bigr)$を得る。補題 3.1 (5)より$\exp(1/2)<2$であり、補題 3.1 (1)より$\exp(\varepsilon\log n)\ge1+\varepsilon\log n$であるから$\mathbb E[X_0]\le\frac{2}{1+\varepsilon\log n}$である。

極限を確かめる。$\delta>0$を任意に取る。$\log$は§D1.24 命題 3.1より狭義単調増加な全単射の逆であるから狭義単調増加である。したがって、整数$N$を$N\ge N_1,\qquad N>\exp\!\left(\frac{2}{\varepsilon\delta}\right)$を満たすように取ると、$n\ge N$のとき$\log n>2/(\varepsilon\delta)$であり$\mathbb P_{n}(X_0\ge1)\le\frac{2}{1+\varepsilon\log n}<\frac{2}{\varepsilon\log n}<\frac{2}{\varepsilon}\cdot\frac{\varepsilon\delta}{2}=\delta$である。$\delta>0$は任意であったから$\lim_{n\to\infty}\mathbb P_{n}(X_0\ge1)=0$である。事象$\{X_0=0\}$は$\{X_0\ge1\}$の補事象であるから$\mathbb P_n(X_0=0)\to1$であり、定義 5.1の意味で孤立点をもたないことは高い確率で成り立つ。▨

証明.$N_2$を$N_2\ge16/\varepsilon^{2}$かつ$N_2\ge2$を満たす整数とし、以下$n\ge N_2$とする。

$p_n$の範囲。主張文で確かめたとおり$p_n\in(0,1)$である。さらに補題 3.1 (4)より$\log n<2\sqrt n$であり、$1-\varepsilon<1$であるから$p_n<\frac{2}{\sqrt n}$である。$n\ge16/\varepsilon^{2}$より$\sqrt n\ge4/\varepsilon$であるから$p_n<\varepsilon/2$である。$\varepsilon<1$より$p_n<1/2$でもある。

$q_n$を下から抑える。$q_n=(1-p_n)^{n-1}$と置く。$0<p_n<1$であるから補題 3.1 (3)より$1-p_n\ge\exp\!\left(-\frac{p_n}{1-p_n}\right)>0$である。$t\mapsto t^{n-1}$は$[0,\infty)$上で単調非減少であるから、§D1.24 定理 2.1を用いて$q_n\ge\exp\!\left(-\frac{(n-1)p_n}{1-p_n}\right)$である。ここで$(n-1)p_n<np_n=(1-\varepsilon)\log n$であり、$p_n<\varepsilon/2$より$1-p_n>1-\varepsilon/2>0$であるから$\frac{(n-1)p_n}{1-p_n}<\frac{(1-\varepsilon)\log n}{1-\varepsilon/2}$である。さらに$\frac{1-\varepsilon}{1-\varepsilon/2}\le1-\frac\varepsilon2$が成り立つ。実際、$1-\varepsilon/2>0$であるから両辺にこれを掛けると$1-\varepsilon\le\left(1-\dfrac\varepsilon2\right)^{2}=1-\varepsilon+\dfrac{\varepsilon^{2}}4$となり、これは$\varepsilon^{2}/4\ge0$と同値だからである。ゆえに$\frac{(n-1)p_n}{1-p_n}<\left(1-\frac\varepsilon2\right)\log n$であり、§D1.24 命題 3.1の単調増加性より$q_n\ge\exp\!\left(-\left(1-\frac\varepsilon2\right)\log n\right)$である。§D1.24 定義 3.2と§D1.24 定理 2.1より$n\,q_n\ge\exp(\log n)\exp\!\left(-\left(1-\frac\varepsilon2\right)\log n\right)=\exp\!\left(\frac\varepsilon2\log n\right)\ge1+\frac\varepsilon2\log n$である。最後の不等号は補題 3.1 (1)による。

第二モーメント法を適用する。$X_0$は非負整数値であり$\mathbb E[X_0]=nq_n>0$であるから、§E16.11 命題 6.2を適用することができ、命題 4.1とあわせて$\mathbb P_{n}(X_0=0)\le\frac{\operatorname{Var}(X_0)}{\mathbb E[X_0]^{2}}\le\frac{1}{nq_n}+\frac{p_n}{1-p_n}$を得る。第一項は上で示した評価より$\dfrac{1}{1+\frac\varepsilon2\log n}$以下である。第二項は、$p_n<1/2$より$1-p_n>1/2$であるから$2p_n$以下であり、$p_n<2/\sqrt n$より$\dfrac{4}{\sqrt n}$以下である。ゆえに$\mathbb P_{n}(X_0=0)\le\frac{1}{1+\frac\varepsilon2\log n}+\frac{4}{\sqrt n}$である。

極限を確かめる。$\delta>0$を任意に取る。整数$N$を$N\ge N_2,\qquad N>\exp\!\left(\frac{4}{\varepsilon\delta}\right),\qquad N>\frac{64}{\delta^{2}}$を満たすように取る。$n\ge N$のとき、$\log$の狭義単調増加性より$\log n>4/(\varepsilon\delta)$であるから$\frac{1}{1+\frac\varepsilon2\log n}<\frac{1}{\frac\varepsilon2\log n}<\frac2\varepsilon\cdot\frac{\varepsilon\delta}4=\frac\delta2$であり、$n>64/\delta^{2}$より$\sqrt n>8/\delta$であるから$\dfrac{4}{\sqrt n}<\dfrac\delta2$である。あわせて$\mathbb P_{n}(X_0=0)<\delta$である。$\delta>0$は任意であったから$\lim_{n\to\infty}\mathbb P_{n}(X_0=0)=0$であり、補事象について$\mathbb P_n(X_0\ge1)\to1$である。▨