Unformatted text preview:

27-1©2006 Raj JainCSE574sWashington University in St. LouisTesting RandomTesting Random--Number GeneratorsNumber GeneratorsRaj Jain Washington UniversitySaint Louis, MO [email protected] slides are available on-line at:http://www.cse.wustl.edu/~jain/cse574-06/27-2©2006 Raj JainCSE574sWashington University in St. LouisOverviewOverview1. Chi-square test2. Kolmogorov-Smirnov Test3. Serial-correlation Test4. Two-level tests5. K-dimensional uniformity or k-distributivity6. Serial Test7. Spectral Test27-3©2006 Raj JainCSE574sWashington University in St. LouisTesting RandomTesting Random--Number GeneratorsNumber GeneratorsGoal: 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 ≠ GoodFail ⇒ Bad ! New tests ⇒ Old generators fail the test ! Tests can be adapted for other distributions27-4©2006 Raj JainCSE574sWashington University in St. LouisChiChi--Square TestSquare Test! Most commonly used test! Can be used for any distribution! Prepare a histogram of the observed data! Compare observed frequencies with theoreticalk = Number of cellsoi= Observed frequency for ith cellei= 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 less27-5©2006 Raj JainCSE574sWashington University in St. LouisExample 27.1Example 27.1! 1000 random numbers with x0 = 1!!Observed difference = 10.380! Observed is Less ⇒ Accept IID U(0, 1)27-6©2006 Raj JainCSE574sWashington University in St. LouisChiChi--Square for Other DistributionsSquare for Other Distributions! Errors in cells with a small eiaffect 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 cells27-7©2006 Raj JainCSE574sWashington University in St. LouisKolmogorovKolmogorov--Smirnov TestSmirnov 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.27-8©2006 Raj JainCSE574sWashington University in St. LouisKolmogorovKolmogorov--Smirnov TestSmirnov 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-127-9©2006 Raj JainCSE574sWashington University in St. LouisExample 27.2Example 27.230 Random numbers using a seed of x0=15:! The numbers are:14, 11, 2, 6, 18, 23, 7, 21, 1, 3, 9, 27, 19, 26, 16, 17, 20, 29, 25, 13, 8, 24, 10, 30, 28, 22, 4, 12, 5, 15.27-10©2006 Raj JainCSE574sWashington University in St. LouisExample 27.2 (Cont)Example 27.2 (Cont)The normalized numbers obtained by dividing the sequence by 31 are:0.45161, 0.35484, 0.06452, 0.19355, 0.58065, 0.74194, 0.22581, 0.67742, 0.03226, 0.09677, 0.29032, 0.87097, 0.61290, 0.83871, 0.51613, 0.54839, 0.64516, 0.93548, 0.80645, 0.41935, 0.25806, 0.77419, 0.32258, 0.96774, 0.90323, 0.70968, 0.12903, 0.38710, 0.16129, 0.48387.27-11©2006 Raj JainCSE574sWashington University in St. LouisExample 27.2 (Cont)Example 27.2 (Cont)! K[0.9;n]value for n = 30 and a = 0.1 is 1.0424! Observed<Table⇒ Pass27-12©2006 Raj JainCSE574sWashington University in St. LouisChiChi--square vs. Ksquare vs. K--S TestS Test27-13©2006 Raj JainCSE574sWashington University in St. LouisSerialSerial--Correlation TestCorrelation Test! Nonzero covariance ⇒ Dependence. The inverse is not true! Rk= Autocovariance at lag k = Cov[xn, xn+k]! For large n, Rkis normally distributed with a mean of zero and a variance of 1/[144(n-k)]! 100(1-α)% confidence interval for the autocovariance is:For k≥ 1 Check if CI includes zero! For k = 0, R0= variance of the sequence Expected to be 1/12 for IID U(0,1)27-14©2006 Raj JainCSE574sWashington University in St. LouisExample 27.3: Serial Correlation TestExample 27.3: Serial Correlation Test10,000 random numbers with x0=1:27-15©2006 Raj JainCSE574sWashington University in St. LouisExample 27.3 (Cont)Example 27.3 (Cont)! All confidence intervals include zero ⇒ All covariances are statistically insignificant at 90% confidence.27-16©2006 Raj JainCSE574sWashington University in St. LouisTwoTwo--Level TestsLevel Tests! If the sample size is too small, the test results may apply locally, but not globally to the complete cycle.! Similarly, global test may not apply locally! Use two-level tests⇒ Use Chi-square test on n samples of size k each and then use a Chi-square test on the set of n Chi-square statistics so obtained⇒ Chi-square on Chi-square test.! Similarly, K-S on K-S! Can also use this to find a ``nonrandom'' segment of an otherwise random sequence.27-17©2006 Raj JainCSE574sWashington University in St. Louiskk--DistributivityDistributivity! k-Dimensional Uniformity! Chi-square ⇒ uniformity in one dimension⇒ Given two real numbers a1and b1between 0 and 1 such that b1> a1! This is known as 1-distributivity property of un.! The 2-distributivity is a generalization of this property in two dimensions:For all choices of a1, b1, a2, b2in [0, 1], b1>a1and b2>a227-18©2006 Raj JainCSE574sWashington University in St. Louiskk--Distributivity (Cont)Distributivity (Cont)! k-distributed if:! For all choices of ai, biin [0, 1], with bi>ai, i=1, 2, ..., k. ! k-distributed sequence is always (k-1)-distributed. The inverse is not true. ! Two tests:1. Serial test2. Spectral test3. Visual test for 2-dimensions: Plot successive overlapping pairs of numbers27-19©2006 Raj JainCSE574sWashington University in St. LouisExample 27.4Example 27.4! Tausworthe sequence generated by:! The sequence is k-distributed for k up to d /l e, that is, k=1.! In two dimensions: Successive


View Full Document

WUSTL CSE 567M - Testing Random- Number Generators

Documents in this Course
Load more
Download Testing Random- Number Generators
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Testing Random- Number Generators and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Testing Random- Number Generators 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?