- Asked 4/10
- 2072 Ashwin · 4+6 marks
- 2072 Magh · 4+6 marks
- 2069 Bhadra (old course) · 2+8 marks
- 2073 Magh · 2+8 marks
Random number properties and Gap test
Short answer
Random numbers must be uniform over [0,1) and independent, with good generators having long periods and reproducibility. The gap test checks independence by comparing observed gap frequencies with F(x)=1-(0.9)^(x+1); the example gives D=0.2645, below the critical value 0.391, so independence is accepted.
What are the properties of random numbers? Explain the steps of the Gap test algorithm with example.
Properties of random numbers
A sequence of random numbers R1, R2, ... used in simulation must have two main properties:
- Uniformity: each number is equally likely to fall anywhere in [0, 1). If the interval is divided into n equal classes, each should receive N/n of the N numbers.
- Independence: the value of a number must not depend on earlier numbers. No pattern, trend or correlation may exist.
Desirable properties of a good generator: long period (full cycle), fast and low memory use, reproducible (same seed gives the same sequence, which helps debugging), can be split into independent streams, and the numbers pass statistical tests.
Gap test
The gap test checks independence. A gap is the number of digits between two successive occurrences of the same digit. For a chosen digit (say 3), if the digits are random the probability that the gap length is x is
P(gap = x) = 0.1 x (0.9)^x
and the cumulative probability is F(x) = 1 - (0.9)^(x+1).
Steps (Kolmogorov-Smirnov version)
- Choose the digit (3) and write the sequence of random digits.
- Mark the positions where the digit occurs and find the gap lengths between successive occurrences.
- Make a frequency table of gaps and compute the cumulative relative frequency SN(x).
- Compute the theoretical F(x) = 1 - (0.9)^(x+1).
- Find D = max |SN(x) - F(x)|.
- Compare D with the critical value D(alpha) from the K-S table for N gaps. If D <= D(alpha), accept independence; otherwise reject.
Example: from a sequence of 120 random digits, digit 3 occurs at positions 7, 13, 18, 20, 35, 36, 41, 43, 45, 88, 90, 105. The gaps are 5, 4, 1, 14, 0, 4, 1, 1, 42, 1, 14 (N = 11 gaps).
| Gap x | Frequency | SN(x) | F(x) = 1 - 0.9^(x+1) | abs(SN - F) |
|---|---|---|---|---|
| 0 | 1 | 0.0909 | 0.1000 | 0.0091 |
| 1 | 4 | 0.4545 | 0.1900 | 0.2645 |
| 4 | 2 | 0.6364 | 0.4095 | 0.2269 |
| 5 | 1 | 0.7273 | 0.4686 | 0.2587 |
| 14 | 2 | 0.9091 | 0.7941 | 0.1150 |
| 42 | 1 | 1.0000 | 0.9892 | 0.0108 |
D = max difference = 0.2645.
Critical value for alpha = 0.05 and N = 11 is D(0.05) = 0.391 (K-S table). Since 0.2645 < 0.391, the hypothesis of independence is accepted: no evidence of dependence in the sequence.
(With very few gaps, the test has low power. In practice at least 50 or more gaps are used. Alternatively, the gap lengths can be grouped into classes and compared with expected frequencies by the chi-square test.)
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Random number properties; KS test algorithm · Simulation and Modeling, chapter 6
- Properties of random numbers · Simulation and Modeling, chapter 6
- Chi-square test on 100 random numbers · Simulation and Modeling, chapter 6
- Write algorithm for Gap test · Simulation and Modeling, chapter 6
- Gap test algorithm; formulate poker test · Simulation and Modeling, chapter 6
- Random number; problems in generating pseudo-random · Simulation and Modeling, chapter 6
- Algorithm for numbers divisible by 9 not 6 · Computer Programming, chapter 2
- Continuous random variable; pdf properties · Probability and Statistics, chapter 3
- Number of turns for iron ring with air gap · Electrical Machines I, chapter 1 · asked 2×