A Worked Exact Runs Test on a Binary Sequence

Why an Exact Runs Test?

A sequence can contain the right number of each outcome and still have an unusual order. For example, a sequence of positive and negative daily changes might alternate often, or one outcome might appear in a long block. The runs test asks whether the observed ordering is consistent with randomness, given the numbers of the two outcomes. It uses the order of the observations, not their numerical magnitudes.

For a short sequence, an exact test is useful because it calculates probabilities from all possible orderings with the same symbol totals. It does not rely on a normal approximation. The exact calculation is conditional: it treats the observed numbers of each outcome as fixed and asks how likely the observed run count would be among their possible arrangements.

Definition: A run is a maximal consecutive block of identical symbols. In the sequence $A,A,B,B,A,B$, the runs are $AA$, $BB$, $A$, and $B$, so the run count is $R=4$. A new run begins each time the symbol changes.

Exact Null Distribution for Fixed Symbol Totals

Suppose a sequence contains $n_A$ symbols of type $A$ and $n_B$ symbols of type $B$, with $n_A,n_B\geq 1$, and let $n=n_A+n_B$. Under the null model for this exact test, every ordering of these fixed symbols is equally likely. This assumption holds, for example, if the symbols were generated independently with the same probability of $A$, conditional on observing the given totals. There are $\binom{n}{n_A}$ possible orderings.

The exact distribution of $R$ can be obtained by counting how many of these orderings have each possible run count. For an even run count $r=2k$, the sequence must have $k$ runs of $A$ and $k$ runs of $B$. For an odd run count $r=2k+1$, one symbol has $k+1$ runs and the other has $k$. The number of ways to split $n_A$ identical symbols into $j$ positive-length runs is $\binom{n_A-1}{j-1}$: place $j-1$ dividers in the $n_A-1$ gaps between symbols. The same count applies to the $B$ symbols.

Theorem: Under the fixed-total random-ordering null model, $$ P(R=2k)= \frac{2\binom{n_A-1}{k-1}\binom{n_B-1}{k-1}} {\binom{n_A+n_B}{n_A}}. $$ For an odd run count $r=2k+1$, $$ P(R=2k+1)= \frac{ \binom{n_A-1}{k}\binom{n_B-1}{k-1} + \binom{n_A-1}{k-1}\binom{n_B-1}{k} } {\binom{n_A+n_B}{n_A}}. $$ A binomial coefficient is zero when its lower index is outside the range from zero to its upper index. This convention handles impossible run counts at the endpoints.

The factor of 2 in the even formula accounts for the two possible starting symbols. In the odd formula, the first term counts orderings with one more $A$-run than $B$-runs; the second counts the reverse. As a check on a computed distribution, the probabilities over all possible run counts must add to 1.

Choosing and Interpreting a Two-Sided Exact Test

A small run count suggests clustering; a large run count suggests unusually frequent alternation. For a two-sided test, this tutorial uses the following explicit rule: calculate the null expected run count, then include in the p-value every possible run count whose absolute distance from that expectation is at least the observed distance. Since

E[R]=1+\frac{2n_A n_B}{n_A+n_B},

the exact two-sided p-value for observed run count $r_{\mathrm{obs}}$ is

p_{\mathrm{exact}} = \sum_{\substack{r:\ |r-E[R]|\geq |r_{\mathrm{obs}}-E[R]|}} P(R=r).

This is a discrete test: the p-value is a sum of exact probabilities, and not every significance level can be attained exactly. Other two-sided exact-test conventions exist and can give different p-values. State the convention used when reporting a result. For the examples and practice below, compare the p-value with $\alpha=0.05$: reject the null when $p_{\mathrm{exact}}\leq 0.05$. A rejection is evidence against random ordering under the stated model, not proof of a particular cause.

Worked Exact Tests

Worked Example: A Sequence With a Moderate Run Count

A hypothetical monitoring system records seven consecutive alerts as $A,A,B,A,B,A,A$. Treat the two alert types as $A$ and $B$. Test for non-random ordering using the fixed-total exact test at $\alpha=0.05$ and the absolute-distance convention above.

Method and observed count. The symbol totals are $n_A=4$, $n_B=3$, so there are $\binom{7}{4}=35$ possible orderings under the conditional null. Grouping consecutive identical symbols gives $AA|B|A|B|AA$, hence $r_{\mathrm{obs}}=5$.

Calculate the relevant null probabilities. The possible run counts are 2 through 7. Applying the exact formulas gives:

$P(R=2)=2/35$. For $R=3$, the count is $\binom{3}{1}\binom{2}{0}+\binom{3}{0}\binom{2}{1}=3+2=5$, so $P(R=3)=5/35$. For $R=4$, the count is $2\binom{3}{1}\binom{2}{1}=12$, so $P(R=4)=12/35$. For $R=5$, the count is $\binom{3}{2}\binom{2}{1}+\binom{3}{1}\binom{2}{2}=6+3=9$, so $P(R=5)=9/35$. For $R=6$, the count is $2\binom{3}{2}\binom{2}{2}=6$, so $P(R=6)=6/35$. Finally, $P(R=7)=1/35$. The counts total $2+5+12+9+6+1=35$, as required.

Calculate the p-value. The expected count is $E[R]=1+2(4)(3)/7=31/7\approx4.4286$. The observed distance is $|5-31/7|=4/7\approx0.5714$. Run counts at least this far from the expectation are $2,3,5,6,7$; $R=4$ is closer and is excluded. Therefore

p_{\mathrm{exact}}=\frac{2+5+9+6+1}{35} =\frac{23}{35}\approx0.6571.

Decision and check. Since $0.6571>0.05$, do not reject the null model. The observed order is not unusually far from the null expected run count by this test. The probability totals checked to 1, and the observed run count has exact null probability $9/35$. A common mistake is to use $9/35$ itself as the two-sided p-value; that is only the probability of exactly five runs, not the probability of all outcomes at least as extreme under the stated rule.

Worked Example: A Strongly Clustered Sequence

A hypothetical quality check classifies nine consecutive components as $A,A,A,A,A,B,B,B,B$. Using the fixed-total exact test and the same two-sided convention, assess whether the ordering is consistent with randomness at $\alpha=0.05$.

Method and observed count. There are $n_A=5$ and $n_B=4$, giving $\binom{9}{5}=126$ possible orderings. The sequence has two runs, $AAAAA|BBBB$, so $r_{\mathrm{obs}}=2$. Its null probability is

P(R=2)= \frac{2\binom{4}{0}\binom{3}{0}}{126} =\frac{2}{126}.

Find the two-sided tail. The null expected run count is $E[R]=1+2(5)(4)/9=49/9\approx5.4444$. The observed distance is $|2-49/9|=31/9\approx3.4444$. The minimum possible run count, 2, is that far from the expectation. The maximum possible run count is 9, whose distance is $|9-49/9|=32/9\approx3.5556$, also at least as large. Every other possible count, from 3 through 8, is closer than the observed count. There are two orderings with two runs and two with nine runs, so

p_{\mathrm{exact}}=P(R=2)+P(R=9) =\frac{2}{126}+\frac{2}{126} =\frac{4}{126}\approx0.0317.

Decision and check. Since $0.0317\leq0.05$, reject the null model. The ordering has unusually few runs, consistent with clustering. The probability $P(R=9)=2/126$ follows by the same endpoint count as for two runs: the two symbols must alternate, starting with either symbol. The common mistake is to include only the lower tail for a two-sided test; here the high-run endpoint is also at least as far from the null mean and must be included under the stated rule.

Worked Example: Unusually Frequent Alternation

A hypothetical sequence of six machine states is $A,B,A,B,A,B$. With $n_A=n_B=3$, use the exact two-sided test at $\alpha=0.05$ to assess its ordering.

Method and observed count. The sequence changes symbol at every position, so it has $r_{\mathrm{obs}}=6$ runs. The number of possible arrangements is $\binom{6}{3}=20$, and the expected run count is $E[R]=1+2(3)(3)/6=4$.

Calculate the full distribution. For $R=2$, the count is $2$, giving probability $2/20$. For $R=3$, the count is $\binom{2}{1}\binom{2}{0}+\binom{2}{0}\binom{2}{1}=4$, giving $4/20$. For $R=4$, the count is $2\binom{2}{1}\binom{2}{1}=8$, giving $8/20$. For $R=5$, the count is $\binom{2}{2}\binom{2}{1}+\binom{2}{1}\binom{2}{2}=4$, giving $4/20$. For $R=6$, the count is $2\binom{2}{2}\binom{2}{2}=2$, giving $2/20$. These counts sum to $2+4+8+4+2=20$.

Calculate the p-value and decide. The observed distance is $|6-4|=2$. Only run counts 2 and 6 are at least two units from the expectation; their probabilities give

p_{\mathrm{exact}}=\frac{2+2}{20}=0.2000.

Since $0.2000>0.05$, do not reject the null model. The sequence alternates completely, but with these small fixed totals, its exact two-sided p-value is not below the chosen significance level. The calculation also checks both tails: counting only $R=6$ would incorrectly omit $R=2$, which is equally far from the expected count.

Assumptions, Scope, and Exam Traps

The exact calculation removes approximation error, but it does not remove the need for a suitable model. The observations must form an ordered sequence of two outcomes, and the null model must justify treating all orderings with the observed totals as equally likely. The test conditions on those totals; it does not test whether the overall proportion of $A$ symbols has a particular value.

Do not count symbols instead of changes. Runs are consecutive blocks, not the number of $A$'s or $B$'s.
Do not use an unconditional denominator. With fixed totals, the number of possible orderings is $\binom{n_A+n_B}{n_A}$.
Do not confuse a point probability with a p-value. $P(R=r_{\mathrm{obs}})$ is generally only one term in the selected tail sum.
State the two-sided convention. Discrete exact tests can use different definitions of two-sided extremeness; the convention determines which outcomes are added.
Keep the conclusion limited. A small p-value is evidence against random ordering under the specified null model. It does not identify why the pattern occurred.

Key takeaway: Count the observed runs, condition on the two observed symbol totals, enumerate the exact null distribution, and sum the probabilities at least as extreme as the observed count under a clearly stated two-sided rule.

Check Your Understanding

For each problem, use the fixed-total exact null model and the absolute-distance two-sided convention defined above. Unless a different level is stated, use $\alpha=0.05$.

A five-observation sequence is $A,A,A,B,B$. Find its run count and its exact point probability under the null. (Answer: $R=2$, $P(R=2)=2/10=0.2000$.)
A six-observation sequence is $A,B,B,A,A,A$, with $n_A=4$ and $n_B=2$. Find the observed run count and its exact point probability. (Answer: $R=3$, $P(R=3)=4/15=0.2667$.)
A sequence has $n_A=3,n_B=2$ and is observed as $A,A,A,B,B$. Find $E[R]$, the two-sided exact p-value, and the decision at $\alpha=0.05$. (Answer: $E[R]=3.4$, $p_{\mathrm{exact}}=3/10=0.3000$; do not reject.)
A balanced sequence with three $A$'s and three $B$'s is observed as $A,B,A,B,B,A$. Find its run count and two-sided exact p-value. (Answer: $R=5$, $p_{\mathrm{exact}}=12/20=0.6000$.)
A sequence contains four $A$'s and three $B$'s and alternates as much as possible, with $R=7$. Find the exact point probability and the two-sided p-value under the stated convention. (Answer: $P(R=7)=1/35=0.0286$, $p_{\mathrm{exact}}=1/35=0.0286$; reject at $\alpha=0.05$.)

What You'll Learn