Run test

The run test (also runs test , Wald-Wolfowitz test according to Abraham Wald and Jacob Wolfowitz , iteration test or Geary test ) is a non-parametric test for the randomness of a sequence. The starting point is an urn model with two types of balls ( dichotomous population). N balls are removed and the hypothesis that the removal occurred by chance should be tested.

method

Spheres were taken from a dichotomous population . The results are available in their chronological order. All neighboring results of the same value are now combined into one run or run. If the sequence is actually random, there shouldn't be too few runs, but not too many either. ${\displaystyle n}$

The null hypothesis is set up: the extraction was made by chance.

To determine the number of runs for which the hypothesis is rejected, the distribution of the runs is required: Let the number of balls of the first type and the second type; it is the number of runs. According to the principle of symmetry, the probability of any sequence of balls being taken at random is the same. There are altogether ${\displaystyle n_{1}}$ ${\displaystyle n_{2}=n-n_{1}}$ ${\displaystyle r}$

${\displaystyle {\frac {(n_{1}+n_{2})!}{n_{1}!\,n_{2}!}}}$

Possibilities of withdrawal.

With regard to the distribution of the number of runs, a distinction is made between the following cases:

1. The number of runs is an even number: ${\displaystyle r}$

There are runs of the balls of the first type and also runs of the balls of the second type. The probability that exactly runs occurred is then ${\displaystyle q={\tfrac {1}{2}}r}$ ${\displaystyle q={\tfrac {1}{2}}r}$ ${\displaystyle r=2q}$

${\displaystyle P(R=2q)={\frac {2{{n_{1}-1} \choose {q-1}}{{n_{2}-1} \choose {q-1}}}{{n_{1}+n_{2}} \choose n_{1}}}}$

2. The number of runs is odd: ${\displaystyle r}$

There are runs of the balls of the first type and runs of the balls of the second type or the other way round. The probability that exactly runs occurred is then calculated as the sum of these two possibilities ${\displaystyle q+1={\tfrac {1}{2}}(r+1)}$ ${\displaystyle q={\tfrac {1}{2}}(r-1)}$ ${\displaystyle r=2q+1}$

${\displaystyle P(R=2q+1)={\frac {{n_{1}-1 \choose q}{n_{2}-1 \choose q-1}+{n_{1}-1 \choose q-1}{n_{2}-1 \choose q}}{n_{1}+n_{2} \choose n_{1}}}}$

If it is too small or too large, this leads to the rejection of the null hypothesis. At a significance level of , H _{0 is} rejected if the following applies to the test variable : ${\displaystyle r}$ ${\displaystyle \alpha }$ ${\displaystyle R}$

${\displaystyle r\leq r({\tfrac {\alpha }{2}})}$ or ${\displaystyle r\geq r(1-{\tfrac {\alpha }{2}})}$

with as a quantile of the distribution of at the point , the principle of conservative testing being applied here. Since calculating the critical values for rejecting the hypothesis is cumbersome, a table is often used. ${\displaystyle r(p)}$ ${\displaystyle R}$ ${\displaystyle p}$ ${\displaystyle r}$

Simple example

For a panel discussion with two political parties, the speakers were supposedly chosen by chance. It was drawn by lot that 4 representatives from the Supi party and 5 representatives from the Toll party in the following series may speak:

S S  T  S  T T T  S  T

A representative from Toll complained that S was preferred. A run test was carried out:

It is n ₁ = 4 and n ₂ = 5. One got r = 6 runs.

It is clear that in the case of many runs there is no suspicion that one of the parties is preferred. The null hypothesis is rejected if there are too few runs. According to the run test table, H _{0 is} rejected if r ≤ 2. So the test variable r = 6 is not in the rejection range; one cannot conclude from the criteria of the run test that the order of the speakers is not random.

By the way, in the next case too:

S S S  T  S  T T T T

with r = 4 runs, the null hypothesis was not rejected, although almost everyone will have a suspicion that Supi was preferred. However, because of the relatively small number of observations, it cannot be ruled out that the result is due to chance.

additions

Parameters of the distribution of R

The expectation of R is

${\displaystyle \operatorname {E} (R)={\frac {2n_{1}n_{2}}{n}}+1}$

and the variance

${\displaystyle \operatorname {Var} (R)={\frac {2n_{1}n_{2}(2n_{1}n_{2}-n)}{n^{2}(n-1)}}}$.

Population with more than two expressions of the characteristic

If there is a finite sequence of real numbers of a metric feature, the sequence is dichotomized: First the median z of the sequence is determined. Values are then interpreted as balls of the first kind, values as balls of the second kind. The resulting dichotomous sequence can then be tested again for randomness (see example below). ${\displaystyle (x_{i})}$ ${\displaystyle x_{i}<z}$ ${\displaystyle x_{i}>z}$

If there is a non-numerical symbol sequence with more than two occurrences, a numerical series must first be generated, whereby the problem here may be that the symbols cannot be sorted.

Normal approximation

For sample sizes n ₁ , n ₂ > 20, the number of runs R is approximately normally distributed with expected value and variance as above. The standardized test variable is obtained

${\displaystyle z={\frac {r-({\frac {2n_{1}n_{2}}{n}}+1)}{\sqrt {\frac {2n_{1}n_{2}(2n_{1}n_{2}-n)}{n^{2}(n_{1}+n_{2}-1)}}}}}$

The hypothesis is rejected if

${\displaystyle z<-z(1-{\frac {\alpha }{2}})}$ or ${\displaystyle z>z(1-{\frac {\alpha }{2}})}$

with as a quantile of the standard normal distribution for the probability . ${\displaystyle z(1-{\frac {\alpha }{2}})}$ ${\displaystyle 1-{\frac {\alpha }{2}}}$

Applications

The run test can be used to check stationarity or non- correlation in a time series or other sequence , especially if the distribution of the characteristic is unknown. The null hypothesis here is that consecutive values ​​are uncorrelated.

The run test can be combined with the chi-square test , since both test variables are asymptotically independent of one another.

Example of a metric characteristic

It is the consequence

13	 3	14	14	1	14	3	8	14	17	9	14	13	2	16	1	3	12	13	14

in front. It is dichotomized with the median z = 13. + Is set for the first expression, and - for the second expression.

0	-10	1	1	-12	1	-10	-5	1	4	-4	1	0	-11	3	-12	-10	-1	0	1

+	-	+	+	-	+	-	-	+	+	-	+	+	-	+	-	-	-	+	+

With n ₁ = 11 (+) and n ₂ = 9 (-) r = 13 runs are obtained. R is approximately normally distributed with the expected value

${\displaystyle \operatorname {E} (R)={\frac {(2\cdot 11\cdot 9)}{20}}+1=10{,}9}$

and the variance

${\displaystyle \operatorname {Var} (R)={\frac {2\cdot 11\cdot 9\cdot (2\cdot 11\cdot 9-20)}{20^{2}\cdot 19}}=4{,}6}$.

The test variable z is then calculated as

${\displaystyle {\frac {13-10{,}9}{\sqrt {4{,}6}}}=1{,}0}$

At a significance level of 0.05, H _{0 is} rejected if | z | > 1.96. This is not the case.

Decision: The hypothesis is not rejected. The elements of the sample were probably taken at random.

literature

• James V. Bradley: Distribution-Free Statistical Tests. 1968, Chapter 12, ISBN 0-13-216259-8
• Herbert Büning, Götz Trenkler : Nonparametric statistical methods. 1999, Chapter 4.5, ISBN 3-11-016351-9
• Abraham Wald , Jacob Wolfowitz : On a Test Whether Two Samples are from the Same Population. The Annals of Mathematical Statistics , Vol. 11, No. 2 (Jun., 1940), pp. 147-162, doi : 10.1214 / aoms / 1177731909 JSTOR 2235872

See also

Autocorrelation , random number generator , pseudo random numbers , trend

Web links

• Programming the run test in Gambas (programming language)
• An amazing experiment - the RUN test
• Wald Wolfowitz Runs Test