Runs Test and Chi Square Distribution

Question

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.

thank you very much for your help in advance!

Answer 1

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.