# Runs Test and Chi Square Distribution

I want to identify random data by applying some tests to the observed byte stream. I used the chi square test already on a frequency analysis, which works fine. To reduce the false-positive rate I want to apply some more tests, like the runs test, which checks for monotonous sequences in the byte sequence (not the runs on the binary level, but on the byte level [values from 0 - 255])

I found some papers which describe the procedure, but my implementation doesn't work, probably I understood something wrong. The papers are unfortunately in German, but what they say in general, is

1) we count either the monotonically increasing or monotonically decreasing sequence of bytes (i.e. 3 | 1, 6, 9, 44, 74 | 11 | 6, 251, 46 | ... => two monotonically increasing sequences).

2) the probability, each sequence must theoretically occur, is defined by

p = r / (r+1)!, where r is the length of the run.

In total I have 6 categories, where category no. 6 includes all runs > 5. When I perform this test on my data, I get a chi-square distribution which is much too high, but the data is definitely random (chi square value between 80 - 100). I performed this test several times on different samples, the distribution remains constant, and the chi-square value remains constant, too, but too high.

I am not 100% sure about the calculation of the probability.

• How are you calculating chi-square values on the runs? – Peter Flom Oct 7 '12 at 13:28
• I have catgegories of length 1, 2, 3, 4, 5 and > 5. If I can compute the probabilities of the occurence if the runs this is very easy to do. As I wrote, I have some formula, but this one seems to be wrong :/ – tom Oct 7 '12 at 15:37
• What do you do about ties, given that your data is discrete? – jbowman Oct 7 '12 at 22:11

My Nonparametrics: Statistical Methods based on Ranks (Lehmann, 1975 edition) gives the formula as:

$p(r=2k) = 2\frac{{n-1\choose{k-1}}^2}{2n\choose{n}}$

where the number of runs is counted as both the runs up and down. Asymptotically,

$\frac{r - n}{\sqrt{n}} \sim \text{N}(0,1)$

An alternative procedure is of course to do a permutation test; generate 10,000 or so random sequences by randomly permuting the collection of data points, and calculate the test statistic for each sequence. You can then compare your calculated test statistic on the original sequence with the collection of randomly-generated test values to get a p-value.

Note that this does not account for the possibility of ties, which is a definite possibility in the OP's case, as each byte can only take on one of 256 possible values.

• so this means my probability calculation is wrong? – tom Oct 7 '12 at 18:07
• The probability you are looking at is a run-length probability, but what you want is a run-count probability. The former takes a particular run and calculates the probability that its length is $r$, but the latter takes a sequence of $n$ elements and calculates the probability of seeing $r$ runs. – jbowman Oct 7 '12 at 22:23