Write algorithm for Gap test

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.