I'm trying to intuitively grasp information theory.

You have a string of size X that contains a lot of information, say it's a movie. You have a string of size N << X which is going to be the algorithm of a PRNG function. And it has an internal state (seed) of size K << X. Now, is it possible that for some N,K the output of the PRNG function is going to be X? It doesn't matter if it takes a universe's lifetime to find N,K for this question.

To be clear, we are talking about an already compressed movie with say, 2^32 bits of entropy being derived from a process described by <2^20 bits of entropy.

I'm not asking how feasible this is, but rather whether or not it can be proven to be impossible. Or can the electric noise (entropy) in the CPU somehow 'magically' generate (be converted to) the missing entropy of the gap?


Now, is it possible that for some N,K the output of the PRNG function is going to be X?

The answer depends on how you understand the question.

Is it possible that the output of some PRNG function (with "small" parameters $N,K$) happens to be my target string (my movie) of "big" length $X$?

Yes, it's possible. (But the probability is extremely low).

Is it always possible, for any given ("big") $X$, to find some ("small") $N,K$ such that the PRNG with those parameters outputs $X$?

No, of course not. Because, even asumming that different $N,K$ produces different outputs, the space of paramenters is much less than the possible outputs.

This is a particular case of a more general property that states that you cannot have a "universal compressor", such that it compresses all its inputs. http://mattmahoney.net/dc/dce.html#Section_11


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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