Algorithms Flashcards
Inversion algorithm
- generate U
- set X = F-1(U)
Rejection algorithm
- Find eneveloppe g
- Find M = sup f/g
- Generate Y from g (inversion)
- Generate U
- if u <= f/gM, set X=y
Box-Muller to generate (X,Y) from N(0,1)
- Generate U1 and U2
- Set R=(-2log(U2))^(1/2) and A = 2piU1
- Set X=Rcos(A) and Y=Rsin(A)
Polar Marsaglia to generate (X,Y) from N(0,1)
- Generate U1 and U2
- Set V1 = 2U1 - 1 and V2 = 2U2 - 1
- if S = V1^2 + V2^2 <= 1,
X = (-2/S log(S))^(1/2) V1 = R cos(A) = R V1 / S^(1/2)
Y = (-2/S log(S))^(1/2) V2 = R sin(A) = R V2 / S^(1/2) - otherwise GO TO 1.
Composition f = pi_1 f_1 + … + pi_k f_k
where sum pi_i = 1
- pick i with probability pi_i (using uniform)
- Generate from f_i using rejection
How to prove Box-Muller and Polar Marsaglia
using Jacobian matrix wrt
- U1 and U2 for Box-Muller
- V1 and V2 for Polar Marsaglia
Generate from Poisson from a to b (homogeneous and non-homogeneous)
homogeneous:
- draw N from Poi(lambda (b-a))
- generate Xi from U(a,b) for i=1,…,N
non-homogeneous:
- draw N from Poi(m(b-a)) where m is integral of lambda(t) from a to b
- generate Xi from U(a,b) for i=1,…,N
- accept if u <= lambda(xi) / sup lambda
Generate ordered uniform (to then generate ordered X from inversion)
- U(n) = Un^(1/n)
- U(k) = U(k+1) Uk^(1/k) for k < n
think of proof this is ordered
Generate from discrete
- using rejection : with F-1x(u) = min{x : Fx(x) >=u}
- using RL method
Pros and cons of rejection
cf. revision
Pros and cons of inversion
cf. revision
Pros and cons of Polar-Marsaglia
cf. revision
Pros and cons of Box-Muller
cf. revision
Proof of Box-Muller
cf. revision
Proof of Polar-Marsaglia
cf. revision
