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