Best way to determine if a list of bytes are random?

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

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.)

• Interestingly these methods all assume the distribution is iid. That is, a simple cyclic sequence, such as 123123123 with very low entropy, would be considered uniform with high probability. Do you know if anybody has considered distribution testing for non iid sequences? Jul 28 '17 at 18:18
• I wrote this to check for things like simple sequences and detect gross variations from uniform random byte distributions... it works pretty well: github.com/earonesty/dotfiles/blob/master/randbytestest.py. Jan 14 '19 at 18:11

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)

• good for numbers, not quite right for byte sequences. could adapt it though Jan 14 '19 at 18:11
• @Erik It is readily applied in many ways. All you need is a way to use your RNG to create bit sequences--and a byte sequence already is a bit sequence. Jan 14 '19 at 18:43
• guess i didn't see how to apply it to, say, an array of 30 samples of 32-byte sequences. it looks very comprehensive... and easy to use (apt install dieharder). Jan 14 '19 at 22:23
• @Erik The docs say "dieharder prefers to test generators that have been wrapped up in a GSL-compatible interface so that they can return an unbounded stream of random numbers." For that purpose, a 32-byte sequence can be interpreted as a sequence of 8 unsigned shorts, 4 unsigned longs, etc. It's quite flexible, but you do have to write an interface. Jan 14 '19 at 22:27
• @ErikAronesty: 30*32 bytes simply isn't enough data, and no randomness test will be able to get around this fact. Dieharder will (for good reason) laugh at your sample size until you have on the order of 1GB worth of data or so. Aug 27 '19 at 23:20

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:

1. generate a statistic for "known good random data" (either mathematically or empirically)
2. generate the same statistic for your sample data (hopefully you have at least 30 samples or so)
3. get a p value for the difference (hypotheses: these are from different distributions)
4. repeat for N statistics
5. bonferonni correct the results (divide by N)