The Wald–Wolfowitz runs test (or simply runs test), named after statisticians Abraham Wald and Jacob Wolfowitz is a non-parametric statistical test that checks a randomness hypothesis for a two-valued data sequence. More precisely, it can be used to test the hypothesis that the elements of the sequence are mutually independent.

Definition

A run of a sequence is a maximal non-empty segment of the sequence consisting of adjacent equal elements. For example, the 21-element-long sequence

+ + + + − − − + + + − + + + + + + − − − −

consists of 6 runs, with lengths 4, 3, 3, 1, 6, and 4. The run test is based on the null hypothesis that each element in the sequence is independently drawn from the same distribution.

Under the null hypothesis, the number of runs in a sequence of N elements is a random variable whose conditional distribution given the observation of N+ positive values and N− negative values (N = N+ + N−) is approximately normal, with:

mean: μ = 2 N + N − N + 1 , variance: σ 2 = 2 N + N − ( 2 N + N − − N ) N 2 ( N − 1 ) = ( μ − 1 ) ( μ − 2 ) N − 1 . {\displaystyle {\begin{aligned}{\text{mean: }}&\mu ={\frac {2\ N_{+}\ N_{-}}{N}}+1,\\[6pt]{\text{variance: }}&\sigma ^{2}={\frac {2\ N_{+}\ N_{-}\ (2\ N_{+}\ N_{-}-N)}{N^{2}\ (N-1)}}={\frac {(\mu -1)(\mu -2)}{N-1}}.\end{aligned}}}

Equivalently, the number of runs is R = 1 2 ( N + + N − + 1 − ∑ i = 1 N − 1 x i x i + 1 ) {\displaystyle R={\frac {1}{2}}(N_{+}+N_{-}+1-\sum _{i=1}^{N-1}x_{i}x_{i+1})}.

These parameters do not assume that the positive and negative elements have equal probabilities of occurring, but only assume that the elements are independent and identically distributed. If the number of runs is significantly higher or lower than expected, the hypothesis of statistical independence of the elements may be rejected.

Historical background

The conceptual groundwork for analyzing the grouping of events in a time series, which underlies the runs test, was articulated in a 1923 paper by hydrologist Robert E. Horton, predating the formalization of the Wald–Wolfowitz test. Horton examined long rainfall records, such as the 176-year series from Padua, Italy, and observed a tendency for wet and dry years to occur in groups (runs of "like events").

Horton independently derived a probability model for the occurrence of groups of successive like events under the assumption of independence. He stated that the probability of a specific group of n like events occurring, followed by an unlike event, was given by a form equivalent to P = (1/2)n+1 (for equally probable events). To quantify the tendency of data to cluster beyond what random chance would produce, he proposed a "periodicity criterion," Cp = m / (2G), where m is the total number of events and G is the number of groups (runs) in the record. A value of Cp significantly greater than 1.0 indicated a systematic tendency toward grouping, which could be mistaken for true cyclical behavior (periodicity). Horton noted that this criterion served as a rapid screening tool to eliminate the need for more laborious analysis (such as Fourier series) when no non-random pattern existed, thereby serving as a "criterion of non-periodicity."

Horton's work also acknowledged limitations in finite samples and introduced a correction factor for short records to account for incomplete groups at the boundaries of the data sequence. He applied this framework extensively to hydrologic data, including rainfall and stream run-off, prefiguring later applications of run analysis in econometrics and climatology.

Proofs

Moments

The number of runs is R = 1 2 ( N + + N − + 1 − ∑ i = 1 N − 1 x i x i + 1 ) {\displaystyle R={\frac {1}{2}}(N_{+}+N_{-}+1-\sum _{i=1}^{N-1}x_{i}x_{i+1})}. By independence, the expectation isE [ R ] = 1 2 ( N + 1 − ( N − 1 ) E [ x 1 x 2 ] ) {\displaystyle E[R]={\frac {1}{2}}(N+1-(N-1)E[x_{1}x_{2}])}Writing out all possibilities, we findx 1 x 2 = { + 1 with probability N + ( N + − 1 ) + N − ( N − − 1 ) N ( N − 1 ) − 1 with probability 2 N + N − N ( N − 1 ) {\displaystyle x_{1}x_{2}={\begin{cases}+1\quad &{\text{ with probability }}{\frac {N_{+}(N_{+}-1)+N_{-}(N_{-}-1)}{N(N-1)}}\\-1\quad &{\text{ with probability }}{\frac {2N_{+}N_{-}}{N(N-1)}}\\\end{cases}}}Thus, E [ x 1 x 2 ] = ( N + − N − ) 2 − N N ( N − 1 ) {\displaystyle E[x_{1}x_{2}]={\frac {(N_{+}-N_{-})^{2}-N}{N(N-1)}}}. Now simplify the expression to get E [ R ] = 2 N + N − N + 1 {\displaystyle E[R]={\frac {2\ N_{+}\ N_{-}}{N}}+1}.

Similarly, the variance of the number of runs isV a r [ R ] = 1 4 V a r [ ∑ i = 1 N − 1 x i x i + 1 ] = 1 4 ( ( N − 1 ) E [ x 1 x 2 x 1 x 2 ] + 2 ( N − 2 ) E [ x 1 x 2 x 2 x 3 ] + ( N − 2 ) ( N − 3 ) E [ x 1 x 2 x 3 x 4 ] − ( N − 1 ) 2 E [ x 1 x 2 ] 2 ) {\displaystyle Var[R]={\frac {1}{4}}Var[\sum _{i=1}^{N-1}x_{i}x_{i+1}]={\frac {1}{4}}((N-1)E[x_{1}x_{2}x_{1}x_{2}]+2(N-2)E[x_{1}x_{2}x_{2}x_{3}]+(N-2)(N-3)E[x_{1}x_{2}x_{3}x_{4}]-(N-1)^{2}E[x_{1}x_{2}]^{2})}and simplifying, we obtain the variance.

Similarly we can calculate all moments of R {\displaystyle R}, but the algebra becomes uglier and uglier.

Asymptotic normality

Theorem. If we sample longer and longer sequences, with lim N + / N = p {\displaystyle \lim N_{+}/N=p} for some fixed p ∈ ( 0 , 1 ) {\displaystyle p\in (0,1)}, then R − μ σ ∼ N ( R / μ − 1 ) {\displaystyle {\frac {R-\mu }{\sigma }}\sim {\sqrt {N}}(R/\mu -1)} converges in distribution to the normal distribution with mean 0 and variance 1.

Proof sketch. It suffices to prove the asymptotic normality of the sequence ∑ i = 1 N − 1 x i x i + 1 {\displaystyle \sum _{i=1}^{N-1}x_{i}x_{i+1}}, which can be proven by a martingale central limit theorem.

Applications

Runs tests can be used to test:

  1. the randomness of a distribution, by taking the data in the given order and marking with + the data greater than the median, and with – the data less than the median (numbers equalling the median are omitted.)
  2. whether a function fits well to a data set, by marking the data exceeding the function value with + and the other data with −. For this use, the runs test, which takes into account the signs but not the distances, is complementary to the chi square test, which takes into account the distances but not the signs.

Related tests

The Kolmogorov–Smirnov test has been shown to be more powerful than the Wald–Wolfowitz test for detecting differences between distributions that differ solely in their location. However, the reverse is true if the distributions differ in variance and have at the most only a small difference in location.[citation needed]

The Wald–Wolfowitz runs test has been extended for use with several samples.

Notes

External links