ñòð. 1 |

â€¢ DIEHARD TESTS (Marsaglia, 1985)

See http://stat.fsu.edu/˜geo/diehard.html

NIST Test suite- 16 tests on the sequences

of bits

http://csrc.nist.gov/rng/

Test U01 Includes the above tests.

http://www.iro.umontreal.ca/˜lecuyer/

Numerical Recipes

â€¢ Provides C or Fortran Code for a number

of numerical routines including random

number generators

â€¢ http:\\lib-www.lanl.gov/numerical/bookcpdf.html

Increasing period of generator-

shuffling

Example of shuffling

Sums or differences mod(m)

(see Fishman Sect. 7.13)

Generating non-uniform random

variates.

The inverse transform

Inverse transform for a

Continuous Distribution

Suppose we wish to generate a random variable

from a distributi on with

probabilit y density function f ( x ) = x / 2, 0 < x < 2.

Then the c.d.f. is

F ( x ) = x / 4, for 0 < x < 2.

2

Inverse

âˆ’1

F (U ) = 2 U so

X = 2 U where U is U [0,1]

is the required generator.

Example: Inverse transform for

a discrete distribution

Consider the distribution with probability function

P[ X = x] = x / 10, for x = 1,2,3,4.

Then the inverse transform method results in the generator

U < .1

âŽ§1

âŽª2 .1 â‰¤ U < .3

âŽª

âˆ’1

X = F (U ) = âŽ¨

.3 â‰¤ U < .6

3

âŽª

âŽª4 .6 â‰¤ U

âŽ©

Graph of c.d.f

Exponential distribution

generator.

Geometric Distribution Generator

Geometric( p ) Distributi on has probabilit y function

x âˆ’1

f ( x ) = (1 âˆ’ p ) p , for x = 1,2,...

The cumulative distributi on function is

F ( x ) = 1 âˆ’ (1 âˆ’ p ) , where [ ] denotes the integer part .

[x ]

Then, solving for an integer j such that

F(j - 1) < U â‰¤ F(j) gives

âŽ¡ log(1 - U) âŽ¤

âŽ¥ where âŽ¡ âŽ¤ denotes ceiling.

j= âŽ¢

âŽ¢ log(1 - p) âŽ¥

Binomial generators

â€¢ Binomial(n,p), n small -inverse transform

or use n

X = âˆ‘ I (U i < p )

i =1

â€¢ Binomial(n,p), n large, p small

âŽ¡ log(1 - U i ) âŽ¤

x +1

X = inf{x; âˆ‘ Gi > n}, where Gi = âŽ¢ âŽ¥ geometric ( p )

âŽ¢ log(1 - p) âŽ¥

i =1

â€¢ acceptance-rejection

Cauchy

What if increments in a time

series returns have a Cauchy

distribution????

plot(10+cumsum(.001./tan(pi*rand(1,10000))))

Generators in Matlab and R(Splus)

Acceptance Rejection

Acceptance-rejection (cont)

Acceptance-rejection

â€¢Suppose a probability â€¢ Generate a point at

density f(x) has c.d.f. random (uniformly)

that is NOT easily under the graph of f(x)

inverted. We cannot use and output the X

inverse transform. coordinate (how?)

â€¢How do we use the â€¢Pick the point at

above theorem to random uniformly in

generate X from f(x)? some larger region and

use it only if it is under

f(x)

Example

â€¢Generate X U[a,b]

â€¢Generate Y U[0,c]

â€¢If Y<f(X), then accept

(i.e. output ) X

â€¢otherwise generate

new values of X,Y and

continue until one is

accepted.

Acceptance-Rejection: Discrete

Random variables

Want to generate X such that P[ X = i ] = pi .

We are able easily to generate Y with P[Y = i ] = qi .

pi

â‰¤ c.

Suppose there is some constant c such that

qi

Method

Generate Y = i, say

Accept this value (i.e. put X = i ) with probability pi / cqi .

Otherwise generate new Y.

Example: acceptance

rejection for discrete random

variables

â€¢ E.g. generate r.v. X with probability function

k

P[ X = i ] = , i = 1,2,...,100 where

i

1 k

k = 0.1928. Here qi = , pi = ,

100 i

pi pi 1

â‰¤ c = 100k = 19.3 for all i = 1,...,100 and =.

qi cqi i

y<-ceiling(100*runif(100000));

x<-y[runif(100000)<=1/y];

â€¢hist(x, freq = FALSE, breaks = 50)

When to use acceptance-rejection

(discrete or continuous)

â€¢ The c.d.f. F(x) is â€¢ It is easy (e.g. by

ñòð. 1 |