一般の離散分布の従う乱数の発生させる方法

エイリアス法は有限要素の離散分布を発生させる方法。一般の離散分布を発生できる。
http://amath.colorado.edu/courses/7400/2004fall/002/Web/SS-10.ppt

二者択一法ともいう。

(alias method)

基本は、npが平均が１になる性質を利用すして、乱数を一様分布にして、こまかく二者択一にもちこむ。

前提
確率：

• p(1),p(2),..,p(n)

値:

x(1),x(2),..,x(n)

の離散分布を発生させる。

事前にエイリアス値とエイリアス確率を決めておく。

エイリアス値

a(1),a(2),..a(n)

エイリアス確率

q(1),q(2),..q(n)

アルゴリズム
sが乱数。

1. iに１からnの乱数。
2. jに一様乱数。
3. j≦q(k)ならば、
　s=x(i)
それ以外なら
　s=a(i)
を出力

エイリアス確率とエイリアス値の計算

1.初期値
　q(k)=np(k)
a(k)=x(k)
2. ２つの集合にグループ分け
　H:{k:q(k)>１}
L:{k:q(k)≦１}
3.Hが要素を一つ選びiとする。Lから要素を選びjとする。
4.a(j)=x(i)
q(i)=q(i)-(1-q(j))
5. q(i)<1ならば、
　Lにiを加え、Hからiを削除する。
6.Lからjを削除する。
7. 3から5をHの要素数が0になるまで繰り返す。