Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!cs.utexas.edu!ut-emx!ccwf.cc.utexas.edu
From: readdm@ccwf.cc.utexas.edu (David M. Read)
Newsgroups: comp.compression
Subject: Re: theoretical compression factor
Message-ID: <46618@ut-emx.uucp>
Date: 3 Apr 91 16:37:54 GMT
References: <20135@alice.att.com> <1991Mar29.031127.9128@bingvaxu.cc.binghamton.edu> <20144@alice.att.com> <1991Apr2.034441.28170@bingvaxu.cc.binghamton.edu>
Sender: news@ut-emx.uucp
Reply-To: readdm@ccwf.cc.utexas.edu (David M. Read)
Organization: UT-Austin Nuclear Physics (Jerry's Kids)
Lines: 21

In article <> kym@bingvaxu.cc.binghamton.edu (R. Kym Horsell) writes:
>But to get back to my original question.
>
>Is p lg p a hard-and-fast bound or not? I still think it's an average.
>
>-kym

Speaking as a physicist (who may be a little naive when it comes to
"information science"), if sum (p lg p) does indeed represent the
total entropy of the ensemble (a proposition which I am not sure I
trust entirely, but that's beside the point), then that is indeed the
limit of what your compressor can do.  You may not violate the Second
Law!

You can get arbitrarily close to that sum, but you may not go under
it, unless you *increase* entropy somewhere else.  Perhaps creating a
"history" (I missed that part of the discussion, I'm afraid) "creates"  
some entropy, which would allow you to dip below the initial entropy
of the ensemble, but it seems to me that doing that would also
increase the number of bit which you need to transmit...so where's the
"win?"