<p>I want to emphasize here that the word &quot;random&quot; means not only <em>identically distributed</em>, but also <em>independent of everything else</em> (including independent of any other choice).</p>
<p>There are numerous &quot;randomness tests&quot; available, including tests that estimate <em>p-values</em> from running various statistical probes, as well as tests that estimate <em>min-entropy</em>, which is roughly a minimum &quot;compressibility&quot; level of a bit sequence and the most relevant entropy measure for &quot;secure random number generators&quot;. There are also various &quot;<a href="https://peteroupc.github.io/randextract.html" rel="nofollow noreferrer">randomness extractors</a>&quot;, such as the von Neumann and Peres extractors, that could give you an idea on how much &quot;randomness&quot; you can extract from a bit sequence. However, all these tests and methods can only be more reliable on the first part of this definition of randomness (&quot;identically distributed&quot;) than on the second part (&quot;independent&quot;).</p>
<p>In general, there is no algorithm that can tell, <em>from a sequence of numbers alone</em>, whether the process generated them in an independent and identically distributed way, without knowledge on what that process is. Thus, for example, although you can tell that a given sequence of bits has more zeros than ones, you can't tell whether those bits—</p>
<ul>
<li>Were truly generated independently of any other choice, or</li>
<li>form part of an extremely long periodic sequence that is only &quot;locally random&quot;, or</li>
<li>were simply reused from another process, or</li>
<li>were produced in some other way,</li>
</ul>
<p>...without more information on the process. As one important example, the process of a person choosing a password is rarely &quot;random&quot; in this sense since passwords tend to contain familiar words or names, among other reasons.</p>
<p>Also I should discuss the article added to your question in 2019. That article dealt with the task of sampling from the distribution of bit strings generated by pseudorandom quantum circuits, and doing so with a low rate of error (a task specifically designed to be exponentially easier for quantum computers than for classical computers), rather than the task of &quot;verifying&quot; whether a particular sequence of bits (taken out of its context) was generated &quot;at random&quot; in the sense given in this answer. There is an explanation on what exactly this &quot;task&quot; is in a <a href="https://arxiv.org/pdf/2007.07872.pdf" rel="nofollow noreferrer">July 2020 paper</a>.</p>
A Good and SIMPLE Measure of Randomness
<p>What is the best algorithm to take a long sequence of integers (say 100,000 of them) and return a measurement of how random the sequence is?</p>

<p>The function should return a single result, say 0 if the sequence is not all all random, up to, say 1 if perfectly random. It can give something in-between if the sequence is somewhat random, e.g. 0.95 might be a reasonably random sequence, whereas 0.50 might have some non-random parts and some random parts.</p>

<p>If I were to pass the first 100,000 digits of Pi to the function, it should give a number very close to 1.  If I passed the sequence 1, 2, ... 100,000 to it, it should return 0.</p>

<p>This way I can easily take 30 sequences of numbers, identify how random each one is, and return information about their relative randomness.</p>

<p>Is there such an animal?</p>

<p>…..</p>

<p>Update 24-Sep-2019: <a href="https://www.theverge.com/2019/9/23/20879485/google-quantum-supremacy-qubits-nasa" rel="noreferrer">Google may have just ushered in an era of quantum supremacy</a> says:</p>

<blockquote>
  <p>"Google’s quantum computer was reportedly able to solve a calculation — proving the randomness of numbers produced by a random number generator — in 3 minutes and 20 seconds that would take the world’s fastest traditional supercomputer, Summit, around 10,000 years. This effectively means that the calculation cannot be performed by a traditional computer, making Google the first to demonstrate quantum supremacy."</p>
</blockquote>

<p>So obviously there is an algorithm to "prove" randomness. Does anyone know what it is? Could this algorithm also provide a measure of randomness?</p>