1/16 連続系アルゴリズム 第10回ノート
- 0 ～ RAND_MAX 整数の一様乱数x
- u = x / ((double)RAND_MAX + 1.0)とすれば[0, 1)の一様乱数uが得られる
- 線形合同法
- x[n] = a * x[n - 1] + C mod m
- a : 乗数
- C : 加数
- m : 法
- C = 0のとき乗算合同法
- 周期：m回以下でもとの数字に戻る
- 確率密度p(x)に従う乱数がほしい
- 逆関数法
- 累積密度分布 f(x) = ∫[-∞, x]p(ξ)dξ
- f^(-1)(y) = inf {x | f(x) >= y}
- が計算できれば u in (0, 1)
- x = f^(-1)(u)
- Box-Muller法（ぼっくすまらーほう）
- 一様乱数u[1], u[2]から
- x[1] = sqrt(-2log(u[1]))cos(2πu2)
- x[2] = sqrt(-2log(u[1]))sin(2πu2)
- u[1] in (0, 1], u[2] in [0, 1)
- x = u[1] + u[2] + ・・・ + u[n] - b（ほぼ正規乱数。バグりにくいので確認に使える）
- 棄却法
- ほしい密度関数 p(x)
- ある密度関数 q(x)
- c : 定数, p(x) <= c * q(x)
- q(x)に従う乱数x, [0, 1)の一様乱数u
- u * c * q(x) <= p(x) ならxを採用。さもなくば棄却->１に戻ってやり直す。
- 例：
- 単位円内で一様分布がほしい
- [-1, 1] * [-1, 1]上の一様分布する乱数(x, y)を取り、x * x + y * y > なら棄却
- モンテカルロ法で円周率求めるあれ
- Monte Carlo法
- 確率分布p(x)に従う乱数x[i]（一様とは限らない）を発生させると
- I[N] = (Σ{i = 1 to N}f(x[i])) / N
- E(I[N]) = ∫f(x)p(x)dx
- 積分の近似とも考えられる
- σ[N] = sqrt((Σ{i = 1 to N}(f(x[i]) - I[N])^2))
- I[N] ± a * σ[N] / sqrt(N) (aは定数)
- N個の乱数で誤差O(1 / sqrt(N))
- p(x)を工夫すればaを小さくできる
- p(x)に従う乱数x[i]
- (Σ(f(x[i]) / p(x[i])) / N ≒ ∫(f(x) / p(x))dx
- p(x) ∝ |f(x)|のとき分散が最小になる(f(x)の絶対値が大きい部分をサンプリングしやすくなるから)
- 加重サンプリング
- 層別サンプリングの一種