{ "id": "ept49x64hj", "slug": "gap-test-randomness-testing", "title": "Gap test (randomness testing)", "updated": "2026-10-15", "topic_path": [ { "id": "physical", "label": "Physical world and mathematics", "api_url": "https://www.edgepedia.org/api/v1/topics/physical" }, { "id": "physical.math", "label": "Mathematics and statistics", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math" }, { "id": "physical.math.statistics", "label": "Statistics and probability", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.statistics" }, { "id": "physical.math.statistics.stats_statistical_inference", "label": "Statistical inference, estimation, sampling, and testing", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.statistics.stats_statistical_inference" }, { "id": "physical.math.statistics.stats_statistical_inference.hypothesis_testing", "label": "Hypothesis testing", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.statistics.stats_statistical_inference.hypothesis_testing" } ], "geo": [ { "id": "geo.nongeo.t1946.physical.math.statistics.stats_statistical_inference.hypothesis_testing", "label": "Non-geographic · 1946 to 2000: Hypothesis testing", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math.statistics.stats_statistical_inference.hypothesis_testing", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1946", "label": "Non-geographic · 1946 to 2000", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946" }, { "id": "geo.nongeo.t1946.physical", "label": "Physical world and mathematics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical" }, { "id": "geo.nongeo.t1946.physical.math", "label": "Mathematics and statistics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math" }, { "id": "geo.nongeo.t1946.physical.math.statistics", "label": "Statistics and probability", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math.statistics" }, { "id": "geo.nongeo.t1946.physical.math.statistics.stats_statistical_inference", "label": "Statistical inference, estimation, sampling, and testing", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math.statistics.stats_statistical_inference" }, { "id": "geo.nongeo.t1946.physical.math.statistics.stats_statistical_inference.hypothesis_testing", "label": "Hypothesis testing", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math.statistics.stats_statistical_inference.hypothesis_testing" } ] } ], "excerpt": "The gap test is a chi-square goodness-of-fit test checking whether spacings between recurrences of a chosen value in a random number sequence follow the expected geometric distribution.", "snippet": "The gap test is a chi-square goodness-of-fit test checking whether spacings between recurrences of a chosen value in a random number sequence follow the expected geometric distribution.", "node": "physical.math.statistics.stats_statistical_inference.hypothesis_testing", "markdown": "# Gap test (randomness testing)\n\nThe gap test is a chi-square goodness-of-fit test that checks whether the spacings between recurrences of a chosen value, digit, or subinterval in a generated random number sequence follow the geometric distribution expected of a truly random source. It is used to validate uniform random number generators (RNGs) by looking for local structure, such as clustering or periodicity, in the sequence.[1](https://dl.acm.org/doi/10.1145/1268776.1268777) A \"gap\" is the number of consecutive draws between two successive hits, where a hit means a draw falls in a target set, usually an interval \\([\\alpha, \\beta]\\) within \\([0,1)\\) with hit probability \\(p = \\beta - \\alpha\\).[1](https://dl.acm.org/doi/10.1145/1268776.1268777) • [2](https://www.cs.fsu.edu/~mascagni/Testing.pdf)\n\n| Key fact | Detail |\n|---|---|\n| What a gap measures | The number of steps between successive visits of the sequence to a set \\(A \\subset [0,1]\\), usually an interval \\([\\alpha, \\beta]\\) with hit probability \\(p = \\beta - \\alpha\\)[1](https://dl.acm.org/doi/10.1145/1268776.1268777) |\n| Null distribution | Gap lengths are independent \\(\\mathrm{Geom}_{0}(p)\\): \\(P(Z = z) = p \\cdot (1-p)^z\\) for \\(z = 0, 1, 2, \\ldots\\)[3](https://www.uni-ulm.de/fileadmin/website_uni_ulm/mawi.inst.110/lehre/ws14/monte_carlo/Skript_Kroese.pdf) |\n| Test statistic | \\( X^2 = \\sum_{i=1}^{k} (c_i - e_i)^2 / e_i\\) with \\( e_i = n_{\\mathrm{gaps}} \\cdot p \\cdot (1-p)^{i-1} \\) for \\(i[4](https://support.nag.com/numeric/cl/nagdoc_cl26/html/g08/g08edc.html) |\n| Validity condition | The expected number per class should exceed 5; sparse tail bins are pooled into a final \"length \\(k\\) or more\" class[3](https://www.uni-ulm.de/fileadmin/website_uni_ulm/mawi.inst.110/lehre/ws14/monte_carlo/Skript_Kroese.pdf) • [4](https://support.nag.com/numeric/cl/nagdoc_cl26/html/g08/g08edc.html) |\n| Boundary handling | An unfinished gap at the end of a sequence is not counted, unless the routine is called again and the gap is carried forward[4](https://support.nag.com/numeric/cl/nagdoc_cl26/html/g08/g08edc.html) • [5](https://support.nag.com/numeric/py/nagdoc_latest/naginterfaces.library.nonpar.randtest_gaps.html) |\n| Suite membership | Included in a classical 12-test battery long used in simulation and cryptography, and in TestU01; absent from the 15 subtests of NIST SP 800-22[6](https://dl.acm.org/doi/fullHtml/10.1145/3447773) • [7](https://www.govinfo.gov/content/pkg/GOVPUB-C13-PURL-LPS115523/pdf/GOVPUB-C13-PURL-LPS115523.pdf) |\n\n## How it works\n\nIf the sequence is a draw of independent uniform variates, each draw hits the interval \\((\\alpha, \\beta)\\) with probability \\(p = \\beta - \\alpha\\), independently of all others. The gap lengths \\(Z_i\\) between successive hits are then independent geometric random variables on \\(\\{0, 1, 2, \\ldots\\}\\), with\n\n\\[ P(Z = z) = p \\cdot (1-p)^z, \\qquad z = 0, 1, 2, \\ldots \\]\n\nThis follows because a gap of length \\(z\\) requires \\(z\\) consecutive misses, each with probability \\(1-p\\), followed by a hit.[3](https://www.uni-ulm.de/fileadmin/website_uni_ulm/mawi.inst.110/lehre/ws14/monte_carlo/Skript_Kroese.pdf) The test compares the observed counts of each gap length against these expected probabilities using a chi-square statistic. In the NAG formulation, gaps of lengths \\(1, \\ldots, k-1\\) get expected counts \\(e_i = n_{\\mathrm{gaps}} \\cdot p \\cdot (1-p)^{i-1}\\), the pooled final class gets \\(e_k = n_{\\mathrm{gaps}} \\cdot (1-p)^{k-1}\\), and\n\n\\[ X^2 = \\sum_{i=1}^{k} \\frac{(c_i - e_i)^2}{e_i} \\]\n\nis referred to a chi-square distribution with \\(k\\) degrees of freedom.[4](https://support.nag.com/numeric/cl/nagdoc_cl26/html/g08/g08edc.html) A practitioner guide instead gives degrees of freedom as the number of bins minus 2, treating \\(p\\) as estimated; the implementations differ on this point.[8](https://metricgate.com/docs/gap-test/) Implementations also differ in indexing: NAG counts gap lengths from 1, while several textbook treatments index gap lengths from 0 with probabilities \\(p_0 = p\\), \\(p_1 = p \\cdot (1-p)\\), \\(p_2 = p \\cdot (1-p)^2\\), and so on.[2](https://www.cs.fsu.edu/~mascagni/Testing.pdf) • [4](https://support.nag.com/numeric/cl/nagdoc_cl26/html/g08/g08edc.html)\n\n## How it is done\n\nThe practitioner steps, assembled from the textbook algorithm and the software documentation, are:[2](https://www.cs.fsu.edu/~mascagni/Testing.pdf) • [4](https://support.nag.com/numeric/cl/nagdoc_cl26/html/g08/g08edc.html)\n\n1. Choose the target set: a single digit, a value, or an interval \\([\\alpha, \\beta]\\) inside the generator's range, giving hit probability \\(p\\).[1](https://dl.acm.org/doi/10.1145/1268776.1268777)\n2. Scan the sequence, incrementing a counter while draws fall outside the target; when a draw falls inside, record the number of misses plus one as one gap length and reset it.[2](https://www.cs.fsu.edu/~mascagni/Testing.pdf)\n3. Bin the gaps: lengths below a cutoff \\(k\\) get their own classes, and every gap of length \\(k\\) or greater is pooled into the final class \\(c_k\\).[4](https://support.nag.com/numeric/cl/nagdoc_cl26/html/g08/g08edc.html)\n4. Compute expected counts from the geometric probabilities and form the chi-square statistic; merge any bin whose expected frequency falls below 5.[4](https://support.nag.com/numeric/cl/nagdoc_cl26/html/g08/g08edc.html) • [8](https://metricgate.com/docs/gap-test/)\n5. Read a p-value from the chi-square distribution; a significant result indicates structure such as periodicity or clustering.[8](https://metricgate.com/docs/gap-test/)\n\nA Kolmogorov–Smirnov-style variant also exists: form the observed cumulative distribution of gap lengths, find the maximum deviation \\(D\\) from the theoretical cumulative distribution, and reject randomness if \\(D\\) exceeds the tabulated critical value.[9](https://www.eg.bucknell.edu/~xmeng/Course/CS6337/Note/master/node46.html)\n\nAn unfinished gap at the end of the sequence is not counted in the NAG C routine.[4](https://support.nag.com/numeric/cl/nagdoc_cl26/html/g08/g08edc.html) The NAG Python routine offers a multiple-call mode in which such an unfinished gap is carried into the next call and used, which matters when a long sequence is fed through in blocks.[5](https://support.nag.com/numeric/py/nagdoc_latest/naginterfaces.library.nonpar.randtest_gaps.html) The routine may also be set to exit early once a specified total number of gaps has been found.[4](https://support.nag.com/numeric/cl/nagdoc_cl26/html/g08/g08edc.html)\n\nThe chi-square approximation improves as the expected counts increase, and the integers \\(n\\) (sample size) and \\(r\\) (cutoff) should be chosen so the expected number per class is greater than 5.[3](https://www.uni-ulm.de/fileadmin/website_uni_ulm/mawi.inst.110/lehre/ws14/monte_carlo/Skript_Kroese.pdf) • [4](https://support.nag.com/numeric/cl/nagdoc_cl26/html/g08/g08edc.html) One guide recommends at least 20 to 30 gaps for a stable approximation, and another rule of thumb keeps the requested gap count somewhat below one eighth of the total sample size so the sequence is not exhausted first.[8](https://metricgate.com/docs/gap-test/) • [10](https://www.itmaybeahack.com/homepage/_static/rngtest/rngdoc.html) Taking \\(n\\) much larger than the bare minimum gives a more powerful test.[11](https://pi.math.cornell.edu/~mec/Winter2009/Luo/test/test.html)\n\n## Origin\n\nThe gap test belongs to the earliest generation of [randomness tests](https://www.edgepedia.org/randomness-test) for tables of random digits. A historical survey describes a set of four classical tests for digits, a frequency test checking uniformity and three others checking independence, the last of these a gap test that observes the number of positions between successive appearances of a given digit and counts the frequency of each gap size for comparison against expected values.[12](https://doi.org/10.1109/wsc.2017.8247790) An earlier and distinct test also called a \"gap test\" was defined on sequences of real numbers, using local maxima and minima and measuring the distance between a minimum and the next one; it is a precursor of a different lineage from the digit-spacing test described in this article. Testing procedures were revised in the following decades; a 1962 survey notes an error in an early testing procedure pointed out by Levene and Wolfowitz, and points to further tests introduced in the early 1940s.[13](https://jackgiffin.com/main/pdfs/Random-Number-Generators-T-E-Hull-and-A-R-Dobell.pdf) A 12-test battery that includes the gap test carried the test into standard simulation practice; a survey of cryptography testing states that this test battery was used in cryptography.[6](https://dl.acm.org/doi/fullHtml/10.1145/3447773) • [14](https://www.informit.com/articles/article.aspx?p=2221790)\n\n## Variants\n\nThe interval form is the general version: any set \\(A \\subset [0,1]\\) with [Lebesgue measure](https://www.edgepedia.org/lebesgue-measure) \\(p\\) may serve, though an interval \\([\\alpha, \\beta]\\) is the usual choice.[1](https://dl.acm.org/doi/10.1145/1268776.1268777) Two special cases connect the gap test to the runs test: taking \\((\\alpha, \\beta) = (0, 1/2)\\) gives what is sometimes called runs above the mean, and \\((1/2, 1)\\) gives runs below the mean.[2](https://www.cs.fsu.edu/~mascagni/Testing.pdf) • [3](https://www.uni-ulm.de/fileadmin/website_uni_ulm/mawi.inst.110/lehre/ws14/monte_carlo/Skript_Kroese.pdf) On digit sequences, the test examines the interval between recurrences of the same digit; in a worked example with eighteen 3's in a digit list, only 17 gaps can occur.[9](https://www.eg.bucknell.edu/~xmeng/Course/CS6337/Note/master/node46.html) The randtoolbox R package implements the test with indicator variables equal to 1 when \\(\\mathrm{lower} \\le U_i \\le \\mathrm{upper}\\), computing the lengths of the resulting zero gaps and the chi-square statistic \\(S = \\sum_{j=1}^m (n_j - n \\cdot p_j)^2 / (n \\cdot p_j)\\).[15](https://rdrr.io/cran/randtoolbox/man/gaptest.html)\n\n## Applications\n\nSuite membership is uneven. The classical 12-test battery used in cryptography includes the gap test, defined there as counting, for each element, how many elements differ from it before it recurs, followed by a chi-square test on the gap lengths.[6](https://dl.acm.org/doi/fullHtml/10.1145/3447773) NIST SP 800-22 lists 15 subtests, including the [Frequency](https://www.edgepedia.org/frequency) (Monobit) Test, the Runs Test, the Binary Matrix Rank Test, and the Discrete Fourier Transform (Spectral) Test; the gap test is not among them.[7](https://www.govinfo.gov/content/pkg/GOVPUB-C13-PURL-LPS115523/pdf/GOVPUB-C13-PURL-LPS115523.pdf) TestU01, a C library for empirical testing of uniform RNGs, implements the gap test among classical and literature-derived tests and offers six predefined batteries: SmallCrush, Crush, and BigCrush for \\((0,1)\\) values, and Rabbit, Alphabit, and BlockAlphabit for bit sequences.[1](https://dl.acm.org/doi/10.1145/1268776.1268777) • [6](https://dl.acm.org/doi/fullHtml/10.1145/3447773) BigCrush can take more than ten hours per generator on a high-end PC, while SmallCrush is two orders of magnitude faster, so testing is advised to start there.[6](https://dl.acm.org/doi/fullHtml/10.1145/3447773)\n\n## Limitations and alternatives\n\nThe result depends on the choice of interval \\([a, b]\\), and the test examines only within-interval gap structure; it cannot detect trends in the values themselves.[8](https://metricgate.com/docs/gap-test/) Correlated sequences inflate the Type I error rate, and small samples reduce power.[8](https://metricgate.com/docs/gap-test/) As alternatives, the runs test covers above- and below-mean excursions as special cases of the same interval framework, the Kolmogorov–Smirnov variant replaces binned chi-square comparison with a maximum-deviation criterion, and modern batteries such as TestU01's SmallCrush, Crush, and BigCrush bundle the gap test with many stronger tests of local and global structure.[1](https://dl.acm.org/doi/10.1145/1268776.1268777) • [2](https://www.cs.fsu.edu/~mascagni/Testing.pdf) • [9](https://www.eg.bucknell.edu/~xmeng/Course/CS6337/Note/master/node46.html)\n\n## References\n\n1. [TestU01: A C library for empirical testing of random number generators](https://dl.acm.org/doi/10.1145/1268776.1268777)\n2. [Testing Random Numbers: Theory and Practice](https://www.cs.fsu.edu/~mascagni/Testing.pdf)\n3. [Monte Carlo Methods (Kroese course notes, Section 1.4.3 Gap Tests)](https://www.uni-ulm.de/fileadmin/website_uni_ulm/mawi.inst.110/lehre/ws14/monte_carlo/Skript_Kroese.pdf)\n4. [nag_gaps_test (g08edc): NAG Library, Mark 26](https://support.nag.com/numeric/cl/nagdoc_cl26/html/g08/g08edc.html)\n5. [naginterfaces.library.nonpar.randtest_gaps, NAG Library for Python 31.1.0.0](https://support.nag.com/numeric/py/nagdoc_latest/naginterfaces.library.nonpar.randtest_gaps.html)\n6. [Recommendations on Statistical Randomness Test Batteries for Cryptographic Purposes](https://dl.acm.org/doi/fullHtml/10.1145/3447773)\n7. [A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications (NIST SP 800-22)](https://www.govinfo.gov/content/pkg/GOVPUB-C13-PURL-LPS115523/pdf/GOVPUB-C13-PURL-LPS115523.pdf)\n8. [Gap Test for Randomness Calculator | MetricGate](https://metricgate.com/docs/gap-test/)\n9. [Gap Test (course notes, Bucknell CS6337)](https://www.eg.bucknell.edu/~xmeng/Course/CS6337/Note/master/node46.html)\n10. [Empirical Tests of Random Number Generators](https://www.itmaybeahack.com/homepage/_static/rngtest/rngdoc.html)\n11. [Section IV: Tests, Gap test (Cornell MEC)](https://pi.math.cornell.edu/~mec/Winter2009/Luo/test/test.html)\n12. [History of uniform random number generation (L'Ecuyer)](https://doi.org/10.1109/wsc.2017.8247790)\n13. [Hull, T.E. and A.R. Dobell, \"Random Number Generators,\" SIAM Review 4.3 (1962) 230–254](https://jackgiffin.com/main/pdfs/Random-Number-Generators-T-E-Hull-and-A-R-Dobell.pdf)\n14. [The Art of Computer Programming: Random Numbers (Knuth, InformIT excerpt)](https://www.informit.com/articles/article.aspx?p=2221790)\n15. [gaptest: the Gap test in randtoolbox](https://rdrr.io/cran/randtoolbox/man/gaptest.html)\n\n---\n*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Statistics and probability › Statistical inference, estimation, sampling, and testing › Hypothesis testing*\n\n*Initially written Sep 29, 2026 · Reviewed: Sep 30, 2026 · Edited: Oct 15, 2026 · Last review: Sep 30, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [ "https://www.cs.fsu.edu/~mascagni/Testing.pdf", "https://www.eg.bucknell.edu/~xmeng/Course/CS6337/Note/master/node46.html", "https://pi.math.cornell.edu/~mec/Winter2009/Luo/test/test.html" ], "url": "https://www.edgepedia.org/gap-test-randomness-testing", "markdown_url": "https://www.edgepedia.org/gap-test-randomness-testing.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Gap test (randomness testing)\", Edgepedia (EdgeChat), https://www.edgepedia.org/gap-test-randomness-testing. Edgepedia Community License 1.0.", "credit_md": "\"[Gap test (randomness testing)](https://www.edgepedia.org/gap-test-randomness-testing)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/gap-test-randomness-testing](https://www.edgepedia.org/gap-test-randomness-testing). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Gap test (randomness testing)\", Edgepedia (EdgeChat), https://www.edgepedia.org/gap-test-randomness-testing. Edgepedia Community License 1.0.", "speakable": "The gap test is a chi-square goodness-of-fit test checking whether spacings between recurrences of a chosen value in a random number sequence follow the expected geometric distribution." }