27-1©2011 Raj JainCSE574sWashington University in St. LouisTesting RandomTesting Random--Number GeneratorsNumber GeneratorsRaj Jain Washington UniversitySaint Louis, MO [email protected]/Video recordings of this lecture are available at:http://www.cse.wustl.edu/~jain/cse567-11/27-2©2011 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©2011 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©2011 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©2011 Raj JainCSE574sWashington University in St. LouisExample 27.1Example 27.1 1000 random numbers with x0 = 1Observed difference = 10.380 Observed is Less ⇒ Accept IID U(0, 1)27-6©2011 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©2011 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©2011 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©2011 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©2011 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©2011 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©2011 Raj JainCSE574sWashington University in St. LouisChiChi--square vs. Ksquare vs. K--S TestS Test27-13©2011 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©2011 Raj JainCSE574sWashington University in St. LouisExample 27.3: Serial Correlation TestExample 27.3: Serial Correlation Test10,000 random numbers with x0=1:27-15©2011 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©2011 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©2011 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©2011 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©2011 Raj JainCSE574sWashington University in St. LouisExample 27.4Example 27.4
View Full Document
Unlocking...