Normal Approximation for the Runs Test

Why Approximate the Runs Distribution?

A runs test asks whether the order of two kinds of observations looks unusual under random ordering. For example, a hypothetical quality-control analyst might label each successive inspection result “within limit” or “outside limit” and count the runs—consecutive observations of the same kind. An unusually small run count suggests clustering; an unusually large count suggests alternation. When the number of observations is moderate or large, a normal approximation can provide a convenient estimate of a tail probability without listing every possible sequence.

The approximation is not a different null model. It describes the distribution of the run count when the two observed category totals are held fixed and their order is assumed random. The fixed totals determine both the center and spread of the distribution. Because the run count is discrete, a continuity correction is important when translating a run-count event into a normal probability.

Definition: Suppose a sequence contains \(n_1\) observations of one category and \(n_2\) of another, where both counts are positive, and let \(N=n_1+n_2\). Under the runs-test null model, all distinct orderings of these fixed observations are equally likely. A run is a maximal consecutive group of observations of the same category. Let \(R\) be the total number of runs. The normal approximation uses the null mean and variance of \(R\) to approximate its distribution.

Null Mean, Variance, and Standardization

With fixed category totals, the null mean and variance are

\mu_R=E[R]=1+\frac{2n_1n_2}{N}, \qquad \sigma_R^2=\operatorname{Var}(R) =\frac{2n_1n_2(2n_1n_2-N)}{N^2(N-1)}.

These formulas require \(n_1,n_2>0\), and the variance is calculated for random ordering conditional on the observed counts. The approximate standardized statistic is \(Z=(R-\mu_R)/\sigma_R\). Under the approximation, \(Z\) is treated as having a standard normal distribution. This is an approximation, not an assertion that the discrete distribution of \(R\) is exactly normal.

Why the Mean Formula Holds

A short indicator argument explains the mean. For each of the \(N-1\) gaps between successive positions, define an indicator that equals 1 if the categories on the two sides of that gap differ, and 0 otherwise. The number of runs is 1 plus the number of such changes. In a random ordering, the probability that a specified gap separates different categories is \(2n_1n_2/[N(N-1)]\): there are \(n_1n_2\) ordered choices of the first category followed by the second, and \(n_2n_1\) choices in the reverse order, out of \(N(N-1)\) ordered pairs. Therefore, by adding the expected indicators,

E[R] =1+(N-1)\frac{2n_1n_2}{N(N-1)} =1+\frac{2n_1n_2}{N}.

The variance formula accounts for dependence between gap indicators: two neighboring gaps share an observation, and even separated gaps are dependent because the category totals are fixed. For example, for neighboring gaps the probability that both are changes is \(n_1n_2/[N(N-1)]\), obtained by counting the two possible category patterns across three positions. Counting the joint change probabilities for neighboring and non-neighboring gaps, then summing variances and covariances, gives the stated \(\sigma_R^2\). Treating the gaps as independent would not give the correct variance.

Continuity Correction for Tail Probabilities

A normal random variable is continuous, whereas \(R\) takes integer values. The continuity correction places a boundary halfway between adjacent integers. For a lower-tail event \(R\le r\), use the boundary \(r+0.5\); for an upper-tail event \(R\ge r\), use \(r-0.5\). Thus, writing \(\Phi\) for the standard normal cumulative distribution function,

P(R\le r)\approx \Phi\!\left(\frac{r+0.5-\mu_R}{\sigma_R}\right), \qquad P(R\ge r)\approx 1-\Phi\!\left(\frac{r-0.5-\mu_R}{\sigma_R}\right).

For a two-sided test, “at least as extreme” is ordinarily measured by distance from the null mean. If the observed count is \(r\), the lower extreme includes integers at or below \(r\), when \(r<\mu_R\). The opposite extreme begins at the smallest integer at least as far above \(\mu_R\) as \(r\) is below it. Apply the appropriate continuity correction to each tail and add the tail probabilities. When the observed count lies above the mean, reverse the roles. This definition makes the two-sided calculation explicit; simply doubling a one-sided probability need not match it exactly because of discreteness and asymmetry.

Worked Example: A Lower-Tail Test With Equal Category Counts

A hypothetical sensor records 5 “stable” and 5 “alert” readings in a fixed sequence. Under random ordering, the observed sequence has \(R=3\) runs. Estimate the lower-tail probability and assess whether this is unusually few runs at the 5% level. Use a normal approximation with a continuity correction.

Method. Calculate the conditional null mean and variance, then approximate \(P(R\le3)\). The correction places the boundary at 3.5 rather than at 3.

Here \(n_1=5\), \(n_2=5\), and \(N=10\). The mean is

\mu_R=1+\frac{2(5)(5)}{10}=6.

The variance and standard deviation are

\sigma_R^2 =\frac{2(5)(5)\{2(5)(5)-10\}}{10^2(10-1)} =\frac{50(40)}{900} =\frac{20}{9} \approx2.2222, \qquad \sigma_R=\sqrt{\frac{20}{9}}\approx1.4907.

Applying the lower-tail continuity correction gives

z=\frac{3+0.5-6}{1.4907} \approx-1.6771, \qquad P(R\le3)\approx\Phi(-1.6771)\approx0.0468.

The estimated probability is about 0.0468, below 0.05, so this approximation indicates unusually few runs at the 5% level. The check is consistent with the equal category counts: the null mean is 6, while 3 is substantially below it. The method avoids using the observed integer itself as the normal boundary.

Worked Example: A Two-Sided Approximation With Unequal Counts

A hypothetical monitoring sequence contains \(n_1=12\) “routine” outcomes and \(n_2=13\) “review” outcomes, in random order under the null model. The observed sequence has \(R=10\) runs. Estimate a two-sided probability by adding the lower tail at least as far below the mean and the corresponding upper tail.

Method. Find the null center and spread, then use continuity-corrected boundaries for the observed lower extreme and the opposite upper extreme. Here \(N=25\), and

\mu_R =1+\frac{2(12)(13)}{25} =1+\frac{312}{25} =13.48.

The variance is

\sigma_R^2 =\frac{2(12)(13)\{2(12)(13)-25\}}{25^2(24)} =\frac{312(287)}{15000} =\frac{89544}{15000} =5.9696, \qquad \sigma_R=\sqrt{5.9696}\approx2.4433.

The observed count is 3.48 below the mean. The lower-tail event is \(R\le10\), so its corrected boundary is 10.5:

z_L=\frac{10.5-13.48}{2.4433}\approx-1.2196, \qquad P(R\le10)\approx\Phi(-1.2196)\approx0.1113.

The opposite tail contains integer counts at least as far above the mean as 10 is below it. Since \(13.48+3.48=16.96\), that event is \(R\ge17\). Its corrected boundary is 16.5:

z_U=\frac{16.5-13.48}{2.4433}\approx1.2360, \qquad P(R\ge17)\approx1-\Phi(1.2360)\approx0.1082.

Adding the two estimated tails gives \(0.1113+0.1082=0.2195\). The approximate two-sided probability is therefore 0.2195. It is not necessary for the two tails to be identical: the mean need not be halfway between the two integer tail boundaries.

Worked Example: Checking Whether the Approximation Is Suitable

A hypothetical short sequence has \(n_1=2\) readings marked “high” and \(n_2=3\) marked “low,” with \(R=2\). Calculate the normal-approximation lower tail, then compare its scale with the exact result from counting the possible fixed-count orderings.

Method. First calculate the normal approximation with the continuity correction. Then check whether the small category counts make reliance on that approximation questionable. Here \(N=5\), so

\mu_R=1+\frac{2(2)(3)}{5}=3.4, \qquad \sigma_R^2 =\frac{2(2)(3)\{2(2)(3)-5\}}{5^2(4)} =\frac{84}{100} =0.84, \qquad \sigma_R\approx0.9165.

For \(R\le2\), the corrected boundary is 2.5. Thus

z=\frac{2.5-3.4}{0.9165}\approx-0.9820, \qquad P(R\le2)\approx\Phi(-0.9820)\approx0.1631.

There are \(\binom{5}{2}=10\) equally likely orderings. Exactly two put the two high readings together at one end, producing two runs: HHL LL or LLH H, more plainly HHL LL and LLH H with the spaces removed as H H L L L and L L L H H. Thus the exact probability of two runs is \(2/10=0.2\); since two runs is the minimum possible here, this is also \(P(R\le2)\). The approximation, 0.1631, differs appreciably from 0.2. With such small counts the discrete distribution is coarse, so the normal approximation is not a reliable substitute for the exact distribution when exact calculation is practical. The comparison avoids treating a computed normal tail as automatically accurate.

When the Approximation Is Useful—and When It Is Not

The normal approximation is most persuasive when both category counts are large enough for the run-count distribution to have a reasonably smooth, mound-shaped form and when the event of interest is not pressed against the minimum or maximum possible number of runs. There is no universal count threshold that guarantees accuracy for every purpose. A rough approximation may be adequate for an exploratory diagnostic, while a decision near a significance cutoff calls for more caution. When counts are small or a tail is especially important, use the exact runs distribution when feasible.

The possible run counts range from 2 to \(N\) when both categories are present. The minimum occurs when each category forms one uninterrupted block; the maximum occurs when the sequence alternates as much as the counts allow. A normal model assigns probability to values beyond this range, another reason it can misrepresent the distribution near its limits. The continuity correction improves the boundary treatment but cannot fix a fundamentally poor shape approximation.

Common Mistakes and Exam Checks

A common mistake is to standardize the observed integer directly for a tail event. For example, in the second worked example, using 10 rather than 10.5 for \(P(R\le10)\) gives \(z=(10-13.48)/2.4433\approx-1.424\), and a tail near 0.0772—not the corrected estimate 0.1113. The event includes the entire probability at \(R=10\), which is why the continuous boundary is halfway between 10 and 11.

Do not estimate the mean as a function of one count alone. Use both fixed totals in \(1+2n_1n_2/N\).
Do not assume independent adjacent comparisons. The sequence has fixed category totals, so the gap indicators are dependent; use the stated variance.
Match the correction to the event. \(R\le r\) uses \(r+0.5\); \(R\ge r\) uses \(r-0.5\).
Define the two-sided extremeness rule. For the distance-from-mean rule used here, determine the opposite integer tail before applying its continuity correction.
Check suitability, not just arithmetic. Small counts and tail events near the possible limits can make a normal approximation misleading.

The normal approximation for the runs test is aligned with the SOA VEE Mathematical Statistics syllabus. A sound solution states the fixed-count random-ordering model, calculates the null mean and variance, identifies the tail event, applies the continuity correction, and qualifies the result if the counts are small.

Check Your Understanding

For each problem, use fixed category totals under random ordering. Answers are rounded to four decimal places where probabilities are requested.

A sequence contains 4 observations of category A and 6 of category B. Calculate the null mean and variance of the run count. (Answer: \(\mu_R=5.8\), \(\sigma_R^2=2.0267\).)
A sequence has 8 observations of each of two categories and an observed run count of 5. Use the normal approximation with a continuity correction to estimate the lower-tail probability. (Answer: approximately \(0.0350\).)
For a sequence whose null mean is 10.4, the observed run count is 7. For a two-sided distance-from-mean calculation, state the lower-tail event and its corrected boundary, and the opposite upper-tail event and its corrected boundary. (Answer: lower event \(R\le7\), boundary 7.5; opposite event \(R\ge14\), boundary 13.5.)
A fixed-count sequence has 2 observations of one category and 3 of the other, and the observed count is 2 runs. Give the normal-approximation lower tail and the exact lower tail, and state why the approximation should be treated cautiously. (Answer: normal approximation approximately \(0.1631\); exact probability \(0.2000\); the category counts are small.)
A sequence has 12 observations of one category, 13 of another, and 10 runs. Using the normal approximation and the distance-from-mean two-sided rule, give both continuity-corrected tail estimates and their sum. (Answer: lower tail approximately \(0.1113\), upper tail approximately \(0.1082\), sum approximately \(0.2195\).)

What You'll Learn