Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
Thanks. We would be analysing machine code rather than plain text, but I see what you mean. I will try the entropy formula suggested by mhum. –  Ozzah Nov 1 '11 at 21:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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