How could you characterize "true randomness" of a finite sequence? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-22T02:54:53Z https://cs.stackexchange.com/feeds/question/93479 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/93479 3 How could you characterize "true randomness" of a finite sequence? John Forkosh https://cs.stackexchange.com/users/43050 2018-06-25T09:07:51Z 2018-06-25T20:09:45Z <p>This question occurred to me while reading <a href="http://arxiv.org/abs/1806.08762/" rel="nofollow noreferrer">http://arxiv.org/abs/1806.08762/</a> Any observed sequence is necessarily finite, and any finite sequence is computable, either by explicitly storing all the data and just printing it, or by fitting an $n^{th}$-degree polynomial to an $n$-length sequence, etc.</p> <p>So there's no such thing as an uncomputable (finite) sequence, whereby the article's title "Experimentally probing the incomputability of quantum randomness", initially struck me as somewhat of a non-sequitur (although the details of the article made somewhat more sense of it).</p> <p>But pursuing the classical non-sequitur sense that initially occurred to me, suppose you have some process purported to be "truly random". So prove it! &nbsp; At best, you can give me a finite sequence generated by that process. Then I just fit a polynomial to it, and poof, it's pseudo-random. So my question... what analysis of such a finite sequence would prove that in the $n\to\infty$ limit, your finite pseudo-random sequence would be truly random (or, in some epsilon-delta sense, approach true randomness to any desired accuracy)?</p> <p>For definiteness and simplicity, and for another argument, suppose we're talking about a sequence of random integers from, say, $1$ to $k$. Then there are $k^n$ $n$-length sequences, and not only can we fit a polynomial to each one, we can use some standard enumeration to enumerate them all. Then, choosing a single (random or not) number $1\ldots k^n$ corresponds to choosing an entire (random or not) sequence. But "single numbers" aren't typically considered random in the first place, whereby (one might argue) neither should finite sequences be. So, again, how could you prove that the $n\to\infty$ limit of the sequence generated by a physical (and supposedly random) process is truly random?</p> <p>What occurred to me as a possible answer is that if "truly_random"$\sim$uncomputable, then consider a sequence of computable functions, say our polynomials $f_n(i), i=1\ldots n$, such that $1\le f_n(i)\le k$ is the $i^{th}$ number of the experimentally-generated $n$-length sequence. Then we'd want to prove that, given a finite number of such computable $f_n$'s, the function $\lim_{n\to\infty}f_n$ is uncomputable. Can that be done (or provably not done), and would it characterize "true randomness"?</p> <p><strong>&nbsp; Edit<br>---------</strong><br> Re @orlp's comment, below: Yeah, I guess I phrased that imprecisely. Indeed, you can even construct a more trivial counterexample to my imprecise wording, using the halting problem.</p> <p>Suppose you claim the have a (let's say <strong>C</strong> language) function <strong>int halts(int n)</strong> whose input is the Godel number of a program, and whose output is $1$ if program <strong>n</strong> halts, or $0$ if not (and let's say $-1$ if <strong>n</strong> is the Godel number of a string that's not a valid program, just so <strong>halts()</strong> is a total function on domain $\mathbb N$). Then $\mathbf{\mbox{halts()}:}\mathbb N\to\{0,1;-1\}$.</p> <p>And let's say ancillary function <strong>int godel(char *filename)</strong> reads the contents of text file <strong>filename</strong>, returning its godel number. Now write the following little <strong>C</strong> program and put it in file <strong>doIhalt.c</strong></p> <pre><code>int main ( int argc, char *argv[] ) { int halts(), godel(); while ( halts(godel("doIhalt.c")) == 1 ) ; exit ( 0 ); } </code></pre> <p>So our <strong>doIhalt</strong> program runs forever if <strong>halts()</strong> says it halts, and contrariwise halts immediately if <strong>halts()</strong> says it runs forever. Thus, if <strong>n=godel("doIhalt.c")</strong> is the Godel number of that program, the one single number <strong>halts(n)</strong> is immediately uncomputable. You don't even need a finite sequence at all, as in @orlp's example, to achieve an uncomputable number.</p> <p>By computability here, however, we're talking about recursive enumerability, whereby the individual elements of our set of integers are given, and the question is whether or not there's a program that enumerates them all. For computer-generated pseudo-random numbers, the answer's a foregone conclusion, "yes". But we're asking about some black-box physical process that's somehow generating number-after-number. And after some finite time we've accumulated a finte sequence of its output. So we obviously have in our hands all those numbers -- that's the premise to begin with. And I was saying, or trying to say, that a finite set of numbers which we "have in our hands" is necessarily computable (meaning r.e.). So how would you say that precisely -- and much more succinctly than I elaborated it above?</p> <p>In any case, my question then was whether or not the behavior of that black-box physical process is "truly random" -- how could we answer that question given only a finite sequence of the box's output (a prefix string, so to speak).</p> <p><strong>&nbsp; Edit#2<br>-------------</strong><br> Re @D.W.'s comment below his answer. Okay, considering that the preceding $\lim_{n\to\infty}f_n$ limit isn't well-defined, the alternative standard characterization involves algorithmic complexity, as follows.</p> <p>First, to briefly recapitulate, we've got a black-box physical process, generating (maybe random) integers, $r_i$, one after another, in the range $1\le r_i\le k$. And for the first $n$ of them, $r_1,r_2,...,r_n$ we construct a function $f_n(i)=r_i,\ i=1...n$. So $f_{n+1}$ might necessarily be very different than $f_n$, or it might be quite similar.</p> <p>Note that a program for the simplest $f_1$ function would just store $r_1$ and print it. Any kind of algorithm to compute that one-number-domain function would surely be more complicated than just printing it. Indeed, let $K(f_n)$ denote the Kolmogorov/algorithmic complexity of (the simplest program that computes) function $f_n$. So the first few $f_n$'s probably just store-and-print all the corresponding $r_i,\ i=1...n$.</p> <p>But eventually, as $n$ gets large enough, storing-and-printing would presumably not be the shortest/simplest way to generate all the necessary $n$ values $r_i,\ i=1...n$. The length/complexity of an algorithm would be shorter than all the necessary data. But, of course, that's <strong>>>only if&lt;&lt;</strong> there exists such an algorithm in the first place.</p> <p>So, for a pseudo-random number generator, we know there's an algorithm. So $lim_{n\to\infty}K(f_n)=const$ because that same algorithm computes as many random numbers as you like. Otherwise, for "truly random" sequences, the limit diverges because there's no algorithm, and there's ultimately no alternative to storing-and-printing all the data.</p> <p>I'm not sure whether or not the above satisfies all (or even some of) @D.W.'s objections below, but in any case, given a finite "prefix string" of the black-box's output $r_i,\ i=1...n$, you still can't tell (I don't think) whether or not that $K(\cdot)$ limit converges.</p> https://cs.stackexchange.com/questions/93479/-/93501#93501 5 Answer by D.W. for How could you characterize "true randomness" of a finite sequence? D.W. https://cs.stackexchange.com/users/755 2018-06-25T15:11:48Z 2018-06-25T20:09:45Z <p>Answer to original question:</p> <p>Your question is based on some faulty premises and misunderstandings.</p> <p>A word/string is neither computable nor uncomputable. Rather, we apply uncomputability to languages (sets of strings), or to functions. See <a href="https://en.wikipedia.org/wiki/Formal_language" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Formal_language</a> and <a href="https://en.wikipedia.org/wiki/Computable_function" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Computable_function</a>.</p> <p>You can't prove that a source is random by looking at a single output from it (and this has nothing to do with computability or uncomputability). Instead, the way you prove a source is random is by proving something about the process that generates it. See <a href="https://cs.stackexchange.com/q/67087/755">How best to statistically verify random numbers?</a>. So, being able to find a pattern in a single output of some source (e.g., being able to fit a polynomial to that output) neither proves that the source is random nor that the source is not random.</p> <p>Finally, "truly random" is not equivalent to "computable". They are not really comparable concepts.</p> <p>Answer to edit #2:</p> <p>I think you are asking about the Kolmogorov complexity of a random sequence. In particular, let $r_1,r_2,r_3,\dots$ be chosen uniformly and independently at random from $\{1,\dots,k\}$, and let $f_n:\{1,\dots,n\} \to \{1,\dots,k\}$ be the function defined by $f_n(i) = r_i$. Then with probability 1,</p> <p>$$\lim_{n \to \infty} K(f_n) = \infty,$$</p> <p>and in particular, with probability exponentially close to 1, we have $K(f_n) = n + O(1)$, so $K(f_n) \to \infty$ as $n \to \infty$. This means that you can't save much space compared to "store-and-print" (with high probability, no more than a constant number of bits).</p> <p>Of course, the Kolmogorov complexity is not computable, so this is not a useful way to distinguish random data from pseudorandom data.</p>