<blockquote>
  <p>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?</p>
</blockquote>

<p>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.</p>

<p>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 &gt; 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 &gt; 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$.</p>

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

CC BY-SA 3.0
2017-06-17T22:30:55.023Z
2017-06-17T22:30:55.023Z
usul
<p>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?</p>

<ul>
<li><p>A good compression algorithm is defined as one that achieves good information-theoretic bounds, such as Shannon coding.</p></li>
<li><p>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. </p></li>
<li><p>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. </p></li>
</ul>

CC BY-SA 3.0
2017-06-04T13:21:01.103Z
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.
aellab
CC BY-SA 3.0
2017-06-04T14:09:09.907Z
It's not clear to me that this can be answered without knowing more about the compression algorithm
Sasho Nikolov
CC BY-SA 3.0
2017-06-04T17:20:02.460Z
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
CC BY-SA 3.0
2017-06-04T17:27:44.893Z
spez: Read "$1/(|{\bf C}^* + 1|)$" as "$1/(|{\bf C}^*| + 1)$"
Daniel Apon
CC BY-SA 3.0
2017-06-05T15:06:42.723Z
I have edited for clarity.
aellab
CC BY-SA 3.0
2017-06-05T15:10:08.277Z
@DanielApon That is true; but as the length of $C$ goes to infinity the effect of that appended zero would be negligible.
aellab
CC BY-SA 3.0
2017-06-05T19:52:27.310Z
For every $|{\bf C}^*|$ from 1 to infinity, the "effect" will be $\frac{1}{|{\bf C}^*| + 1}.$ Thus, it is "always" some $\frac{1}{\mathsf{poly}(|{\bf C}^*|)},$ which is **non**-negligible in the length of the output, $|{\bf C}^*|$ (respectively, call this quantity $n$).
Daniel Apon
CC BY-SA 3.0
2017-06-05T19:55:26.903Z
For instance: the output length $n$ of a cryptographic collision-resistant hash function is typically treated as equal to the security parameter $\lambda.$ (There are issues related to birthday attacks if you avoid this 'norm.')

This holds regardless of the length of the input to the CRHF (even if from $\{0,1\}^*,$ formally).
Daniel Apon
CC BY-SA 3.0
2017-06-05T20:00:16.190Z
Note that collision-resistance is a *strictly weaker* property than having uniform output. So if your notion of uniform output from a compression algorithm is weak to birthday attacks (for finding collisions), then it must be *at least* equivalently far from uniform output.
Daniel Apon
CC BY-SA 3.0
2017-06-06T08:21:55.500Z
@DanielApon What I mean is that if $X(n)$ is a randomly sampled bit from the compression of a random string of length $n$, then $Prob[X(n) = 1]$ converges to 1/2 as $n$ tends to infinity (assuming the unmodified compression algorithm was uniform).
aellab
CC BY-SA 3.0
2017-06-06T08:34:29.537Z
Admittedly this does not really imply that the distribution is "close" to uniform (there was a contradiction between the original phrasing of the question, which mentioned sampling a bit uniformly at random, and my latest "edit", which demanded that the distribution of bits in the string itself would be uniform), so I will try to reword my question.
aellab
CC BY-SA 3.0
2017-06-06T09:46:10.023Z
It's still unclear what is "good".
Emil Jeřábek
CC BY-SA 3.0
2017-06-12T12:14:51.327Z
I think you mean that you sample a bit at random. A random byte should have probability 1/256 for 0.
MotiNK
CC BY-SA 3.0
2017-06-12T16:00:08.243Z
(Meta) I decided to retract my Close vote after the recent edits. (While things remain somewhat unclear, I think you are "headed in the right direction"..) Maybe it would help this question out, if you explained your greater motivation for wanting a compression function with some particular property. I recommend updating with an intro paragraph or so on why this type of function+property is interesting to you (in order to facilitate more creative answers).
Daniel Apon
<it.information-theory><encoding>
Entropy of a byte in a compression algorithm?
aellab
# Entropy of a byte in a compression algorithm?

(Asked by: username_0 on 2017-06-04)

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.

**Tags:** it.information-theory, encoding

> **Comments:**
> **username_0**: 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.  
> **username_1**: It's not clear to me that this can be answered without knowing more about the compression algorithm  
> **username_2**: 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.  
> **username_2**: spez: Read "$1/(|{\bf C}^* + 1|)$" as "$1/(|{\bf C}^*| + 1)$"  
> **username_0**: I have edited for clarity.  
> **username_0**: @DanielApon That is true; but as the length of $C$ goes to infinity the effect of that appended zero would be negligible.  
> **username_2**: For every $|{\bf C}^*|$ from 1 to infinity, the "effect" will be $\frac{1}{|{\bf C}^*| + 1}.$ Thus, it is "always" some $\frac{1}{\mathsf{poly}(|{\bf C}^*|)},$ which is **non**-negligible in the length of the output, $|{\bf C}^*|$ (respectively, call this quantity $n$).  
> **username_2**: For instance: the output length $n$ of a cryptographic collision-resistant hash function is typically treated as equal to the security parameter $\lambda.$ (There are issues related to birthday attacks if you avoid this 'norm.')  This holds regardless of the length of the input to the CRHF (even if from $\{0,1\}^*,$ formally).  
> **username_2**: Note that collision-resistance is a *strictly weaker* property than having uniform output. So if your notion of uniform output from a compression algorithm is weak to birthday attacks (for finding collisions), then it must be *at least* equivalently far from uniform output.  
> **username_0**: @DanielApon What I mean is that if $X(n)$ is a randomly sampled bit from the compression of a random string of length $n$, then $Prob[X(n) = 1]$ converges to 1/2 as $n$ tends to infinity (assuming the unmodified compression algorithm was uniform).  
> **username_0**: Admittedly this does not really imply that the distribution is "close" to uniform (there was a contradiction between the original phrasing of the question, which mentioned sampling a bit uniformly at random, and my latest "edit", which demanded that the distribution of bits in the string itself would be uniform), so I will try to reword my question.  
> **username_3**: It's still unclear what is "good".  
> **username_4**: I think you mean that you sample a bit at random. A random byte should have probability 1/256 for 0.  
> **username_2**: (Meta) I decided to retract my Close vote after the recent edits. (While things remain somewhat unclear, I think you are "headed in the right direction"..) Maybe it would help this question out, if you explained your greater motivation for wanting a compression function with some particular property. I recommend updating with an intro paragraph or so on why this type of function+property is interesting to you (in order to facilitate more creative answers).  

---

## 1 answers

### Answer by username_5 on 2017-06-17. Score: 1 | Accepted answer

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


---

