Xref: utzoo comp.compression:43 alt.comp.compression:170
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!think.com!hsdndev!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.compression,alt.comp.compression
Subject: Re: theoretical compression factor
Message-ID: <18263:Mar2518:10:4091@kramden.acf.nyu.edu>
Date: 25 Mar 91 18:10:40 GMT
References: <1991Mar25.031214.25696@bingvaxu.cc.binghamton.edu> <1991Mar25.054838.15588@bingvaxu.cc.binghamton.edu> <15098:Mar2512:53:1291@kramden.acf.nyu.edu>
Organization: IR
Lines: 12

In article <15098:Mar2512:53:1291@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
> There is no way that a compressor can turn every string with as many 0's
> as 1's into a string of half the length.

To forestall argument: There are (2n)!/(n!)^2 bit strings of length 2n
with n bits set. This exceeds (2n/e)^(2n) / (n/e)^(2n)(2\pi n)exp(1/6n),
i.e., 2^(2n) / (2\pi n)exp(1/6n). So for large n there are at least
2n - 3 - log n bits of information in such strings, and there is no way
they can all be compressed to length n, as the method in question claims
to do.

---Dan