Testing Random- Number Generators
[Pages:39]Testing RandomNumber Generators
Raj Jain Washington University Saint Louis, MO 63130
Jain@cse.wustl.edu
Audio/Video recordings of this lecture are available at:
Washington University in St. Louis
CSE574s
27-1
?2008 Raj Jain
Overview
1. Chi-square test 2. Kolmogorov-Smirnov Test 3. Serial-correlation Test 4. Two-level tests 5. K-dimensional uniformity or k-distributivity 6. Serial Test 7. Spectral Test
Washington University in St. Louis
CSE574s
27-2
?2008 Raj Jain
Testing Random-Number Generators
Goal: To ensure that the random number generator produces a random stream. ! Plot histograms ! Plot quantile-quantile plot ! Use other tests ! Passing a test is necessary but not sufficient ! Pass Good
Fail Bad ! New tests Old generators fail the test ! Tests can be adapted for other distributions
Washington University in St. Louis
CSE574s
27-3
?2008 Raj Jain
Chi-Square Test
! Most commonly used test ! Can be used for any distribution ! Prepare a histogram of the observed data ! Compare observed frequencies with theoretical k = Number of cells oi = Observed frequency for ith cell ei = Expected frequency
! D=0 Exact fit ! D has a chi-square distribution with k-1 degrees of freedom. Compare D with 2[1-; k-1] Pass with confidence if D is less
Washington University in St. Louis
CSE574s
27-4
?2008 Raj Jain
Example 27.1
! 1000 random numbers with x0 = 1
!
! Observed difference = 10.380
! Observed is Less Accept IID U(0, 1)
Washington University in St. Louis
CSE574s
27-5
?2008 Raj Jain
Chi-Square for Other Distributions
! Errors in cells with a small ei affect the chi-square statistic more
! Best when ei's are equal. Use an equi-probable histogram with variable cell sizes
! Combine adjoining cells so that the new cell probabilities are approximately equal.
! The number of degrees of freedom should be reduced to k-r-1 (in place of k-1), where r is the number of parameters estimated from the sample.
! Designed for discrete distributions and for large sample sizes only Lower significance for finite sample sizes and continuous distributions
! If less than 5 observations, combine neighboring cells
Washington University in St. Louis
CSE574s
27-6
?2008 Raj Jain
Kolmogorov-Smirnov Test
! Developed by A. N. Kolmogorov and N. V. Smirnov ! Designed for continuous distributions ! Difference between the observed CDF (cumulative distribution
function) Fo(x) and the expected cdf Fe(x) should be small.
Washington University in St. Louis
CSE574s
27-7
?2008 Raj Jain
Kolmogorov-Smirnov Test
! K+ = maximum observed deviation below the expected cdf ! K- = minimum observed deviation below the expected cdf
! K+ < K[1-;n] and K- < K[1-;n] Pass at level of significance. ! Don't use max/min of Fe(xi)-Fo(xi) ! Use Fe(xi+1)-Fo(xi) for K! For U(0, 1): Fe(x)=x ! Fo(x) = j/n,
where x > x1, x2, ..., xj-1
Washington University in St. Louis
CSE574s
27-8
?2008 Raj Jain
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- python random number between
- random number generator 1 10
- random number picker 1 100
- python random number in range
- random number from 1 to 100
- random number generator 1 50
- google random number generator
- random number generator list 1 10
- random number generator pairs
- pick random number between
- random number generators
- best random number generator