Random Numbers: Generation and Testing

Every simulation in this course runs on random numbers: the random digits that drove the simulation tables, and the inter-arrival and service times of the single-server queue. This section shows how a computer produces those numbers with two generators, and how three statistical tests check that the numbers behave like real random numbers: uniform on [0, 1] and independent of each other. All five problems of Exercise 3 are solved step by step.

Objectives

• Compute the sequence of a multiplicative generator and find its cycle and its period.
• Compute random numbers in [0, 1] with a linear congruential generator (LCG).
• Apply the Kolmogorov-Smirnov test to check that a small sample is uniform.
• Apply the chi-square test to check that a large sample is uniform.
• Apply the autocorrelation test to check that numbers at a fixed distance are independent.
• Read the critical value from the correct table and state the decision.

1. What a random number must do

A simulation turns random numbers $R_1, R_2, \ldots$ into random events: an arrival, a service time, a demand. For this to give correct results, the numbers must have two properties:

The generators below compute each number from the one before it, so after some time the sequence repeats. Each test starts from a hypothesis: the numbers are uniform, or the numbers are independent. The test either rejects that hypothesis or does not reject it.

2. Generating random numbers

The multiplicative generator

$$Z_i = (a \, Z_{i-1}) \bmod m$$

• $Z_0$ is the seed, the starting value.
• $a$ is the multiplier and $m$ is the modulus.
• x mod m is the remainder after dividing x by m, so every $Z_i$ is between 0 and m - 1.

Each $Z_i$ depends only on $Z_{i-1}$. When a value appears for the second time, the sequence repeats from that point: the generator is cycling. The number of values in one cycle is the period. A long period is better, because the numbers start to repeat later.

Q1 (a): Z0 = 1, a = 11, m = 16

$$\begin{aligned} Z_1 &= (11 \times 1) \bmod 16 = 11 \bmod 16 = 11 \\ Z_2 &= (11 \times 11) \bmod 16 = 121 \bmod 16 = 9 \\ Z_3 &= (11 \times 9) \bmod 16 = 99 \bmod 16 = 3 \\ Z_4 &= (11 \times 3) \bmod 16 = 33 \bmod 16 = 1 \\ Z_5 &= (11 \times 1) \bmod 16 = 11 \quad \text{(cycling)} \end{aligned}$$

$Z_4 = Z_0 = 1$, so the cycle is 1, 11, 9, 3 and the period is m / 4 = 16 / 4 = 4 numbers.

Q1 (b): Z0 = 2, a = 11, m = 16

$$\begin{aligned} Z_1 &= (11 \times 2) \bmod 16 = 22 \bmod 16 = 6 \\ Z_2 &= (11 \times 6) \bmod 16 = 66 \bmod 16 = 2 \\ Z_3 &= (11 \times 2) \bmod 16 = 6 \quad \text{(cycling)} \end{aligned}$$

The period is 2 numbers. The values of a and m are the same as in (a); only the seed changed, and the period fell from 4 to 2. The choice of seed matters.

Q1 (c): Z0 = 1, a = 2, m = 13

$$\begin{aligned} Z_1 &= (2 \times 1) \bmod 13 = 2 \\ Z_2 &= (2 \times 2) \bmod 13 = 4 \\ Z_3 &= (2 \times 4) \bmod 13 = 8 \\ Z_4 &= (2 \times 8) \bmod 13 = 16 \bmod 13 = 3 \\ Z_5 &= (2 \times 3) \bmod 13 = 6 \\ Z_6 &= (2 \times 6) \bmod 13 = 12 \\ Z_7 &= (2 \times 12) \bmod 13 = 24 \bmod 13 = 11 \\ Z_8 &= (2 \times 11) \bmod 13 = 22 \bmod 13 = 9 \\ Z_9 &= (2 \times 9) \bmod 13 = 18 \bmod 13 = 5 \\ Z_{10} &= (2 \times 5) \bmod 13 = 10 \\ Z_{11} &= (2 \times 10) \bmod 13 = 20 \bmod 13 = 7 \\ Z_{12} &= (2 \times 7) \bmod 13 = 14 \bmod 13 = 1 \quad \text{(cycling)} \end{aligned}$$

The period is 12 = m - 1: every value from 1 to 12 appears once before the sequence repeats. This is the longest period possible for m = 13, because 0 never appears (once Z = 0, every later value is 0 too).

Note on the exercise sheet. The table on the sheet is correct, but the step lines skip one value: they go from $Z_6 = 12$ directly to 24 mod 13 = 9. In fact 24 mod 13 = 11 is $Z_7$, and 9 comes one step later, as the table shows.

Q1 (d): Z0 = 2, a = 3, m = 13

$$\begin{aligned} Z_1 &= (3 \times 2) \bmod 13 = 6 \\ Z_2 &= (3 \times 6) \bmod 13 = 18 \bmod 13 = 5 \\ Z_3 &= (3 \times 5) \bmod 13 = 15 \bmod 13 = 2 \quad \text{(cycling)} \end{aligned}$$

The period is only 3 numbers. With the same modulus as (c), the multiplier a = 3 gives a very short cycle, where a = 2 gave the full 12.

The linear congruential generator (LCG)

The LCG adds a constant c, the increment, before the remainder:

$$X_i = (a \, X_{i-1} + c) \bmod m$$

Every $X_i$ is an integer from 0 to m - 1. To get a random number in [0, 1], divide by the modulus:

$$R_i = \dfrac{X_i}{m}$$

Q2: X0 = 27, a = 8, c = 47

For m = 100, the remainder is the two rightmost digits:

$$\begin{aligned} X_1 &= (8 \times 27 + 47) \bmod 100 = (216 + 47) \bmod 100 = 263 \bmod 100 = 63 \\ X_2 &= (8 \times 63 + 47) \bmod 100 = (504 + 47) \bmod 100 = 551 \bmod 100 = 51 \\ X_3 &= (8 \times 51 + 47) \bmod 100 = (408 + 47) \bmod 100 = 455 \bmod 100 = 55 \end{aligned}$$

The first three random numbers in [0, 1] are:

$$R_1 = \dfrac{63}{100} = 0.63, \quad R_2 = \dfrac{51}{100} = 0.51, \quad R_3 = \dfrac{55}{100} = 0.55$$

Note on the exercise sheet. The question gives m = 102, but the solution computes with m = 100. We follow the solution. With m = 102 the integers are 59, 9, 17, and the random numbers are 59/102 = 0.578, 9/102 = 0.088 and 17/102 = 0.167.

3. Testing uniformity

Both tests use the same hypothesis, $H_0$: the numbers are uniformly distributed on [0, 1]. Both compute a statistic from the data and compare it with a critical value from a table at the level of significance $\alpha$. If the statistic is smaller than the critical value, $H_0$ is not rejected.

The Kolmogorov-Smirnov test

The test compares the sample with the ideal uniform distribution, point by point:

1. Sort the numbers in ascending order: $R_{(1)} \le R_{(2)} \le \ldots \le R_{(N)}$.
2. Compute the largest distance above the ideal line:

$$D^{+} = \max_{1 \le i \le N} \left[ \dfrac{i}{N} - R_{(i)} \right]$$

3. Compute the largest distance below it:

$$D^{-} = \max_{1 \le i \le N} \left[ R_{(i)} - \dfrac{i - 1}{N} \right]$$

4. Take $D = \max(D^{+}, D^{-})$.
5. Read $D_{\alpha}$ for N and $\alpha$ from the KS table. If $D < D_{\alpha}$, $H_0$ is not rejected.

Q3: 0.54, 0.73, 0.98, 0.11, 0.68 with α = 0.05

Sorted, the numbers are 0.11, 0.54, 0.68, 0.73, 0.98, and N = 5:

$$D^{+} = 0.09, \quad D^{-} = 0.34, \quad D = \max(0.09, 0.34) = 0.34$$

From the KS table, $D_{0.05} = 0.565$ for N = 5. Since $D = 0.34 < 0.565$, $H_0$ is not rejected: the numbers pass the uniformity test.

The chi-square test

1. Divide [0, 1] into n equal class intervals.
2. Count $O_i$, the number of values that fall in interval i.
3. Compute the expected count for every interval: $E_i = N / n$.
4. Compute the statistic:

$$\chi_0^2 = \sum_{i=1}^{n} \dfrac{(O_i - E_i)^2}{E_i}$$

5. Read $\chi^2_{\alpha, n-1}$ from the chi-square table, with n - 1 degrees of freedom. If $\chi_0^2 < \chi^2_{\alpha, n-1}$, $H_0$ is not rejected.

Q4: 100 numbers with α = 0.05

The data is classified into n = 10 intervals: [0, 0.1], (0.1, 0.2], (0.2, 0.3], and so on up to (0.9, 1.0]. With N = 100, every interval expects $E_i = 100 / 10 = 10$ values.

$$\chi_0^2 = 3.4, \qquad \chi^2_{0.05, \, 9} = 16.9$$

The table value is in row n - 1 = 9 of the chi-square table, column $\chi^2_{0.05}$. Since $\chi_0^2 = 3.4 < 16.9$, $H_0$ is not rejected, and the data is considered uniformly distributed.

Note on the exercise sheet. The conclusion slide writes $\chi_0^2 > \chi^2_{0.05, 9}$. The correct relation is $\chi_0^2 < \chi^2_{0.05, 9}$ (3.4 against 16.9), which is why $H_0$ is not rejected.

4. Testing independence: the autocorrelation test

Uniform numbers can still depend on each other, for example if every fifth number is always small. The autocorrelation test checks the numbers at a fixed distance:

• i is the position of the first number tested.
• m is the lag, the distance between two tested numbers. Here m is not the modulus of a generator.
• N is the number of values in the sequence.
• M is the largest integer that keeps the last tested number inside the sequence:

$$i + (M + 1) \, m \le N$$

The estimate of the autocorrelation, its standard deviation and the test statistic are:

$$\hat{\rho}_{im} = \dfrac{1}{M + 1} \left[ \sum_{k=0}^{M} R_{i + km} \, R_{i + (k+1)m} \right] - 0.25$$ $$\sigma_{\hat{\rho}_{im}} = \dfrac{\sqrt{13M + 7}}{12 (M + 1)}, \qquad Z_0 = \dfrac{\hat{\rho}_{im}}{\sigma_{\hat{\rho}_{im}}}$$

The hypothesis $H_0$: the numbers are independent. If $-z_{\alpha/2} \le Z_0 \le z_{\alpha/2}$, $H_0$ is not rejected. For $\alpha = 0.05$, $\alpha/2 = 0.025$, so look for the cumulative probability 0.975 in the normal table: $z_{0.025} = 1.96$.

Q5: the 3rd, 8th, 13th, ... numbers with α = 0.05

The test starts at the 3rd number, so i = 3. From the 3rd to the 8th is a lag of m = 5, and N = 30.

$$3 + (M + 1) \times 5 \le 30 \;\Rightarrow\; 8 + 5M \le 30 \;\Rightarrow\; M \le 4.4 \;\Rightarrow\; M = 4$$

The tested numbers are $R_3, R_8, R_{13}, R_{18}, R_{23}, R_{28}$ = 0.23, 0.28, 0.33, 0.27, 0.05, 0.36, shown in bold above.

$$\begin{aligned} \hat{\rho}_{35} &= \dfrac{1}{5} \left[ R_3 R_8 + R_8 R_{13} + R_{13} R_{18} + R_{18} R_{23} + R_{23} R_{28} \right] - 0.25 \\ &= \dfrac{1}{5} \left[ (0.23)(0.28) + (0.28)(0.33) + (0.33)(0.27) + (0.27)(0.05) + (0.05)(0.36) \right] - 0.25 \\ &= \dfrac{1}{5} \left[ 0.0644 + 0.0924 + 0.0891 + 0.0135 + 0.0180 \right] - 0.25 \\ &= \dfrac{0.2774}{5} - 0.25 = 0.0555 - 0.25 = -0.1945 \end{aligned}$$ $$\sigma_{\hat{\rho}_{35}} = \dfrac{\sqrt{13 \times 4 + 7}}{12 \times 5} = \dfrac{\sqrt{59}}{60} = \dfrac{7.68}{60} = 0.128$$ $$Z_0 = \dfrac{-0.1945}{0.128} = -1.5195$$

Since $-1.96 < -1.5195 < 1.96$, $H_0$ is not rejected: the 3rd, 8th, 13th, ... numbers look independent.

5. Common mistakes

1. Forgetting to divide by m. An LCG gives integers. The random number in [0, 1] is $X_i / m$: in Q2, 63 becomes 0.63.
2. Testing the numbers unsorted. The KS test needs the numbers in ascending order first. With the original order of Q3, the column i/N would be matched with the wrong values.
3. Mixing up the two KS columns. $D^{+}$ uses $i/N - R_{(i)}$; $D^{-}$ uses $R_{(i)} - (i-1)/N$. Each one is a maximum over its own column, and negative entries simply lose.
4. Wrong degrees of freedom. The chi-square table is read at n - 1 degrees of freedom, where n is the number of intervals, not the number of values: 9, not 99.
5. Reversing the decision. In all three tests, a statistic inside the critical limit means $H_0$ is not rejected. A large $D$, a large $\chi_0^2$ or a large $|Z_0|$ is what rejects.
6. Rounding M up. M is the largest integer with $i + (M+1)m \le N$. In Q5, M ≤ 4.4 gives M = 4; M = 5 would need a 33rd number.

6. Practice

Solve each problem, then check the answers at the end of this page. Use $D_{0.05} = 0.565$ for N = 5, $\chi^2_{0.05, 4} = 9.49$, and $z_{0.025} = 1.96$.

1. A multiplicative generator has Z0 = 3, a = 5 and m = 16. Compute the values until the sequence cycles, and give the period.
2. An LCG has X0 = 7, a = 21, c = 13 and m = 100. Compute the first three random numbers in [0, 1].
3. Use the Kolmogorov-Smirnov test with $\alpha = 0.05$ to check the uniformity of 0.44, 0.81, 0.14, 0.05, 0.93.
4. Fifty numbers were classified into 5 equal intervals, with observed counts 12, 7, 9, 13, 9. Use the chi-square test with $\alpha = 0.05$.
5. With the 30 numbers of Q5, test the 1st, 7th, 13th, ... numbers for autocorrelation with $\alpha = 0.05$.

Key takeaways

• A multiplicative generator computes $Z_i = (a Z_{i-1}) \bmod m$; the seed, the multiplier and the modulus decide how long the period is.
• An LCG adds an increment, $X_i = (a X_{i-1} + c) \bmod m$, and $R_i = X_i / m$ gives a number in [0, 1].
• Kolmogorov-Smirnov: sort, compute $D^{+}$ and $D^{-}$, take the larger, compare with $D_{\alpha}$.
• Chi-square: count each interval, sum $(O_i - E_i)^2 / E_i$, compare with the table at n - 1 degrees of freedom.
• Autocorrelation: find M, compute $\hat{\rho}$, $\sigma$ and $Z_0$, and compare $Z_0$ with $\pm z_{\alpha/2}$.
• In every test, a statistic inside the limit means the hypothesis is not rejected.

Answers

Practice 1

$Z_1 = (5 \times 3) \bmod 16 = 15$, $Z_2 = (5 \times 15) \bmod 16 = 75 \bmod 16 = 11$, $Z_3 = (5 \times 11) \bmod 16 = 55 \bmod 16 = 7$, $Z_4 = (5 \times 7) \bmod 16 = 35 \bmod 16 = 3$, which is $Z_0$ again. The cycle is 3, 15, 11, 7, and the period is 4 = m / 4.

Practice 2

$X_1 = (21 \times 7 + 13) \bmod 100 = 160 \bmod 100 = 60$, $X_2 = (21 \times 60 + 13) \bmod 100 = 1273 \bmod 100 = 73$, $X_3 = (21 \times 73 + 13) \bmod 100 = 1546 \bmod 100 = 46$. The random numbers are 0.60, 0.73 and 0.46.

Practice 3

$D^{+} = 0.26$, $D^{-} = 0.21$, so $D = 0.26$. Since $0.26 < 0.565$, $H_0$ is not rejected: the numbers are uniform.

Practice 4

$E_i = 50 / 5 = 10$. The terms are 0.4, 0.9, 0.1, 0.9, 0.1, so $\chi_0^2 = 2.4$. With n - 1 = 4 degrees of freedom, $\chi^2_{0.05, 4} = 9.49$. Since $2.4 < 9.49$, $H_0$ is not rejected.

Practice 5

i = 1, m = 6, N = 30: $1 + (M+1) \times 6 \le 30$ gives $M \le 3.83$, so M = 3. The tested numbers are $R_1, R_7, R_{13}, R_{19}, R_{25}$ = 0.12, 0.64, 0.33, 0.75, 0.95.

$$\hat{\rho}_{16} = \dfrac{1}{4} \left[ (0.12)(0.64) + (0.64)(0.33) + (0.33)(0.75) + (0.75)(0.95) \right] - 0.25 = \dfrac{1.248}{4} - 0.25 = 0.062$$ $$\sigma = \dfrac{\sqrt{13 \times 3 + 7}}{12 \times 4} = \dfrac{\sqrt{46}}{48} = 0.1413, \qquad Z_0 = \dfrac{0.062}{0.1413} = 0.439$$

Since $-1.96 < 0.439 < 1.96$, $H_0$ is not rejected: these numbers look independent.