Expected Runs and Variance Under Random Ordering

Why the Fixed Counts Matter

A runs statistic counts consecutive groups of identical symbols. For example, the sequence A A B A B B has four runs: A A, B, A, and B B. In a runs test, the observed number of runs is compared with what would be expected if the same observed counts of the two symbols had been placed in random order.

The fixed-count condition is essential. If a sequence contains \(n_1\) symbols of type A and \(n_2\) symbols of type B, random ordering means that every distinct arrangement of those \(N=n_1+n_2\) symbols is equally likely. It does not mean that each position receives an independent A or B with a fixed probability. The formulas for the expectation and variance below are for this uniform random permutation model.

Definition: A run is a maximal consecutive block of identical symbols. Let \(R\) be the number of runs in a sequence with \(n_1\) A symbols and \(n_2\) B symbols, where \(N=n_1+n_2\). Under the null model, the \(N\) symbols are randomly ordered, conditional on these counts: each distinct ordering is equally likely. Assume \(n_1\geq 1\) and \(n_2\geq 1\).

This model treats the sequence as a random permutation of fixed labels. For instance, it can represent a hypothetical process-monitoring record in which the numbers of observations above and below a specified reference value have already been fixed, and the question is whether their order is consistent with random ordering. No interest-rate or mortality assumption is involved: the model is a finite probability distribution over arrangements.

Expected Number of Runs

A useful way to count runs is to count changes between adjacent positions. A sequence always begins with one run. Each adjacent pair with different symbols starts one additional run. Write \(I_j=1\) if positions \(j\) and \(j+1\) have different symbols, and \(I_j=0\) otherwise, for \(j=1,\ldots,N-1\). Then

R=1+\sum_{j=1}^{N-1} I_j.

For any specified adjacent pair, there are \(N(N-1)\) ordered ways to fill its two positions from the fixed collection of symbols. There are \(n_1n_2\) ways to place A then B, and \(n_2n_1\) ways to place B then A. Thus the probability of a change at that pair is \(2n_1n_2/[N(N-1)]\). By linearity of expectation, the expected number of changes is the sum of this probability over the \(N-1\) adjacent pairs.

Theorem: Under uniform random ordering with fixed, positive counts \(n_1\) and \(n_2\), the expected number of runs is

E[R]=1+\frac{2n_1n_2}{N}, \qquad N=n_1+n_2.

Worked Example: Expected Runs With Unequal Counts

A hypothetical quality-control record has five A labels and three B labels. Conditional on those counts, suppose all distinct orderings are equally likely. Find the expected number of runs. This is a fixed-count random-permutation model; no interest or mortality assumption applies.

Method. Use the adjacent-change indicator argument. Here \(n_1=5\), \(n_2=3\), and \(N=5+3=8\).

The probability that a specified adjacent pair differs is

P(I_j=1)=\frac{2(5)(3)}{8(7)}=\frac{30}{56}=\frac{15}{28}.

There are \(N-1=7\) adjacent pairs, so the expected number of changes is

E\left[\sum_{j=1}^{7} I_j\right]=7\left(\frac{15}{28}\right)=\frac{15}{4}=3.75.

Adding the initial run gives

E[R]=1+\frac{15}{4}=\frac{19}{4}=4.75.

The common mistake is to use an independent-position probability for a change, even though the counts are fixed. The fixed-count adjacent-pair probability is \(15/28\), not \(2(5/8)(3/8)\). The computed expectation is between the smallest possible number of runs, 2, and the largest possible number, 7, as it should be.

Variance: Why Adjacent Changes Are Dependent

The indicators \(I_j\) are not independent. In particular, \(I_j\) and \(I_{j+1}\) share a position. Even indicators for disjoint pairs are dependent because the total counts of A and B are fixed. Therefore, adding the individual indicator variances alone does not give the variance of \(R\); the covariances must also be included.

Set \(a=n_1\) and \(b=n_2\), so \(N=a+b\), and write \(p=2ab/[N(N-1)]\). For two neighboring indicators to both equal 1, their three positions must have the pattern A-B-A or B-A-B. Counting these patterns gives

E[I_jI_{j+1}] =\frac{ab(a-1)+ab(b-1)}{N(N-1)(N-2)} =\frac{ab}{N(N-1)}.

The last equality uses \((a-1)+(b-1)=N-2\). Thus the covariance for a neighboring pair of indicators is \(ab/[N(N-1)]-p^2\).

For two non-overlapping adjacent pairs, both pairs must contain one A and one B. There are four possible orientations across the two pairs. Counting assignments to their four positions gives

E[I_jI_k] =\frac{4a(a-1)b(b-1)}{N(N-1)(N-2)(N-3)}, \qquad |j-k|>1,

when \(N\geq 4\). The corresponding covariance is this joint probability minus \(p^2\). There are \(N-2\) neighboring pairs of indicators, and \((N-2)(N-3)/2\) non-overlapping pairs. Applying the variance-of-a-sum identity, which includes twice the covariance for each unordered pair, gives the following expression before simplification:

\begin{aligned} \operatorname{Var}(R) ={}&(N-1)p(1-p)\\ &+2(N-2)\left(\frac{ab}{N(N-1)}-p^2\right)\\ &+(N-2)(N-3)\left( \frac{4a(a-1)b(b-1)}{N(N-1)(N-2)(N-3)}-p^2 \right). \end{aligned}

Substituting \(p=2ab/[N(N-1)]\) and \(a+b=N\), then collecting terms over a common denominator, simplifies this expression to

Theorem: For two nonempty symbol groups randomly ordered with their counts fixed,

\operatorname{Var}(R) =\frac{2n_1n_2(2n_1n_2-N)}{N^2(N-1)}.

This formula also gives the correct values for \(N=2\) and \(N=3\), for which there are no non-overlapping pairs of indicators (and the joint-probability calculation for such pairs is unnecessary).

The derivation shows why dependence matters: the variance contains contributions from both overlapping and disjoint pairs. The final formula is nonnegative because \(n_1,n_2\geq1\) implies \(2n_1n_2\geq n_1+n_2=N\). Equality occurs when one count is 1 and \(N=2\), where the ordering and number of runs are fixed.

Worked Example: Variance for Balanced Counts

A hypothetical sequence contains four A labels and four B labels. Conditional on these counts, every ordering is equally likely. Find the mean and variance of the number of runs. This is a fixed-count permutation model, not independent sampling; no interest or mortality assumption applies.

Method. Apply the expectation and variance formulas with \(n_1=4\), \(n_2=4\), and \(N=8\). The expected number is

E[R]=1+\frac{2(4)(4)}{8}=1+4=5.

For the variance, first calculate the factors in the numerator:

2n_1n_2=2(4)(4)=32, \qquad 2n_1n_2-N=32-8=24.

The denominator is

$$ N^2(N-1)=8^2(7)=64(7)=448. $$

Therefore,

\operatorname{Var}(R)=\frac{32(24)}{448} =\frac{768}{448} =\frac{12}{7} \approx 1.7143.

The common mistake is to treat the seven adjacent-change indicators as independent Bernoulli variables and use only \((N-1)p(1-p)\). They are dependent, so that calculation omits covariance terms. The result is consistent with the symmetry of the model: exchanging A and B does not change the distribution of the number of runs.

Worked Example: A Single Label of One Type

A hypothetical sequence contains one A and five B labels, randomly ordered conditional on those counts. Find the mean and variance of the number of runs, and verify them by considering the position of A. No interest or mortality assumption applies.

Method. First use the fixed-count formulas with \(n_1=1\), \(n_2=5\), and \(N=6\):

E[R]=1+\frac{2(1)(5)}{6} =1+\frac{5}{3} =\frac{8}{3}.

For the variance,

\operatorname{Var}(R) =\frac{2(1)(5)\bigl(2(1)(5)-6\bigr)}{6^2(5)} =\frac{10(4)}{180} =\frac{2}{9} \approx 0.2222.

To check, A is equally likely to occupy any of the six positions. If it is at either end, there are two runs; this occurs with probability \(2/6=1/3\). If it is in one of the four interior positions, it is separated from B labels on both sides, so there are three runs; this occurs with probability \(4/6=2/3\). The mean from these possibilities is

E[R]=2\left(\frac{1}{3}\right)+3\left(\frac{2}{3}\right) =\frac{8}{3}.

Using \(E[R^2]=2^2(1/3)+3^2(2/3)=22/3\), the variance check is

\operatorname{Var}(R)=E[R^2]-E[R]^2 =\frac{22}{3}-\left(\frac{8}{3}\right)^2 =\frac{66-64}{9} =\frac{2}{9}.

The common mistake is to say that one A always creates two runs. It creates two runs only when it is at an end; an interior A creates three. Both direct checks agree with the formulas.

Assumptions and Practical Checks

The results apply to a binary sequence under a specific null model, not to every sequence that happens to contain two kinds of observations. Before using them, check that the following conditions are appropriate:

Two symbols: every observation has been assigned to exactly one of two categories, A or B.
Fixed counts: the values of \(n_1\) and \(n_2\) are conditioned on, rather than modeled as random counts.
Uniform ordering under the null: all distinct arrangements with those counts are equally likely. This is the meaning of random ordering here.
Meaningful sequence order: the order of observations is the order relevant to the question, such as time or a prespecified sequence of positions.

If the observations are assigned to A or B independently with a fixed probability, the number of each symbol is generally random. That is a different probability model, and the fixed-count formulas need not apply. Likewise, a changing probability of observing A across positions, or a design that restricts which arrangements are possible, violates uniform random ordering. The formulas describe the null distribution’s mean and variance; they do not by themselves determine an exact probability for a particular observed number of runs.

Key takeaway: With positive fixed counts \(n_1,n_2\) and a uniformly random ordering, \(E[R]=1+2n_1n_2/N\) and \(\operatorname{Var}(R)=2n_1n_2(2n_1n_2-N)/[N^2(N-1)]\). The fixed counts create dependence between adjacent-change indicators, so the variance requires covariance terms.

Check Your Understanding

For each problem, assume uniform random ordering conditional on the stated symbol counts. Give the mean and variance unless the question asks for an interpretation.

A sequence has three A labels and five B labels. Find the expected number of runs and its variance. (Answer: \(E[R]=4.75\), \(\operatorname{Var}(R)=165/112\approx1.4732\).)
A sequence has four A labels and four B labels. Find the expected number of runs and its variance. (Answer: \(E[R]=5\), \(\operatorname{Var}(R)=12/7\approx1.7143\).)
A sequence has two A labels and seven B labels. Find the expected number of runs and its variance. (Answer: \(E[R]=37/9\approx4.1111\), \(\operatorname{Var}(R)=133/162\approx0.8210\).)
A sequence has one A label and seven B labels. Find the mean and variance, then explain why the number of runs can be either two or three. (Answer: \(E[R]=11/4=2.75\), \(\operatorname{Var}(R)=3/16=0.1875\); A at an end gives two runs, while A in an interior position gives three.)
Compare a sequence with five A and five B labels to one with two A and eight B labels. Which has the larger expected number of runs and which has the larger variance? (Answer: the five-and-five sequence has the larger mean, \(6\) versus \(4.2\), and the larger variance, \(20/9\approx2.2222\) versus \(176/225\approx0.7822\).)

What You'll Learn