Can PRNGs be used to magically compress stuff?

Question

This idea occurred to me as a kid learning to program and on first encountering PRNG's. I still don't know how realistic it is, but now there's stack exchange.

Here's a 14 year-old's scheme for an amazing compression algorithm:

Take a PRNG and seed it with seed s to get a long sequence of pseudo-random bytes. To transmit that sequence to another party, you need only communicate a description of the PRNG, the appropriate seed and the length of the message. For a long enough sequence, that description would be much shorter then the sequence itself.

Now suppose I could invert the process. Given enough time and computational resources, I could do a brute-force search and find a seed (and PRNG, or in other words: a program) that produces my desired sequence (Let's say an amusing photo of cats being mischievous).

PRNGs repeat after a large enough number of bits have been generated, but compared to "typical" cycles my message is quite short so this dosn't seem like much of a problem.

Voila, an effective (if rube-Goldbergian) way to compress data.

So, assuming:

• The sequence I wish to compress is finite and known in advance.
• I'm not short on cash or time (Just as long as a finite amount of both is required)

I'd like to know:

• Is there a fundamental flaw in the reasoning behind the scheme?
• What's the standard way to analyse these sorts of thought experiments?

Summary

It's often the case that good answers make clear not only the answer, but what it is that I was really asking. Thanks for everyone's patience and detailed answers.

Here's my nth attempt at a summary of the answers:

• The PRNG/seed angle doesn't contribute anything, it's no more than a program that produces the desired sequence as output.
• The pigeonhole principle: There are many more messages of length > k than there are (message generating) programs of length <= k. So some sequences simply cannot be the output of a program shorter than the message.
• It's worth mentioning that the interpreter of the program (message) is necessarily fixed in advance. And it's design determines the (small) subset of messages which can be generated when a message of length k is received.

At this point the original PRNG idea is already dead, but there's at least one last question to settle:

• Q: Could I get lucky and find that my long (but finite) message just happens to be the output of a program of length < k bits?

Strictly speaking, it's not a matter of chance since the meaning of every possible message (program) must be known in advance. Either it is the meaning of some message of < k bits or it isn't.

If I choose a random message of >= k bits randomly (why would I?), I would in any case have a vanishing probability of being able to send it using less than k bits, and an almost certainty of not being able to send it at all using less than k bits.

OTOH, if I choose a specific message of >= k bits from those which are the output of a program of less than k bits (assuming there is such a message), then in effect I'm taking advantage of bits already transmitted to the receiver (the design of the interpreter), which counts as part of the message transferred.

Finally:

• Q: What's all this entropy/kolmogorov complexity business?

Ultimately, both tell us the same thing as the (simpler) pigeonhole principle tells us about how much we can compress: perhaps not at all, perhaps some, but certainly not as much as we fancy (unless we cheat).

Answer 1

You've got a brilliant new compression scheme, eh? Alrighty, then...

♫ Let's all play, the entropy game ♫

Just to be simple, I will assume you want to compress messages of exactly $n$ bits, for some fixed $n$. However, you want to be able to use it for longer messages, so you need some way of differentiating your first message from the second (it cannot be ambiguous what you have compressed).

So, your scheme is to determine some family of PRNG/seeds such that if you want to compress, say, $01000111001$, then you just write some number $k$, which identifies some precomputed (and shared) seed/PRNG combo that generates those bits after $n$ queries. Alright. How many different bit-strings of length $n$ are there? $2^n$ (you have n choices between two items; $0$ and $1$). That means you will have to compute $2^n$ of these combos. No problem. However, you need to write out $k$ in binary for me to read it. How big can $k$ get? Well, it can be as big as $2^n$. How many bits do I need to write out $2^n$? $\log{2^n} = n$.

Oops! Your compression scheme needs messages as long as what you're compressing!

"Haha!", you say, "but that's in the worst case! One of my messages will be mapped to $0$, which needs only $1$ bit to represent! Victory!"

Yes, but your messages have to be unambiguous! How can I tell apart $1$ followed by $0$ from $10$? Since some of your keys are length $n$, all of them must be, or else I can't tell where you've started and stopped.

"Haha!", you say, "but I can just put the length of the string in binary first! That only needs to count to $n$, which can be represented by $\log{n}$ bits! So my $0$ now comes prefixed with only $\log{n}$ bits, I still win!"

Yes, but now those really big numbers are prefixed with $\log{n}$ bits. Your compression scheme has made some of your messages even longer! And half of all of your numbers start with $1$, so half of your messages are that much longer!

You then proceed to throw out more ideas like a terminating character, gzipping the number, and compressing the length itself, but all of those run into cases where the resultant message is just longer. In fact, for every bit you save on some message, another message will get longer in response. In general, you're just going to be shifting around the "cost" of your messages. Making some shorter will just make others longer. You really can't fit $2^n$ different messages in less space than writing out $2^n$ binary strings of length $n$.

"Haha!", you say, "but I can choose some messages as 'stupid' and make them illegal! Then I don't need to count all the way to $2^n$, because I don't support that many messages!"

You're right, but you haven't really won. You've just shrunk the set of messages you support. If you only supported $a=0000000011010$ and $b=111111110101000$ as the messages you send, then you can definitely just have the code $a\rightarrow 0$, $b\rightarrow 1$, which matches exactly what I've said. Here, $n=1$. The actual length of the messages isn't important, it's how many there are.

"Haha!", you say, "but I can simply determine that those stupid messages are rare! I'll make the rare ones big, and the common ones small! Then I win on average!"

Yep! Congratulations, you've just discovered entropy! If you have $n$ messages, where the $i$th message has probability $p_i$ of being sent, then you can get your expected message length down to the entropy $H = \sum_{i=1}^np_i\log(1/p_i)$ of this set of messages. That's a kind of weird expression, but all you really need to know is that's it's biggest when all messages are equally likely, and smaller when some are more common than others. In the extreme, if you know basically every message is going to be $a=000111010101$. Then you can use this super efficient code: $a\rightarrow0$, $x\rightarrow1x$ otherwise. Then your expected message length is basically $1$, which is awesome, and that's going to be really close to the entropy $H$. However, $H$ is a lower bound, and you really can't beat it, no matter how hard you try.

Anything that claims to beat entropy is probably not giving enough information to unambiguously retrieve the compressed message, or is just wrong. Entropy is such a powerful concept that we can lower-bound (and sometimes even upper-bound) the running time of some algorithms with it, because if they run really fast (or really slow), then they must be doing something that violates entropy.

Answer 2

There are $2^N-1$ binary strings of length less than $N$, and $2^N$ binary strings of length exactly $N$. This means that whatever your compression algorithm is, there must be some string which it can't compress at all, just because the mapping from original string to compressed string must be injective (one-to-one). This is the driving force behind many applications of Kolmogorov complexity.

In real life, we often know something about the sequence we are compressing, say it's voice or a picture. In the case of lossless compression, Shannon's source coding theorem shows that the optimal compression rate is equal to the entropy of the source. For lossy encoding there are other theorems in information theory (rate-distortion theory). So even in this case there's a limit to how much you can compress data.

Answer 3

Imagine that your seed $s$ has length $k$. Your PRNG is a deterministic function of the seed, so it outputs at most $2^k$ different sequences of length $n$. There are $2^n$ of these, so your scheme isn't going to work unless it falls back on just sending the whole $n$-bit string when there is no corresponding $s$.

(As another answer noted, this will happen for any compression function you choose at all.)

Answer 4

Beside other already answared points, I just want to add this link: https://www.schneier.com:443/blog/archives/2009/09/the_doghouse_cr.html

Now, the annual energy output of our sun is about 1.21×10^41 ergs. This is enough to power about 2.7×10^56 single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. If we built a Dyson sphere around the sun and captured all its energy for 32 years, without any loss, we could power a computer to count up to 2^192. Of course, it wouldn't have the energy left over to perform any useful calculations with this counter.

So only iterating (no comparing...) to find a valid 187bit constellation of your desired data would take under (not attainable) ideal conditions more energy than the sun emits over a year.

Answer 5

A very quick proof that an universal compressor cannot exist. Let´s suppose you do make one, and you compress an input. Now, iteratively compress the output of your program. If you can always reduce the size, it will get smaller and smaller on every step, until you are down to 1 bit.

You could argue that, perhaps, the output of your algorithm has such a structure that it cannot be compressed more, but then you could just apply a deterministic shuffle* before recompressing.

Footnote: Some deterministic shuffling actually helps in some compression schemes: http://pytables.github.io/usersguide/optimization.html?highlight=shuffling#shufflingoptim

Answer 6

The use of a PRNG for "compression" is basically useful in one situation: when it is necessary to use a "random" bunch of data and compactly record what data was used. Most pseudo-random generators can only generate a tiny fraction of possible sequences, but if one only needs a small-to-moderate number of "random" sequences, the fraction of possible sequences that a PRNG can generate will often be more than adequate.

If the sequence of data that one wishes to store happens coincidentally to match what a certain PRNG would generate given the right seed, storing the seed may be a compact alternative to storing the data. Unless the source of data is such that such matches are likely to occur, however, they would be so infrequent that searching for them would not be worthwhile.

Answer 7

Something to consider to add to the cacophony of answers that assert why there are some strings that cannot be compressed owing to the, by definition, injective nature of decompression, and the limited universe of compressed strings from which to select to represent messages is this: most strings cannot be compressed because there are very many more high entropy, disordered strings than there are lower entropy and structured ones, therefore giving rise to the condition that we see in practice that: compression is most of the time useful, since the messages we most often wish to compress are those most often possessive of some aliquot of order and structure, and by this dint, are part of the very much smaller universe of lower entropy objects. This means it is possible that, by choosing a suitable output length, we can compress everything in the smaller, structured universe. The term structured, entropy and ordered here are deliberately imprecise, to reflect the subjective definitions of the semantics and usefulness of messages we may wish to compress.

And in direct answer to the questioner's request : *yes, you could of course just get lucky and find the output of your PRNG is the exact message you wish to compress, it's just that you so often won't find this is the case because the very property that characterises a PRNG, namely, its ability to product an (almost) unending variety of different strings, make it concomitantly unlikley to produce yours.

Of course you could mitigate this unlikelihood by using a PRNG to walk over a "domain graph" of word to word transitions, and you increase greatly the likelihood of your message's apparition, and also find you must now add the domain graph to the compressed message length.