問題
は互いに独立な
区間内の値における一様乱数である。この2つを用いて
内における一様乱数を作れ
解答
他に作り方はいくらでもあるかもしれないが、そのうちの1つは以下のようになる。
$$(X,Y)=(\sqrt{A}\cos{(2\pi B)},\sqrt{A}\sin{(2\pi B)})$$
証明
とりあえず特性関数が同じであることを示せばOK
一様乱数の特性関数は以下のようになる。
$$f(p,q)=\iint_D \frac{1}{\pi}\exp(i(px+qy))dxdy$$
$$=\int_{0}^{2\pi}\int_{0}^{1}\frac{1}{\pi}\exp(ir(p\cos{\theta}+q\sin{\theta}))rdrd\theta$$
先程解答にあげたやつの特性関数は以下のようになる。
$$f(p,q)=\int_{0}^{1}\int_{0}^{1}\exp(i\sqrt{a}(p\cos(2\pi b)+q\sin(2\pi b)))dbda$$
ここで、という置換をする。このとき
は
から
までで
は
から
までで
となるため、これは
$$f(p,q)=\int_{0}^{2\pi}\int_{0}^{1}\exp(ir(p\cos\theta+q\sin\theta))\frac{2r}{2\pi}drd\theta$$
$$f(p,q)=\int_{0}^{2\pi}\int_{0}^{1}\frac{1}{\pi}\exp(ir(p\cos\theta+q\sin\theta))rdrd\theta$$
よって2つの特性関数は一致するため、分布は一致する。
一般化
n次元単位球内での一様分布を作るにはどうしたらいいか
$$D=\{(x_1,\ldots,x_n)\in\mathbb{R}^n|x_1^2+\cdots+x_n^2\leq 1\}$$
内での一様分布について考える。
結論としては、恐らく
という
上で一様分布を取るような乱数を持ってきたとき
$$\sqrt[n]{U}\omega$$
とすれば多分OKっぽい。ここでは
上の一様乱数である。
また、の生成も難しくはない。
という正規乱数を用意した時、（正規乱数自体はボックスミューラー法で生成することができる。）
$$\omega=\frac{1}{\sqrt{X_1^2+\cdots+X_n^2}}\left(X_1,\ldots,X_n\right)$$
とすればOKである。
ここで、
$$\int_{\partial D}d\omega=1$$
に注意
以下軽く証明
一様分布における特性関数は以下のようになる。
$$\int_{D}\frac{1}{V_n}\exp(i(\xi_1x_1+\cdots\xi_nx_n))dx_1\cdots x_n$$
$$=\int_{0}^{1}\int_{\partial D}\frac{1}{V_n}\exp(ir(\xi,\omega))S_nd\omega r^{n-1}dr$$
と置換すると
より
$$=\int_{0}^{1}\int_{\partial D}\frac{S_n}{nV_n}\exp(i(\xi,\sqrt[n]{u}\omega))d\omega du$$
ここで、となっているため、*2
$$=\int_{0}^{1}\int_{\partial D}\exp(i(\xi,\sqrt[n]{u}\omega))d\omega du$$
よりこれはの特性関数となっている。
重要性
2次元の単位円内部では以下のように生成すればOKである。
①という
内での一様分布を持ってくる（
は独立）
②なら
を出力して終了
③なら①に戻ってやり直す
このような方法で生成するとき、理論上無限回の処理が必要になるかもしれない。しかし平均では回で処理が終わることになる。*3この時点では現実的なアルゴリズムで問題ない。
しかしn次元に一般化すると以下のようになるはずである。
①という
内での一様分布を持ってくる（
は互いに独立）
②なら
を出力して終了
③なら①に戻ってやり直す
この場合だとn次元球面の体積をとしたとき、平均で
回の処理が必要になる。
という評価ができるため、nが十分大きい状況を考えた時に必要な処理回数は発散してしまう。要はアルゴリズムとして高速ではなくなる。
そこで今回紹介した手法を使うと、一様乱数を高速に生成することができるのである。
