Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.)
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.
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
apt install dieharder).
$\endgroup$
Jan 14, 2019 at 22:23
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.
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.
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.
I made a fairly weak set of tests that was nevertheless very useful for me, and indicative of the nature of randomness tests in general:
Source is here: https://github.com/earonesty/dotfiles/blob/master/randbytestest.py
