# Entropy of a byte in a compression algorithm?

I have a (fixed, long) string of bytes that I want to compress, $C$. I use a typical (good) lossless compression algorithm on it, to generate a compressed string of bytes, $C^*$. Then I define a random variable $X$ which samples a bit uniformly at random from $C^*$. Should I expect Prob[X = 0] to be close to 1/2?

• A good compression algorithm is defined as one that achieves good information-theoretic bounds, such as Shannon coding.

• A counter-example would be a compression algorithm that achieves, on average, a non-equal proportion of bits as the length of $C$ goes to infinity, where the contents of $C$ itself are chosen uniformly at random among all strings of that length.

• This is to say the following: Let $S(n)$ be a string of length $n$ chosen uniformly at random. Let $C(s)$ be the result of the compression algorithm with input $s$. Let $X(s)$ denote the proportion of '0's in the string $s$. Then the question is whether $X(C(S(n)))$ necessarily converges to $1/2$ as $n$ goes to infinity.

• I am not sure if this is the right place for this question; please feel free to close, or migrate, if that is the case. – mich Jun 4 '17 at 13:21
• It's not clear to me that this can be answered without knowing more about the compression algorithm – Sasho Nikolov Jun 4 '17 at 14:09
• For every $\mathsf{Compress},$ I define $\mathsf{Compress}^*$ which runs its input ${\bf C}$ through $\mathsf{Compress}$ to obtain ${\bf C}^*$, and then $\mathsf{Compress}^*$ appends a 0-bit to the end of ${\bf C}^*$ and outputs that string. Note that $\mathsf{Compress}^*$ remains a "reasonable/good" compression algorithm by any "typical measure," but the output of $\mathsf{Compress}^*$ is now guaranteed to be non-negligibly-far ($1/(|{\bf C}^*+1|)$-far = $1/\mathsf{poly}$-far) from uniform. – Daniel Apon Jun 4 '17 at 17:20
• I have edited for clarity. – mich Jun 5 '17 at 15:06
• It's still unclear what is "good". – Emil Jeřábek Jun 6 '17 at 9:46

To see one somewhat-formal argument for why the output's length is asymptotically larger than its entropy, suppose for simplicity the length is $n$ and formalize your hypothesis by, e.g. supposing the fraction of ones is always at least $p$, with $p > 0.5$. Using a Chernoff bound, the total number of such strings is at most $q 2^n$ where $q = 2^{-cn}$ for some constant $c > 0$, and so the maximum entropy of the output is at most the log of this number, which is $n(1-c)$, which is significantly smaller than $n$.