Simulation Formula Sheet Spring, 2003

Linear Congruential Random Number Generators.  Xn+1 = aXn + c  (mod m)

Inverse Transform Method   U = F(X)  or X = F-1(U)

# Rejection Method. Pick c ³ f(x)/g(x).  Sample g(x) to get Y. Accept Y as a sample of f(x)  if U £ f(Y)/cg(Y)

Squeeze Method:  If g(x) = f(x)/ch(x), find  gL(x) £ g(x) £ gH(x).  To avoid calculating g(y) in the A-R method, test u £ gL(y) and u > gH(y)

Pr[Lo] = òmax{0,gL(x)}h(x)dx; Pr[Hi] = òmin{1,gH(x)}h(x)dx

Polar Method:  v1 = 2u1 – 1, v2 = 2u2 – 1;  s = v12 + v22 £ 1

z1 = v1(-2lns/s)1/2;         z2 = v2(-2lns/s)1/2

Choleski Method (Mulivariate Normal Distribution ).  Given the covariance matrix å = (sij), and the vector of means m = (m1,…, mn)T:

Factor å = CCT, where C is lower triangular.

Obtain a vector z = (z1,…,zn)T with zi iid from standard normal

x = Cz + m  samples the multivariate distribution.

Convolution Method: h(z) = òf(z-w)g(w)dw  is the pdf for Z = X + Y

Composition Method: f(x) = Saif(x)

Hit or Miss.  q =

Crude Monte Carlo.

Stopping Criteria. Pr(½ - q½ ³ d) £ a.  Use Chebyshev:   Pr(½ - m½ ³ ks/Ön) £ 1/k2.                or Normal Approximation

# Recursion formulas

k+1 = (kk + Xk+1)/(k+1)

Sk+12 = Sk2(k-1)/k  +  ( 1+k) (k+1 - k)2

# Mean Square Error

MSE(F) = EF(g(X1,…,Xn) - q(F))2

# Bootstrap Approximation

MSE(Fe) = EFe(g(X1,…,Xn) - q(Fe))2

# Goodness of Fit

Discrete case:  T = S(Ni – npi)2/npi    (Chi-square with m-1-k degrees of freedom)

Continuous case: D = Maxx½Fe(x) – F(x)½ p-value = P(D ³ d) is independent of F

Two-Sample Test

R = sum of ranks in 1st sample  p-value = 2Min{P(R £ r), P(R ³ r)}

Pn,m(r) = [n/(n+m)]Pn-1,m(r-n-m) + [m/(n+m)]Pn,m-1(r) , where

P1,0(k) = 0 if k £ 0; = 1 otherwise;        P0,1(k) = 0 if k < 0, = 1 otherwise.

Kruskal-Wallace (multiple sample) R = (12/N(N+1))S(Ri – Ni(N+1)/2)2/Ni