Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Is there some algorithm out there that can return some value indicating a level of randomness? I believe it's called Data Entropy.

I recently read this article: http://faculty.rhodes.edu/wetzel/random/mainbody.html

Would his approach of analyzing coin flips apply for bytes? Should I drop down to the bit level where it's true/false again or is there a way to determine based on the full byte value?

Are their better analyses than this article?

share|improve this question
add comment

7 Answers

up vote 11 down vote accepted

In TCS, another approach to this problem has been via property testing of distributions, where one is to distinguish whether a distribution is (truly) uniform distribution or is "not even close" to being uniform (in a formal way). Here one gets precise bounds on the number of samples needed to decide on the question.

See, for example Section 6 of the following tutorial: http://people.csail.mit.edu/ronitt/papers/icm.ps

In particular, one can decide whether a distribution on $[n]$ is truly uniform or is $\epsilon$-far (in total variation distance) from uniform with $O(\sqrt{n}/\epsilon^4)$ queries/samples from the said distribution. (This is also tight in the sense that $\Omega(\sqrt{n})$ samples are needed.)

Another good resource is Paul Valiant's PhD thesis.

share|improve this answer
add comment

From random.org:

Oddly enough, it is theoretically impossible to prove that a random number generator is really random. Rather, you analyse an increasing amount of numbers produced by a given generator, and depending on the results, your confidence in the generator increases (or decreases, as the case may be)

More information can be found here

share|improve this answer
add comment

There is no single correct algorithm for measuring randomness. Various statistical tests are one possible approach, as the others have already said. Another possibility is to compress the byte sequence and see what happens. If you get about 8 bits/byte (or more), then the sequence is random in respect to the data model underlying the compressor.

Of the standard compression methods, PPM uses an explicit statistical model to predict the next character based on the preceding context. Its main weakness is that it cannot utilize large-scale repetitiveness such as identical repetitions of a long random sequence.

Compression methods based on the LZ77 parsing or the Burrows-Wheeler Transform (BWT) perform well, when there are many repeated substrings in the sequence. However, many practical implementations have limited block/window size to save memory, making them also unable to utilize large-scale repetitiveness.

Instead of compressing the sequence, you could also compute some measure related to the data model of the compressor: high-order empirical entropy for PPM, the number of equal letter runs in the BWT, or the number of phrases in the LZ77 parsing. In the first two cases, 8 bits of entropy per byte or n(1 - 1/256) runs for a sequence of length n mean fully random data.

share|improve this answer
add comment

Kolmogorov complexity is one way to measure the randomness of strings and it is algorithmically uncomputable. Using this notion, it is impossible to measure the randomness of all strings. The existence of such algorithm could be used to solve the halting problem.

share|improve this answer
add comment

As other answers mentioned, the decision version of this problem (like the Halting problem and a number of other problems like the Tiling Problem) is undecidable. However, I believe you are asking about practical ways to measure the randomness of a collection of bits.

Standard practice here is to run the data through a series of randomness tests, like the Chi-Square test.

share|improve this answer
add comment

Entropy is defined for distributions and it's problematic to apply it to unbounded bit string. Normally if you have k possible event types, you observe n events, with p'th event occurring $i_p$ times. You define your distribution to be $(i_1/n,\ldots,i_k/n)$ and compute the entropy of that. But how do you define "events" when you get a string of length n? You could define your events to be "observed bit 1" and "observed bit 0", or you could have events of the form "observed string x" where x is some string of length n. In latter case, your entropy is going to be 0.

In practice, there's no universal test for stream randomness, instead there's a series of tests, and if your stream tries k of the best tests and passes them all, we can be reasonably sure it's random...until someone invents k+1'st test that breaks it.

Here's what Knuth says about it in "Art of Computer Algorithms, Vol 2"

"If a sequence behaves randomly with respect to tests T1 ,T2 , ..., Tn, we cannot be sure in general that it will not be a miserable failure when it is subjected to a further test T(n+1). Yet each test gives us more and more confidence in the randomness of the sequence. In practice, we apply about half a dozen different kinds of statistical tests to a sequence, and if it passes them satisfactorily we consider it to be random - it is then presumed innocent until proven guilty."

I'd recommend reading Knuth's "Art of Computer Algorithms" section 3.1 for general introduction to pseudorandomness and 3.3 on statistical tests for streams.

share|improve this answer
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.