--- title: "Random number properties and Gap test" subject: "Simulation and Modeling" chapter: 6 key: "semester_8/simulation_and_modeling:rn-properties-gap-test" source: https://www.bctengineer.com/q/semester_8/simulation_and_modeling/rn-properties-gap-test site: BCT Engineering --- # Random number properties and Gap test Simulation and Modeling · Chapter 6: Random Number - Asked in: 2072 Ashwin, 4+6 marks; 2072 Magh, 4+6 marks; 2069 Bhadra (old course), 2+8 marks; 2073 Magh, 2+8 marks (asked 4 times) - Video: [Simulation Modeling 25 Uniformity and Independence Properties](https://www.youtube.com/watch?v=2KNi3nZP9Qk) — İsmail Başoğlu - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_8/simulation_and_modeling/rn-properties-gap-test - Whole chapter: https://www.bctengineer.com/md/semester_8/simulation_and_modeling/chapter-6 ## Question What are the properties of random numbers? Explain the steps of the Gap test algorithm with example. ## 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. ## Answer #### Properties of random numbers A sequence of random numbers R1, R2, ... used in simulation must have two main properties: 1. **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. 2. **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)** 1. Choose the digit (3) and write the sequence of random digits. 2. Mark the positions where the digit occurs and find the gap lengths between successive occurrences. 3. Make a frequency table of gaps and compute the cumulative relative frequency SN(x). 4. Compute the theoretical F(x) = 1 - (0.9)^(x+1). 5. Find D = max |SN(x) - F(x)|. 6. 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.) ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Which two properties must a sequence of random numbers have? A. Uniformity and independence B. Periodicity and correlation C. Normality and uniformity D. Speed and dependence Answer: A. Random numbers must be uniform on [0,1) and independent of one another. (Key point: Two key properties) 2. In the gap test, what is a gap? A. The difference between the largest and smallest digit B. The number of digits between two successive occurrences of the same digit C. The number of times a digit occurs in total D. The difference between SN(x) and F(x) Answer: B. A gap is the count of digits lying between successive occurrences of the chosen digit. (Key point: Meaning of a gap) 3. For a random digit sequence and a single chosen digit, the theoretical cdf of the gap length is: A. F(x) = 0.1 x B. F(x) = 1 - (0.1)^(x+1) C. F(x) = (0.9)^(x+1) D. F(x) = 1 - (0.9)^(x+1) Answer: D. P(gap = x) = 0.1(0.9)^x, which sums to F(x) = 1 - 0.9^(x+1). (Key point: Theoretical gap cdf) 4. In the example, D = 0.2645 and D(0.05) = 0.391. What is the conclusion? A. Independence is rejected because D is positive B. Independence is accepted because D <= D(alpha) C. The test is invalid because N is 11 D. Uniformity is rejected Answer: B. If D <= critical value, there is no evidence against independence, so it is accepted. (Key point: Gap test decision) ## Related in Simulation and Modeling - [Random number properties; KS test algorithm](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Arn-properties-ks-algorithm) — Simulation and Modeling, chapter 6 - [Properties of random numbers](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Arn-properties) — Simulation and Modeling, chapter 6 - [Chi-square test on 100 random numbers](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Achi-square-uniformity-100-numbers) — Simulation and Modeling, chapter 6 - [Write algorithm for Gap test](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Agap-test-algorithm) — Simulation and Modeling, chapter 6 - [Gap test algorithm; formulate poker test](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Agap-test-poker-formulate) — Simulation and Modeling, chapter 6 - [Random number; problems in generating pseudo-random](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Arn-problems-pseudo-random) — Simulation and Modeling, chapter 6 ## Related in other subjects - [Algorithm for numbers divisible by 9 not 6](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Aalgo-flowchart-divisible-9-not-6) — Computer Programming, chapter 2 - [Continuous random variable; pdf properties](https://www.bctengineer.com/question.md?key=semester_5%2Fprobability_and_statistics%3Acontinuous-rv-pdf-properties) — Probability and Statistics, chapter 3 - [Number of turns for iron ring with air gap](https://www.bctengineer.com/question.md?key=semester_4%2Felectrical_machines_i%3Airon-ring-1p25m-turns-0p5wb) — Electrical Machines I, chapter 1, asked 2×