2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – mich Jun 4 '17 at 13:21
  • 3
    $\begingroup$ It's not clear to me that this can be answered without knowing more about the compression algorithm $\endgroup$ – Sasho Nikolov Jun 4 '17 at 14:09
  • 3
    $\begingroup$ 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. $\endgroup$ – Daniel Apon Jun 4 '17 at 17:20
  • 1
    $\begingroup$ I have edited for clarity. $\endgroup$ – mich Jun 5 '17 at 15:06
  • 1
    $\begingroup$ It's still unclear what is "good". $\endgroup$ – Emil Jeřábek supports Monica Jun 6 '17 at 9:46
1
$\begingroup$

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?

Roughly, yes. The compression algorithm is lossless (bijective), so the entropy of the input is the same as the entropy of the output. Under your hypothetical, the output's length is asymptotically larger than its entropy, so asmyptotically larger than the input's entropy. So the compression algorithm does not reach the Shannon entropy bound.

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

OK, this isn't totally formal, but I hope it's a useful answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.