Wald–Wolfowitz runs test

Proofs

Moments

The number of runs is ${\displaystyle R=\frac{1}{2}(N_{+}+N_{-}+1-\sum _{i=1}^{N-1}{x}_i{x}_{i+1})}$. By independence, the expectation is$${\displaystyle E[R]=\frac{1}{2}(N+1-(N-1)E[x_1{x}_2])}$$Writing out all possibilities, we find$${\displaystyle x_1{x}_2=\{\begin{array}{ll}+1& \text{ with probability }\frac{N_{+}(N_{+}-1)+N_{-}(N_{-}-1)}{N(N-1)}\\ -1& \text{ with probability }\frac{2N_{+}{N}_{-}}{N(N-1)}\end{array}}$$Thus, ${\displaystyle E[x_1{x}_2]=\frac{(N_{+}-N_{-}{)}^2-N}{N(N-1)}}$. Now simplify the expression to get ${\displaystyle E[R]=\frac{2N_{+}{N}_{-}}{N}+1}$.

Similarly, the variance of the number of runs is$${\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 ${\displaystyle R}$, but the algebra becomes uglier and uglier.

Asymptotic normality

Theorem. If we sample longer and longer sequences, with ${\displaystyle lim{N}_{+}/N=p}$ for some fixed ${\displaystyle p\in (0,1)}$, then ${\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 ${\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.

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