確率分布からの標本生成 | 数値解析 I

1 一般化逆関数

定義 1.1. $\mu$ を $\R$ 上の Borel 確率測度とし、 $F(x):=\mu((-\infty,x])$ $(x\in\R)$ と置く。 $F$ は確率空間 $(\R,\mathcal B(\R),\mu)$ 上の恒等写像の分布関数であるから、§E11.3 命題 2.2 (1)により非減少であり、§E11.3 命題 2.2 (3)により $\lim_{x\to-\infty}F(x)=0$ 、 $\lim_{x\to\infty}F(x)=1$ である。 $0<u<1$ とすると、 $u<1$ であるから $F(x)\ge u$ を満たす $x\in\R$ が存在し、 $u>0$ であるから $F(x_0)<u$ を満たす $x_0\in\R$ が存在して、 $x\le x_0$ ならば $F(x)\le F(x_0)<u$ である。したがって集合 $\{x\in\R\mid F(x)\ge u\}$ は空でなく、下に有界である。

Q_F(u):=\inf\{x\in\R\mid F(x)\ge u\}\qquad(0<u<1)

で定まる写像 $Q_F\colon(0,1)\to\R$ を $F$ の一般化逆関数 (generalized inverse) という。

定理 1.2. $\mu$ を $\R$ 上の Borel 確率測度、 $F(x):=\mu((-\infty,x])$ $(x\in\R)$ とし、 $Q_F$ を $F$ の一般化逆関数とする。

$u\in(0,1)$ と $x\in\R$ に対して、 $Q_F(u)\le x$ であることと $u\le F(x)$ であることは同値である。特に $F(Q_F(u))\ge u$ である。
$Q_F$ は非減少であり、Borel 可測である。
$(\Omega,\mathcal F,P)$ を確率空間とし、 $U$ を $(0,1)$ に値をとり一様分布 $U[0,1]$ に従う確率変数とする。このとき $X:=Q_F(U)$ は確率変数であり、 $X$ の分布は $\mu$ である。

証明. $u\in(0,1)$ とし、 $S_u:=\{x\in\R\mid F(x)\ge u\}$ と置く。§E11.3 命題 2.2 (1)により、 $x\in S_u$ かつ $x\le x'$ ならば $x'\in S_u$ である。

(1)を示す。 $u\le F(x)$ ならば $x\in S_u$ であるから、 $Q_F(u)=\inf S_u\le x$ である。各 $n\in\NN$ に対して、下限の定義により $y_n<Q_F(u)+1/n$ を満たす $y_n\in S_u$ が存在するから、 $Q_F(u)+1/n\in S_u$ である。§E11.3 命題 2.2 (2)により $F(Q_F(u))=\lim_{n\to\infty}F(Q_F(u)+1/n)\ge u$ である。したがって、 $Q_F(u)\le x$ ならば $F(x)\ge F(Q_F(u))\ge u$ である。

(2)を示す。 $0<u\le v<1$ ならば $S_v\subset S_u$ であるから、 $Q_F(u)\le Q_F(v)$ である。 $x\in\R$ に対して、(1)により

Q_F^{-1}((-\infty,x])=\{u\in(0,1)\mid u\le F(x)\}=(0,1)\cap(0,F(x)]

であり、右辺は区間であるから Borel 集合である。 $Q_F^{-1}(B)$ が Borel 集合となる $B\subset\R$ の全体は、逆像が補集合と可算和を保つことからシグマ加法族をなし、すべての左半直線を含む。§E9.1 命題 3.3により、このシグマ加法族は $\mathcal B(\R)$ を含む。

(3)を示す。 $U$ は可測であり、 $Q_F$ は Borel 可測であるから、 $X=Q_F\circ U$ は確率変数である。 $U[0,1]$ の密度を積分すると、 $0\le t\le1$ に対して $P(U\le t)=t$ である。 $U$ は $(0,1)$ に値をとるから、(1)により各 $x\in\R$ に対して $\{X\le x\}=\{U\le F(x)\}$ であり、 $0\le F(x)\le1$ から $P(X\le x)=F(x)=\mu((-\infty,x])$ である。§E11.3 定理 2.3により $X$ の分布は $\mu$ である。▨

例 1.3. $\nu$ を一様分布 $U[1,2]$ とし、 $\mu:=\frac12\delta_0+\frac12\nu$ 、 $F(x):=\mu((-\infty,x])$ と置く。

F(x)=\begin{cases}0&(x<0),\\ 1/2&(0\le x<1),\\ x/2&(1\le x<2),\\ 1&(x\ge2)\end{cases}

であり、 $F$ は $0$ で跳び、 $[0,1)$ で定数である。 $0<u\le1/2$ ならば、 $F(0)\ge u$ であり $x<0$ で $F(x)=0<u$ であるから、 $Q_F(u)=0$ である。 $1/2<u<1$ ならば、 $F(x)\ge u$ は $x\ge2u$ と同値であるから、 $Q_F(u)=2u$ である。 $\mu$ の原子 $0$ は $Q_F$ が定数となる区間 $(0,1/2]$ に対応し、 $F$ が定数である区間 $[0,1)$ は $Q_F$ の $u=1/2$ における跳び（値 $0$ から右極限 $1$ へ）に対応する。 $F$ は連続でも狭義単調でもないので逆写像をもたないが、定理 1.2 (3)により、 $(0,1)$ に値をとり $U[0,1]$ に従う $U$ に対して $Q_F(U)$ の分布は $\mu$ であり、 $P(Q_F(U)=0)=P(U\le1/2)=1/2$ である。

命題 1.4. $n\in\NN$ とし、実数 $x_1<\cdots<x_n$ と $p_1,\ldots,p_n\ge0$ が $\sum_{j=1}^np_j=1$ を満たすとする。 $c_0:=0$ 、 $c_j:=\sum_{i=1}^jp_i$ $(1\le j\le n)$ と置き、 $\mu:=\sum_{j=1}^np_j\delta_{x_j}$ 、 $F(x):=\mu((-\infty,x])$ とする。 $u\in(0,1)$ に対して $J(u):=\min\{j\in\{1,\ldots,n\}\mid c_j\ge u\}$ と置く。

$u\in(0,1)$ に対して $J(u)$ は定まり、 $1\le j\le n$ について、 $J(u)=j$ であることと $c_{j-1}<u\le c_j$ であることは同値である。さらに $Q_F(u)=x_{J(u)}$ である。
$(\Omega,\mathcal F,P)$ を確率空間とし、 $U$ を $(0,1)$ に値をとり $U[0,1]$ に従う確率変数とすると、 $x_{J(U)}$ の分布は $\mu$ であり、 $1\le j\le n$ に対して $P(J(U)=j)=p_j$ である。 $p_j=0$ ならば、すべての $u\in(0,1)$ に対して $J(u)\ne j$ である。
$c_1,\ldots,c_n$ は $c_1=p_1$ 、 $c_j=c_{j-1}+p_j$ $(2\le j\le n)$ により $n-1$ 回の加算で計算される。 $u\in(0,1)$ に対し、 $j=1,2,\ldots$ の順に $c_j\ge u$ を判定して最初に成り立った $j$ を出力する手続きは、 $J(u)$ 回の比較の後に $J(u)$ を出力する。特に比較の回数は $n$ 以下である。
$u\in(0,1)$ に対し、 $\ell_0:=0$ 、 $h_0:=n$ と置く。 $h_t-\ell_t\ge2$ であるとき、 $m_t:=\lfloor(\ell_t+h_t)/2\rfloor$ と置いて、 $c_{m_t}\ge u$ ならば $(\ell_{t+1},h_{t+1}):=(\ell_t,m_t)$ 、 $c_{m_t}<u$ ならば $(\ell_{t+1},h_{t+1}):=(m_t,h_t)$ と定める。この手続きは、比較 $c_{m_t}\ge u$ を高々 $\lceil\log_2n\rceil$ 回行った後に $h_t-\ell_t=1$ となって終わり、そのときの $h_t$ は $J(u)$ に等しい。

証明.(1)を示す。 $p_j\ge0$ であるから $c_0\le c_1\le\cdots\le c_n=1$ であり、 $u<1$ から $J(u)$ は定まる。 $J(u)=j$ ならば、 $c_j\ge u$ であり、 $j=1$ のときは $c_0=0<u$ 、 $j\ge2$ のときは $J(u)$ の最小性から $c_{j-1}<u$ である。逆に $c_{j-1}<u\le c_j$ ならば、 $i<j$ に対して $c_i\le c_{j-1}<u$ であるから $J(u)=j$ である。 $x\in\R$ に対して $\{i\mid x_i\le x\}$ の元の個数を $k(x)$ とすると、 $x_1<\cdots<x_n$ から $F(x)=c_{k(x)}$ である。 $j:=J(u)$ とすると、 $F(x_j)=c_j\ge u$ であるから、定理 1.2 (1)により $Q_F(u)\le x_j$ である。 $x<x_j$ ならば $k(x)\le j-1$ であるから $F(x)\le c_{j-1}<u$ であり、定理 1.2 (1)により $Q_F(u)>x$ である。したがって $Q_F(u)=x_j$ である。

(2)を示す。(1)により $x_{J(U)}=Q_F(U)$ であるから、定理 1.2 (3)により $x_{J(U)}$ の分布は $\mu$ である。 $0\le t\le1$ に対して $P(U\le t)=t$ であるから、 $P(J(U)=j)=P(c_{j-1}<U\le c_j)=c_j-c_{j-1}=p_j$ である。 $p_j=0$ ならば $c_{j-1}=c_j$ であり、 $c_{j-1}<u\le c_j$ を満たす $u$ は存在しない。

(3)を示す。加算は $j=2,\ldots,n$ の各段で一回ずつ行われる。(1)と列 $(c_j)$ の非減少性により、 $j<J(u)$ ならば $c_j<u$ であり、 $c_{J(u)}\ge u$ であるから、判定が最初に成り立つのは $j=J(u)$ であり、そこまでの比較は $J(u)$ 回である。

(4)の証明は演習とする（問題 5.2）。▨

例 1.5. $n=3$ 、 $(x_1,x_2,x_3)=(0,1,2)$ 、 $(p_1,p_2,p_3)=(1/2,0,1/2)$ とすると、 $(c_1,c_2,c_3)=(1/2,1/2,1)$ である。 $0<u\le1/2$ ならば $J(u)=1$ 、 $1/2<u<1$ ならば $J(u)=3$ であり、 $J$ は値 $2$ をとらない。 $u=1/2$ では $c_1=c_2=u$ であり、最小の添字 $1$ が選ばれて $Q_F(1/2)=0=x_1$ となる。命題 1.4 (4)の手続きでは $\ell_0=0$ 、 $h_0=3$ 、 $m_0=1$ である。 $u\le1/2$ ならば $c_1\ge u$ から $(\ell_1,h_1)=(0,1)$ となって $1$ を出力し、 $u>1/2$ ならば $(\ell_1,h_1)=(1,3)$ 、 $m_1=2$ であり、 $c_2=1/2<u$ から $(\ell_2,h_2)=(2,3)$ となって $3$ を出力する。

2 独立な入力と棄却法

命題 2.1. $(\Omega,\mathcal F,P)$ を確率空間、 $I$ を空でない添字集合とし、部分シグマ加法族の族 $(\mathcal G_i)_{i\in I}$ は相互独立であるとする。 $S$ を空でない添字集合とし、 $(J_s)_{s\in S}$ を $I$ の空でない有限部分集合からなる族であって、 $s\ne s'$ ならば $J_s\cap J_{s'}=\emptyset$ を満たすものとする。

$\mathcal H_s:=\sigma\bigl(\bigcup_{i\in J_s}\mathcal G_i\bigr)$ $(s\in S)$ と置くと、 $(\mathcal H_s)_{s\in S}$ は相互独立である。
各 $i\in I$ に対して $e_i\in\NN$ と確率ベクトル $W_i\colon\Omega\to\R^{e_i}$ が与えられ、 $\mathcal G_i=\sigma(W_i):=\{W_i^{-1}(B)\mid B\in\mathcal B(\R^{e_i})\}$ であるとする。各 $s\in S$ について $J_s$ の元を $i_{s,1},\ldots,i_{s,p_s}$ と並べ、 $E_s:=e_{i_{s,1}}+\cdots+e_{i_{s,p_s}}$ と置き、 $m_s\in\NN$ と Borel 可測写像 $h_s\colon\R^{E_s}\to\R^{m_s}$ をとって $Z_s:=h_s(W_{i_{s,1}},\ldots,W_{i_{s,p_s}})$ と置く。このとき $(\sigma(Z_s))_{s\in S}$ は相互独立である。

証明. 証明は演習とする（問題 5.1）。▨

定理 2.2. $d\in\NN$ とし、 $f,g\colon\R^d\to[0,\infty)$ を $\int_{\R^d}f(x)\,dx=\int_{\R^d}g(x)\,dx=1$ を満たす Borel 可測関数、 $M>0$ を実数とし、すべての $x\in\R^d$ に対して $f(x)\le Mg(x)$ であるとする。 $g(x)>0$ ならば $a(x):=f(x)/(Mg(x))$ 、 $g(x)=0$ ならば $a(x):=0$ と置く。確率空間 $(\Omega,\mathcal F,P)$ 上の確率ベクトル $Y_k\colon\Omega\to\R^d$ と確率変数 $V_k\colon\Omega\to(0,1)$ $(k\in\NN)$ について、部分シグマ加法族の族 $\sigma(Y_1),\sigma(V_1),\sigma(Y_2),\sigma(V_2),\ldots$ は相互独立であり、各 $Y_k$ は密度 $g$ をもち、各 $V_k$ は $U[0,1]$ に従うとする。 $A_k:=\{V_k\le a(Y_k)\}$ 、 $K(\omega):=\{k\in\NN\mid\omega\in A_k\}$ と置く。 $s\in\NN$ と $\omega\in\Omega$ に対して、 $K(\omega)$ が $s$ 個以上の元をもつならば、 $T_s(\omega)$ を $K(\omega)$ の $s$ 番目に小さい元とし、 $X_s(\omega):=Y_{T_s(\omega)}(\omega)$ と置く。 $K(\omega)$ の元が $s$ 個未満ならば、 $T_s(\omega):=s$ 、 $X_s(\omega):=0$ と置く。 $0^0=1$ と約束する。

$a$ は $[0,1]$ に値をとる Borel 可測関数である。任意の $k\in\NN$ と Borel 集合 $B\subset\R^d$ に対して $P(\{Y_k\in B\}\cap A_k)=\frac1M\int_Bf(x)\,dx$ が成り立つ。特に $P(A_k)=1/M$ であり、 $M\ge1$ である。
各 $T_s$ は確率変数、各 $X_s$ は確率ベクトルである。 $r\in\NN$ 、整数 $1\le k_1<\cdots<k_r$ と Borel 集合 $B_1,\ldots,B_r\subset\R^d$ に対して $P(T_1=k_1,\ldots,T_r=k_r,\ X_1\in B_1,\ldots,X_r\in B_r)=\Bigl(1-\frac1M\Bigr)^{k_r-r}M^{-r}\prod_{s=1}^r\int_{B_s}f(x)\,dx$ が成り立つ。 $K(\omega)$ が無限集合となる $\omega$ の全体は確率 $1$ の事象である。
各 $r\in\NN$ に対して $\sigma(X_1),\ldots,\sigma(X_r)$ は相互独立であり、各 $X_s$ は密度 $f$ をもつ。
$T_1-1$ は幾何分布 $\operatorname{Geom}(1/M)$ に従い、 $E[T_1]=M$ である。各 $r\in\NN$ に対して $E[T_r]=rM$ である。特に、 $(Y_k,V_k)$ の生成と $V_k\le a(Y_k)$ の判定からなる試行1回の費用が定数 $c\ge0$ であるとき、最初の $r$ 個の出力を得るまでの費用 $cT_r$ の期待値は $crM$ である。

証明.(1)を示す。 $\{g>0\}$ 上で $a=f/(Mg)$ は Borel 可測関数の商であり、 $\{g=0\}$ 上で $a=0$ であるから、 $a$ は Borel 可測である。 $g(x)>0$ ならば $f(x)\le Mg(x)$ から $0\le a(x)\le1$ である。 $g(x)=0$ ならば $0\le f(x)\le Mg(x)=0$ であるから、すべての $x\in\R^d$ で

a(x)g(x)=\frac{f(x)}M

が成り立つ。Borel 集合の長方形の逆像 $\{Y_k\in B\}\cap\{V_k\in C\}$ は事象であるから、 $(Y_k,V_k)$ は $\mathcal B(\R^d)\otimes\mathcal B(\R)$ に関して可測であり、その法則 $\nu$ は $\R^d\times\R$ 上の確率測度である。 $\sigma(Y_k)$ と $\sigma(V_k)$ の独立性から、Borel 集合 $B\subset\R^d$ 、 $C\subset\R$ に対して $\nu(B\times C)=\mu_{Y_k}(B)\mu_{V_k}(C)$ であり、§E9.10 定理 5.1の一意性により $\nu=\mu_{Y_k}\otimes\mu_{V_k}$ である。写像 $(y,v)\mapsto a(y)-v$ は $\mathcal B(\R^d)\otimes\mathcal B(\R)$ に関して可測であるから、 $D:=\{(y,v)\mid y\in B,\ v\le a(y)\}$ は可測である。§E9.11 定理 2.3を $\mathbf 1_D$ に適用すると

P(\{Y_k\in B\}\cap A_k)=\nu(D)=\int_{\R^d}\mathbf 1_B(y)\,P(V_k\le a(y))\,d\mu_{Y_k}(y)=\int_{\R^d}\mathbf 1_B(y)a(y)\,d\mu_{Y_k}(y)

である。ここで $0\le a(y)\le1$ と、 $0\le t\le1$ に対する $P(V_k\le t)=t$ を用いた。 $\mu_{Y_k}$ は Lebesgue 測度に関して密度 $g$ をもつから、§E9.15 命題 4.3を非負関数 $\mathbf 1_Ba$ に適用すると、右辺は $\int_Ba(y)g(y)\,dy=M^{-1}\int_Bf(y)\,dy$ に等しい。 $B=\R^d$ とすると $P(A_k)=1/M$ であり、 $P(A_k)\le1$ から $M\ge1$ である。

(2)を示す。写像 $h\colon\R^{d+1}\to\R^{d+1}$ を $h(y,v):=(y,\mathbf 1_{[0,\infty)}(a(y)-v))$ で定めると $h$ は Borel 可測であり、 $Z_k:=h(Y_k,V_k)=(Y_k,\mathbf 1_{A_k})$ である。命題 2.1 (2)を、添字 $(k,1)$ に $Y_k$ 、添字 $(k,2)$ に $V_k$ を対応させ、 $J_k:=\{(k,1),(k,2)\}$ として適用すると、 $\sigma(Z_1),\sigma(Z_2),\ldots$ は相互独立である。Borel 集合 $B\subset\R^d$ に対して $\{Y_k\in B\}\cap A_k=Z_k^{-1}(B\times\{1\})$ と $\Omega\setminus A_k=Z_k^{-1}(\R^d\times\{0\})$ は $\sigma(Z_k)$ に属する。

$r\in\NN$ とし、整数の組 $\kappa=(k_1,\ldots,k_r)$ で $1\le k_1<\cdots<k_r$ を満たすものと Borel 集合 $B_1,\ldots,B_r\subset\R^d$ に対して

E_\kappa(B_1,\ldots,B_r):=\bigcap_{s=1}^r\bigl(\{Y_{k_s}\in B_s\}\cap A_{k_s}\bigr)\cap\bigcap_{\substack{1\le k\le k_r\\ k\notin\{k_1,\ldots,k_r\}}}(\Omega\setminus A_k)

と置く。 $\sigma(Z_1),\ldots,\sigma(Z_{k_r})$ の相互独立性と(1)により

P(E_\kappa(B_1,\ldots,B_r))=\Bigl(1-\frac1M\Bigr)^{k_r-r}M^{-r}\prod_{s=1}^r\int_{B_s}f(x)\,dx

(2.2.1)

である。 $\omega\in E_\kappa(\R^d,\ldots,\R^d)$ であることは、 $K(\omega)$ が $r$ 個以上の元をもち、その小さい方から $r$ 個が $k_1,\ldots,k_r$ であることと同値である。したがって $\kappa$ を動かした事象 $E_\kappa(\R^d,\ldots,\R^d)$ は互いに交わらず、その和集合は $\{\omega\mid K(\omega)\text{ は }r\text{ 個以上の元をもつ}\}=:\Omega_r$ であり、 $\Omega_r$ は事象である。 $\Omega_r$ 上では $T_s$ と $X_s$ $(s\le r)$ は $K(\omega)$ の小さい方から $r$ 個の元で定まるから、

\{T_1=k_1,\ldots,T_r=k_r,\ X_1\in B_1,\ldots,X_r\in B_r\}\cap\Omega_r=E_\kappa(B_1,\ldots,B_r)

(2.2.2)

である。 $s\in\NN$ 、 $k\in\NN$ と Borel 集合 $B\subset\R^d$ に対して、 $\{T_s=k\}$ は $k_s=k$ を満たす長さ $s$ の組 $\kappa$ にわたる $E_\kappa(\R^d,\ldots,\R^d)$ の有限和と、 $k=s$ の場合の $\Omega\setminus\Omega_s$ との和であり、 $\{X_s\in B\}$ は長さ $s$ の組 $\kappa$ にわたる $E_\kappa(\R^d,\ldots,\R^d,B)$ の可算和と、 $0\in B$ の場合の $\Omega\setminus\Omega_s$ との和である。よって $T_s$ は確率変数、 $X_s$ は確率ベクトルである。

組 $\kappa$ に $g_1:=k_1$ 、 $g_s:=k_s-k_{s-1}$ $(2\le s\le r)$ を対応させる写像は、長さ $r$ の組の全体から $\NN^r$ への全単射であり、 $k_r-r=\sum_{s=1}^r(g_s-1)$ である。 $0\le1-1/M<1$ であるから、§E11.5 補題 1.1により $\sum_{g\in\NN}(1-1/M)^{g-1}=M$ であり、式 (2.2.1)を $\kappa$ について加えると

\sum_\kappa P(E_\kappa(B_1,\ldots,B_r))=\prod_{s=1}^r\Bigl(\sum_{g\in\NN}\Bigl(1-\frac1M\Bigr)^{g-1}\frac1M\int_{B_s}f(x)\,dx\Bigr)=\prod_{s=1}^r\int_{B_s}f(x)\,dx

(2.2.3)

である。 $B_1=\cdots=B_r=\R^d$ とすると $P(\Omega_r)=1$ である。したがって式 (2.2.2)と式 (2.2.1)から主張の等式を得る。 $K(\omega)$ が無限集合となる $\omega$ の全体は $\bigcap_{r\in\NN}\Omega_r$ であり、その確率は $1$ である。

(3)を示す。 $r\in\NN$ と Borel 集合 $B_1,\ldots,B_r\subset\R^d$ をとる。式 (2.2.2)により、 $\kappa$ にわたる事象 $E_\kappa(B_1,\ldots,B_r)$ は互いに交わらず、その和集合は $\{X_1\in B_1,\ldots,X_r\in B_r\}\cap\Omega_r$ である。 $P(\Omega_r)=1$ と式 (2.2.3)から

P(X_1\in B_1,\ldots,X_r\in B_r)=\prod_{s=1}^r\int_{B_s}f(x)\,dx

である。 $t\ne s$ に対して $B_t=\R^d$ とすると $P(X_s\in B_s)=\int_{B_s}f(x)\,dx$ であるから、 $X_s$ は密度 $f$ をもつ。 $\sigma(X_s)$ の元は $X_s^{-1}(B)$ の形であり、選ばれない添字に $\R^d$ を置くと、相異なる $s_1,\ldots,s_q\in\{1,\ldots,r\}$ と $\sigma(X_{s_j})$ の元に対して積の公式が成り立つ。§E11.7 定義 1.1により $\sigma(X_1),\ldots,\sigma(X_r)$ は相互独立である。

(4)を示す。 $T_0:=0$ 、 $G_s:=T_s-T_{s-1}$ $(s\in\NN)$ と置く。 $r\in\NN$ と $(g_1,\ldots,g_r)\in\NN^r$ に対して、事象 $\{G_1=g_1,\ldots,G_r=g_r\}$ は $k_s:=g_1+\cdots+g_s$ とした事象 $\{T_1=k_1,\ldots,T_r=k_r\}$ に等しいから、(2)を $B_1=\cdots=B_r=\R^d$ として

P(G_1=g_1,\ldots,G_r=g_r)=\prod_{s=1}^r\frac1M\Bigl(1-\frac1M\Bigr)^{g_s-1}

を得る。 $t\ne s$ の $g_t$ について和をとると、§E11.5 補題 1.1により $g\in\NN$ に対して $P(G_s=g)=M^{-1}(1-M^{-1})^{g-1}$ であり、これらの和は $1$ である。したがって $P(G_s-1\in\N)=1$ であり、 $G_s-1$ は $\operatorname{Geom}(1/M)$ に従う。 $\lvert G_s-1\rvert$ はほとんど確実に $G_s-1$ に等しく、 $1/M\in(0,1]$ であるから、§E11.5 命題 1.5により $E[\lvert G_s-1\rvert]=E[G_s-1]=(1-1/M)/(1/M)=M-1<\infty$ である。よって $G_s-1$ は可積分であり、§E11.4 命題 1.2により $E[G_s]=M$ である。 $G_1=T_1$ であるから $T_1-1$ は $\operatorname{Geom}(1/M)$ に従い、 $E[T_1]=M$ である。 $T_r=G_1+\cdots+G_r$ であるから、§E11.4 命題 1.2により $E[T_r]=rM$ であり、 $E[cT_r]=crM$ である。▨

例 2.3. $f(x):=\sqrt{2/\pi}\,e^{-x^2/2}\mathbf 1_{[0,\infty)}(x)$ 、 $g(x):=e^{-x}\mathbf 1_{[0,\infty)}(x)$ と置く。§E11.5 命題 2.5により $\int_\R e^{-x^2/2}\,dx=\sqrt{2\pi}$ であり、被積分関数は偶関数であるから $\int_\R f=1$ である。 $g$ は $\operatorname{Exp}(1)$ の密度である。 $x\ge0$ に対して

\frac{f(x)}{g(x)}=\sqrt{\frac2\pi}\,e^{x-x^2/2}=\sqrt{\frac{2e}\pi}\,e^{-(x-1)^2/2}\le\sqrt{\frac{2e}\pi}

であり、等号は $x=1$ で成り立つ。 $x<0$ では $f(x)=g(x)=0$ である。したがって $M:=\sqrt{2e/\pi}\approx1.3155$ に対して $f\le Mg$ が成り立ち、 $x\ge0$ で $a(x)=e^{-(x-1)^2/2}$ 、 $x<0$ で $a(x)=0$ である。 $0<M'<M$ ならば $f(1)=Mg(1)>M'g(1)$ であるから、 $f\le M'g$ を満たす正の定数 $M'$ のうち最小のものは $M$ であり、定理 2.2 (4)の $E[T_1]=M$ もこの $M$ で最小になる。

$U_1,U_2,\ldots$ を $(0,1)$ に値をとり、相互独立で、それぞれ $U[0,1]$ に従う確率変数とする。 $\operatorname{Exp}(1)$ の分布関数 $F$ は $x<0$ で $0$ 、 $x\ge0$ で $1-e^{-x}$ であり、 $u\in(0,1)$ に対して $F(x)\ge u$ は $x\ge-\log(1-u)$ と同値であるから、 $Q_F(u)=-\log(1-u)$ である。 $Y_k:=-\log(1-U_{2k-1})$ 、 $V_k:=U_{2k}$ と置くと、定理 1.2 (3)により $Y_k$ は $\operatorname{Exp}(1)$ に従い、命題 2.1 (2)により $\sigma(Y_1),\sigma(V_1),\sigma(Y_2),\ldots$ は相互独立である。

$f$ と $g$ の役割を入れ替え、 $\operatorname{Exp}(1)$ の密度を目標、 $\sqrt{2/\pi}\,e^{-x^2/2}\mathbf 1_{[0,\infty)}$ を提案の密度とすると、 $x\ge0$ での比 $\sqrt{\pi/2}\,e^{x^2/2-x}$ は $x\to\infty$ で発散するので、定理 2.2の仮定を満たす実数 $M$ は存在しない。

3 正規分布に従う標本

定理 3.1. $(\Omega,\mathcal F,P)$ を確率空間とする。

$U,V$ を $(0,1)$ に値をとり、独立で、それぞれ $U[0,1]$ に従う確率変数とする。 $R:=\sqrt{-2\log U},\qquad Z=(Z_1,Z_2):=(R\cos2\pi V,\ R\sin2\pi V)$ と置くと、 $Z$ は $N_2(0,I_2)$ に従い、 $Z_1$ と $Z_2$ は独立で、それぞれ $N(0,1)$ に従う。
$n\in\NN$ とし、 $U_1,\ldots,U_{2n}$ を $(0,1)$ に値をとり、相互独立で、それぞれ $U[0,1]$ に従う確率変数とする。 $1\le j\le n$ に対して、 $(U,V)=(U_{2j-1},U_{2j})$ から上の式で得る $Z$ を $(Z_{2j-1},Z_{2j})$ とする。このとき、 $1\le r\le2n$ を満たす各整数 $r$ に対して $(Z_1,\ldots,Z_r)$ は $N_r(0,I_r)$ に従う。

証明.(1)を示す。 $W:=\R^2\setminus\{(x,0)\mid x\ge0\}$ と置くと、 $W$ は開集合である。 $\rho(u):=\sqrt{-2\log u}$ と置き、 $\Phi\colon(0,1)^2\to\R^2$ を

\Phi(u,v):=\bigl(\rho(u)\cos2\pi v,\ \rho(u)\sin2\pi v\bigr)

で定めると $Z=\Phi(U,V)$ である。 $\rho$ は $(0,1)$ 上で正の値をとる $C^1$ 級関数であり、 $\rho'(u)=-1/(u\rho(u))$ である。 $\sin2\pi v=0$ を満たす $v\in(0,1)$ は $1/2$ だけであり、そのとき $\cos2\pi v=-1$ であるから、 $\Phi$ は $W$ に値をとる。 $z=(z_1,z_2)\in W$ に対して $\lVert z\rVert>0$ かつ $\lVert z\rVert-z_1>0$ であるから、

\Psi(z):=\Bigl(e^{-\lVert z\rVert^2/2},\ \frac{\pi-2\arctan\tau(z)}{2\pi}\Bigr),\qquad\tau(z):=\frac{z_2}{\lVert z\rVert-z_1}

は $W$ から $(0,1)^2$ への $C^1$ 級写像である。

$(u,v)\in(0,1)^2$ とし、 $\theta:=2\pi v\in(0,2\pi)$ と置く。 $\lVert\Phi(u,v)\rVert^2=-2\log u$ であり、 $\tau(\Phi(u,v))=\sin\theta/(1-\cos\theta)=\tan(\pi/2-\theta/2)$ と $\pi/2-\theta/2\in(-\pi/2,\pi/2)$ から $\arctan\tau(\Phi(u,v))=\pi/2-\theta/2$ である。したがって $\Psi(\Phi(u,v))=(u,v)$ である。

$z\in W$ とし、 $\rho_z:=\lVert z\rVert$ 、 $\beta:=\rho_z-z_1>0$ 、 $\tau:=\tau(z)$ 、 $\theta:=\pi-2\arctan\tau\in(0,2\pi)$ と置く。 $z_1^2+z_2^2=\rho_z^2$ から $\beta^2+z_2^2=2\rho_z\beta$ 、 $\beta^2-z_2^2=-2z_1\beta$ であり、 $1+\tau^2=2\rho_z/\beta$ 、 $1-\tau^2=-2z_1/\beta$ である。したがって

\cos\theta=-\frac{1-\tau^2}{1+\tau^2}=\frac{z_1}{\rho_z},\qquad\sin\theta=\frac{2\tau}{1+\tau^2}=\frac{z_2}{\rho_z}

である。 $\Psi(z)$ の第一成分 $u$ は $\rho(u)=\rho_z$ を満たし、第二成分は $\theta/(2\pi)$ であるから、 $\Phi(\Psi(z))=z$ である。よって $\Phi$ は $(0,1)^2$ から $W$ への $C^1$ 級微分同相であり、 $\Phi^{-1}=\Psi$ である。偏導関数は $\partial_u\Phi=\rho'(u)(\cos2\pi v,\sin2\pi v)$ 、 $\partial_v\Phi=2\pi\rho(u)(-\sin2\pi v,\cos2\pi v)$ であるから、

\det D\Phi(u,v)=2\pi\rho(u)\rho'(u)=-\frac{2\pi}u

である。

$U$ と $V$ は独立であるから、§E11.7 定理 2.1により $(U,V)$ の法則は $\mu_U\otimes\mu_V$ であり、§E9.11 定理 2.3により $(U,V)$ は $\R^2$ 上の密度 $\mathbf 1_{[0,1]^2}$ をもつ。 $P((U,V)\in(0,1)^2)=1$ であるから、§E11.8 定理 5.1により $Z$ は密度

\mathbf 1_W(z)\frac{\mathbf 1_{[0,1]^2}(\Psi(z))}{\lvert\det D\Phi(\Psi(z))\rvert}=\mathbf 1_W(z)\frac{e^{-\lVert z\rVert^2/2}}{2\pi}

をもつ。 $\R^2\setminus W$ は $\R\times\{0\}$ に含まれ、§E9.11 定理 2.3により $\R\times\{0\}$ の Lebesgue 測度は $0$ であるから、 $Z$ は密度 $\varphi_2(z)=(2\pi)^{-1}e^{-\lVert z\rVert^2/2}$ をもち、§E11.10 定義 3.1により $N_2(0,I_2)$ に従う。Borel 集合 $B_1,B_2\subset\R$ に対して、§E9.11 定理 2.3により $P(Z_1\in B_1,Z_2\in B_2)=\int_{B_1}\varphi_1\int_{B_2}\varphi_1$ である。 $B_2=\R$ または $B_1=\R$ とすると $Z_1$ と $Z_2$ はそれぞれ $N(0,1)$ に従い、§E11.7 命題 1.2により $Z_1$ と $Z_2$ は独立である。

(2)を示す。 $\Phi$ を $(0,1)^2$ の外で $0$ と置いて延長した写像 $\bar\Phi\colon\R^2\to\R^2$ は Borel 可測であり、 $(Z_{2j-1},Z_{2j})=\bar\Phi(U_{2j-1},U_{2j})$ である。命題 2.1 (2)を $J_j:=\{2j-1,2j\}$ $(1\le j\le n)$ に適用すると、 $\sigma((Z_1,Z_2)),\ldots,\sigma((Z_{2n-1},Z_{2n}))$ は相互独立である。Borel 集合 $B_1,\ldots,B_{2n}\subset\R$ に対して、この独立性と(1)から

P(Z_1\in B_1,\ldots,Z_{2n}\in B_{2n})=\prod_{j=1}^nP(Z_{2j-1}\in B_{2j-1},\ Z_{2j}\in B_{2j})=\prod_{i=1}^{2n}\int_{B_i}\varphi_1

である。 $1\le r\le2n$ とし、 $i>r$ に対して $B_i=\R$ と置くと、§E9.11 定理 2.3により右辺は $\int_{B_1\times\cdots\times B_r}\varphi_r$ に等しい。 $P((Z_1,\ldots,Z_r)\in C)=\int_C\varphi_r$ を満たす Borel 集合 $C\subset\R^r$ の全体は、両辺が $C$ について確率測度であるから Dynkin 系をなし、空集合と $\R^r$ の半開直方体をすべて含む。空集合と半開直方体の全体は π 系であり、その有限非交和の全体 $\mathcal R_r$ はこの π 系を含み、この π 系が生成するシグマ加法族に含まれる。§E9.4 定理 3.3により $\sigma(\mathcal R_r)=\mathcal B(\R^r)$ であるから、この π 系は $\mathcal B(\R^r)$ を生成する。§E9.1 定理 4.8により $(Z_1,\ldots,Z_r)$ は密度 $\varphi_r$ をもち、 $N_r(0,I_r)$ に従う。▨

命題 3.2. $(\Omega,\mathcal F,P)$ を確率空間とし、 $d\in\NN$ 、 $m\in\R^d$ 、 $\Sigma$ を $d$ 次実対称半正定値行列とする。

$r\in\NN$ と $A\in\R^{d\times r}$ が $AA^{\mathsf T}=\Sigma$ を満たし、確率ベクトル $Z\colon\Omega\to\R^r$ が $N_r(0,I_r)$ に従うならば、 $m+AZ$ は $N_d(m,\Sigma)$ に従い、すべての $\omega\in\Omega$ で $m+AZ(\omega)\in m+\operatorname{Ran}\Sigma$ である。 $\operatorname{rank}\Sigma<d$ ならば、 $m+AZ$ は $d$ 次元 Lebesgue 測度に関する密度をもたない。
$\Sigma$ が正定値ならば、 $\Sigma$ の Cholesky 因子 $C$ と $N_d(0,I_d)$ に従う $Z$ に対して、 $m+CZ$ は $N_d(m,\Sigma)$ に従う。 $C$ は§E20.5 定理 5.2 (5)の式により $d^3/3+d^2/2-5d/6$ 回の四則演算と $d$ 回の平方根で計算され、 $C$ と $z\in\R^d$ から $m+Cz$ を得る計算は $d^2+d$ 回の四則演算で行われる。したがって、 $n\in\NN$ 個の標本を作るとき、 $C$ を一度計算すれば、四則演算は $d^3/3+d^2/2-5d/6+n(d^2+d)$ 回、平方根は $d$ 回、 $N(0,1)$ に従う標本は $nd$ 個である。
$\Sigma$ を $\R^d$ の標準内積に関する線形写像とみなすと正作用素であり、その正の平方根 $B:=\Sigma^{1/2}$ は $BB^{\mathsf T}=\Sigma$ を満たす。 $k:=\operatorname{rank}\Sigma\ge1$ ならば、 $\Sigma$ の固有ベクトルからなる正規直交基底 $q_1,\ldots,q_d$ と対応する固有値 $\lambda_1,\ldots,\lambda_d$ であって $\lambda_1,\ldots,\lambda_k>0$ 、 $\lambda_{k+1}=\cdots=\lambda_d=0$ を満たすものが存在し、 $A_k:=(\sqrt{\lambda_1}\,q_1,\ldots,\sqrt{\lambda_k}\,q_k)\in\R^{d\times k}$ は $A_kA_k^{\mathsf T}=\Sigma$ を満たす。 $A_k$ と $z\in\R^k$ から $m+A_kz$ を得る計算は $2dk$ 回の四則演算で行われる。 $k=0$ ならば $\Sigma=0$ であり、 $A:=0\in\R^{d\times1}$ は $AA^{\mathsf T}=\Sigma$ を満たし、 $m+AZ=m$ である。

証明.(1)を示す。§E11.10 定理 4.2により $m+AZ$ は Gaussian 確率ベクトルであり、平均は $m$ 、共分散は $AA^{\mathsf T}=\Sigma$ であるから、 $N_d(m,\Sigma)$ に従う。 $x\in\R^d$ が $\Sigma x=0$ を満たすならば $\lVert A^{\mathsf T}x\rVert^2=x^{\mathsf T}AA^{\mathsf T}x=0$ であるから、 $\ker\Sigma=\ker A^{\mathsf T}$ である。したがって $\operatorname{rank}\Sigma=d-\dim\ker A^{\mathsf T}=\operatorname{rank}A^{\mathsf T}=\operatorname{rank}A$ であり、 $\operatorname{Ran}\Sigma=\operatorname{Ran}AA^{\mathsf T}\subset\operatorname{Ran}A$ と合わせて $\operatorname{Ran}\Sigma=\operatorname{Ran}A$ である。よってすべての $\omega$ で $m+AZ(\omega)\in m+\operatorname{Ran}\Sigma$ である。 $\operatorname{rank}\Sigma<d$ の場合の主張は§E11.10 定理 6.1である。

(2)を示す。§E20.5 定理 5.2 (3)により $\Sigma$ は Cholesky 因子 $C$ をもち、 $CC^{\mathsf T}=\Sigma$ であるから、(1)を $r=d$ 、 $A=C$ として適用する。 $C$ の計算の回数は§E20.5 定理 5.2 (5)による。 $C$ は下三角行列であるから、 $m+Cz$ の第 $i$ 成分 $m_i+\sum_{j=1}^ic_{ij}z_j$ は $i$ 回の乗算と $i$ 回の加算で計算され、合計は $\sum_{i=1}^d2i=d^2+d$ 回である。

(3)を示す。 $\Sigma^{\mathsf T}=\Sigma$ であり、すべての $x\in\R^d$ で $\langle\Sigma x,x\rangle=x^{\mathsf T}\Sigma x\ge0$ であるから、 $\Sigma$ は正作用素である。§E3.38 定理 1.1により、正作用素 $B$ で $B^2=\Sigma$ を満たすものがただ一つ存在する。 $B$ は自己随伴であるから $B^{\mathsf T}=B$ であり、 $BB^{\mathsf T}=B^2=\Sigma$ である。§E3.37 定理 3.1により、 $\Sigma$ の固有ベクトルからなる正規直交基底 $q_1,\ldots,q_d$ が存在する。 $\Sigma q_i=\lambda_iq_i$ とすると $\lambda_i=q_i^{\mathsf T}\Sigma q_i\ge0$ であり、番号を付け替えて正の固有値を前に並べる。 $x=\sum_{i=1}^d(q_i^{\mathsf T}x)q_i$ から

\Sigma x=\sum_{i=1}^d\lambda_i(q_i^{\mathsf T}x)q_i=\sum_{\lambda_i>0}\lambda_iq_iq_i^{\mathsf T}x

である。 $\lambda_i>0$ ならば $q_i=\Sigma(\lambda_i^{-1}q_i)$ であるから、 $\operatorname{Ran}\Sigma$ は $\{q_i\mid\lambda_i>0\}$ で張られ、正の固有値の個数は $k$ に等しい。上の式から $\Sigma=\sum_{i=1}^k\lambda_iq_iq_i^{\mathsf T}=A_kA_k^{\mathsf T}$ である。 $m+A_kz$ の各成分は $k$ 回の乗算と $k$ 回の加算で計算されるから、合計は $2dk$ 回である。 $k=0$ ならば $\operatorname{Ran}\Sigma=\{0\}$ であるから $\Sigma=0$ である。▨

例 3.3. $m\in\R^2$ とし、 $Z=(Z_1,Z_2)$ を定理 3.1 (1)で作った $N_2(0,I_2)$ に従う確率ベクトルとする。

$\Sigma_1:=\begin{pmatrix}4&2\\2&2\end{pmatrix}$ と $C:=\begin{pmatrix}2&0\\1&1\end{pmatrix}$ について $CC^{\mathsf T}=\Sigma_1$ であり、 $C$ は対角成分が正の下三角行列であるから、§E20.5 定理 5.2 (4)により $\Sigma_1$ は正定値であり、 $C$ は $\Sigma_1$ の Cholesky 因子である。命題 3.2 (2)により $m+(2Z_1,\ Z_1+Z_2)$ は $N_2(m,\Sigma_1)$ に従う。
$\Sigma_2:=\begin{pmatrix}1&1\\1&1\end{pmatrix}$ は $q_1=(1,1)/\sqrt2$ に対する固有値 $2$ と $q_2=(1,-1)/\sqrt2$ に対する固有値 $0$ をもち、 $\operatorname{rank}\Sigma_2=1$ である。 $A_1=\sqrt2\,q_1=(1,1)^{\mathsf T}$ であり、 $m+(Z_1,Z_1)$ は $N_2(m,\Sigma_2)$ に従い、すべての標本が直線 $m+\{(t,t)\mid t\in\R\}$ 上にある。 $\Sigma_2/\sqrt2$ は対称であり $x^{\mathsf T}(\Sigma_2/\sqrt2)x=(x_1+x_2)^2/\sqrt2\ge0$ 、 $(\Sigma_2/\sqrt2)^2=\Sigma_2$ であるから、§E3.38 定理 1.1の一意性により $\Sigma_2^{1/2}=\Sigma_2/\sqrt2$ である。 $m+\Sigma_2^{1/2}Z=m+\frac{Z_1+Z_2}{\sqrt2}(1,1)$ は同じ法則に従うが、二つの $N(0,1)$ 標本を用いる。 $\det\Sigma_2=0$ であるから $\Sigma_2$ は正定値でなく、§E20.5 定理 5.2 (4)により Cholesky 因子をもたない。
$\Sigma_3:=\operatorname{diag}(0,1)$ に§E20.5 定理 5.2 (5)の式を形式的に適用すると $c_{11}=0$ となり、 $c_{21}=a_{21}/c_{11}$ は定義されない。一方、 $q_1=(0,1)$ 、 $\lambda_1=1$ から $A_1=(0,1)^{\mathsf T}$ であり、 $m+(0,Z_1)$ は $N_2(m,\Sigma_3)$ に従う。

4 格子と求根の誤差

命題 4.1. $\mu$ を $\R$ 上の Borel 確率測度、 $F(x):=\mu((-\infty,x])$ $(x\in\R)$ とし、 $(\Omega,\mathcal F,P)$ を確率空間とする。

$\hat U$ を $(0,1)$ に値をとる確率変数とし、 $\delta:=\sup_{0\le t\le1}\lvert P(\hat U\le t)-t\rvert$ と置く。このとき $\hat X:=Q_F(\hat U)$ は確率変数であり、すべての $x\in\R$ に対して $\lvert P(\hat X\le x)-F(x)\rvert\le\delta$ である。
$M\in\NN$ とし、確率変数 $\hat U$ が $H_M:=\{(2k+1)/(2M)\mid k\in\Z,\ 0\le k\le M-1\}$ 上の一様分布に従うならば、 $\sup_{0\le t\le1}\lvert P(\hat U\le t)-t\rvert=1/(2M)$ である。

証明.(1)を示す。定理 1.2 (2)により $\hat X$ は確率変数である。 $x\in\R$ に対して、定理 1.2 (1)により $\{\hat X\le x\}=\{\hat U\le F(x)\}$ であり、 $0\le F(x)\le1$ であるから、 $\lvert P(\hat X\le x)-F(x)\rvert=\lvert P(\hat U\le F(x))-F(x)\rvert\le\delta$ である。

(2)を示す。 $t\in[0,1]$ とし、 $\xi:=Mt$ と置く。 $(2k+1)/(2M)\le t$ は $k\le\xi-1/2$ と同値であり、 $0\le\xi+1/2<M+1$ であるから、 $0\le k\le M-1$ と $k\le\xi-1/2$ を満たす整数 $k$ の個数は $\lfloor\xi+1/2\rfloor$ である。したがって $P(\hat U\le t)=\lfloor\xi+1/2\rfloor/M$ であり、 $\xi-1/2<\lfloor\xi+1/2\rfloor\le\xi+1/2$ から $\lvert P(\hat U\le t)-t\rvert\le1/(2M)$ である。 $t=1/(2M)$ では $P(\hat U\le t)=1/M$ であり、差は $1/(2M)$ に等しい。▨

注意 4.2. $b\in\NN$ 、 $M:=2^b$ とし、 $X$ を $\{0,\ldots,M-1\}$ 上の一様分布に従う確率変数とすると、§E20.33 命題 4.1 (1)により $(X+1/2)/M$ は $H_M$ 上の一様分布に従い、命題 4.1 (2)により $\sup_{0\le t\le1}\lvert P((X+1/2)/M\le t)-t\rvert=2^{-(b+1)}$ である。 $X/M$ は値 $0$ を確率 $1/M$ でとり、すべての $x\in\R$ で $F(x)\ge0$ であるから $\{x\mid F(x)\ge0\}$ は下に有界でなく、 $Q_F$ の定義式は $u=0$ で実数を与えない。§E20.33 例 4.2 (4)により $M=2^{64}$ のとき $(M-1)/M$ の binary64 への最近接丸めは $1$ であり、 $\operatorname{Exp}(1)$ の分布関数 $F$ では $F(x)\ge1$ を満たす実数 $x$ が存在しない。

$\hat U$ が $(0,1)$ に値をとり $H_M$ 上の一様分布に従うとき、 $\hat X=Q_F(\hat U)$ の分布は $M$ 個以下の点からなる集合 $Q_F(H_M)$ に確率 $1$ を与えるので、 $\mu$ が原子をもたなければ $\hat X$ の分布は $\mu$ と異なる。 $\delta$ は一つの確率変数の分布についての量であり、複数の入力の相互独立性を測らない。有限状態生成器の出力の値の集合を $Z$ 、状態集合を $S$ とすると、§E20.33 命題 1.4により、 $\lvert Z\rvert^k>\lvert S\rvert$ を満たす $k$ 個の連続する出力は、初期状態を確率変数としても相互独立で一様とはならない。

命題 4.3. $\mu$ を $\R$ 上の Borel 確率測度、 $F(x):=\mu((-\infty,x])$ $(x\in\R)$ とする。実数 $a<b$ について $F$ は $[a,b]$ 上で連続かつ狭義単調増加であるとし、 $u\in(0,1)$ は $F(a)<u\le F(b)$ を満たすとする。

$Q_F(u)\in(a,b]$ であり、 $Q_F(u)$ は $F(x)=u$ を満たす $x\in[a,b]$ のただ一つである。 $u=F(b)$ ならば $Q_F(u)=b$ である。 $u<F(b)$ ならば、§E20.4 定義 2.2の二分法を $[a,b]$ 上の関数 $x\mapsto F(x)-u$ に適用すると、ある段 $n$ で停止して $m_n=Q_F(u)$ を出力するか、どの段でも停止せず、すべての $n\in\N$ に対して $\lvert m_n-Q_F(u)\rvert\le2^{-(n+1)}(b-a)$ が成り立つ。
$u<F(b)$ とし、さらに $F$ は $(a,b)$ で微分可能であり、ある実数 $m>0$ についてすべての $t\in(a,b)$ で $F'(t)\ge m$ であるとする。 $\hat x\in[a,b]$ と $\ep\ge0$ が $\lvert F(\hat x)-u\rvert\le\ep$ を満たすならば、 $\lvert\hat x-Q_F(u)\rvert\le\ep/m$ である。

証明. $q:=Q_F(u)$ と置く。

(1)を示す。 $F(a)<u$ であるから、定理 1.2 (1)により $q\le a$ は成り立たず、 $q>a$ である。 $u\le F(b)$ であるから、同じく $q\le b$ である。定理 1.2 (1)により $F(q)\ge u$ であり、 $a<x<q$ ならば $q\le x$ が成り立たないので $F(x)<u$ である。 $F$ は $q\in(a,b]$ で左から連続であるから、 $F(q)=\lim_{x\uparrow q}F(x)\le u$ であり、 $F(q)=u$ である。 $F$ は $[a,b]$ 上で狭義単調増加であるから、 $F(x)=u$ を満たす $x\in[a,b]$ は $q$ だけである。 $u=F(b)$ ならば $b$ がその $x$ であるから $q=b$ である。 $u<F(b)$ とし、 $\phi(x):=F(x)-u$ $(x\in[a,b])$ と置くと、 $\phi$ は連続であり $\phi(a)\phi(b)<0$ であるから、§E20.4 定義 2.2の二分法が定まる。段 $n$ で停止するならば $\phi(m_n)=0$ であるから $m_n=q$ である。どの段でも停止しないならば、§E20.4 定理 2.3 (3)により $\phi$ の零点 $r$ で、すべての $n\in\N$ に対して $\lvert m_n-r\rvert\le2^{-(n+1)}(b-a)$ を満たすものが存在し、零点の一意性により $r=q$ である。

(2)を示す。 $\phi(x):=F(x)-u$ $(x\in[a,b])$ は $[a,b]$ 上で連続、 $(a,b)$ で微分可能であり、 $\phi(a)\phi(b)<0$ 、すべての $t\in(a,b)$ で $\lvert\phi'(t)\rvert\ge m$ を満たす。点列 $x_k:=\hat x$ $(k\in\N)$ は $k=0$ で残差判定 $\lvert\phi(x_0)\rvert\le\ep$ を満たすから、§E20.4 命題 6.2 (3)を $\tau_f:=\ep$ として適用すると、 $\lvert\hat x-r\rvert\le\ep/m$ を満たす $\phi$ の零点 $r\in[a,b]$ が存在する。(1)により $r=q$ である。▨

例 4.4. $\lambda>0$ とし、 $F$ を $\operatorname{Exp}(\lambda)$ の分布関数とする。 $F$ は $x<0$ で $0$ 、 $x\ge0$ で $1-e^{-\lambda x}$ であり、 $u\in(0,1)$ に対して $F(x)\ge u$ は $x\ge-\lambda^{-1}\log(1-u)$ と同値であるから、 $Q_F(u)=-\lambda^{-1}\log(1-u)$ である。 $b>Q_F(u)$ とすると、 $F$ は $[0,b]$ 上で連続かつ狭義単調増加であり、 $F(0)=0<u<F(b)$ であって、 $t\in(0,b)$ で $F'(t)=\lambda e^{-\lambda t}\ge\lambda e^{-\lambda b}$ である。命題 4.3 (2)により、 $\hat x\in[0,b]$ と $\lvert F(\hat x)-u\rvert\le\ep$ から $\lvert\hat x-Q_F(u)\rvert\le\ep e^{\lambda b}/\lambda$ を得る。 $b>Q_F(u)$ から $e^{\lambda b}>1/(1-u)$ であり、 $\ep>0$ ならばこの上界は $\ep/(\lambda(1-u))$ より大きい。

この増大は評価の粗さによるものではない。 $Q_F(u)\le\hat x$ ならば

F(\hat x)-u=\int_{Q_F(u)}^{\hat x}\lambda e^{-\lambda t}\,dt\le\lambda e^{-\lambda Q_F(u)}(\hat x-Q_F(u))=\lambda(1-u)(\hat x-Q_F(u))

であるから、 $\hat x-Q_F(u)\ge(F(\hat x)-u)/(\lambda(1-u))$ である。 $\lambda=1$ 、 $u=1-10^{-6}$ とすると $Q_F(u)=6\log10\approx13.8155$ であり、 $F(\hat x)-u=10^{-12}$ を満たす $\hat x\ge Q_F(u)$ は $\hat x-Q_F(u)\ge10^{-6}$ を満たす。 $b=14$ とすると $F(14)=1-e^{-14}>u$ であり、命題 4.3 (2)の上界は $10^{-12}e^{14}\approx1.2026\times10^{-6}$ である。命題 4.3 (1)の二分法の誤差の上界 $2^{-(n+1)}b$ は $F'$ を含まない。

命題 4.5. $\mu$ を $\R$ 上の Borel 確率測度、 $F(x):=\mu((-\infty,x])$ $(x\in\R)$ とし、 $(\Omega,\mathcal F,P)$ を確率空間とする。 $\hat U$ を $(0,1)$ に値をとる確率変数、 $\delta:=\sup_{0\le t\le1}\lvert P(\hat U\le t)-t\rvert$ 、 $\hat X:=Q_F(\hat U)$ とする。 $\eta\ge0$ とし、確率変数 $\tilde X$ はほとんど確実に $\lvert\tilde X-\hat X\rvert\le\eta$ を満たすとする。

すべての $x\in\R$ に対して $F(x-\eta)-\delta\le P(\tilde X\le x)\le F(x+\eta)+\delta$ である。
$\mu$ が密度 $f$ をもち、ある実数 $L\ge0$ についてすべての $x\in\R$ で $f(x)\le L$ であるならば、すべての $x\in\R$ に対して $\lvert P(\tilde X\le x)-F(x)\rvert\le\delta+L\eta$ である。

証明.(1)を示す。 $E:=\{\lvert\tilde X-\hat X\rvert\le\eta\}$ と置くと $P(E)=1$ である。 $E$ 上では、 $\hat X\le x-\eta$ ならば $\tilde X\le x$ であり、 $\tilde X\le x$ ならば $\hat X\le x+\eta$ である。したがって $P(\hat X\le x-\eta)\le P(\tilde X\le x)\le P(\hat X\le x+\eta)$ である。命題 4.1 (1)により $P(\hat X\le x-\eta)\ge F(x-\eta)-\delta$ かつ $P(\hat X\le x+\eta)\le F(x+\eta)+\delta$ である。

(2)を示す。 $F(x+\eta)-F(x)=\mu((x,x+\eta])=\int_{(x,x+\eta]}f\le L\eta$ であり、同様に $F(x)-F(x-\eta)\le L\eta$ である。(1)と合わせて $F(x)-L\eta-\delta\le P(\tilde X\le x)\le F(x)+L\eta+\delta$ を得る。▨

例 4.6. $\mu:=\delta_0$ とすると $F=\mathbf 1_{[0,\infty)}$ であり、すべての $u\in(0,1)$ で $Q_F(u)=0$ である。 $\eta>0$ とし、 $\hat U$ を $(0,1)$ に値をとり $U[0,1]$ に従う確率変数とすると、命題 4.5の $\delta$ は $0$ である。 $\tilde X:=\eta$ と置くと $\lvert\tilde X-Q_F(\hat U)\rvert=\eta$ である。 $0\le x<\eta$ では $P(\tilde X\le x)=0$ 、 $F(x)=1$ であるから、 $\sup_{x\in\R}\lvert P(\tilde X\le x)-F(x)\rvert=1$ であり、この値は $\eta$ によらない。命題 4.5 (1)の両端は $x=0$ で $F(-\eta)=0$ と $F(\eta)=1$ である。 $\mu$ は Lebesgue 密度をもたないので、命題 4.5 (2)は適用されない。

例 4.7. $F$ を $\operatorname{Exp}(1)$ の分布関数とし、 $M:=2^{32}$ とし、 $\hat U$ を $H_M$ に値をとり $H_M$ 上の一様分布に従う確率変数とする。命題 4.1 (2)により、命題 4.5の $\delta$ は $2^{-33}$ である。 $H_M$ の最大元は $1-2^{-33}$ であり、 $e^{-24}\approx3.78\times10^{-11}<2^{-33}\approx1.16\times10^{-10}$ から、すべての $u\in H_M$ で $F(0)=0<u<F(24)$ である。 $F$ は $[0,24]$ 上で連続かつ狭義単調増加である。各 $u\in H_M$ に対して、命題 4.3 (1)の二分法を $[0,24]$ 上で厳密算術により実行し、段 $40$ までに停止すればその出力を、停止しなければ $m_{40}$ を $\beta(u)$ とする。 $\hat U$ は有限集合 $H_M$ に値をとるので、 $\tilde X:=\beta(\hat U)$ はすべての $\omega\in\Omega$ で定まる確率変数であり、命題 4.3 (1)によりすべての $\omega\in\Omega$ で $\lvert\tilde X-Q_F(\hat U)\rvert\le2^{-41}\cdot24=3\cdot2^{-38}$ である。 $\operatorname{Exp}(1)$ の密度は $1$ 以下であるから、命題 4.5 (2)により

\sup_{x\in\R}\lvert P(\tilde X\le x)-F(x)\rvert\le2^{-33}+3\cdot2^{-38}=35\cdot2^{-38}\approx1.27\times10^{-10}

である。

5 演習

問題 5.1.命題 2.1の証明を完成させよ。

解答.

命題 2.1 (1)を示す。 $(\mathcal G_i)_{i\in I}$ の相互独立性は、相異なる有限個の添字と各 $\mathcal G_i$ の事象に対する積の公式であり、§E11.13 補題 4.1が仮定する独立性と同じ条件である。 $q\ge1$ とし、相異なる $s_1,\ldots,s_q\in S$ をとる。 $J_{s_1},\ldots,J_{s_q}$ は二つずつ交わらない $I$ の空でない有限部分集合であるから、§E11.13 補題 4.1により、 $E_t\in\mathcal H_{s_t}$ $(1\le t\le q)$ に対して $P\bigl(\bigcap_{t=1}^qE_t\bigr)=\prod_{t=1}^qP(E_t)$ である。相異なる $s_1,\ldots,s_q$ は任意であるから、§E11.7 定義 1.1により $(\mathcal H_s)_{s\in S}$ は相互独立である。

命題 2.1 (2)を示す。 $s\in S$ とし、 $W_{J_s}:=(W_{i_{s,1}},\ldots,W_{i_{s,p_s}})\colon\Omega\to\R^{E_s}$ と置く。Borel 集合 $C_l\subset\R^{e_{i_{s,l}}}$ $(1\le l\le p_s)$ に対して $W_{J_s}^{-1}(C_1\times\cdots\times C_{p_s})=\bigcap_lW_{i_{s,l}}^{-1}(C_l)\in\mathcal H_s$ である。 $W_{J_s}^{-1}(C)\in\mathcal H_s$ を満たす Borel 集合 $C\subset\R^{E_s}$ の全体はシグマ加法族をなし、このような直積をすべて含む。 $\R^{E_s}$ の半開直方体は、各 $l$ について $\R^{e_{i_{s,l}}}$ の半開直方体 $C_l$ をとった直積 $C_1\times\cdots\times C_{p_s}$ であり、各 $C_l$ は Borel 集合であるから、このシグマ加法族は半開直方体の有限非交和の全体 $\mathcal R_{E_s}$ を含む。§E9.4 定理 3.3により $\sigma(\mathcal R_{E_s})=\mathcal B(\R^{E_s})$ であるから、このシグマ加法族は $\mathcal B(\R^{E_s})$ に等しい。したがって、Borel 集合 $B\subset\R^{m_s}$ に対して $Z_s^{-1}(B)=W_{J_s}^{-1}(h_s^{-1}(B))\in\mathcal H_s$ であり、 $\sigma(Z_s)\subset\mathcal H_s$ である。相異なる $s_1,\ldots,s_q$ と $F_t\in\sigma(Z_{s_t})$ に対して $F_t\in\mathcal H_{s_t}$ であるから、命題 2.1 (1)により積の公式が成り立つ。▨

問題 5.2.命題 1.4 (4)を示せ。

解答.

$c_0=0<u$ と $c_n=1\ge u$ から、 $t=0$ で $\ell_t<h_t$ かつ $c_{\ell_t}<u\le c_{h_t}$ である。 $h_t-\ell_t\ge2$ でこの二条件が成り立つとすると、 $\ell_t+1\le m_t\le(\ell_t+h_t)/2<h_t$ であり、 $c_{m_t}\ge u$ ならば $(\ell_{t+1},h_{t+1})=(\ell_t,m_t)$ 、 $c_{m_t}<u$ ならば $(\ell_{t+1},h_{t+1})=(m_t,h_t)$ であるから、二条件は $t+1$ でも成り立つ。 $w_t:=h_t-\ell_t$ と置くと、 $m_t-\ell_t=\lfloor w_t/2\rfloor$ 、 $h_t-m_t=\lceil w_t/2\rceil$ であるから $w_{t+1}\le\lceil w_t/2\rceil$ である。 $w_t\ge2$ ならば $\lceil w_t/2\rceil<w_t$ であり、 $w_t\ge1$ がつねに成り立つから、手続きは有限回で $w_t=1$ となって終わる。

$N:=\lceil\log_2n\rceil$ と置くと $w_0=n\le2^N$ である。 $w_t\le2^j$ かつ $j\ge1$ ならば $w_{t+1}\le\lceil2^j/2\rceil=2^{j-1}$ であるから、比較を $t$ 回行った後も続くならば $2\le w_t\le2^{N-t}$ であり、 $t\le N-1$ である。比較の回数を $T$ とすると、 $T\ge1$ のとき $T-1$ 回の比較の後に手続きは続いているから $T-1\le N-1$ であり、 $T\le N$ である。終わったとき $h_t=\ell_t+1$ かつ $c_{h_t-1}<u\le c_{h_t}$ であるから、命題 1.4 (1)により $h_t=J(u)$ である。▨

問題 5.3. $M\in\NN$ とし、 $\hat U$ を $(0,1)$ に値をとる確率変数で、その値の集合が高々 $M$ 個の元からなるものとする。 $\delta:=\sup_{0\le t\le1}\lvert P(\hat U\le t)-t\rvert$ に対して $\delta\ge1/(2M)$ であることを示せ。

解答.

$\hat U$ の値の集合を $\{v_1,\ldots,v_k\}$ 、 $0<v_1<\cdots<v_k<1$ 、 $1\le k\le M$ とし、 $G(t):=P(\hat U\le t)$ と置く。 $G$ は $[0,v_1)$ で $0$ 、 $[v_k,1]$ で $1$ であり、 $1\le i\le k-1$ に対して $[v_i,v_{i+1})$ 上で定数 $\gamma_i$ である。 $t\in[0,v_1)$ では $t=\lvert G(t)-t\rvert\le\delta$ であるから $v_1\le\delta$ である。 $t=v_k$ では $1-v_k\le\delta$ である。 $t\in[v_i,v_{i+1})$ では $\gamma_i-\delta\le t\le\gamma_i+\delta$ であるから、 $v_{i+1}-v_i\le2\delta$ である。したがって

1=v_1+\sum_{i=1}^{k-1}(v_{i+1}-v_i)+(1-v_k)\le\delta+2(k-1)\delta+\delta=2k\delta\le2M\delta

であり、 $\delta\ge1/(2M)$ である。命題 4.1 (2)により、 $H_M$ 上の一様分布はこの下界に等しい $\delta$ を与える。▨

§E20.34確率分布からの標本生成

1 一般化逆関数

2 独立な入力と棄却法

3 正規分布に従う標本

4 格子と求根の誤差

5 演習

前提記事