Exact Conditional Runs Test

Concept Overview

A run is a maximal consecutive block of identical symbols in an ordered sequence. For a binary sequence of zeroes and ones, analyzing the number of runs provides a non-parametric test for randomness. If the symbols are arranged randomly, the number of runs will typically fall within a predictable range.

The Exact Conditional Runs Test conditions on the observed total number of zeroes and ones. Instead of relying on a normal approximation, this module computes the exact discrete probability distribution (PMF) by enumerating all distinguishable combinations of the given elements uniformly.

Worked Example: Computing Runs

Consider the sequence 000111. We first identify the counts and observed runs:

1. There are n₀ = 3 zeroes and n₁ = 3 ones. The total length n = 6.
2. The total number of unique distinguishable arrangements is the binomial coefficient: 6 choose 3 = 20 assignments.
3. We observe 2 runs: one block of three zeroes followed by one block of three ones.

The conditional expected number of runs is given by:

E[R] = 1 + (2 · n0 · n1) / n = 1 + (2 · 3 · 3) / 6 = 1 + 18 / 6 = 4

To compute the p-value, we consider all run counts R and find those that are at least as extreme as our observed count. The absolute difference between the observed runs (2) and the mean (4) is |2 - 4| = 2. We sum the probabilities of all run counts R such that |R - 4| ≥ 2. In this case, R ≤ 2 or R ≥ 6.

The p-value is P(R=2) + P(R=6) = 1/10 + 1/10 = 1/5, or exactly 0.2.

Interactive Experiment

Open the Exact Conditional Runs Test module to test arbitrary short binary sequences.

1. Enter the sequence 000111 in the Sequence input. Verify that the expected runs (conditionalMean) is 4 and the p-value is exactly 1/5 (0.2).
2. Change the sequence to an alternating pattern: 010101. The number of runs is now 6. Notice that the distance from the mean is still 2, so the p-value remains 1/5.
3. Enter a sequence like 001011. This produces exactly 4 runs, perfectly matching the conditional mean. The p-value becomes 1, as all outcomes are at least as extreme as a distance of 0.

Limitations

This exact conditional test requires enumerating or computing combinatorial functions that grow rapidly with sequence length. The module restricts the length of the binary string to a maximum of 10 to guarantee fast execution and UI responsiveness.

Additionally, degenerate sequences (containing only one type of symbol, or the empty sequence) do not possess order-test information. In such degenerate cases, the conditional law is singular and does not prove or disprove randomness, instead it reflects the fundamental lack of variability in the sample.

References

NIST/SEMATECH e-Handbook of Statistical Methods: Runs Test for Detecting Non-randomness. Note that while the handbook describes a normal approximation for large samples, this module expressly uses the bounded original exact extremeness law without approximation.