5
$\begingroup$

In a comment on this question, @Kaveh wondered whether the questioner really wanted to ask "is there a relation between strings with high Kolmogorov complexity and pseudorandomness?" This is not the question that was answered, in the end, but I would like to know the answer.

I understand that any pseudorandom sequence can be given a short description, by describing the program that generated it (as Travis M. points out in the question linked above). So in one sense the sequence such a sequence does not have high Kolmogorov complexity.

On the other hand, it seems as if there's some connection between pseudorandomness and Kolmogorov complexity. For if you didn't know the algorithm, then sequences generated by a good (passes lots of appropriate statistical tests, etc.) PRNG could not be described more briefly than by giving the sequence--on average, at least. Right? That's implicit in the kind of tests that good PRNGs have to pass: The tests are meant to rule out cycles and other regular patterns. (We can also require that the PRNG be cryptographically secure, if that helps.)

Happy to be told that I'm hopelessly confused. Just point me in the right direction.

$\endgroup$
4
  • $\begingroup$ Can you clarify what you mean by pseudorandomness, i.e., which notion of pseudorandomness you're thinking of? In the definitions I am familiar with (from cryptography), there is no such thing as a "pseudorandom sequence". Rather there is the notion of a process that is pseudorandom. This makes me wonder if perhaps you might be thinking of a different notion of pseudorandomness. $\endgroup$
    – D.W.
    Feb 2, 2017 at 5:09
  • $\begingroup$ Thanks @D.W. Just a sequences generated by what's considered a high quality PRNG. That's a nontrivial requirement on sequences, given properties that a good PRNG is supposed to satisfy. (If it generates 0 1 0 1 ad infinitum, it's not close, of course. Now generalize that idea.) Not all good PRNGs are good for cryptography, though. The sequence may be "random" enough for say Monte Carlo simulations but be reverse engineerable, so bad for cryptography. $\endgroup$
    – Mars
    Feb 2, 2017 at 6:19
  • $\begingroup$ e.g. see Pseudorandom number generator in Wikipedia. $\endgroup$
    – Mars
    Feb 2, 2017 at 6:28
  • $\begingroup$ But perhaps my terminology is nonstandard. Is there another term for this kind of property of sequences? $\endgroup$
    – Mars
    Feb 2, 2017 at 6:38

1 Answer 1

6
$\begingroup$

The standard notion of pseudorandomness is about a process. You can say that the process (the pseudorandom generator) is pseudorandom, or not. The notion of pseudorandomness of a single string is not defined; that's not something you can talk about.

Kolmogorov randomness is a property of a bit-string. You can say that a particular bit-string (sequence) is Kolmogorov-random, or not. Effectively, a bit-string is Kolmogorov-random if it has high Kolmogorov complexity, i.e., there's no program that outputs that string that's shorter than the string itself.

If you have a pseudorandom generator, then the strings it outputs are never Kolmogorov-random. Any output from the pseudorandom generator can always be generated by a short program (a program that hardcodes the seed to the pseudorandom generator, as well as the code of the pseudorandom generator itself), so isn't Kolmogorov-random.

That's the relationship.


Incidentally, Kolmogorov-random is not about knowledge of a program to generate the string. Knowledge is irrelevant. What matters is existence: whether or not exists a program that generates the string. If there exists a short program that generates the string, then the string is not Kolmogorov-random -- and this remains true even if you don't know the program, or even if it would be difficult to find the program.


You asked about compressibility. Let $G$ be a pseudorandom generator (in the standard cryptographic sense, i.e., computationally indistinguishable from true-random). There is a sense in which outputs of $G$ are compressible, and a sense in which they are not.

The outputs of $G$ are compressible, if you don't care how long the compression algorithm takes to run. Given $G$, we can construct a compression algorithm $C$ that compresses outputs from $G$ to something much shorter. The catch is that $C$ takes a very long time to run: it takes exponential time. In particular, $C$ works by exhaustively trying all possible seeds to see which is correct, and outputting the correct one. This isn't of much relevance in practice -- an algorithm whose running time exceeds the predicted lifetime of the solar system isn't of much engineering relevance -- but it does demonstrate that the outputs of $G$ are Kolmogorov-compressible and thus aren't Kolmogorov-random.

Outputs of $G$ are not compressible (with high probability), if you limit the compression algorithm's running time to something reasonable. For instance, suppose we limit $C$ to run in polynomial time, but allow $C$ to be otherwise unrestricted; then with high probability, running $C$ on the output of $G$ will not lead to any appreciable compression. (Why? Truly random bit-strings are, with high probability, not compressible by $C$. If pseudorandom outputs from $G$ were compressible, then you would obtain a polynomial-time algorithm for distinguishing outputs of $G$ from truly-random strings, which is exactly what the definition of pseudorandomness promises cannot happen.) So in practice, outputs of a pseudorandom generator are not compressible.

Maybe this helps enlighten the connection and contrast between standard pseudorandomness and Kolmogorov-randomness. Standard pseudorandomness is about fooling a fast distinguisher (say, one that runs in polynomial time). Kolmogorov-randomness is about fooling a short distinguisher (one whose source code is shorter than the pseudorandom string). "Fast" is largely orthogonal to "short"; you can have a short program that is very slow (e.g., exponential running time), and you can have a long program that is still fairly efficient (its source code is longer than the input string, but its running time is at most polynomial in the length of that string).

$\endgroup$
10
  • $\begingroup$ Thanks D.W. This states a point I made in the question, but goes much further and is clearer. It also provides a clarification about terminology. However, the deeper question that I have is expressed in my last paragraph. I hope that someone will be able to help me formulate it more clearly. $\endgroup$
    – Mars
    Feb 2, 2017 at 15:56
  • $\begingroup$ @Mars, what exactly would you like to know? Outputs from a PRNG can always described more briefly than by giving the sequence, even for a good PRNG; I describe how in my answer. $\endgroup$
    – D.W.
    Feb 2, 2017 at 16:03
  • $\begingroup$ fwiw: p. 541 of Li and Vitanyi, 3rd ed.: "Definition 7.1.8 A sequential test δ is called a sequential ptime (pspace) test if δ is polynomial-time (polynomial-space) computable. An infinite sequence ω is ptime (pspace) pseudorandom if for every sequential ptime (pspace) test δ, and every polynomial p, it satisfies δ(ω_1:p(n)) < n for all but finitely many n." (emphasis added) Not sure if that's relevant, and my question is not about the meaning of "pseudorandom sequence". $\endgroup$
    – Mars
    Feb 2, 2017 at 16:04
  • $\begingroup$ What makes a process pseudorandom? I think you'll see that it has to do with the kind of sequences it produces. There is some sense in which they are difficult to compress. $\endgroup$
    – Mars
    Feb 2, 2017 at 16:06
  • $\begingroup$ @Mars, yes, but not in the Kolmogorov sense! $\endgroup$
    – D.W.
    Feb 2, 2017 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.