添付ファイル '116 �A���n�A���S���Y�� ��10��m�[�g.html'

ダウンロード

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法（ぼっくすまらーほう）
    • 独立な2つの標準正規乱数が同時に得られる
    • 一様乱数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)
      1. q(x)に従う乱数x, [0, 1)の一様乱数u
      2. 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)の絶対値が大きい部分をサンプリングしやすくなるから)
      • 加重サンプリング
      • 層別サンプリングの一種

添付ファイル

添付ファイルを参照するには、(下のファイル一覧にあるように)attachment:filenameと記述します。 [get]リンクのURLは変更される可能性が高いので、利用しないでください。

ファイルを添付する権限がありません。