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.
- 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?
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.
- 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).