CPE 619 Testing Random-Number GeneratorsOverviewTesting Random-Number GeneratorsChi-Square TestExample 27.1Chi-Square for Other DistributionsKolmogorov-Smirnov TestSlide 8Example 27.2Example 27.2 (cont’d)Slide 11Chi-square vs. K-S TestSerial-Correlation TestExample 27.3: Serial Correlation TestExample 27.3 (cont’d)Two-Level Testsk-Distributivityk-Distributivity (cont’d)Example 27.4Example 27.5Serial TestSerial Test (cont’d)Spectral TestExample 27.6: Spectral TestExample 27.6 (cont’d)Spectral Test (More)Example 27.7Example 27.7 (cont’d)Slide 29Slide 30Slide 31Slide 32Slide 33SummaryRandom Variate GenerationSlide 36Random-Variate GenerationInverse TransformationProofExample 28.1Example 28.2Example 28.2 (cont’d)Applications of the Inverse-Transformation TechniqueRejectionSlide 45CompositionSlide 47Example 28.4ConvolutionConvolution: ExamplesCharacterizationSlide 52Summary (cont’d)Homework #6CPE 619Testing Random-Number GeneratorsAleksandar MilenkovićThe LaCASA LaboratoryElectrical and Computer Engineering DepartmentThe University of Alabama in Huntsvillehttp://www.ece.uah.edu/~milenkahttp://www.ece.uah.edu/~lacasa2OverviewChi-square testKolmogorov-Smirnov TestSerial-correlation TestTwo-level testsK-dimensional uniformity or k-distributivitySerial TestSpectral Test3Testing Random-Number 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 distributions4Chi-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 less5Example 27.11000 random numbers with x0 = 1 Observed difference = 10.380 Observed is Less  Accept IID U(0, 1)6Chi-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 cells7Kolmogorov-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 small8Kolmogorov-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-19Example 27.230 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.10Example 27.2 (cont’d)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.11Example 27.2 (cont’d)K[0.9;n] value for n = 30 and a = 0.1 is 1.0424Observed<TablePass12Chi-square vs. K-S Test13Serial-Correlation TestNonzero covariance Dependence. The inverse is not trueRk = Autocovariance at lag k = Cov[xn, xn+k]For large n, Rk is 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)14Example 27.3: Serial Correlation Test10,000 random numbers with x0=1:15Example 27.3 (cont’d)All confidence intervals include zero  All covariances are statistically insignificant at 90% confidence.16Two-Level 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.17k-Distributivityk-Dimensional UniformityChi-square  uniformity in one dimension Given two real numbers a1 and b1 between 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, b2 in [0, 1], b1>a1 and b2>a218k-Distributivity (cont’d)k-distributed if:For all choices of ai, bi in [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 numbers19Example 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 overlapping pairs (xn, xn+1)20Example 27.5Consider the polynomial:Better 2-distributivity than Example 27.421Serial TestGoal: To test for uniformity in two dimensions or higher.In two dimensions, divide the space between 0 and 1 into K2 cells of equal area xn +1xn22Serial Test (cont’d)Given {x1, x2,…, xn}, use n/2 non-overlapping pairs (x1, x2), (x3, x4), … and count the points in each of the K2