Runs Test

Although the term "chance" plays a central role in statistics, it is not a simple decision whether a particular series of numbers is random or not. Here, a multitude of aspects matter, the most important of which are listed as follows:

• type of the distribution of the random numbers
• cyclic repetition in the series (pseudo random numbers)
• auto correlation function of the series
• distribution of the differences of the series
• iteration lengths in binary or dichotomized series

If we look at a sequence of binary random numbers (e.g. 00101110110111000100110) we may pose the question how many "runs" (sub-sequences consisting of all-ones or all-zeroes) normally occur in a random sequence of a certain number of zeroes and ones. A small number of runs indicates a mixing which is not thorough enough, while a number of runs which is too high points to systematic ordering effects in the sequence. If the number of actually detected runs differs too much from the number of expected runs this may raise the suspicion that the sequence is not random.

The example sequence above can be divided into the following runs:

00 | 1 | 0 | 111 | 0 | 11 | 0 | 111 | 000 | 1 | 00 | 11 | 0

The random sequence contains 13 runs with a total of 23 random numbers (11 zeroes, and 12 ones). In order to decide whether the number of found runs is improbable (i.e. the probability that this particular number of runs to occur is below the level of significance) one first has to determine the distribution of runs as a function of the counts of zeroes and ones (n₁ and n₂).

This distribution may be derived from combinatorial calculations. From these considerations we can infer that the probability p(r) of observing r runs, given n₁ and n₂, can be calculated as follows:

With increasing n₁ and n₂ the distribution converges to a normal distribution having the mean μ_r and the standard deviation σ_r:

In practice this approximation allows to simplify the calculation for samples with n₁ and n₂ > 20 (which is a substantial numeric advantage, since the binomial coefficients tend to become very high for large samples). However, one has to be careful if n₁ and n₂ differ too much, as the approximation deviates considerably from the exact values.⁽¹⁾

Applications of the runs test

The runs test may also be used to check whether two distributions are equal or not. The idea behind is as follows: if the samples A and B, which are drawn from different distributions, are combined into one big sample, the sorted big sample will only show a random sequence of values originating from A and B if both distribution are equal in all parameters. Otherwise the values of at least one of the two distributions will lump in certain regions, which will result in longer runs and a smaller number of runs than expected. For example, it is obvious that two distributions showing different variances will result in longer runs at the outer parts of the joint distribution. This test is a so-called omnibus test which compares both distributions in all their aspects.

Hint:

The runs test according to Wald and Wolfowitz may be extended to at least ordinal data by dichotomizing the data using the median as a threshold. Thus all data which are greater than the median will be assigned to a value of 1, all others to 0. Values which are exactly equal to the median will assigned to either 0 or 1 by chance. If the number of actual runs significantly differs from the expected number of runs this indicates that the sequence is not random.

(1)

The approximation by a normal distribution can be used only if n1 and n2 are about the same. If the frequency of occurence of one of the two states (0 or 1) is considerably higher than the other the approximation by a normal distribution is detectably wrong. This is due to the fact that an even number of runs shows a lower probability than an odd number (the reason for this peculiarity can be found in the fact that an even number of runs is only possible if the sequence starts with the less frequent state).