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!

| cite | improve this question | | | | |
  • $\begingroup$ How are you calculating chi-square values on the runs? $\endgroup$ – Peter Flom Oct 7 '12 at 13:28
  • $\begingroup$ 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 :/ $\endgroup$ – tom Oct 7 '12 at 15:37
  • $\begingroup$ What do you do about ties, given that your data is discrete? $\endgroup$ – 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.

| cite | improve this answer | | | | |
  • $\begingroup$ so this means my probability calculation is wrong? $\endgroup$ – tom Oct 7 '12 at 18:07
  • $\begingroup$ 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. $\endgroup$ – jbowman Oct 7 '12 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.