---
title: "Write algorithm for Gap test"
subject: "Simulation and Modeling"
chapter: 6
key: "semester_8/simulation_and_modeling:gap-test-algorithm"
source: https://www.bctengineer.com/q/semester_8/simulation_and_modeling/gap-test-algorithm
site: BCT Engineering
---

# Write algorithm for Gap test

Simulation and Modeling · Chapter 6: Random Number

- Asked in: 2074 Magh, 4 marks
- Video: [Simulation Modeling | Tutorial #19 |  The Gap Test (Algorithm)](https://www.youtube.com/watch?v=WPAuDQYlQiI) — RANJI RAJ
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_8/simulation_and_modeling/gap-test-algorithm
- Whole chapter: https://www.bctengineer.com/md/semester_8/simulation_and_modeling/chapter-6

## Question

Write an algorithm for Gap Test.

## Short answer

Choose a target digit or interval [α,β) with probability p. Scan the sequence, record gap lengths (number of non‑target digits between consecutive occurrences). Collect n gaps, group by length. Compute theoretical cumulative probability F(x)=1−(1−p)^(x+1). Compare observed SN(x) using K‑S test (D=max|F(x)−SN(x)|) or chi‑square test (χ²=∑(Oi−Ei)²/Ei). Reject independence if statistic exceeds critical value.

## Answer

The **gap test** checks the **independence** of a sequence of random digits. It counts the gaps (number of other digits) between successive occurrences of a particular digit, and compares the observed gap lengths with the gap distribution expected from a random sequence.

**Theory.** Choose a digit (or interval [α, β) in [0, 1)) as the target. Probability that a digit is the target is p = (β − α) (for a single digit p = 0.1). The probability of a gap of length x is
P(gap = x) = p(1 − p)^x, and the cdf is F(x) = 1 − (1 − p)^(x+1).

**Algorithm**
1. Take the sequence of N numbers. Select the target digit (or interval [α, β]).
2. Scan the sequence. Whenever the target occurs, note its position. The gap is the number of non-target numbers between two successive occurrences.
3. Collect n gaps. Group them by length (0, 1, 2, ... and a final class "x or more").
4. Compute the observed relative frequency of each gap class, and the cumulative one SN(x).
5. Compute the theoretical probabilities with F(x) = 1 − (1 − p)^(x+1).
6. Compare them with either the **K-S test** (D = max|F(x) − SN(x)|, compare with Dα for n gaps), or the **chi-square test** (χ0² = Σ (Oi − Ei)²/Ei with Ei = n·P(gap class), merge classes with Ei < 5, df = classes − 1).
7. If the statistic exceeds the critical value, reject independence; otherwise accept it.

**Small illustration.** Digits: 4 1 3 5 1 7 2 8 2 0 7 9 1 3 5 2 7 9 4 1 6 3 3 9 6 3. With target digit 3, it occurs at positions 3, 14, 22, 23, 26. The gaps are 10, 7, 0 and 2. With p = 0.1, the expected P(gap = 0) = 0.1, P(gap = 1) = 0.09, and so on; these are compared with the observed frequencies over a long sequence.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What property does the gap test check?
   A. Uniformity
   B. Independence
   C. Period length
   D. Mean value
   Answer: B. The gap test examines gaps between occurrences of a target digit to check independence. (Key point: Purpose of gap test)

2. For target probability p, the probability that the gap length is x is:
   A. p^x (1 - p)
   B. p (1 - p)^x
   C. (1 - p)^(x+1)
   D. p x
   Answer: B. A gap of x means x non-targets followed by a target: P(gap = x) = p(1 - p)^x. (Key point: Gap probability)

3. If the target is the interval [alpha, beta), what is p?
   A. alpha + beta
   B. beta - alpha
   C. alpha x beta
   D. 0.1 always
   Answer: B. The chance a number falls in the interval is its length, beta - alpha. (Key point: Interval target)

4. What is the decision in the gap test?
   A. Reject independence if the statistic exceeds the critical value
   B. Accept independence if the statistic exceeds the critical value
   C. Always accept
   D. Reject if the statistic is zero
   Answer: A. If the K-S D or chi-square statistic exceeds the critical value, independence is rejected; otherwise accepted. (Key point: Decision rule)

## Related in Simulation and Modeling

- [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 properties and Gap test](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Arn-properties-gap-test) — Simulation and Modeling, chapter 6, asked 4×
- [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