Pigeonhole principle

[georgemw at speakeasy.net]

On 8 Jan 2002, at 14:27, Michael Motyka wrote:


> Here we go :
> 
> "As Eric correctly points out, true random input simply cannot be
> compressed, it doesn't matter how clever you are or how much time and
> computing power you have access to."
> 
> This is a statement of belief isn't it? Odd.
> 
> Mike
> 
> 

No, it's s statement of mathematical fact, easily understandable
by anyone of average intelligence with a little thought.

The piegonhole principle states that if there are N pigeonholes
and  M > N objects that have to be stuffed into the
piegonholes, at least one of the pigeonholes will have to contain
more than one object.

Any compression algorithm is a mapping between files.

Therefore, there CANNOT exist an algorithm which will
compress all files.  Because there are always twice as many
bit patterns N + 1 bits long as there are bit patterns N bits
long.

Clear enough?

If not, consider this (which Eric also mentioned in his
original post): If you really had an algorithm that could compress
ANY file to 1/100 its size, you could run the output data through
the algorithm again and get something 1/10000 the size of the
original file.  

Now, the philsophically inclined might point out that,
although there cannot exist an algorithm which can compress
all files, and that any given "compression" algorithm is highly
unlikely to be able to compress a truly random file,
nonetheless there are no specific files of which you can
say, "this file is uncompressible", since you could always
devise an algorithm specifically designed to compress
that particular file (for example, by mapping it to a file of zero length
and mapping all other files to themselves with an extra 0 on the 
ebd).  To which the paractical man replies, "you're in a balloon
about 20 feet off the ground".

George