Random Number

 

Properties of Random Numbers

What is random number?

A number chosen from some specified distribution randomly such that selection of large set of these numbers reproduces the underlying distribution is called random number.

---

General Properties

1. Uniformity:
- The random numbers generated should be uniform. That means a sequence of random numbers should be equally probable every where.
- If we divide all the set of random numbers into several numbers of class interval then number of samples in each class should be same.
- If ‘N’ number of random numbers are divided into ‘K’ class interval, then expected number of samples in each class should be equal to ei = N / K.

2. Independent:
- Each random number should be independent samples drawn from a continuous uniform distribution between 0 and 1.
- The probability density function is given by:
f(x) = 1, 0 <= x <= 1
= 0, otherwise

3. Maximum Density:
- The large samples of random number should be generated in a given range.

4. Maximum Cycle:
- It states that the repetition of numbers should be allowed only after a large interval of time.

---

Generation of Pseudo-Random numbers

Pseudo Random Number

- Pseudo random numbers are the random numbers that are generated by using some known methods so as to produce a sequence of numbers in [0,1] that can simulates the ideal properties of random numbers.
- Pseudo random numbers are not completely random as the set of random numbers can be replicated because of use of some known method.

---

Problems Associated

- The problems associated with pseudo random numbers are as follows:
1. The generated numbers might not be uniformly distributed.
2. The generated numbers might be discrete valued instead of continuous valued.
3. The mean of the generated numbers might be too high or too low.
4. The variance of the generated numbers might be too high or too low.
5. There might be presence of correlation between the generated numbers.

---

Considerations

- The important considerations that should be made while generating pseudo random numbers are as follows:
1. The method used to generate random number should be fast because the simulation problem requires a large set of random numbers which can increase time complexity of the system.
2. The method used should be portable to different platform and programming languages so as to generate same results wherever it is executed.
3. The method should have long cycle.
4. The random numbers should be replicable. It means that the same set of random numbers should be generated with same starting point.
5. The generated random numbers should approximate the uniformity and independence properties.

---

Random Number generation methods

Linear Congruential Method:

- A sequence of integers X1, X2, X3, ……….. are produced between zero and m-1 by using the recursive relation as follows:
X(i+1) = (a X(i) + c) mod m, for I = 0, 1, 2, 3, 4, ……….. (Equation 1)
- The initial random integer X(0), is known as seed, a is called multiplier, c is increment and m is the modulus.
- The form is called mixed congruential method if c is not equal to 0 in equation 1.
- The form is called multiplicative congruential method if c is equal to 0 in equation 1.
- The random numbers corresponding to each random integer can be obtained as:
R(i) = X(i) / m , for I = 0, 1, 2, 3, …………..

- Example: For the values selection with X(0) = 30, a = 12, c = 21 and m = 100, the sequence of random numbers generated are as follows:
X(0) = 30
X(1) = (12 * 30 + 21) mod 100 =381 mod 100 = 81
X(2) = (12 * 81 + 21) mod 100 = 993 mod 100 = 93
X(3) = (12 * 93 + 21) mod 100 = 1137 mod 100 = 37
and so on…

The random numbers between [0, 1] generated are as follows:
R(0) = 0.3
R(1) = 0.81
R(2) = 0.93
R(3) = 0.37 and so on…….

---

Combined Linear Congruential Method:

- Combined linear congruential method uses the combination of two or more multiplicative congruential generators so as to provide good statistical properties and a longer period.
- Let X(i, 1), X(i, 2), X(i, 3), ……… are the ith output from k different multiplicative congruential generators, then the combined generator is of form:
X(i) = Summation from j = 1 to k [(-1)^(j-1) * X(i,j)] mod m(j) – 1
This generates random integers between 0 and m(j)-2.
- The random numbers are calculated as:
R(i) = X(i) / m(j), if X(i) > 0
= (m(j) – 1) / m(j), if X(i) = 0

---

Test for random numbers

Kolmogorov-Smirnov Test:

- This test compares the continuous cdf, F(x), of the uniform distribution with the empirical cdf, S(x), of the sample of N observations.

- Mathematically,
F(x) = x , 0 <= x <= 1
For samples from random generator be R(1), R(2), …………, R(N), then empirical cdf is given by:
S(x) = [numbers of R(1), R(2), ………. R(N) which are less or equal to x] / N

- It is based on largest absolute deviation between F(x) and S(x) over the range of random variable. It can be given by:
D = max | F(x) – S(x) |

- The sampling distribution of D is tabulated as a function of N which is standard for comparison purpose.

Algorithm:
1. Rank the data from smallest to largest such that R(1) <= R(2) <= ……….. <= R(N)
2. Compute:
D+ = max [ i / N – R(i) ] for i = 1 to N
D- = max [ R(i) – (i - 1) / N ] for i = 1 to N
3. Compute D = max(D+, D-)
4. Locate in table of sampling distribution of D, the critical value D(alpha), for specified significance level alpha and given sample size N.
5. If the sample statistic D is greater than D(alpha), the null hypothesis that the data are a sample from a uniform distribution is rejected. Else, no difference has been detected and the distribution is uniform.

---

Chi-Square Test:

- The chi-square test uses sample statistic : chi-square = Summation i = 1 to n [ (O(i) – E(i))^2 / E(i) ]
- O(i) = Observed number in the ith class
- E(i) = Expected number in the ith class
- n = Number of class
- Degree of freedom = n – 1
- If chi-square for sample random numbers is less than standard chi-square at alpha and degree of freedom(n-1), then the null hypothesis is not rejected.