# Test for randomness

I'm trying to write a program to compute a metric for the entropy in files to determine a probability that the file is compressed or encrypted. Compressed and encrypted files have very, very, very high entropy compared to most other types of files.

I need a figure between 0 and 1. Zero being not random at all and 1 being totally random. I don't expect any input will ever give 0 or 1, though.

I have a paper here which describes a simple runs test. We have a sequence of $n$ values.

Starting at the first value, we write a "+" if the following value is greater, or a "-" if the following value is smaller.

Consecutive +'s and -'s are grouped into runs, and we can say we have $r$ runs.

We say $E(r) = \frac{2n - 1}{3}$ and $Var(r) = \frac{16r - 29}{90}$

(Don't ask me where these come from - I have no idea. Apparently for $n \gt 20$ we can say that $r$ is reasonably approximated by a normal distribution. The document doesn't explain. If you know, I'd love to know too!).

We can get a $Z$ value which is $\frac{r - E(r)}{\sqrt{Var(r)}}$

If we do a significance test at, say, $\alpha = 0.05$ then we can say something like $-\alpha \lt Z \lt \alpha$ and hence we can/cannot reject the sequence as being random given level of significance.

First of all: Is this runs test suitable to determine the entropy of a file? Secondly, how do I convert the $Z$ value to a figure between 0 and 1? My first guess was to put it directly into the CDF of a standard normal but I was getting results which didn't seem to match the test data I was using. Things that should have been very random were giving very, very low figures of entropy.

-
Is there a particular reason that you're not using the entropy formula for calculating entropy? –  mhum Nov 1 '11 at 7:32
Presumably $r$ in the expression for the variance should be $n$? –  joriki Nov 1 '11 at 7:36

Your inequality $-\alpha \lt Z \lt \alpha$ is wrong. $Z$ measures by how many standard deviations the result is above the mean, whereas $\alpha$ is a significance. You need to use the cumulative distribution function of the standard normal distribution to convert $Z$ into a significance, as described here. This also answers you second question, since the result will already be a number between $0$ and $1$ measuring the significance of the deviation from the mean. If this is what you were already doing when you got the unexpected low values, please post your numbers so we can tell what might be going wrong.
Concerning your first question whether this test is suitable: That will depend heavily on your data, but generally I would think it would be a rather poor indicator. For instance, text has quite a low entropy and compresses very well, but I would expect the pattern of runs of $+$ and $-$ in your test to reflect only a small part of that regularity.