Testing Random Number Generators - Rice University

Testing Random Number Generators

Dr. John Mellor-Crummey

Department of Computer Science Rice University

johnmc@cs.rice.edu

COMP 528 Lecture 22 12 April 2005

Testing Random Number Generators

Does observed data satisfies a particular distribution?

? Chi-square test ? Kolmogorov-Smirnov test ? Serial correlation test ? Two-level tests ? K-distributivity ? Serial test ? Spectral test

2

Chi-Square Test

? Designed for testing discrete distributions, large samples ? General test: can be used for testing any distribution

--uniform random number generators

--random variate generators

# ?

The statistical test:

n (oi

k=1

" ei)2 ei

< $2 [1"% ;k "1]

?

? Components

--k is the number of bins in the histogram

?

--oi --ei

is is

the the

number

n!umber

of of

observed expected

values values

in in

bin bin

i i

in in

the the

histogram histogram

The test

--if

the

sum

is

less

than

"2 [1#$

;k#1],

then

the

hypothesis

that

the

observations come from the specified distribution cannot be

rejected at a level of significance

3

!

Chi-Square Constraints

? Data must be a random sample of the population

--to which you wish to generalize claims

? Data must be reported in raw frequencies (not percentages) ? Measured variables must be independent ? Values/categories on independent and dependent variables

-- must be mutually exclusive and exhaustive

? Observed frequencies cannot be too small ? Use Chi-square test only when observations are independent:

--no category or response is influenced by another

? Chi-square is an approximate test of the probability of getting the

frequencies you've actually observed if the null hypothesis were true

--based on the expectation that within any category, sample frequencies are normally distributed about the expected population value

--distribution cannot be normal when expected population values are close to zero since frequencies cannot be negative

--when expected frequencies are large, there is no problem with the assumption of normal distribution 4

Chi-Square Test of Matlab's U(0,1)

[n,x] = hist(rand(1000,1),30) bar(x,n) e = 1000/30.0

sum(power(n-e,2)/e) 17.900

"2 [.05;29]

=

17.708

<

17.900

<

"2 [.10;29]

=

19.768

According to the result of the Chi-Square test, we can reject the null hypothesis that Matlab's random number generator generates uniform random numbers with only 5% confidence.

5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download