§E13.27乱択アルゴリズム

証明.(1)を示す。$k$についての数学的帰納法（§D2.1 命題 1.2）による。

$k=1$のとき、$C=B_1$であり$\mathbb P_0^{(1)}(B_1)=\sum_{\rho_1\in B_1}\mathbb P_0(\{\rho_1\})=\mathbb P_0(B_1)$である。

$k\ge2$とし、$k-1$で主張が成り立つとする。写像$\rho\mapsto((\rho_1,\dots,\rho_{k-1}),\rho_k)$は$\Omega_0^{k}$から$\Omega_0^{k-1}\times\Omega_0$への全単射であり、$C$を$C'\times B_k$へ写す。ここで$C'=\{\sigma\in\Omega_0^{k-1}:\ \sigma_i\in B_i\ (i=1,\dots,k-1)\}$である。この全単射で和を書き換え、各項の積を最後の因子と残りの因子へ分けると$\mathbb P_0^{(k)}(C)=\sum_{\sigma\in C'}\ \sum_{\rho_k\in B_k}\left(\prod_{i=1}^{k-1}\mathbb P_0(\{\sigma_i\})\right)\mathbb P_0(\{\rho_k\}) =\left(\sum_{\sigma\in C'}\prod_{i=1}^{k-1}\mathbb P_0(\{\sigma_i\})\right)\left(\sum_{\rho_k\in B_k}\mathbb P_0(\{\rho_k\})\right)$となる。ここでは有限和の入れ替えと分配法則だけを用いた。第一の因子は$\mathbb P_0^{(k-1)}(C')$であり、帰納法の仮定より$\prod_{i=1}^{k-1}\mathbb P_0(B_i)$に等しい。第二の因子は$\mathbb P_0(B_k)$である。ゆえに主張の等式を得る。

(2)を示す。 各$\mathbb P_0^{(k)}(\{\rho\})$は非負実数の有限積であるから非負である。(1)を$B_1=\dots=B_k=\Omega_0$に対して適用すると$C=\Omega_0^{k}$であり、$\mathbb P_0^{(k)}(\Omega_0^{k})=\prod_{i=1}^{k}\mathbb P_0(\Omega_0)=1$である。事象の確率をその元の一点集合の確率の和で定めたので$\mathbb P_0^{(k)}$は有限加法的であり、$\Omega_0^{k}$が有限集合であるから可算加法性は有限加法性に帰着する。ゆえに$\mathbb P_0^{(k)}$は確率測度である。

(3)を示す。$\Omega_0$の元は実数とは限らないので、§E11.7 定義 1.1 (2)、すなわち部分シグマ加法族の族の相互独立性の形で確かめる。第$i$射影$\pi_i$が生成する部分シグマ加法族は$\mathcal G_i=\{\pi_i^{-1}(B):\ B\subseteq\Omega_0\}$である。$\Omega_0^{k}$のすべての部分集合が事象であるから$\mathcal G_i\subseteq2^{\Omega_0^{k}}$であり、$\mathcal G_i$は逆像を取る操作が合併・補集合と可換であることからシグマ加法族である。

$j\ge1$とし、相異なる添字$i_1,\dots,i_j\in\{1,\dots,k\}$と$B_{i_1},\dots,B_{i_j}\subseteq\Omega_0$を取る。残りの添字$i$については$B_i=\Omega_0$と置くと$\bigcap_{r=1}^{j}\pi_{i_r}^{-1}(B_{i_r})=\{\rho:\ \rho_i\in B_i\ (i=1,\dots,k)\}$であるから、(1)より、この事象の確率は$\prod_{i=1}^{k}\mathbb P_0(B_i)=\prod_{r=1}^{j}\mathbb P_0(B_{i_r})$である。ここで$\mathbb P_0(\Omega_0)=1$を用いた。他方、(1)を一つの添字に対して適用すると$\mathbb P_0^{(k)}(\pi_{i_r}^{-1}(B_{i_r}))=\mathbb P_0(B_{i_r})$であるから、両者は一致する。ゆえに射影の族は相互独立である。▨

証明.(2)を先に示す。。$j\ge0$を整数とし、$q=1-\theta$と置く。$\theta=1$のときは$q=0$であり、$\mathbb P_{\theta}(\{1\})=1$、$k\ge2$で$\mathbb P_{\theta}(\{k\})=0$である。したがって$j=0$では$\mathbb P_{\theta}(N>0)=1=0^{0}$、$j\ge1$では$\mathbb P_{\theta}(N>j)=0=0^{j}$であり、いずれも主張の形になる。ここで$0^{0}=1$という規約を用いた。

$\theta\in(0,1)$のとき$q\in(0,1)$である。$k$を$k=j+i$（$i\ge1$）と書き換えると$\mathbb P_{\theta}(N>j)=\sum_{k=j+1}^{\infty}q^{k-1}\theta=\sum_{i=1}^{\infty}q^{\,j+i-1}\theta=\theta q^{j}\sum_{i=1}^{\infty}q^{\,i-1}$である。§B1.9 定理 4.1を初項$1$、公比$q$に対して適用すると、最後の和は$\dfrac{1}{1-q}=\dfrac1\theta$である。ゆえに$\mathbb P_{\theta}(N>j)=\theta q^{j}\cdot\dfrac1\theta=q^{j}$である。

(1)を示す。 各点の確率は非負である。(2)を$j=0$に対して適用すると$\mathbb P_{\theta}(\Omega_{\theta})=\mathbb P_{\theta}(N>0)=1$である。また$\mathbb P_{\theta}(\emptyset)=0$である。

可算加法性を確かめる。$C_1,C_2,\dots$を二つずつ交わらない事象とし、$C=\bigcup_{l\ge1}C_l$と置く。

第一に、二つの量をそれぞれ上限として書き直す。項がすべて非負である族の総和は、その族の有限部分族についての和の全体の上限に等しい。したがって$\mathbb P_{\theta}(C)$は、集合$\mathcal S=\left\{\textstyle\sum_{k\in F}\mathbb P_{\theta}(\{k\})\ :\ F\subseteq C,\ F\ \text{は有限}\right\}$の上限である。同じ理由を二重に適用すると、$\sum_{l\ge1}\mathbb P_{\theta}(C_l)$は、集合$\mathcal T=\left\{\textstyle\sum_{i=1}^{r}\sum_{k\in F_i}\mathbb P_{\theta}(\{k\})\ :\ r\ge0,\ l_1<\dots<l_r,\ F_i\subseteq C_{l_i}\ \text{は有限}\right\}$の上限である。

第二に、$\mathcal S=\mathcal T$を示す。$F\subseteq C$を有限集合とする。$C_l$が二つずつ交わらないので、$F$の各元はちょうど一つの$C_l$に属し、$F$は$F\cap C_l$たちの二つずつ交わらない合併へ一意に分解される。$F$は有限であるから$F\cap C_l\ne\emptyset$となる$l$は有限個であり、それらを$l_1<\dots<l_r$、$F_i=F\cap C_{l_i}$と置くと$\sum_{k\in F}\mathbb P_{\theta}(\{k\})=\sum_{i=1}^{r}\sum_{k\in F_i}\mathbb P_{\theta}(\{k\})$である。ゆえに$\mathcal S\subseteq\mathcal T$である。逆に、$l_1<\dots<l_r$と有限集合$F_i\subseteq C_{l_i}$が与えられたとき、$F=\bigcup_{i=1}^{r}F_i$は$C$の有限部分集合であり、$F_i$たちは二つずつ交わらないから$\sum_{i=1}^{r}\sum_{k\in F_i}\mathbb P_{\theta}(\{k\})=\sum_{k\in F}\mathbb P_{\theta}(\{k\})$である。ゆえに$\mathcal T\subseteq\mathcal S$である。

二つの集合が一致するので上限も一致し、$\mathbb P_{\theta}(C)=\sum_{l\ge1}\mathbb P_{\theta}(C_l)$である。したがって$\mathbb P_{\theta}$は§E9.2 定義 1.1の意味の測度であり、全体の確率が$1$であるから確率測度である。

(3)を示す。命題 2.2 (1)を$B_1=\dots=B_j=\Omega_0\setminus B$に対して適用すると、最初の$j$回がすべて失敗する事象の確率は$\mathbb P_0(\Omega_0\setminus B)^{j}=(1-\theta)^{j}$である。▨

証明.$q=1-\theta$と置く。$\theta\in(0,1]$より$q\in[0,1)$である。整数$m\ge1$に対し$N_m=N\cdot\mathbf 1_{\{1,\dots,m\}}$と定める。$N_m$は値$0,1,\dots,m$しか取らない非負単関数である。§E9.6 命題 1.2を、$\Omega_{\theta}$の互いに交わらない分割$\{1\},\{2\},\dots,\{m\},\{m+1,m+2,\dots\}$と係数$1,2,\dots,m,0$に対して適用すると$\int_{\Omega_{\theta}}N_m\,d\mathbb P_{\theta}=\sum_{k=1}^{m}k\,\mathbb P_{\theta}(\{k\})=\sum_{k=1}^{m}k\,q^{k-1}\theta$である。ここで、この分割と係数により定められる関数はちょうど$N_m$であって$N$ではないことに注意する。$N$は$k>m$でも値$k$を取るからである。

各点$k\in\Omega_{\theta}$について、$m\le m'$ならば$N_m(k)\le N_{m'}(k)$であり、$m\ge k$のとき$N_m(k)=k=N(k)$である。したがって$(N_m)_{m\ge1}$は各点で単調非減少であり、その上限は$N$である。§E9.7 定理 1.1を適用すると$\mathbb E[N]=\int_{\Omega_{\theta}}N\,d\mathbb P_{\theta}=\lim_{m\to\infty}\sum_{k=1}^{m}k\,q^{k-1}\theta$である。ここまでの議論は$\theta\in(0,1]$の全体について成り立ち、$\theta=1$を除外していない。

級数の値を求める（$\theta=1$の場合）。$q=0$である。$k=1$の項は$1\cdot q^{0}\cdot\theta=1$であり（$0^{0}=1$という命題 4.2の証明と同じ規約による）、$k\ge2$の項は$q^{k-1}=0$であるから$0$である。ゆえにすべての$m\ge1$について部分和は$1$に等しく、$\mathbb E[N]=1=1/\theta$である。

級数の値を求める（$\theta\in(0,1)$の場合）。$q\in(0,1)$である。上の極限は$\theta\sum_{k=1}^{\infty}kq^{k-1}$と書くことができる。§E11.5 補題 1.1より$\displaystyle\sum_{k=0}^{\infty}kq^{k}=\frac{q}{(1-q)^{2}}=\frac{q}{\theta^{2}}$である。左辺の$k=0$の項は$0$であるから$\sum_{k=1}^{\infty}kq^{k}=q/\theta^{2}$であり、各部分和を$q>0$で割って極限を取ると$\sum_{k=1}^{\infty}kq^{k-1}=\frac{1}{\theta^{2}}$である。ゆえに$\mathbb E[N]=\theta\cdot\dfrac{1}{\theta^{2}}=\dfrac1\theta$である。

いずれの場合も$\mathbb E[N]=1/\theta$は有限であるから、§E11.4 定義 1.1の意味で$N$は可積分である。

総費用。$cN$は可積分であるから、§E11.4 命題 1.2を$X=N$、$Y=0$、$a=c$、$b=0$に対して適用して$\mathbb E[cN]=c\mathbb E[N]=c/\theta$である。仮定より各点で$0\le S\le cN$であり、$S$と$cN$はいずれも非負の値を取る確率変数であるから、§E9.6 命題 2.2を$f=S$、$g=cN$に対して適用して$\mathbb E[S]\le\mathbb E[cN]=c/\theta$である。とくに$\mathbb E[S]$は有限であるから、$S$は§E11.4 定義 1.1の意味で可積分である。▨

証明.(1)を示す。$x\notin L$とする。定義 3.1 条件 (a)より、すべての$r\in R$について$A(x,r)=0$である。ゆえに$\rho\in R^{k}$に対し$A(x,\rho_i)=0$が各$i$で成り立ち、その最大値も$0$である。

(2)を示す。$x\in L$とする。$A$の出力は$0$または$1$であるから、$A^{(k)}(x,\rho)=0$であることと、すべての$i$について$A(x,\rho_i)=0$であることは同値である。$B=\{r\in R:\ A(x,r)=0\}$と置くと$\bigl\{\rho\in R^{k}:\ A^{(k)}(x,\rho)=0\bigr\}=\{\rho:\ \rho_i\in B\ (i=1,\dots,k)\}$である。命題 2.2 (1)を$B_1=\dots=B_k=B$に対して適用すると$\mathbb P_R^{(k)}\bigl(A^{(k)}(x,\cdot)=0\bigr)=\mathbb P_R(B)^{k}$である。定義 3.1 条件 (b)より$\mathbb P_R(A(x,\cdot)=1)\ge\delta$であり、$B$はその補事象であるから$\mathbb P_R(B)\le1-\delta$である。$0\le\mathbb P_R(B)\le1-\delta$であり$t\mapsto t^{k}$は$[0,\infty)$上で単調非減少であるから$\mathbb P_R(B)^{k}\le(1-\delta)^{k}$である。

(1)とあわせると、$A^{(k)}$は$x\notin L$で決して$1$を出力せず、$x\in L$で$1$を出力する確率が$1-(1-\delta)^{k}$以上であるから、成功確率$1-(1-\delta)^{k}$の一側誤りアルゴリズムである。

(3)を示す。$\delta=1$のときは$1-\delta=0$であり、$k=1$で$(1-\delta)^{1}=0\le\eta$である。$\delta\in(0,1)$のときは$0<1-\delta<1$であるから、§B1.7 定理 2.1 (3)より$(1-\delta)^{k}\to0$（$k\to\infty$）である。したがって、$\eta>0$に対して整数$k$が存在して$(1-\delta)^{k}\le\eta$が成り立つ。この$k$に対し(2)より誤り確率は$\eta$以下である。

(4)を示す。$M=\max_{r\in R}T(x,r)$と置く。$R$は空でない有限集合であるからこの最大値は定まる。各$i$について$T(x,\rho_i)\le M$であるから、$k$個の和は$kM$以下である。▨