RANDOM NUMBERS

[Audio] Hello, this is a presentation on Random Numbers..

[Audio] Random Numbers and its properties, Pseudo Random Numbers A random number is a number chosen by chance. ie randomly, from a set of numbers. All the numbers in a specified distribution have an equal probability of being chosen randomly. For a number in a sequence or distribution to be truly random, it must be independent. Whereas, Pseudo means false, so false random numbers are being generated. The goal of any generation scheme is to produce a sequence of numbers between 0 and 1. When generating pseudo-random numbers, certain problems or errors can occur. These errors, or departures from ideal randomness, are all related to the properties stated previously. Some examples include the following: 1. The generated numbers may not be uniformly distributed. 2. The mean of the generated numbers may be too high or too low. 3. The variance of the generated numbers may be too high or low 4. There may be dependence..

[Audio] Method of Generation of Random numbers 1. Tabulation Method 2. Mid Square Method 3. Linear Congruential Method.

[Audio] Method of generating Random Numbers Linear congruential Method. The linear congruential method, produces a sequence of integers, X\, X2,... between zero and m — 1 according to the following recursive relationship: Xi+1 = (a Xi + c) mod m, i = 0,1, 2,...( 7.1) The initial value X0 is called the seed, a is called the constant multiplier, c is the increment, and m is the modulus. If c ≠ 0 is in Equation (7.1), the form is called the mixed congruential method. When c = 0, the form is known as the multiplicative congruential method. The selection of the values for a, c, m and Xo drastically affects the statistical properties and the cycle length. . An example will illustrate how this technique operates..

[Audio] example: Use the linear congruential method to generate a sequence of random numbers with X0 = 27,a= 17, c = 43, and m = 100. The sequence of Xi and subsequent Ri values is computed as follows: X0 = 27 X1 = ( 17.27 + 43) mod 100 = 502 mod 100 = 2 R1= 2⁄100=0. 02 X2 = ( 17 • 2 + 43) mod 100 = 77 mod 100 = 77 R2=77 ⁄100= 0. 77 *[ 3pt] X3 = (17•77+ 43) mod 100 = 1352 mod 100 = 52 R3=52 ⁄ 100=0. 52.

[Audio] Tests for Random Numbers The desirable properties of random numbers — are uniformity and independence. To insure that these desirable properties are achieved, a number of tests can be performed. The tests can be placed in two categories according to the properties of interest, The first entry in the list below concerns testing for uniformity. The second through fifth entries concern testing for independence. The five types of tests 1. Frequency test Uses the Kolmogorov-Smirnov or the chi-square test to compare the distribution of the set of numbers generated to a uniform distribution. 2. Runs test Tests the runs up and down or the runs above, and below the mean by comparing the actual values to expected values. The statistic for comparison is the chi-square. 3. Autocorrelation test Tests the correlation between numbers and compares the sample correlation to the expected correlation of zero. 4. Gap test Counts the number of digits that appear between repetitions of a particular digit and then uses the Kolmogorov-Smirnov test to compare with the expected size of gaps, 5 Poker test Treats numbers grouped together as a poker hand. Then the hands obtained are compared to what is expected using the chi-square test..

[Audio] In testing for uniformity, the hypotheses are as follows: H0: Ri ~ U/[ 0,1] H1: Ri ~U/[ 0,l] The null hypothesis, H0 reads that the numbers are distributed uniformly on the interval [0,1]. Failure to reject the null hypothesis means that no evidence of nonuniformity has been detected on the basis of this test. This does not imply that further testing of the generator for uniformity is unnecessary..

[Audio] In testing fo H0: Ri ~ independently H1:Ri~independently This null hypothesis H0 reads that the numbers are independent. Failure to reject the null hypothesis means that no evidence of dependence has been detected on the basis of this test. This does not imply that further testing of the generator for independence is unnecessaryr independence, the hypotheses are as follows:.

[Audio] Frequency Tests A basic test that should always be performed to validate a new generator is the test of uniformity. Two different methods of testing are available. They are the Kolmogorov-Smirnov and the chi-square test. Both of these tests measure the degree of agreement between the distribution of a sample of generated random numbers and the theoretical uniform distribution. Both tests are based on the null hypothesis of no significant difference between the sample distribution and the theoretical distribution..

[Audio] The Kolmogorov-Smirnov test This test compares the continuous cdf, F(X), of the uniform distribution to the empirical cdf, SN(x), of the sample of N observations. By definition, F(x) = x, 0 <= x <= 1 If the sample from the random-number generator is R1 R2, ,• • •, RN,then the empirical cdf, SN( X), is defined by SN(X) = number of R1 R2, ,• • •, Rn which are <= x/(N) As N becomes larger, SN(X) should become a better approximation to F(X) , provided that the null hypothesis is true..

The Kolmogorov-Smirnov test. The Kolmogorov-Smirnov test is based on the largest absolute deviation between F(x) and SN(X) over the range of the random variable. That is.it is based on statistic. D = max | F(x) - SN(x) For testing against a uniform CDF, the test procedure follows these steps: Step 1. Rank the data from smallest to largest. Let R( i ) denote ith smallest observation, so that R (1) <= R (2) <= • • • <= R (N) Step 2. Compute D + = max 1<= i <=N D - = max 1<= i <=N Step3. Compute D = max(D+ , D- ). Step 4. Determine the critical value, Da, from Table A.8 for the specified significance level a and the given sample size N. Step 5. If the sample statistic D is greater than the critical value, Da, the null hypothesis that the data are a sample from a uniform distribution is rejected. If D <= Da, conclude that no difference has been detected between the true distribution of and the uniform distribution.

[Audio] The chi-Square test A Pearson's chi-square test is a statistical test for categorical data. It is used to determine whether your data are significantly different from what you expected. There are two types of Pearson's chi-square tests: The chi-square goodness of fit test is used to test whether the frequency distribution of a categorical variable is different from your expectations. The chi-square test of independence is used to test whether two categorical variables are related to each other..

[Audio] The chi-square Formula: The larger the difference between the observations and the expectations ( O − E in the equation), the bigger the chi-square will be. To decide whether the difference is big enough to be statistically significant, you compare the chi-square value to a critical value..

[Audio] Runs Tests Runs up and down The run test examines the arrangement of numbers in a sequence to test the hypothesis of independence. Though the numbers can pass the uniform tests in, it's not sure that they might not be independent. A run is defined as a succession of similar events proceeding and followed by a different event. E.g. in a sequence of tosses of a coin, we may have H T T H H T T T H T The first toss proceeded and the last toss is followed by a "no event". This sequence has six runs, the first with a length of one, the second and third with a length of two, the fourth length of three, and the fifth and sixth length of one. A few features of a run two characteristics: number of runs and the length of run an up run is a sequence of numbers each of which is succeeded by a larger number; a down run is a sequence of numbers each of which is succeeded by a smaller number.

Runs Test. Runs above and below the mean. The runs above below test is a statistical test that counts the number of runs above the mean and below the mean. If the number of runs above meameansd below means are balanced along with having a sufficient number of runs then the Run the s test is accepted. Properties of Runs Above Below Test: The sequence above the mean is an above run. The sequence below the mean is a below run. If the number of runs is too low than sample runs above the below test will be rejected. If the number of runs above means and below mean are not balanced runs above below test will be rejected. The number of runs is the sum of the above run and below run always. The maximum number of runs can be up to N. The minimum number of runs can be 1..

Test of Autocorrelation. The autocorrelation Test is a statistical test that determines whether a random number generator is producing independent random numbers in a sequence. The test for autocorrelation is concerned with the dependence between numbers in a sequence. The test computes the autocorrelation between every m number (m is also known as lag) starting with ith index. The variables involved in this test are: M is the log, the space between the number being tested. i is the index or number from we start. N is the number of random numbers generated. M is the largest integer such that I+(M+1).<+N..

gap test. Examine length of “gaps” between occurrences of Uj ∈ I = ( α, β), where 0 ≤ α < β ≤1, and p = β − α. A gap is the length r where the Length of Uj , Uj+1, . . ., Uj+r have Uj , Uj+r ∈ I and all the others are not. Algorithm: 1. Initialize: j← -1, s ← 0 2. r ← 0 3. if ( α ≤ Uj ≤ β), j ← j+1 else goto 5. 4. r ← r+1, goto 3. 5. record gap length. if r ≥ t, COUN T [t] ← COUN T [t]+1 else COUN T [r] ← COUN T [r]+1 6. Repeat until n gaps are found. COUN T [0], COUN T [1], . . ., COUN T [t] should have the following probability: I p0 = p, p1 = p(1 − p), p2 = p(1 − p) 2 , . . . , pt−1 = p(1 − p) t−1, pt = p(1 − p) t Now, we can apply the χ 2 test. Special cases: I (α,β) = (0, 1 2 ) ← runs above the mean I (α,β) = ( 1 2,1) ← runs below the mean.

Poker Test. Poker test is the test for independence based on the frequency with which certain digits are repeated within a series of numbers. This test not only tests for the randomness of the sequence of numbers but also the digits comprising each of the numbers. The acceptance is done if the observed value of chi-square sums for all the possible combinations of digits is less than the acceptable value for the given degree of freedom of the specified confidence interval. Every random number of five digits or every sequence of the digits is treated as a poker hand..