Exact Distribution of the Number of Runs

Why an Exact Runs Distribution Is Useful

A runs test examines the order of two kinds of symbols in a sequence. If observations are labelled A or B, a run is a maximal consecutive block of identical symbols. For example, AABABB has four runs: AA, B, A, and BB. The total number of each symbol does not determine the run count: rearranging the same symbols can produce strong clustering or frequent alternation.

For a small sample, the distribution of the number of runs can be found by counting every possible ordering with the observed symbol totals. This gives exact probabilities under the random-ordering model, without relying on a large-sample approximation. The key is to use the correct sample space: all arrangements with the specified numbers of A and B, not all binary sequences of that length.

Definition: Suppose a sequence contains $n_A$ symbols A and $n_B$ symbols B, with $n_A,n_B\geq 1$. Let $N=n_A+n_B$, and let $R$ be its number of runs. Under the conditional random-ordering model, every distinct sequence with these fixed symbol totals is equally likely. There are $\binom{N}{n_A}$ such sequences, so $P(R=r)$ is the number of these sequences with $r$ runs divided by $\binom{N}{n_A}$.

This model is appropriate when the test’s null hypothesis says that, conditional on the observed numbers of the two symbols, their order is random. It does not assert that the symbol totals themselves are random in a particular way. If either symbol is absent, there is just one possible ordering and $R=1$; the counting formulas below are stated for both totals positive.

Counting Sequences With a Given Number of Runs

A run-counting problem can be viewed as a problem about blocks. If there are $k$ runs of A, then the A symbols have been divided into $k$ nonempty blocks. The number of ways to divide $n_A$ identical symbols into $k$ ordered, nonempty blocks is $\binom{n_A-1}{k-1}$: place $k-1$ dividers in the $n_A-1$ gaps between consecutive symbols. The same reasoning applies to the B symbols.

The blocks of A and B must alternate. For an even number of runs, the sequence starts and ends with different symbols, so the number of A-blocks equals the number of B-blocks. For an odd number, one symbol has one more block than the other; there are two possible starting symbols.

Theorem: For $n_A,n_B\geq 1$, the number $C_r$ of sequences with exactly $r$ runs is $$ C_{2k}=2\binom{n_A-1}{k-1}\binom{n_B-1}{k-1} $$ for $k\geq 1$, and $$ C_{2k+1}= \binom{n_A-1}{k}\binom{n_B-1}{k-1} + \binom{n_A-1}{k-1}\binom{n_B-1}{k} $$ for $k\geq 0$. A binomial coefficient is zero when its lower index is negative or greater than its upper index. Thus the formulas automatically give zero for impossible run counts. The exact probability is $$ P(R=r)=\frac{C_r}{\binom{n_A+n_B}{n_A}}. $$

Why the Counting Formulas Hold

For $2k$ runs, there must be $k$ A-blocks and $k$ B-blocks. If the sequence starts with A, its block pattern is A, B, A, B, and so on, ending with B. The A symbols can be split into $k$ nonempty blocks in $\binom{n_A-1}{k-1}$ ways, and the B symbols can be split in $\binom{n_B-1}{k-1}$ ways. Starting with B gives the same number of choices, accounting for the factor of 2.

For $2k+1$ runs, a sequence starting with A has $k+1$ A-blocks and $k$ B-blocks. The number of such sequences is $\binom{n_A-1}{k}\binom{n_B-1}{k-1}$. A sequence starting with B instead has $k$ A-blocks and $k+1$ B-blocks, giving $\binom{n_A-1}{k-1}\binom{n_B-1}{k}$. These starting cases are disjoint, so their counts add.

Dividing by $\binom{n_A+n_B}{n_A}$ converts each count into a probability because, under the stated model, each fixed-total sequence has the same probability. A useful check is that the counts over all possible run values must add to $\binom{n_A+n_B}{n_A}$.

Worked Example: Find the Entire Exact Distribution

A sequence has four A symbols and three B symbols. Under conditional random ordering, find the exact distribution of $R$, the number of runs.

Method. Use the block-count formulas and divide each count by the total number of fixed-total sequences. The sample-space size is $\binom{7}{4}=35$.

The possible run counts range from 2 (all symbols of each type together) to 7 (complete alternation is possible because the totals differ by only one). Apply the formulas:

$r=2$: $C_2=2\binom{3}{0}\binom{2}{0}=2$.
$r=3$: $C_3=\binom{3}{1}\binom{2}{0}+\binom{3}{0}\binom{2}{1}=3+2=5$.
$r=4$: $C_4=2\binom{3}{1}\binom{2}{1}=2(3)(2)=12$.
$r=5$: $C_5=\binom{3}{2}\binom{2}{1}+\binom{3}{1}\binom{2}{2}=6+3=9$.
$r=6$: $C_6=2\binom{3}{2}\binom{2}{2}=2(3)(1)=6$.
$r=7$: $C_7=\binom{3}{3}\binom{2}{2}+\binom{3}{2}\binom{2}{3}=1+0=1$.

Therefore the probabilities are $2/35, 5/35, 12/35, 9/35, 6/35,$ and $1/35$, respectively. As a check, the counts add to $2+5+12+9+6+1=35$, the full sample-space size. The common mistake to avoid is treating all $2^7=128$ binary strings as equally likely: most do not have exactly four A symbols and three B symbols.

Using Exact Probabilities to Form a Critical Region

A critical region specifies which observed run counts lead to rejection of a null hypothesis. The direction of the alternative matters. A clustering alternative looks for unusually few runs; an alternation alternative looks for unusually many. For a one-sided clustering test with significance level $\alpha$, accumulate probabilities from the smallest possible run count upward. Include run counts only while their total probability does not exceed $\alpha$. Because $R$ takes discrete values, the resulting test may have size less than $\alpha$.

The probability of a tail is an exact probability under the conditional random-ordering model. It is not generally equal to the nominal significance level. In particular, do not include the next possible value merely because doing so would make the critical region closer to $\alpha$: that would exceed the specified level.

Worked Example: Construct a Small-Sample Clustering Region

A sequence contains five A symbols and four B symbols. For a one-sided test of clustering, find a nonrandomized lower-tail critical region with significance level $0.10$. Also calculate the exact tail probability when the observed number of runs is 3.

Method. Count the lower tail under conditional random ordering. The total number of sequences is $\binom{9}{5}=126$.

The smallest possible run count is 2. Its count is $C_2=2\binom{4}{0}\binom{3}{0}=2$, so $P(R=2)=2/126$. For three runs, $C_3=\binom{4}{1}\binom{3}{0}+\binom{4}{0}\binom{3}{1}=4+3=7$. Thus $P(R\leq 3)=(2+7)/126=9/126=0.0714$, to four decimal places.

The next count is $C_4=2\binom{4}{1}\binom{3}{1}=2(4)(3)=24$. Including $R=4$ would give $P(R\leq 4)=(2+7+24)/126=33/126=0.2619$, which is greater than $0.10$. Therefore the largest lower-tail critical region not exceeding the level is $R\leq 3$, with actual size $0.0714$. If the observed value is 3, its lower-tail probability is also $0.0714$. The correction to the common “closest to 0.10” mistake is to keep the nonrandomized region at or below the specified level.

Worked Example: Combine Exact Point and Tail Probabilities

A sequence has six A symbols and five B symbols. Find the probability of exactly six runs and the upper-tail probability $P(R\geq 9)$. The upper tail corresponds to unusually frequent alternation.

Method. Calculate the relevant sequence counts, then divide by the fixed-total sample-space size $\binom{11}{6}=462$.

For six runs, $r=2k$ with $k=3$. Hence $C_6=2\binom{5}{2}\binom{4}{2}=2(10)(6)=120$, and $P(R=6)=120/462=0.2597$, to four decimal places.

For nine runs, the odd-run formula has $k=4$: $C_9=\binom{5}{4}\binom{4}{3}+\binom{5}{3}\binom{4}{4}=5(4)+10(1)=30$. For ten runs, $C_{10}=2\binom{5}{4}\binom{4}{4}=2(5)(1)=10$. For eleven runs, $C_{11}=\binom{5}{5}\binom{4}{4}+\binom{5}{4}\binom{4}{5}=1+0=1$. Therefore $P(R\geq 9)=(30+10+1)/462=41/462=0.0887$, to four decimal places.

The results pass a range check: eleven runs are possible only by alternating as far as the unequal symbol totals allow, and the count for that endpoint is one, corresponding to the unique sequence that starts and ends with A. The trap avoided here is reporting $P(R=9)$ as the upper-tail probability; the tail must also include the probabilities for 10 and 11 runs.

Common Errors and Practical Checks

Exact counting is manageable when each step is tied to the fixed-total sample space. Before using a calculated probability, check that the run count is feasible, that each block is nonempty, and that the denominator matches the observed symbol totals.

Using the wrong denominator. With fixed totals, the denominator is $\binom{n_A+n_B}{n_A}$, not $2^{n_A+n_B}$. The latter treats strings with different symbol totals as possible outcomes in the conditional model.
Forgetting the two starting symbols. The even-run formula has a factor of 2 because either symbol can start the alternating block pattern. The odd-run formula adds two different starting cases instead.
Counting transitions rather than runs. The number of runs is one more than the number of changes between adjacent symbols. For instance, AABABB has three changes and four runs.
Including an impossible run count. A sequence cannot have more runs than symbols, and the block formulas also require enough symbols to make every block nonempty. The zero-binomial convention handles such cases.
Mixing point probabilities and tail probabilities. $P(R=r)$ concerns one run count; a one-sided test probability sums all outcomes at least as extreme in the specified direction.

For a two-sided alternative, “as extreme” must be defined by the testing convention being used; different exact two-sided conventions can produce different regions for a discrete distribution. The counting formulas still supply all the probabilities needed, but the tail rule should be stated rather than assumed.

Key takeaway: With fixed numbers of two symbols, count alternating blocks of each type, divide by $\binom{n_A+n_B}{n_A}$, and sum the appropriate exact tail to form a critical region. Check that all run-count probabilities add to one.

Check Your Understanding

For each problem, use the conditional random-ordering model and the exact block-count formulas.

A sequence has three A symbols and two B symbols. Find $P(R=3)$. (Answer: $3/10=0.3000$)
A sequence has four A symbols and four B symbols. Find $P(R=2)$. (Answer: $2/70=0.0286$)
A sequence has three A symbols and four B symbols. Find $P(R\geq 6)$. (Answer: $7/35=0.2000$)
A sequence has five A symbols and three B symbols. Find the lower-tail probability $P(R\leq 3)$. (Answer: $8/56=0.1429$)
A sequence has four A symbols and three B symbols. For a one-sided alternation test, find $P(R\geq 6)$. (Answer: $7/35=0.2000$)

What You'll Learn