<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-08-25T18:13:30.087Z
2010-08-25T18:13:30.087Z
Jouni Sirén
<p>From random.org:</p>

<blockquote>
  <p>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)</p>
</blockquote>

<p>More information <a href="http://www.random.org/analysis/" rel="noreferrer">can be found here</a></p>

CC BY-SA 2.5
2010-08-25T17:14:33.917Z
2010-08-25T17:14:33.917Z
Niels
<p><a href="http://www.phy.duke.edu/~rgb/General/dieharder.php" rel="nofollow noreferrer">http://www.phy.duke.edu/~rgb/General/dieharder.php</a></p>

CC BY-SA 4.0
2019-01-14T18:11:01.223Z
good for numbers, not quite right for byte sequences.   could adapt it though
Erik Aronesty
CC BY-SA 4.0
2019-01-14T18:43:53.433Z
@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.
whuber
CC BY-SA 4.0
2019-01-14T22:23:24.783Z
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`).
Erik Aronesty
CC BY-SA 4.0
2019-01-14T22:27:07.647Z
@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.
whuber
CC BY-SA 4.0
2019-08-27T23:20:30.313Z
@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.
Jay Sullivan
CC BY-SA 4.0
2019-08-28T18:44:12.343Z
@JaySullivan it's not hard to make a test for smaller samples that produces a reasonable likelihood of randomness using various regressions and is perfectly suitable to answer the question "did you forget to use a random number generator" or "did you accidentally zero out the leftmost 6 bits", etc.   that's what i needed.   wasnt too hard to write
Erik Aronesty
CC BY-SA 2.5
2010-08-25T17:58:43.007Z
2010-08-25T17:58:43.007Z
whuber
<p>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.</p>

CC BY-SA 2.5
2010-08-25T16:58:30.707Z
2010-08-25T16:58:30.707Z
Mohammad Al-Turkistany
<p>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.</p>

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

CC BY-SA 2.5
2010-08-25T17:30:24.623Z
2010-08-25T17:30:24.623Z
Ross Snider
<p>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.</p>

<p>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.</p>

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

<p>"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."</p>

<p>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.</p>

CC BY-SA 2.5
2010-08-25T18:15:47.633Z
2010-08-25T18:15:47.633Z
Yaroslav Bulatov
<p>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:</p>

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

<p>Source is here:  <a href="https://github.com/earonesty/dotfiles/blob/master/randbytestest.py" rel="nofollow noreferrer">https://github.com/earonesty/dotfiles/blob/master/randbytestest.py</a></p>

CC BY-SA 4.0
2019-01-14T22:28:54.470Z
2019-01-15T18:28:46.937Z
2019-01-15T18:28:46.937Z
Erik Aronesty
<p>In TCS, another approach to this problem has been via <i>property testing of distributions</i>, 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.</p>

<p>See, for example Section 6 of the following tutorial:
<a href="http://people.csail.mit.edu/ronitt/papers/icm.ps" rel="noreferrer">http://people.csail.mit.edu/ronitt/papers/icm.ps</a></p>

<p>In particular, one can decide whether a distribution on $[n]$ is truly uniform or is $\epsilon$-far (in <a href="http://en.wikipedia.org/wiki/Total_variation_distance_of_probability_measures" rel="noreferrer">total variation distance</a>) 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.)</p>

CC BY-SA 3.0
2017-07-28T18:18:42.997Z
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?
Thomas Ahle
CC BY-SA 4.0
2019-01-14T18:11:52.630Z
I wrote this to check for things like simple sequences and detect gross variations from uniform random byte distributions... it works pretty well: https://github.com/earonesty/dotfiles/blob/master/randbytestest.py.
Erik Aronesty
CC BY-SA 3.0
2010-08-27T16:37:07.690Z
2017-07-19T07:48:12.547Z
2017-07-19T07:48:12.547Z
Alex Andoni
<p>Is there some algorithm out there that can return some value indicating a level of randomness? I believe it's called <a href="http://en.wikipedia.org/wiki/Entropy_%28information_theory%29" rel="noreferrer">Data Entropy</a>.</p>

<p>I recently read this article: <a href="http://faculty.rhodes.edu/wetzel/random/mainbody.html" rel="noreferrer">http://faculty.rhodes.edu/wetzel/random/mainbody.html</a></p>

<p>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?</p>

<p>Are their better analyses than this article?</p>

<randomness>
Best way to determine if a list of bytes are random?
Corey Ogburn
# Best way to determine if a list of bytes are random?

(Asked by: username_0 on 2010-08-25)

Is there some algorithm out there that can return some value indicating a level of randomness? I believe it's called [Data Entropy](http://en.wikipedia.org/wiki/Entropy_%28information_theory%29).

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?

**Tags:** randomness

---

## 8 answers

### Answer by username_9 on 2010-08-27. Score: 16 | Accepted answer

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](http://en.wikipedia.org/wiki/Total_variation_distance_of_probability_measures)) 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.)

> **Comments:**
> **username_10**: 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?  
> **username_4**: I wrote this to check for things like simple sequences and detect gross variations from uniform random byte distributions... it works pretty well: https://github.com/earonesty/dotfiles/blob/master/randbytestest.py.  

---

### Answer by username_1 on 2010-08-25. Score: 6

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.


---

### Answer by username_2 on 2010-08-25. Score: 5

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](http://www.random.org/analysis/)


---

### Answer by username_3 on 2010-08-25. Score: 4

<http://www.phy.duke.edu/~rgb/General/dieharder.php>

> **Comments:**
> **username_4**: good for numbers, not quite right for byte sequences.   could adapt it though  
> **username_3**: @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.  
> **username_4**: 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`).  
> **username_3**: @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.  
> **username_5**: @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.  
> **username_4**: @JaySullivan it's not hard to make a test for smaller samples that produces a reasonable likelihood of randomness using various regressions and is perfectly suitable to answer the question "did you forget to use a random number generator" or "did you accidentally zero out the leftmost 6 bits", etc.   that's what i needed.   wasnt too hard to write  

---

### Answer by username_6 on 2010-08-25. Score: 3

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.


---

### Answer by username_7 on 2010-08-25. Score: 3

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.


---

### Answer by username_8 on 2010-08-25. Score: 3

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.


---

### Answer by username_4 on 2019-01-14. Score: 0

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)

Source is here: <https://github.com/earonesty/dotfiles/blob/master/randbytestest.py>


---

