# How do you test randomness?

Suppose I receive a list of 1 million coinflips, and I want to know how likely it is that the list was randomly generated.

My first thought would be to count the number of heads and tails, which should be evenly distributed (around 500.000). But suppose the distribution looks normal, its still possible the list contains patterns or repititions. For example, the first half of the list may be the heads, and the last half the tails. In real random data, that would be highly unlikely.

So how do you calculate the 'randomness' of this list?

• possible duplicate of What tests can I do to ensure my PRNG is working correctly? – otus Oct 16 '14 at 14:12
• Short answer: You can't test if it's good. You can only check if it's bad in specific ways. – CodesInChaos Oct 16 '14 at 14:21
• Maurer's universal statistical test (see A. J. Menezes et al., Handbook of Applied Cryptography, sec.5.4.5 (available online)) may be of some interest to you. – Mok-Kong Shen Oct 16 '14 at 19:05
• See @e-sushi 's answer in the duplicate question for several good tests. – John Deters Oct 17 '14 at 3:07
• @otus I disagree about your proposed duplicate: testing the randomess of a CSPRNG output is completely different from testing the randomness of an entropy source. For one thing, the former is just about useless, the latter is useful. – Gilles 'SO- stop being evil' Oct 17 '14 at 9:42

• Can you never prove pseudorandomness or do we just not know how? Existance of one-way functions would imply existence of pseudorandom generators right? It would also imply $P\neq NP$. – mikeazo Oct 17 '14 at 18:24
• Given an algorithm, you can prove that it's output is pseudorandom based on some computational assumption, but that is as close as you can get. For instance, Blum-Blum-Shub is a PRNG that is pseudorandom if factoring is a hard problem. As you say, PRNG implies $P \neq NP$, which is not known. – Travis Mayberry Oct 17 '14 at 19:37